0

I am reading "C++ Primer", and in the chapter about containers, the book suggests to always use std::vector whenever possible, eg when there is no demand to insert or delete in the middle or front.

I tested a bit with std::vector and noticed that every time it needs to reallocate, it always reallocates a piece of memory that is three times larger than its previous size. I wonder if this is always the case, and why would it execute in such a way.

In addition, how is the memory/time efficiency of std::vector compared to built-in static and dynamic arrays? Why would the book suggest always using std::vector even in a simple scenario which a simple static array could handle?

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Eason51
  • 17
  • 4
  • 2
    Three times larger you say? I know compilers that do x2 and x1.5, but haven't heard of anyone doing x3. – HolyBlackCat Feb 27 '21 at 09:47
  • Does this answer your question? [Arrays vs Vectors: Introductory Similarities and Differences](https://stackoverflow.com/questions/15079057/arrays-vs-vectors-introductory-similarities-and-differences) – Aykhan Hagverdili Feb 27 '21 at 09:48
  • 1
    @HolyBlackCat perhaps some compiler does x3 for small sizes and some other factor for larger sizes. No restrictions on that afaik – Aykhan Hagverdili Feb 27 '21 at 09:49
  • 1
    How do you check these reallocations? Please try to create a [mcve] of your benchmark and [edit] your question to show it to us. – Some programmer dude Feb 27 '21 at 09:55
  • What hasn't been mentioned yet is that std::vector 2nd template argument is an Allocator. – Allan Wind Feb 27 '21 at 09:58
  • "it always reallocates a piece of memory that is three times larger than its previous size" well no, that's implementation dependent. – JHBonarius Feb 27 '21 at 10:20
  • "std::vector compared to built-in static and dynamic arrays" std::vector is part of the C++ standard, so it is "build-in"... don't confuse C with C++. – JHBonarius Feb 27 '21 at 10:26
  • "Why would the book suggest always using std::vector even in a simple scenario which a simple static array could handle?" Because the cost of handling the boundaries of an array (development, test and risk) is almost always higher than the performance gain. – Alessandro Teruzzi Feb 27 '21 at 10:38

3 Answers3

3

why would it execute in such a way

Because even though this wastes some memory, it makes insertions faster, by reducing the number of reallocations.

It keeps push_back complexity at amortized O(1), while increasing the size by 1 and reallocating each time would make it O(n).

reallocates a piece of memory that is three times larger than its previous size. I wonder if this is always the case

The standard just says that push_back has to have amortized O(1) complexity, and compilers (more precisely, standard library implementations) are free to achieve that by any means.

This disallows increasing capacity by 1 each time, as that would make the complexity O(n). Apparently achieving amortized O(1) requires the size to be increased by N times, but N can have any value. As show in the comments, N can wary between insertions, and is normally between 1.5 and 2.

memory/time efficiency of std::vector compared to built-in static and dynamic arrays?

Access speed should be nearly the same. Insertion and removal speed can't be compared because arrays have fixed size. Vectors might use more memory because, as you noticed, they can allocate memory for more elements that they actually have.

Why would the book suggest always using std::vector even in a simple scenario which a simple static array could handle?

There's no need to replace fixed-size arrays with vectors, as long as static arrays are small enough to fit into the stack.

std::vector should be used instead of manually allocating arrays with new to reduce the risk of memory leaks and other bugs.

HolyBlackCat
  • 78,603
  • 9
  • 131
  • 207
1

I tested a bit with std::vector and noticed that every time it needs to reallocate, it always reallocates a piece of memory that is three times larger than its previous size. I wonder if this is always the case, and why would it execute in such a way.

For context, a possible reallocation strategy for resizing filled resizable containers is to double their size as to not totally lose the O(1) insertion time complexity, because the reallocation time complexity is O(N).

The logarithmic nature of the number of reallocations makes this insertion operation not lose its tendencially O(1) time complexity, the use of multiplier 3 follows the same logic, it has its advantages, the reallocation is less frequent making it potentially less time costly, but it has the downside of being more likely to have more unused space.

Following this rule any multiplier is arguably valid, deppending on what is more important, time or space complexity, there is also the possibility of having a changing the value deppending on the size of the vector, which makes sense, smaller vectors can have larger multipliers but as they grow it's more rational to allocate space more frequently as to not have too much wasted memory.

The strategies can vary dramatically, from having fixed multipilers to having the change deppending on the container's current size, for instance, see this answer, and tests kindly shared by @JHBonarius.

In addition, how is the memory/time efficiency of std::vector compared to built-in static and dynamic arrays? Why would the book suggest always using std::vector even in a simple scenario which a simple static array could handle?

It's arguable that you should always use std::vector if you have an array that you know to always have the same size, it's perfectly fine to use std::array, however, std::vector can behave similarly to std::array if you reserve space for it and do not store more elements in it than the reserved size, so I can see the logic in tendencially using std::vector, though I disagree on the always part, it's too definitive.

anastaciu
  • 23,467
  • 7
  • 28
  • 53
0

Using vectors is one of the easiest and most reliable ways of storing data. when you use array, you have to define size at compile time. Also arrays size fixed you can't change it when you need. Using dynamic arrays (pointer) is always risky. Memory allocation, deallocation etc. If you are using a pointer somewhere, your eye should always be on it.

dilem-ma-vi
  • 33
  • 7
  • ? No, you're overgeneralizing. And internally std::vector is a dynamically allocated array. – JHBonarius Feb 27 '21 at 10:21
  • overgeneralizng? books that I have read ( I read many different books) says same thing. And yes vector is a dynamic array but you don't have do deal memory(allocation, deallocation, initialization ....) – dilem-ma-vi Feb 27 '21 at 10:49
  • Why is it 'easier' then others? Why more reliable? And what about just storing something on the stack `int i=0;` much easier then using a vector. I.e. `std::vector` has a specific purpose, and is good for that specific purpose. – JHBonarius Feb 27 '21 at 10:56
  • As i said before define and use. You don't deal with memory. I think you focus wrong point. Of course we don't talk about int a=5; int b=7; int sum =a+b; And if you read, I say "one of the easiest and most reliable ways of storing data". Of course it is not suitable for all condition. This is because there are other containers (list, map, queue, set, ......) and you can define your container. – dilem-ma-vi Feb 27 '21 at 11:07
  • Well, you do always deal with memory, but the managed type handles it for you. However, this question is specifically asking about how std::vector deals with memory, so details are quite important here. – JHBonarius Feb 27 '21 at 11:14