What does std::vector look like in memory?

Question

I read that std::vector should be contiguous. My understanding is, that its elements should be stored together, not spread out across the memory. I have simply accepted the fact and used this knowledge when for example using its data() method to get the underlying contiguous piece of memory.

However, I came across a situation, where the vector's memory behaves in a strange way:

std::vector<int> numbers;
std::vector<int*> ptr_numbers;
for (int i = 0; i < 8; i++) {
    numbers.push_back(i);
    ptr_numbers.push_back(&numbers.back());
}

I expected this to give me a vector of some numbers and a vector of pointers to these numbers. However, when listing the contents of the ptr_numbers pointers, there are different and seemingly random numbers, as though I am accessing wrong parts of memory.

I have tried to check the contents every step:

for (int i = 0; i < 8; i++) {
    numbers.push_back(i);
    ptr_numbers.push_back(&numbers.back());
    for (auto ptr_number : ptr_numbers)
       std::cout << *ptr_number << std::endl;
    std::cout << std::endl;
}

The result looks roughly like this:

1

some random number
2

some random number
some random number
3

So it seems as though when I push_back() to the numbers vector, its older elements change their location.

So what does it exactly mean, that std::vector is a contiguous container and why do its elements move? Does it maybe store them together, but moves them all together, when more space is needed?

Edit: Is std::vector contiguous only since C++17? (Just to keep the comments on my previous claim relevant to future readers.)

Solution 1

It roughly looks like this (excuse my MS Paint masterpiece):

The std::vector instance you have on the stack is a small object containing a pointer to a heap-allocated buffer, plus some extra variables to keep track of the size and and capacity of the vector.

---

So it seems as though when I push_back() to the numbers vector, its older elements change their location.

The heap-allocated buffer has a fixed capacity. When you reach the end of the buffer, a new buffer will be allocated somewhere else on the heap and all the previous elements will be moved into the new one. Their addresses will therefore change.

---

Does it maybe store them together, but moves them all together, when more space is needed?

Roughly, yes. Iterator and address stability of elements is guaranteed with std::vector only if no reallocation takes place.

---

I am aware, that std::vector is a contiguous container only since C++17

The memory layout of std::vector hasn't changed since its first appearance in the Standard. ContiguousContainer is just a "concept" that was added to differentiate contiguous containers from others at compile-time.

Solution 2

The Answer

It's a single contiguous storage (a 1d array). Each time it runs out of capacity it gets reallocated and stored objects are moved to the new larger place — this is why you observe addresses of the stored objects changing.

It has always been this way, not since C++17.

TL; DR

The storage is growing geometrically to ensure the requirement of the amortized O(1) push_back(). The growth factor is 2 (Cap_n+1 = Cap_n + Cap_n) in most implementations of the C++ Standard Library (GCC, Clang, STLPort) and 1.5 (Cap_n+1 = Cap_n + Cap_n / 2) in the MSVC variant.

If you pre-allocate it with vector::reserve(N) and sufficiently large N, then addresses of the stored objects won't be changing when you add new ones.

In most practical applications is usually worth pre-allocating it to at least 32 elements to skip the first few reallocations shortly following one other (0→1→2→4→8→16).

It is also sometimes practical to slow it down, switch to the arithmetic growth policy (Cap_n+1 = Cap_n + Const), or stop entirely after some reasonably large size to ensure the application does not waste or grow out of memory.

Lastly, in some practical applications, like column-based object storages, it may be worth giving up the idea of contiguous storage completely in favor of a segmented one (same as what std::deque does but with much larger chunks). This way the data may be stored reasonably well localized for both per-column and per-row queries (though this may need some help from the memory allocator as well).

Solution 3

std::vector being a contiguous container means exactly what you think it means.

However, many operations on a vector can re-locate that entire piece of memory.

One common case is when you add element to it, the vector must grow, it can re-allocate and copy all elements to another contiguous piece of memory.

Solution 4

So what does it exactly mean, that std::vector is a contiguous container and why do its elements move? Does it maybe store them together, but moves them all together, when more space is needed?

That's exactly how it works and why appending elements does indeed invalidate all iterators as well as memory locations when a reallocation takes place¹. This is not only valid since C++17, it has been the case ever since.

There are a couple of benefits from this approach:

• It is very cache-friendly and hence efficient.
• The data() method can be used to pass the underlying raw memory to APIs that work with raw pointers.
• The cost of allocating new memory upon push_back, reserve or resize boil down to constant time, as the geometric growth amortizes over time (each time push_back is called the capacity is doubled in libc++ and libstdc++, and approx. growths by a factor of 1.5 in MSVC).
• It allows for the most restricted iterator category, i.e., random access iterators, because classical pointer arithmetic works out well when the data is contiguously stored.
• Move construction of a vector instance from another one is very cheap.

These implications can be considered the downside of such a memory layout:

• All iterators and pointers to elements are invalidate upon modifications of the vector that imply a reallocation. This can lead to subtle bugs when e.g. erasing elements while iterating over the elements of a vector.
• Operations like push_front (as std::list or std::deque provide) aren't provided (insert(vec.begin(), element) works, but is possibly expensive¹), as well as efficient merging/splicing of multiple vector instances.

¹ Thanks to @FrançoisAndrieux for pointing that out.

Solution 5

In terms of the actual structure, an std::vector looks something like this in memory:

