What does std::vector look like in memory?

Clash Royale CLAN TAG#URR8PPP

up vote
6
down vote

favorite

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?

c++ memory vector contiguous

share|improve this question

edited 24 mins ago

asked 42 mins ago

McSim

99128

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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
  35 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  That is what I read on cppreference: std::vector (for T other than bool) meets the requirements of Container, AllocatorAwareContainer, SequenceContainer , ContiguousContainer (since C++17) and ReversibleContainer.
  – McSim
  32 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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.
  – PaulMcKenzie
  30 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  If you want to observe the effect of contiguous memory then use reserve in advance.
  – macroland
  30 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @PaulMcKenzie Thanks for the explanation.
  – McSim
  26 mins ago
  

  
  
  
  

 | 
show 1 more comment

up vote
6
down vote

favorite

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?

c++ memory vector contiguous

share|improve this question

edited 24 mins ago

asked 42 mins ago

McSim

99128

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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
  35 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  That is what I read on cppreference: std::vector (for T other than bool) meets the requirements of Container, AllocatorAwareContainer, SequenceContainer , ContiguousContainer (since C++17) and ReversibleContainer.
  – McSim
  32 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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.
  – PaulMcKenzie
  30 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  If you want to observe the effect of contiguous memory then use reserve in advance.
  – macroland
  30 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @PaulMcKenzie Thanks for the explanation.
  – McSim
  26 mins ago
  

  
  
  
  

 | 
show 1 more comment

up vote
6
down vote

favorite

up vote
6
down vote

favorite

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?

c++ memory vector contiguous

share|improve this question

edited 24 mins ago

asked 42 mins ago

McSim

99128

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?

c++ memory vector contiguous

c++ memory vector contiguous

share|improve this question

edited 24 mins ago

asked 42 mins ago

McSim

99128

share|improve this question

edited 24 mins ago

asked 42 mins ago

McSim

99128

share|improve this question

share|improve this question

edited 24 mins ago

edited 24 mins ago

edited 24 mins ago

asked 42 mins ago

McSim

99128

asked 42 mins ago

McSim

99128

asked 42 mins ago

McSim

99128

99128

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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
  35 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  That is what I read on cppreference: std::vector (for T other than bool) meets the requirements of Container, AllocatorAwareContainer, SequenceContainer , ContiguousContainer (since C++17) and ReversibleContainer.
  – McSim
  32 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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.
  – PaulMcKenzie
  30 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  If you want to observe the effect of contiguous memory then use reserve in advance.
  – macroland
  30 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @PaulMcKenzie Thanks for the explanation.
  – McSim
  26 mins ago
  

  
  
  
  

 | 
show 1 more comment

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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
  35 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  That is what I read on cppreference: std::vector (for T other than bool) meets the requirements of Container, AllocatorAwareContainer, SequenceContainer , ContiguousContainer (since C++17) and ReversibleContainer.
  – McSim
  32 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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.
  – PaulMcKenzie
  30 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  If you want to observe the effect of contiguous memory then use reserve in advance.
  – macroland
  30 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @PaulMcKenzie Thanks for the explanation.
  – McSim
  26 mins ago
  

  
  
  
  

1

1

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
35 mins ago

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
35 mins ago

That is what I read on cppreference: std::vector (for T other than bool) meets the requirements of Container, AllocatorAwareContainer, SequenceContainer , ContiguousContainer (since C++17) and ReversibleContainer.
– McSim
32 mins ago

That is what I read on cppreference: std::vector (for T other than bool) meets the requirements of Container, AllocatorAwareContainer, SequenceContainer , ContiguousContainer (since C++17) and ReversibleContainer.
– McSim
32 mins ago

1

1

@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.
– PaulMcKenzie
30 mins ago

@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.
– PaulMcKenzie
30 mins ago

If you want to observe the effect of contiguous memory then use reserve in advance.
– macroland
30 mins ago

If you want to observe the effect of contiguous memory then use reserve in advance.
– macroland
30 mins ago

@PaulMcKenzie Thanks for the explanation.
– McSim
26 mins ago

@PaulMcKenzie Thanks for the explanation.
– McSim
26 mins ago

 | 
show 1 more comment

5 Answers
5

active

oldest

votes

up vote
8
down vote



accepted

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 not guaranteed with std::vector.

---

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.

share|improve this answer

answered 37 mins ago

Vittorio Romeo

