2

Assume that 

vector<vector<shared_ptr<Base>>> vec
vec.reserve(100)
vec[0].reserve(20)  // Error : vector subscript out of range

I am trying to reserve memory for both outer vector and inner vector. I know that the vec is empty so I cannot reserve memory for the inner vector. I could only resize() or shrink_to_fit() afterward. However, using resize() or shrink_to_fit() is useless due to that is not what I wanted to do.

The intention of reserving memory for the inner vector is trying to allocate the memory well for faster searching of inner elements afterward. I am just wondering if I do not reserve the memory, the memory that is pre-allocated is expensive and chaos.

I would like to ask :

  1. Are there any way to reserve memory for the inner vector
  2. Does my concept of "concerning about bad allocation of memory will be caused without reserving memory for the vector" correct?

Sorry for my poor english and I am using VC++ 2010.

bschung5
  • 23
  • 1
  • 5
  • possible duplicate of [Choice between vector::resize() and vector::reserve()](http://stackoverflow.com/questions/7397768/choice-between-vectorresize-and-vectorreserve). – mfontanini Apr 25 '13 at 17:19
  • 1
    Don't worry about it until you demonstrate that this is causing a problem in a critical strip of your code via profiling tools. – djechlin Apr 25 '13 at 17:19
  • Bjarne Stroustrup himself no longer worries about reserving space in vectors, see http://www.stroustrup.com/bs_faq2.html#slow-containers – Mark Ransom Apr 25 '13 at 17:23
  • In a word, don't. In a few words, it makes little sense. You only need to reserve memory right before you put the first item in. – n. m. could be an AI Apr 25 '13 at 18:06

3 Answers3

5

You can't reserve memory for both inner and outer vectors... the inner vectors don't get constructed if you've only reserved space in the outer vector. You can resize the outer vector then do a reserve for each element thereof, or you can do the reserving on the inner vectors as they're added.

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
2

If you're sure you need to do this at all, I would probably resize the outer vector, then reserve space in each inner vector.

If 100 elements is even close to accurate, the space for your outer vector is almost irrelevant anyway (typically going to be something like 1200 bytes on a 32-bit system or 2400 bytes on a 64-bit system).

That may be a little less convenient (may force you to track how many items are created vs. really in use) but if you want to reserve space in your inner vectors, you don't really have a lot of choices.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • I would use under 20 elements and I know the accurate maximum elements of both outer and inner vector. May I interpret that my concerning is over concern and the problems are actually can be neglected? – bschung5 Apr 25 '13 at 17:43
  • If you start out knowing the number of items in both the outer and inner vectors, it probably makes the most sense to reserve the right size for the outer vector, then create each inner vector at its correct size before pushing it into the outer vector (but yes, ignoring all this probably won't hurt much). – Jerry Coffin Apr 25 '13 at 18:03
0

I'd start with how you're going to interface with the final container and what you know about its content in advance. Once you have settled on a convenient interface, you can implement the code behind it. For example, you could make sure that every new inner vector get created with a capacity of 100 elements. Or, you could use a map from an x/y pair to a shared pointer, which can make sense in a sparsely populated container. Or how about allocating the 100x100 elements statically and just not reallocating at all? The important point is that all these alternatives can be implemented without changing the interface to the final container, so this gives you the freedom to experiment with different approaches.

BTW: Check out make_shared, which avoid the allocation overhead of shared_ptr, I believe. Alternatively, Boost also has an intrusive_ptr which uses an internal reference counter. These shared_ptr instances are also only half the size of a shared_ptr. However, you need benchmarks to actually prove which way is fastest. Anything else is just more or less vague speculation and guesswork.

Ulrich Eckhardt
  • 16,572
  • 3
  • 28
  • 55