struct vector {    // Simple C struct as example (T is the type supplied by the template)
  T *begin;        // vector::begin() probably returns this value
  T *end;          // vector::end() probably returns this value
  T *end_capacity; // First non-valid address
  // Allocator state might be stored here (most allocators are stateless)
};

Relevant code snippet from the libc++ implementation as used by LLVM

Printing the raw memory contents of an std::vector:
(Don't do this if you don't know what you're doing!)

#include <iostream>
#include <vector>

struct vector {
    int *begin;
    int *end;
    int *end_capacity;
};

int main() {
    union vecunion {
        std::vector<int> stdvec;
        vector           myvec;
        ~vecunion() { /* do nothing */ }
    } vec = { std::vector<int>() };
    union veciterator {
        std::vector<int>::iterator stditer;
        int                       *myiter;
        ~veciterator() { /* do nothing */ }
    };

    vec.stdvec.push_back(1); // Add something so we don't have an empty vector

    std::cout
      << "vec.begin          = " << vec.myvec.begin << "\n"
      << "vec.end            = " << vec.myvec.end << "\n"
      << "vec.end_capacity   = " << vec.myvec.end_capacity << "\n"
      << "vec's size         = " << vec.myvec.end - vec.myvec.begin << "\n"
      << "vec's capacity     = " << vec.myvec.end_capacity - vec.myvec.begin << "\n"
      << "vector::begin()    = " << (veciterator { vec.stdvec.begin() }).myiter << "\n"
      << "vector::end()      = " << (veciterator { vec.stdvec.end()   }).myiter << "\n"
      << "vector::size()     = " << vec.stdvec.size() << "\n"
      << "vector::capacity() = " << vec.stdvec.capacity() << "\n"
      ;
}

View more solutions

Comments

[PaulMcKenzie]

The vector has to keep its promise to have elements contiguous, which means if vector has to move the elements to a bigger space, it does. -- I am aware, that std::vector is a contiguous container only since C++17 -- It has been contiguous since 1998.

[PaulMcKenzie]

@McSim Those are just the official names that are used now. It was always guaranteed std::vector stored its items in contiguous memory. Unofficially it was contiguous, because there was a defect in the standard not stating it was contiguous. Then (if I recall), the defect was corrected in the 03 standard.

[macroland]

If you want to observe the effect of contiguous memory then use reserve in advance.

[HolyBlackCat]

Nitpicking: growth factor depends on implementation. I heard MSVC uses 1.5

[Vittorio Romeo]

Growth factor is implementation-defined.

[lubgr]

Why is the arrow not exactly vertical in your drawing? Made me hesitate before upvoting.

[Vittorio Romeo]

@lubgr: I intentionally made it skewed so that it is not mistaken for operator->.

[egst]

I like the pros and cons mentioned, but I will keep the current accepted answer for now as it is more about answering the question than additional notes. It's a pity, I cannot accept two answers though :)

[StaceyGirl]

@bobah In practice it is not 2x in some implementations.

[Fureeish]

"Iterator and address stability of elements is not guaranteed" - it actually is, as long as no reallocation takes place. If you push_back() with size < capacity, address stability is guaranteed

[Galik]

@bobah Yes but over time (usage) that additional cost is reduced tending towards zero (but never reaching it). Doesn't the growth factor simply alter the rate of amortization?

[Galik]

@bobah Well this answer suggests that the growth rate merely needs to be exponential in order to achieve the required amortized complexity stackoverflow.com/a/5232342/3807729

[StaceyGirl]

@bobah MSVC version. Vectors member function _Calculate_growth calculates it like this: const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;. This was already mentioned in the first comment.

[Konrad Rudolph]

In fact, growth factor 2 is pretty bad and 1.5x actually works better, even though this may seem counter-intuitive. And since this is well-known, I’m somewhat surprised that stdlibc++ and libc++ still use 2x.

[Yakk - Adam Nevraumont]

@VittorioRomeo That's ridiculous, operator->() is horizontal. operator↑() on the other hand...

[Yakk - Adam Nevraumont]

For those curious and unwilling to follow a link, a growth factor of 2 leads to the walking vector problem; no sum of previous buffers allocated for a vector can ever quite fits its new allocation. So on a system where the only meaningful allocation is a growing std::vector, a 2x growth factor means you consume almost 2x the memory you'd expect to, half of your memory is returned vector buffers sitting fallow. With 1.5, after ... 4? cycles the previous buffers are big enough to allocate a new buffer in.

[Ti Strga]

@lubgr "exactly vertical" arrows require hardware support

[phuclv]

@TiStrga no, any proper drawing tool will allow you to draw straight lines by holding Shift while dragging the mouse

[ilkkachu]

@phuclv, Straight yes, but an exactly vertical line also requires a properly oriented screen.

[bobah]

@Yakk-AdamNevraumont - the growth factor of two never caused me any problems. In production code one would typically make sure to pre-allocate the vector to skip first few almost-instant reallocations and slow it down (or stop from growing entirely) after some size. For theoretical discussions it's best to switch to the thread at the CS site (I pasted the link in one of my earlier comments).

[orlp]

@Yakk-AdamNevraumont Is that even a concern nowadays with virtual memory?

[orlp]

@Yakk-AdamNevraumont That's not how modern allocators with virtual memory work though. No one is swapping pages that are free, that's ridiculous.

[aquila]

rather misguiding answer with lots of redundancy