50.9k14135272

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Why is the arrow not exactly vertical in your drawing? Made me hesitate before upvoting.
  – lubgr
  26 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @lubgr: I intentionally made it skewed so that it is not mistaken for operator->.
  – Vittorio Romeo
  23 mins ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  "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
  – Fureeish
  10 mins ago
  

  
  
  
  

add a comment | 

up vote
3
down vote

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.

share|improve this answer

answered 38 mins ago

nos

170k42312420

add a comment | 

up vote
2
down vote

It's a single contiguous storage (a 1d array) that gets reallocated each time it runs out of capacity (with the 2x growth factor).

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 has always been this way, not since C++17.

share|improve this answer

answered 38 mins ago

bobah

12.3k12245

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Nitpicking: growth factor depends on implementation. I heard MSVC uses 1.5
  – HolyBlackCat
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Growth factor is implementation-defined.
  – Vittorio Romeo
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes in theory, but not in practice, because to achieve amortized O(1) push_back() it needs to grow the storage as 2x. No one, of cause, in a sane mind would let it do that after certain capacity as it may eat all available memory very quickly, but that's done manually in the client code.
  – bobah
  30 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @bobah In practice it is not 2x in some implementations.
  – Ivan
  14 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does the growth factor actually affect the amortized complexity?
  – Galik
  12 mins ago
  

  
  
  
  

 | 
show 4 more comments

up vote
1
down vote

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. 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 insertion, resizing, etc. which 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) are impossible, as well as efficient merging/splicing of multiple vector instances.

share|improve this answer

edited 21 mins ago

answered 27 mins ago

lubgr

6,45011340

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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 :)
  – McSim
  16 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This answer seems to imply that inserting new elements always has a risk of iterator invalidation. It should mention that with the proper precautions (notably that size doesn't exceed capacity) you can be guaranteed that it won't occur. Also, push_front is omitted from std::vector's interface as a sign that it should probably not be used. But you can achieve the same result by using v.insert(v.begin(), element);. Operations "like push_front aren't quite impossible.
  – François Andrieux
  1 min ago
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

What you are seeing is that std::vector has to reallocate its element because it needs more memory.

For example initially it could allocate memory for 4 integers, but when you insert 5th int, it has to allocate a new memory chunk and copy old 4 integers there. Therefor elements change their address.

It is said that std::vector::resize invalidates all pointer and iterators derived from it when it needs to change its capacity:

Reallocation invalidates all the references, pointers, and iterators
referring to the elements in the sequence. No reallocation shall take
place during insertions that happen after a call to reserve() until
the time when an insertion would make the size of the vector greater
than the value of capacity().

So you can try reserving memory beforehand:

std::vector<int> numbers;
std::vector<int*> ptr_numbers;
numbers.reserve(8); // <--- Here
for (int i = 0; i < 8; i++) 
 numbers.push_back(i);
 ptr_numbers.push_back(&numbers.back());

share|improve this answer

edited 16 mins ago

answered 38 mins ago

Ivan

3,21592240

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  "It is said" - by who?
  – Ville-Valtteri
  36 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Ville-Valtteri By people on the internet. Or by the standard.
  – Ivan
  36 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Ivan When you provide a quote you should also offer a link to wherever you are go it from if you want it to have credibility.
  – François Andrieux
  5 mins ago
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52330010%2fwhat-does-stdvector-look-like-in-memory%23new-answer', 'question_page');

);

Post as a guest

Name Email

5 Answers
5

active

oldest

votes

5 Answers
5

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
8
down vote



accepted

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 not guaranteed with std::vector.

---

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.

share|improve this answer

answered 37 mins ago

Vittorio Romeo

50.9k14135272

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Why is the arrow not exactly vertical in your drawing? Made me hesitate before upvoting.
  – lubgr
  26 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @lubgr: I intentionally made it skewed so that it is not mistaken for operator->.
  – Vittorio Romeo
  23 mins ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  "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
  – Fureeish
  10 mins ago
  

  
  
  
  

add a comment | 

up vote
8
down vote



accepted

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 not guaranteed with std::vector.

---

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.

share|improve this answer

answered 37 mins ago

Vittorio Romeo

50.9k14135272

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Why is the arrow not exactly vertical in your drawing? Made me hesitate before upvoting.
  – lubgr
  26 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @lubgr: I intentionally made it skewed so that it is not mistaken for operator->.
  – Vittorio Romeo
  23 mins ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  "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
  – Fureeish
  10 mins ago
  

  
  
  
  

