170

I have a vector<CustomClass*> and I put a lot of items in the vector and I need fast access, so I don't use list. How to set initial size of vector (for example to be 20 000 places, so to avoid copy when I insert new)?

Morgoth
  • 4,935
  • 8
  • 40
  • 66
Damir
  • 54,277
  • 94
  • 246
  • 365
  • 1
    There's a constructor and a two functions for this in any `std::vector` reference, depending which fits your needs better. – chris Jul 12 '12 at 17:46
  • 1
    You can't avoid copying just be setting the initial value. – juanchopanza Jul 12 '12 at 17:47
  • 1
    Avoid copies of? Storing pointers is pretty lightweight in terms of cost to copy. – user7116 Jul 12 '12 at 17:47
  • 1
    similar: http://stackoverflow.com/questions/10108985/is-it-more-efficient-to-set-the-size-of-a-vector-up-front –  Jul 12 '12 at 18:00
  • Vector of pointers are bad for caching the actual elements, so there is little gain here storing vector of pointers. List might be still good for this. – Avi Jun 03 '23 at 21:49

2 Answers2

242
std::vector<CustomClass *> whatever(20000);

or:

std::vector<CustomClass *> whatever;
whatever.reserve(20000);

The former sets the actual size of the array -- i.e., makes it a vector of 20000 pointers. The latter leaves the vector empty, but reserves space for 20000 pointers, so you can insert (up to) that many without it having to reallocate.

At least in my experience, it's fairly unusual for either of these to make a huge difference in performance--but either can affect correctness under some circumstances. In particular, as long as no reallocation takes place, iterators into the vector are guaranteed to remain valid, and once you've set the size/reserved space, you're guaranteed there won't be any reallocations as long as you don't increase the size beyond that.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • Which of these would be more efficient for a large number of insertions/deletions? – ctor Jul 12 '12 at 17:51
  • 4
    @Loggie: I doubt there would be any difference in efficiency. Mostly it changes how you use it -- with the former, you just address the pointers, so something like `whatever[10000] = somepointer;`, where the latter requires you to `push_back` each pointer you add. At least if you're accustomed to `vector`, the latter is probably simpler and more natural. – Jerry Coffin Jul 12 '12 at 17:53
  • If the size of the container being copied from is known, why isn't it more efficient to (re)size and then copy instead of pushing_back? –  Aug 13 '14 at 16:53
  • 1
    @Cincinnatus: Because it has a call to `reserve`, which pre-allocates the memory size. In theory, setting the size could still be minutely faster, since it also avoids incrementing the current size every time you add an item. In reality, I doubt you could measure that though. – Jerry Coffin Aug 13 '14 at 17:01
  • 1
    actually, if you're doing this on a hot path, and the code is called a lot, you can make a lot of instruction and time saving. – bayindirh Dec 22 '14 at 21:25
  • @bayindirh That is completely context-sensitive. An alternative argument is that, in other cases, `.reserve()` + `(emplace|push)_back()` could be faster than `.resize()` + assign/`copy()`, because the latter would have to first default-construct all the new elements, only to immediately overwrite them right after. And that's if it's even possible to default-construct the elements, which it might not be! There is no point in making such broad, blunt statements without any context and evidence for them. What is best can vary a lot between situations. – underscore_d Oct 13 '18 at 23:56
  • @underscore_d It depends on the cost of constructing the elements. If you're working on pre-constructed elements on the vector directly, you may be right. On the other side, if you're creating elements somewhere and putting them to vector after working on them, there's no need to create elements beforehand. If my memory serves right, my previous comment was written when I was working on a code which was hitting a vector ~1M times per second. So, that's not without context or evidence at least from my point of view. – bayindirh Oct 14 '18 at 14:49
  • Using `reserve()` can do a lot of good. I've done it many times on larger vectors and you definitely see a difference (not even speaking on how your memory is not going to be all broken up if you don't do it.) – Alexis Wilke Nov 18 '18 at 01:42
  • `std::vector whatever(20000);` does not work in recent Cpp, right? It errors: "error: expected identifier before numeric constant". – xealits Jun 08 '23 at 11:49
  • @xealits: Sort of, but mostly no. This works in the places it used to work. But now you can also do in-class initialization--and that requires curly braces, not parentheses (and yes, what you've quoted sounds like the error message gcc generates if you try to use parens for in-class initialization). – Jerry Coffin Jun 08 '23 at 15:22
22

You need to use the reserve function to set an initial allocated size or do it in the initial constructor.

vector<CustomClass *> content(20000);

or

vector<CustomClass *> content;
...
content.reserve(20000);

When you reserve() elements, the vector will allocate enough space for (at least?) that many elements. The elements do not exist in the vector, but the memory is ready to be used. This will then possibly speed up push_back() because the memory is already allocated.

  • Allocating the size can also be provided during construction by passing in an integral argument (e.g. `std::vector content(100);`) – adelbertc Jul 12 '12 at 17:53
  • @kstruct: Yes, but it can be less efficient - by a very small amount. –  Jul 12 '12 at 18:00