vector of vectors and push_back

It depends on whether or not your compiler and standard library implementation supports move constructors. This is unlikely since move constructors are part of C++0x. If not, then there's going to be a whole lot of copying going on.

I would use boost::multi_array. There's a bit of a learning curve to it, but it's pretty nice once you figure out how to do some basic things with it.

A std::deque isn't required to be stored contiguously (so it is allowed to do less copying when the deque grows), and has efficient random access. Depending on your SC++L implementation, a deque might be a reasonable drop in replacement for your outer vector.

Quote:

Original post by LonelyStar In this reallocation, will all the inner vectors be swapped, or is it somehow smart enough to just move the pointers?

It is possible that this could be the case if your std::vector implementation is specialised to handle the case that it's value_type is another std::vector. I have heard of implementations doing this but I don't think it's very common and from a quick glance through the MSVC9's implementation it doesn't seem to do it.

If you're trying to implement a resizeable 2-dimensional array, then boost::multi_array is the best solution.

Quote:

Original post by dmatter I have heard of implementations doing this but I don't think it's very common and from a quick glance through the MSVC9's implementation it doesn't seem to do it.

It does according to this.

Thanks for the correction, looks like I was way off [rolleyes]

MMh, what happens if I resize an boost::multi_array in one dimension? Does it not need to copy all its elements? The documentation sounds, like it would ...

There is a lot of copying incured by multi_array unfortunately, it's because it models a resizeable array and, in C++, arrays tend to be space-efficient. A vector on the other hand is rarely space efficient.

As usual it's all about tradeoffs, multi_array is the most convenient form of resizeable N-dimensional rectangular array in C++, it has less memory overhead as well as more efficient iteration and access than other solutions tend to have, the downside is that resizing isn't as efficient as, say, a vector. If the cost you pay for resizing is countered by what you gain in iteration and access then the choice is well worth it. If you're not sure which you need most then, again, choose multi_array for the convenience.

Other solutions have tradeoffs elsewhere. A vector-of-vectors is very poor at maintaining rectangular shape, it is not as memory efficient and has added overhead for iteration and access. It is good at being resizeable though thanks to all the pointer swaptimisation it can do behind the scenes.

Another solution is a combination of a fixed-sized row array contained within a resizeable vector:

typedef std::vector< boost::array > fixed_row_2d_array;

This is almost a middle-ground solution, it's faster at resizing than a multi_array but not as good as a vector-of-vectors. It's faster at iteration and access than a vector-of-vectors but not as fast as a multi_array. Space-wise it's quite inefficient. Convenience-wise it's not as good as a multi_array but it's better than a vector-of-vectors.

If you're not sure which solution is best for you, then pick the multi_array by default [smile]

If you know your rough maximum size for your outer std::vector you can use the "reserve" to allocate enough memory to make sure that your vector doesn't move on you.

Alternatively you could use an std::list instead of a vector but then you need to iterate through the list to find elements in the middle. You'll loose your O(1) access time

What are you trying to do? What are these vectors for?

Quote:

Original post by dmatter Another solution is a combination of a fixed-sized row array contained within a resizeable vector: typedef std::vector< boost::array > fixed_row_2d_array; This is almost a middle-ground solution, it's faster at resizing than a multi_array but not as good as a vector-of-vectors. It's faster at iteration and access than a vector-of-vectors but not as fast as a multi_array. Space-wise it's quite inefficient. Convenience-wise it's not as good as a multi_array but it's better than a vector-of-vectors.

I beg to differ about the space inefficiency. boost::array carries no explicit overhead, and the outer vector will pack the boost::array instances together neatly. You only pay for struct padding per boost::array instance, plus the factor-of-N inefficiency of the outer vector (which is the same as I'd expect to pay with boost::multi_array, assuming that it allocates a single chunk of memory in a std::vector-like sceheme under the hood). And the only time on normal architectures that there'd be any struct padding would be with primitive types smaller than int. So yeah, you might not want to represent a sequence of pairs of byte values with a std::vector >, but that's about it. :)

Do keep in mind, though, that this way you won't be able to resize the inner dimension.

Quote:

Original post by Zahlman plus the factor-of-N inefficiency of the outer vector (which is the same as I'd expect to pay with boost::multi_array, assuming that it allocates a single chunk of memory in a std::vector-like sceheme under the hood).

This, I think, is what I was referring to. A std::vector would grow its capacity by a factor of N (typically it doubles I believe) when full, this is the apparent space inefficiency I meant. Compared to a boost::multi_array which, it appears to me at least, will only allocate the required amount of memory for its desired size.

Quote:

Original post by dmatter Compared to a boost::multi_array which, it appears to me at least, will only allocate the required amount of memory for its desired size.

My mental model of a boost::multi_array implementation basically involved using a std::vector as the backing store, but upon closer examination it appears to behave the way you envisioned. :) I suppose this makes sense, as there is no interface provided for pushing or inserting (that would be clumsy, anyway; you'd be inserting an N-1 dimensional "slice", and would need a way to specify which dimension was omitted...)