add a comment | 

up vote
8
down vote



accepted

up vote
8
down vote



accepted

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 not guaranteed with std::vector.

---

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.

share|improve this answer

answered 37 mins ago

Vittorio Romeo

50.9k14135272

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 not guaranteed with std::vector.

---

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.

share|improve this answer

answered 37 mins ago

Vittorio Romeo

50.9k14135272

share|improve this answer

share|improve this answer

answered 37 mins ago

Vittorio Romeo

50.9k14135272

answered 37 mins ago

Vittorio Romeo

50.9k14135272

answered 37 mins ago

Vittorio Romeo

50.9k14135272

50.9k14135272

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Why is the arrow not exactly vertical in your drawing? Made me hesitate before upvoting.
  – lubgr
  26 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @lubgr: I intentionally made it skewed so that it is not mistaken for operator->.
  – Vittorio Romeo
  23 mins ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  "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
  – Fureeish
  10 mins ago
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Why is the arrow not exactly vertical in your drawing? Made me hesitate before upvoting.
  – lubgr
  26 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @lubgr: I intentionally made it skewed so that it is not mistaken for operator->.
  – Vittorio Romeo
  23 mins ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  "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
  – Fureeish
  10 mins ago
  

  
  
  
  

2

2

Why is the arrow not exactly vertical in your drawing? Made me hesitate before upvoting.
– lubgr
26 mins ago

Why is the arrow not exactly vertical in your drawing? Made me hesitate before upvoting.
– lubgr
26 mins ago

1

1

@lubgr: I intentionally made it skewed so that it is not mistaken for operator->.
– Vittorio Romeo
23 mins ago

@lubgr: I intentionally made it skewed so that it is not mistaken for operator->.
– Vittorio Romeo
23 mins ago

2

2

"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
– Fureeish
10 mins ago

"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
– Fureeish
10 mins ago

add a comment | 

up vote
3
down vote

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.

share|improve this answer

answered 38 mins ago

nos

170k42312420

add a comment | 

up vote
3
down vote

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.

share|improve this answer

answered 38 mins ago

nos

170k42312420

add a comment | 

up vote
3
down vote

up vote
3
down vote

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.

share|improve this answer

answered 38 mins ago

nos

170k42312420

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.

share|improve this answer

answered 38 mins ago

nos

170k42312420

share|improve this answer

share|improve this answer

answered 38 mins ago

nos

170k42312420

answered 38 mins ago

nos

170k42312420

answered 38 mins ago

nos

170k42312420

170k42312420

add a comment | 

add a comment | 

up vote
2
down vote

It's a single contiguous storage (a 1d array) that gets reallocated each time it runs out of capacity (with the 2x growth factor).

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 has always been this way, not since C++17.

share|improve this answer

answered 38 mins ago

bobah

12.3k12245

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Nitpicking: growth factor depends on implementation. I heard MSVC uses 1.5
  – HolyBlackCat
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Growth factor is implementation-defined.
  – Vittorio Romeo
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes in theory, but not in practice, because to achieve amortized O(1) push_back() it needs to grow the storage as 2x. No one, of cause, in a sane mind would let it do that after certain capacity as it may eat all available memory very quickly, but that's done manually in the client code.
  – bobah
  30 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @bobah In practice it is not 2x in some implementations.
  – Ivan
  14 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does the growth factor actually affect the amortized complexity?
  – Galik
  12 mins ago
  

  
  
  
  

 | 
show 4 more comments

up vote
2
down vote

It's a single contiguous storage (a 1d array) that gets reallocated each time it runs out of capacity (with the 2x growth factor).

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 has always been this way, not since C++17.

share|improve this answer

answered 38 mins ago

bobah

12.3k12245

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Nitpicking: growth factor depends on implementation. I heard MSVC uses 1.5
  – HolyBlackCat
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Growth factor is implementation-defined.
  – Vittorio Romeo
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes in theory, but not in practice, because to achieve amortized O(1) push_back() it needs to grow the storage as 2x. No one, of cause, in a sane mind would let it do that after certain capacity as it may eat all available memory very quickly, but that's done manually in the client code.
  – bobah
  30 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @bobah In practice it is not 2x in some implementations.
  – Ivan
  14 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does the growth factor actually affect the amortized complexity?
  – Galik
  12 mins ago
  

  
  
  
  

 | 
