C++ STL Containers and pointer validity

Question

Consider this piece of code:

Uint counter = 0;

int* p1;
int* p2;

deque<int>  dequeInstance;
vector<int> vectorInstance;

dequeInstance.push_back(3);
dequeInstance.push_back(7);

p1 = &dequeInstance.back();

dequeInstance.push_back(17);

p2 = &dequeInstance.back();

if(*p1 == !7)
    ++counter;

if(*p2 == !17)
    ++counter;

vectorInstance.push_back(3);
vectorInstance.push_back(7);

p1 = &vectorInstance.back();

vectorInstance.push_back(17);

p2 = &vectorInstance.back();

if(*p1 == !7)
    ++counter;

if(*p2 == !17)
    ++counter;



return counter;

I would have expected that when I pushed the third element to the back of the vector, the pointer to the second element would have been invalidated, as my understanding of std::vector is that its a straight array which is wiped and recreated every time its modified. By the end of this code however 'counter' is equal to zero.

What am I missing here?

icecrime · Accepted Answer · 2010-12-05 09:12:59Z

5

Hopefully for performance, std::vector is not 'wiped and recreated every time it's modified'.

A vector has a capacity which may exceed its size, which means that it can allocate more memory than truly used. When you push_back, a reallocation will only occur if the new size is greater than the old capacity, and in this case, iterators are invalidated.

In your case, you should check the value of capacity right after the std::vector instantiation. You will see that it's without any doubt greater than 3, thus, none of your push_back calls trigger a reallocation and all iterators remain valid.

Also note that std::vector provides a reserve member function which allow you to control the vector capacity. This is really useful when you know how many elements are expected to be inserted in order to avoid ulterior reallocation.

answered Dec 5, 2010 at 9:12

icecrime

77.2k13 gold badges106 silver badges113 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

fredoverflow Over a year ago

The standard guarantees amortized constant time for push_back. This means vector cannot possibly be resized every time. Hope is not necessary here :)

Goz · Accepted Answer · 2010-12-05 09:15:58Z

2

Ok you have a few problems. Firstly, !n = 0 unless n = 0 and then it equals 1. Therefore counter never gets incremented.

Secondly a vector does not necessarily destroy the contents when you push_back a new element. A vector has 2 "sizes". 1 is the number of elements in the vector and 2 is the amount of memory allocated. The vector only gets reallocated and copied when the amount of memory allocated runs out.

Furthermore after you have deleted an area of memory the memory is not necessarily cleared and may still point at valid data.

You aren't using iterators so they don't get invalidated. You are using pointers and they are simply pointing at an area of memory. Just because that memory isn't allocated does not mean that the pointer is invalid. This is one of the major dangers that C/C++ can leave you with. Make sure you don't do things like this as you are invoking "undefined behaviour" which can do anything from "not cause any problems and seemingly work" through to "crash horrifically and bring down your operating system in a dangerous way".

answered Dec 5, 2010 at 9:15

Goz

62.5k26 gold badges131 silver badges212 bronze badges

2 Comments

Tomas Over a year ago

whoops! Thats meant to be !=. I was retyping what I wrote in the morning. I need some sleep.

Goz Over a year ago

@Tomas: Well none-the-less counter never gets incremented because the pointer is either still pointing to valid data or it is pointing at memory and undefined behaviour, in your case, is seeing that the values still remain in memory after the allocation has been returned to the heap...

Collectives™ on Stack Overflow

C++ STL Containers and pointer validity

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related