0

Suppose T is a type, and I want to make a vector<vector<T>>. I know the eventual size will be m x n, where m and n are runtime constants. (If they were compile-time constants I'd use std::array<std::array<T, n>, m>.) Suppose I have three choices of what to do with my double vector before I continue with my program in earnest:

Option 1

std::vector<std::vector<T>> dbl_vect(m);
for (auto & v : dbl_vect)
    v.reserve(n);

Option 2

std::vector<std::vector<T>> dbl_vect;
dbl_vect.reserve(m);

Option 3

std::vector<std::vector<T>> dbl_vect;

Let's suppose I am not worried about iterator & reference invalidation from vector reallocation, so we can remove that from the decision process.

Of course the code that follows these would have to be a little different, since #1 creates the (empty) rows of the dbl_vector, so we have to access the rows rather than pushing more back.

Option #2 seems fairly useless, because it has no idea how much space to reserve for each row.

Option #1 requires me to go through a linear pass of m empty vectors and resize them manually, but it prevents reallocation. If T were pretty big, this would almost certainly be preferable, I believe, because it would prevent copies/moves.

Question: Suppose T = char (or pick your favorite POD type). Under what circumstances should I be indifferent between options 1 and 3, or even prefer #3? Is this mostly due to the relatively small size of a char, or because of the way the compiler will (not) default-initialize a char? If T is larger, maybe user-defined, at what point (in size of the double vector or in size of T) should I start caring?

Here a somewhat similar question is asked, regarding one vector and T=int.

Eric Auld
  • 1,156
  • 2
  • 14
  • 23
  • 2
    What problem are you trying to solve by using `reserve()` rather than just creating the `vector`s you want ? – Sid S Apr 27 '19 at 00:31
  • @SidS Just so I'm clear, you mean creating them one-by-one and calling `push_back` as I go? That would likely mean reallocation, which may be worth avoiding. – Eric Auld Apr 27 '19 at 00:41
  • @EricAuld: No, he means create them from an iterator so they have the values from the start. – Mooing Duck Apr 27 '19 at 00:42
  • @MooingDuck Oh. I'm assuming my code is more complicated than that, so I don't know ahead of time what their values will be. (Imagine a situation where I'm writing code to return to me all the possible partitions of... you get the point) – Eric Auld Apr 27 '19 at 00:43
  • 1
    #4 `std::vector vec; vec.reserve(m * n);` – Indiana Kernick Apr 27 '19 at 00:44
  • @Kerndog73 Yes, very good point. I deliberately did not include that because it seems obviously better. That might even make my question irrelevant. – Eric Auld Apr 27 '19 at 00:46
  • I would do this allocation-initialization from the start: std::vector> dbl_vect(m, std::vector(n)); – Mauricio Cele Lopez Belon Apr 27 '19 at 03:52
  • @MauricioCeleLopezBelon Why would that be better than #1? In your version I am calling T's default constructor m*n times but not using the result. – Eric Auld Apr 27 '19 at 04:24
  • @EricAuld Of course it works best when T is a basic type (or any type with copy semantics such as pointers or smart pointers) – Mauricio Cele Lopez Belon Apr 27 '19 at 14:14

2 Answers2

0

If you know the inner size will be m, one possibility is to make a std::vector<S>, where S is your custom type standing for a std::vector<T>, except it knows how many entries it will have. A similar solution is suggested here (except there m is a compile-time constant).

Eric Auld
  • 1,156
  • 2
  • 14
  • 23
-2

#3 just default-initializes the vector. There is nothing you gain from this, as the containing vector will have a capacity of zero. Dynamically allocating memory is slow, so to minimize this I would always go with #1 or a variant thereof.

Krystian S
  • 1,586
  • 7
  • 23
  • 2
    I don't think that's true. It creates an empty outer vector and no inner vectors. (Option 3 wouldn't tell it how many inner vectors to create.) As opposed to 1 which actually creates the (empty, m) inner vectors, which will eventually have n entries. Not saying you're wrong in the big picture, but unless I'm mistaken, you're wrong about the initialization. – Eric Auld Apr 27 '19 at 00:39
  • Yes. the containing vector has no elements, I should have expressed that more clearly – Krystian S Apr 27 '19 at 00:55
  • "...will in turn value-initialize or default-initialize...all of the contained vectors." That's what I'm saying option 3 will not do. None of the contained vectors will be created, only the single containing vector. – Eric Auld Apr 27 '19 at 01:13