show 4 more comments

up vote
2
down vote

up vote
2
down vote

It's a single contiguous storage (a 1d array) that gets reallocated each time it runs out of capacity (with the 2x growth factor).

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 has always been this way, not since C++17.

share|improve this answer

answered 38 mins ago

bobah

12.3k12245

It's a single contiguous storage (a 1d array) that gets reallocated each time it runs out of capacity (with the 2x growth factor).

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 has always been this way, not since C++17.

share|improve this answer

answered 38 mins ago

bobah

12.3k12245

share|improve this answer

share|improve this answer

answered 38 mins ago

bobah

12.3k12245

answered 38 mins ago

bobah

12.3k12245

answered 38 mins ago

bobah

12.3k12245

12.3k12245

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Nitpicking: growth factor depends on implementation. I heard MSVC uses 1.5
  – HolyBlackCat
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Growth factor is implementation-defined.
  – Vittorio Romeo
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes in theory, but not in practice, because to achieve amortized O(1) push_back() it needs to grow the storage as 2x. No one, of cause, in a sane mind would let it do that after certain capacity as it may eat all available memory very quickly, but that's done manually in the client code.
  – bobah
  30 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @bobah In practice it is not 2x in some implementations.
  – Ivan
  14 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does the growth factor actually affect the amortized complexity?
  – Galik
  12 mins ago
  

  
  
  
  

 | 
show 4 more comments

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Nitpicking: growth factor depends on implementation. I heard MSVC uses 1.5
  – HolyBlackCat
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Growth factor is implementation-defined.
  – Vittorio Romeo
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes in theory, but not in practice, because to achieve amortized O(1) push_back() it needs to grow the storage as 2x. No one, of cause, in a sane mind would let it do that after certain capacity as it may eat all available memory very quickly, but that's done manually in the client code.
  – bobah
  30 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @bobah In practice it is not 2x in some implementations.
  – Ivan
  14 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does the growth factor actually affect the amortized complexity?
  – Galik
  12 mins ago
  

  
  
  
  

1

1

Nitpicking: growth factor depends on implementation. I heard MSVC uses 1.5
– HolyBlackCat
33 mins ago

Nitpicking: growth factor depends on implementation. I heard MSVC uses 1.5
– HolyBlackCat
33 mins ago

1

1

Growth factor is implementation-defined.
– Vittorio Romeo
33 mins ago

Growth factor is implementation-defined.
– Vittorio Romeo
33 mins ago

Yes in theory, but not in practice, because to achieve amortized O(1) push_back() it needs to grow the storage as 2x. No one, of cause, in a sane mind would let it do that after certain capacity as it may eat all available memory very quickly, but that's done manually in the client code.
– bobah
30 mins ago

Yes in theory, but not in practice, because to achieve amortized O(1) push_back() it needs to grow the storage as 2x. No one, of cause, in a sane mind would let it do that after certain capacity as it may eat all available memory very quickly, but that's done manually in the client code.
– bobah
30 mins ago

@bobah In practice it is not 2x in some implementations.
– Ivan
14 mins ago

@bobah In practice it is not 2x in some implementations.
– Ivan
14 mins ago

Does the growth factor actually affect the amortized complexity?
– Galik
12 mins ago

Does the growth factor actually affect the amortized complexity?
– Galik
12 mins ago

 | 
show 4 more comments

up vote
1
down vote

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. 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 insertion, resizing, etc. which 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) are impossible, as well as efficient merging/splicing of multiple vector instances.

share|improve this answer

edited 21 mins ago

answered 27 mins ago

lubgr

6,45011340

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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 :)
  – McSim
  16 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This answer seems to imply that inserting new elements always has a risk of iterator invalidation. It should mention that with the proper precautions (notably that size doesn't exceed capacity) you can be guaranteed that it won't occur. Also, push_front is omitted from std::vector's interface as a sign that it should probably not be used. But you can achieve the same result by using v.insert(v.begin(), element);. Operations "like push_front aren't quite impossible.
  – François Andrieux
  1 min ago
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

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. 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 insertion, resizing, etc. which 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) are impossible, as well as efficient merging/splicing of multiple vector instances.

share|improve this answer

edited 21 mins ago

answered 27 mins ago

lubgr

6,45011340

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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 :)
  – McSim
  16 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This answer seems to imply that inserting new elements always has a risk of iterator invalidation. It should mention that with the proper precautions (notably that size doesn't exceed capacity) you can be guaranteed that it won't occur. Also, push_front is omitted from std::vector's interface as a sign that it should probably not be used. But you can achieve the same result by using v.insert(v.begin(), element);. Operations "like push_front aren't quite impossible.
  – François Andrieux
  1 min ago
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

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. 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 insertion, resizing, etc. which 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) are impossible, as well as efficient merging/splicing of multiple vector instances.

share|improve this answer

edited 21 mins ago

answered 27 mins ago

lubgr

6,45011340

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. 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 insertion, resizing, etc. which 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) are impossible, as well as efficient merging/splicing of multiple vector instances.

share|improve this answer

edited 21 mins ago

answered 27 mins ago

lubgr

6,45011340

share|improve this answer

share|improve this answer

edited 21 mins ago

edited 21 mins ago

edited 21 mins ago

answered 27 mins ago

lubgr

6,45011340

answered 27 mins ago

lubgr

6,45011340

answered 27 mins ago

lubgr

6,45011340

6,45011340

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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 :)
  – McSim
  16 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This answer seems to imply that inserting new elements always has a risk of iterator invalidation. It should mention that with the proper precautions (notably that size doesn't exceed capacity) you can be guaranteed that it won't occur. Also, push_front is omitted from std::vector's interface as a sign that it should probably not be used. But you can achieve the same result by using v.insert(v.begin(), element);. Operations "like push_front aren't quite impossible.
  – François Andrieux
  1 min ago
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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 :)
  – McSim
  16 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  This answer seems to imply that inserting new elements always has a risk of iterator invalidation. It should mention that with the proper precautions (notably that size doesn't exceed capacity) you can be guaranteed that it won't occur. Also, push_front is omitted from std::vector's interface as a sign that it should probably not be used. But you can achieve the same result by using v.insert(v.begin(), element);. Operations "like push_front aren't quite impossible.
  – François Andrieux
  1 min ago
  
  

  
  
  
  

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 :)
– McSim
16 mins ago

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 :)
– McSim
16 mins ago

This answer seems to imply that inserting new elements always has a risk of iterator invalidation. It should mention that with the proper precautions (notably that size doesn't exceed capacity) you can be guaranteed that it won't occur. Also, push_front is omitted from std::vector's interface as a sign that it should probably not be used. But you can achieve the same result by using v.insert(v.begin(), element);. Operations "like push_front aren't quite impossible.
– François Andrieux
1 min ago

This answer seems to imply that inserting new elements always has a risk of iterator invalidation. It should mention that with the proper precautions (notably that size doesn't exceed capacity) you can be guaranteed that it won't occur. Also, push_front is omitted from std::vector's interface as a sign that it should probably not be used. But you can achieve the same result by using v.insert(v.begin(), element);. Operations "like push_front aren't quite impossible.
– François Andrieux
1 min ago

add a comment | 

up vote
1
down vote

What you are seeing is that std::vector has to reallocate its element because it needs more memory.

For example initially it could allocate memory for 4 integers, but when you insert 5th int, it has to allocate a new memory chunk and copy old 4 integers there. Therefor elements change their address.

It is said that std::vector::resize invalidates all pointer and iterators derived from it when it needs to change its capacity:

Reallocation invalidates all the references, pointers, and iterators
referring to the elements in the sequence. No reallocation shall take
place during insertions that happen after a call to reserve() until
the time when an insertion would make the size of the vector greater
than the value of capacity().

So you can try reserving memory beforehand:

std::vector<int> numbers;
std::vector<int*> ptr_numbers;
numbers.reserve(8); // <--- Here
for (int i = 0; i < 8; i++) 
 numbers.push_back(i);
 ptr_numbers.push_back(&numbers.back());

share|improve this answer

edited 16 mins ago

answered 38 mins ago

Ivan

3,21592240

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  "It is said" - by who?
  – Ville-Valtteri
  36 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Ville-Valtteri By people on the internet. Or by the standard.
  – Ivan
  36 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Ivan When you provide a quote you should also offer a link to wherever you are go it from if you want it to have credibility.
  – François Andrieux
  5 mins ago
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

What you are seeing is that std::vector has to reallocate its element because it needs more memory.

For example initially it could allocate memory for 4 integers, but when you insert 5th int, it has to allocate a new memory chunk and copy old 4 integers there. Therefor elements change their address.

It is said that std::vector::resize invalidates all pointer and iterators derived from it when it needs to change its capacity:

Reallocation invalidates all the references, pointers, and iterators
referring to the elements in the sequence. No reallocation shall take
place during insertions that happen after a call to reserve() until
the time when an insertion would make the size of the vector greater
than the value of capacity().

So you can try reserving memory beforehand:

std::vector<int> numbers;
std::vector<int*> ptr_numbers;
numbers.reserve(8); // <--- Here
for (int i = 0; i < 8; i++) 
 numbers.push_back(i);
 ptr_numbers.push_back(&numbers.back());

share|improve this answer

edited 16 mins ago

answered 38 mins ago

Ivan

3,21592240

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  "It is said" - by who?
  – Ville-Valtteri
  36 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Ville-Valtteri By people on the internet. Or by the standard.
  – Ivan
  36 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Ivan When you provide a quote you should also offer a link to wherever you are go it from if you want it to have credibility.
  – François Andrieux
  5 mins ago
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

What you are seeing is that std::vector has to reallocate its element because it needs more memory.

For example initially it could allocate memory for 4 integers, but when you insert 5th int, it has to allocate a new memory chunk and copy old 4 integers there. Therefor elements change their address.

It is said that std::vector::resize invalidates all pointer and iterators derived from it when it needs to change its capacity:

Reallocation invalidates all the references, pointers, and iterators
referring to the elements in the sequence. No reallocation shall take
place during insertions that happen after a call to reserve() until
the time when an insertion would make the size of the vector greater
than the value of capacity().

So you can try reserving memory beforehand:

std::vector<int> numbers;
std::vector<int*> ptr_numbers;
numbers.reserve(8); // <--- Here
for (int i = 0; i < 8; i++) 
 numbers.push_back(i);
 ptr_numbers.push_back(&numbers.back());

share|improve this answer

edited 16 mins ago

answered 38 mins ago

Ivan

3,21592240

What you are seeing is that std::vector has to reallocate its element because it needs more memory.

For example initially it could allocate memory for 4 integers, but when you insert 5th int, it has to allocate a new memory chunk and copy old 4 integers there. Therefor elements change their address.

It is said that std::vector::resize invalidates all pointer and iterators derived from it when it needs to change its capacity:

Reallocation invalidates all the references, pointers, and iterators
referring to the elements in the sequence. No reallocation shall take
place during insertions that happen after a call to reserve() until
the time when an insertion would make the size of the vector greater
than the value of capacity().

So you can try reserving memory beforehand:

std::vector<int> numbers;
std::vector<int*> ptr_numbers;
numbers.reserve(8); // <--- Here
for (int i = 0; i < 8; i++) 
 numbers.push_back(i);
 ptr_numbers.push_back(&numbers.back());

share|improve this answer

edited 16 mins ago

answered 38 mins ago

Ivan

3,21592240

share|improve this answer

share|improve this answer

edited 16 mins ago

edited 16 mins ago

edited 16 mins ago

answered 38 mins ago

Ivan

3,21592240

answered 38 mins ago

Ivan

3,21592240

answered 38 mins ago

Ivan

3,21592240

3,21592240

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  "It is said" - by who?
  – Ville-Valtteri
  36 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Ville-Valtteri By people on the internet. Or by the standard.
  – Ivan
  36 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Ivan When you provide a quote you should also offer a link to wherever you are go it from if you want it to have credibility.
  – François Andrieux
  5 mins ago
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  "It is said" - by who?
  – Ville-Valtteri
  36 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Ville-Valtteri By people on the internet. Or by the standard.
  – Ivan
  36 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Ivan When you provide a quote you should also offer a link to wherever you are go it from if you want it to have credibility.
  – François Andrieux
  5 mins ago
  
  

  
  
  
  

1

1

"It is said" - by who?
– Ville-Valtteri
36 mins ago

"It is said" - by who?
– Ville-Valtteri
36 mins ago

@Ville-Valtteri By people on the internet. Or by the standard.
– Ivan
36 mins ago

@Ville-Valtteri By people on the internet. Or by the standard.
– Ivan
36 mins ago

@Ivan When you provide a quote you should also offer a link to wherever you are go it from if you want it to have credibility.
– François Andrieux
5 mins ago

@Ivan When you provide a quote you should also offer a link to wherever you are go it from if you want it to have credibility.
– François Andrieux
5 mins ago

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52330010%2fwhat-does-stdvector-look-like-in-memory%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email