Under what circumstances can the STL move a vector?

[Richard Thompson]

I've got a memory overwrite problem, and it looks as if a vector has
been moved, even though I haven't inserted or deleted any elements in
it. Is this possible? In other words, are there any circumstances in
which the STL will move a vector, or invalidate iterators to elements
in the vector, if you don't insert or remove elements?

My actual problem seems to be as follows:

I have class X, which contains an STL vector. The constructor does
very little, and leaves the vector empty. X has no assignment or copy
ctors:

class X {
...
vector<wibble> wvec;
};

I also have a heap of X's, which is maintained as a vector. The first
item on the heap is created by pushing an X onto the back of the empty
heap:

vector<wibble>& create_heap_item() {
...
heap.push_back(X(...));
return heap.back().wvec;
}

The routine which calls 'create_heap_item' gets a reference to wvec,
and uses it to insert items into wvec:

vector<wibble>& wref = create_heap_item();
wref.insert(wreg.begin(), a_wibble);
...

This all seems to work Ok as long as there's only one item on the
heap. However, when I add a second item, everything goes wrong. I have
various reverse iterators into the first wvec stored in other classes,
but after adding the second heap item these now appear to point into
the *second* wvec. It's almost as if the first wvec has moved. Or am I
just messing up my references?

Any ideas? This is driving me crazy...

TIA

Richard

[Shezan Baig]

Richard Thompson wrote:

I've got a memory overwrite problem, and it looks as if a vector has
been moved, even though I haven't inserted or deleted any elements in
it. Is this possible? In other words, are there any circumstances in
which the STL will move a vector, or invalidate iterators to elements
in the vector, if you don't insert or remove elements?

My actual problem seems to be as follows:

I have class X, which contains an STL vector. The constructor does
very little, and leaves the vector empty. X has no assignment or copy
ctors:

class X {
...
vector<wibble> wvec;
};

I also have a heap of X's, which is maintained as a vector. The first
item on the heap is created by pushing an X onto the back of the empty heap:

vector<wibble>& create_heap_item() {
...
heap.push_back(X(...));
return heap.back().wvec;
}

The routine which calls 'create_heap_item' gets a reference to wvec,
and uses it to insert items into wvec:

vector<wibble>& wref = create_heap_item();
wref.insert(wreg.begin(), a_wibble);
...

This all seems to work Ok as long as there's only one item on the
heap. However, when I add a second item, everything goes wrong. I have various reverse iterators into the first wvec stored in other classes, but after adding the second heap item these now appear to point into
the *second* wvec. It's almost as if the first wvec has moved. Or am I just messing up my references?

It is best not to store iterators for future use, as it is very likely
that they will become invalid (even if you don't *directly* modify the
source vector). This is illustrated in your current problem.

When you push something to 'heap', the 'heap' vector can move things
around (even though you did not touch the first element). So your
first 'X' object was probably moved somewhere else, hence any iterators
for any of its members becomes invalid.

One solution is to store the index of elements in 'heap' into the
'wref' vector (instead of storing the iterators). There may be other
solutions, but that depends on what exactly you are trying to do.

Hope this helps,
-shez-

Any ideas? This is driving me crazy...

TIA

Richard

[Thomas Tutone]

"Richard Thompson" wrote:

I've got a memory overwrite problem, and it looks as if a vector has
been moved, even though I haven't inserted or deleted any elements in
it. Is this possible? In other words, are there any circumstances in
which the STL will move a vector, or invalidate iterators to elements
in the vector, if you don't insert or remove elements?
When you push_back into a vector, there may be insufficient space, the
vector may be moved, and iterators may be invalidated.

My actual problem seems to be as follows:

I have class X, which contains an STL vector. The constructor does
very little, and leaves the vector empty. X has no assignment or copy
ctors:

class X {
...
vector<wibble> wvec;
};
X does have a copy constructors and operator=() - they're declared
implicitly unless you tell the compiler otherwise. If you don't want them
available, declare them as private and don't define them:

class X {
private:
X(const& X); // declared but not defined
void operator=(const& X); // declared but not defined
....
};

I also have a heap of X's, which is maintained as a vector. The first
item on the heap is created by pushing an X onto the back of the empty
heap:

vector<wibble>& create_heap_item() {
...
heap.push_back(X(...));
return heap.back().wvec;
}
Is the vector static or a global variable? If not, what are you returning a
reference to? If the vector is local to create_heap_item, you're returning
a reference to a local variable - i.e., a dangling reference.

The routine which calls 'create_heap_item' gets a reference to wvec,
and uses it to insert items into wvec:

vector<wibble>& wref = create_heap_item();
wref.insert(wreg.begin(), a_wibble);
That insert invalidates all iterators to wref.
...

This all seems to work Ok as long as there's only one item on the
heap. However, when I add a second item, everything goes wrong.
Theoretically, when you add the second item, all the iterators may be
invalidated. Usually, I would expect it would take more than a single
addition to cause that to happen, though.
I have
various reverse iterators into the first wvec stored in other classes,
but after adding the second heap item these now appear to point into
the *second* wvec. It's almost as if the first wvec has moved. Or am I
just messing up my references?

You don't give enough info. It may be that you're using dangling
references, or that you're invalidating your iterators by inserts or
push_backs. Give a short stand-alone, compilable piece of code that
duplicates the problem and someone can probably help you.

Best regards,

Tom

[Howard Hinnant]

In article <8n********************************@4ax.com>,
Richard Thompson <no****@nospam.com> wrote:

This all seems to work Ok as long as there's only one item on the
heap. However, when I add a second item, everything goes wrong. I have
various reverse iterators into the first wvec stored in other classes,
but after adding the second heap item these now appear to point into
the *second* wvec. It's almost as if the first wvec has moved. Or am I
just messing up my references?

A vector is allowed to reallocate (and thus invalidate outstanding
iterators, pointers and references) when size() threatens to exceed
capacity(). You can use reserve() to set capacity() and thus choose
when you want the reallocation to happen.

-Howard

[Victor Bazarov]

"Richard Thompson" <no****@nospam.com> wrote...

I've got a memory overwrite problem, and it looks as if a vector has
been moved, even though I haven't inserted or deleted any elements in
it. Is this possible? In other words, are there any circumstances in
which the STL will move a vector, or invalidate iterators to elements
in the vector, if you don't insert or remove elements?
I don't think so. What makes you believe that that is what happens?
My actual problem seems to be as follows:

I have class X, which contains an STL vector. The constructor does
very little, and leaves the vector empty. X has no assignment or copy
ctors:

class X {
...
vector<wibble> wvec;
};

I also have a heap of X's, which is maintained as a vector. The first
item on the heap is created by pushing an X onto the back of the empty
heap:

vector<wibble>& create_heap_item() {
...
heap.push_back(X(...));
How is 'heap' declared?
return heap.back().wvec;
}

The routine which calls 'create_heap_item' gets a reference to wvec,
and uses it to insert items into wvec:

vector<wibble>& wref = create_heap_item();
wref.insert(wreg.begin(), a_wibble);
OK, but this *does* change the actual vector.
...

This all seems to work Ok as long as there's only one item on the
heap. However, when I add a second item, everything goes wrong.
When you add another element to the vector *and* the vector has to
reallocate, all references and iterator are invalidated.
I have
various reverse iterators into the first wvec stored in other classes,
Don't.
but after adding the second heap item these now appear to point into
the *second* wvec. It's almost as if the first wvec has moved. Or am I
just messing up my references?
The rule of thumb: don't hang onto references or pointers or iterators
to any elements of such volatile data structure as 'std::vector'.
Any ideas? This is driving me crazy...

Instead of storing reference, store indices.

V

[Andrew Koenig]

"Richard Thompson" <no****@nospam.com> wrote in message
news:8n********************************@4ax.com...

I've got a memory overwrite problem, and it looks as if a vector has
been moved, even though I haven't inserted or deleted any elements in
it. Is this possible? In other words, are there any circumstances in
which the STL will move a vector, or invalidate iterators to elements
in the vector, if you don't insert or remove elements?
If you destroy the vector itself, its elements go away.
My actual problem seems to be as follows: I have class X, which contains an STL vector. The constructor does
very little, and leaves the vector empty. X has no assignment or copy
ctors: class X {
...
vector<wibble> wvec;
}; I also have a heap of X's, which is maintained as a vector. The first
item on the heap is created by pushing an X onto the back of the empty
heap:

vector<wibble>& create_heap_item() {
...
heap.push_back(X(...));
return heap.back().wvec;
} The routine which calls 'create_heap_item' gets a reference to wvec,
and uses it to insert items into wvec:

vector<wibble>& wref = create_heap_item();
wref.insert(wreg.begin(), a_wibble); This all seems to work Ok as long as there's only one item on the
heap. However, when I add a second item, everything goes wrong. I have
various reverse iterators into the first wvec stored in other classes,
but after adding the second heap item these now appear to point into
the *second* wvec. It's almost as if the first wvec has moved. Or am I
just messing up my references?

I assume you mean wref.insert(wref.begin(), a_wibble), rather than using
wreg.begin().

Anyway, when you call wref.insert, that can potentially reallocate wref.
That, in turn, copies the elements of wref and destroys the originals.
That, in turn, invalidates any iterators that refer to elements of the
originals.

[Richard Thompson]

Thanks guys - I'm amazed to get so many replies on a Sunday afternoon.
In response to the general queries, the heap is external, and I don't
carry out any inserts/deletes *directly* to the affected vector that
could cause a re-allocation.

I've managed to knock up a test case that, amazingly, actually shows
the problem. The code below is self-contained so you should just be
able to cut/paste/compile/run. The output from g++ 3.3, Linux RH7.2,
is:

richard 78 > a.out
Heap has 2 levels
Level 1:
1
2
134530840
Level 2:
4
5
6

The output I'm hoping for is 1, 2, 3, 4, 5, 6.

I'm concerned about the general advice not to store
references/iterators/whatever in case reallocation happens. Anyone who
canm tell me what's going on in this code will get my undying
gratitude.. :)

------------------------------------------
#include <vector>
#include <iostream>

using std::vector;
using std::cout;
using std::endl;

struct X {
vector<int> Ivec;
};

vector<X> heap; // the heap is external

vector<int> &create_heap_item(void) {
heap.push_back(X());
return heap.back().Ivec;
}

int main(void) {
vector<int>::reverse_iterator
ivit, l1rbegin, l1rend, l2rbegin, l2rend;

// create heap level 1: push in integers at the front
vector<int> &ivref1 = create_heap_item();
ivref1.insert(ivref1.begin(), 1);
ivref1.insert(ivref1.begin(), 2);
ivref1.insert(ivref1.begin(), 3);
l1rbegin = ivref1.rbegin();
l1rend = ivref1.rend();

// create heap level 2: push in integers at the front
vector<int> &ivref2 = create_heap_item();
ivref2.insert(ivref2.begin(), 4);
ivref2.insert(ivref2.begin(), 5);
ivref2.insert(ivref2.begin(), 6);
l2rbegin = ivref2.rbegin();
l2rend = ivref2.rend();

// dump the vectors: read from the back
cout << "Heap has " << heap.size() << " levels\n";
cout << "Level 1:\n";
for(ivit = l1rbegin; ivit < l1rend; ivit++)
cout << *ivit << endl;
cout << "Level 2:\n";
for(ivit = l2rbegin; ivit < l2rend; ivit++)
cout << *ivit << endl;
}

[Shezan Baig]

Richard Thompson wrote:

Thanks guys - I'm amazed to get so many replies on a Sunday afternoon. In response to the general queries, the heap is external, and I don't
carry out any inserts/deletes *directly* to the affected vector that
could cause a re-allocation.

I've managed to knock up a test case that, amazingly, actually shows
the problem. The code below is self-contained so you should just be
able to cut/paste/compile/run. The output from g++ 3.3, Linux RH7.2,
is:

richard 78 > a.out
Heap has 2 levels
Level 1:
1
2
134530840
Level 2:
4
5
6

The output I'm hoping for is 1, 2, 3, 4, 5, 6.

I'm concerned about the general advice not to store
references/iterators/whatever in case reallocation happens. Anyone who canm tell me what's going on in this code will get my undying
gratitude.. :)

------------------------------------------
#include <vector>
#include <iostream>

using std::vector;
using std::cout;
using std::endl;

struct X {
vector<int> Ivec;
};

vector<X> heap; // the heap is external

vector<int> &create_heap_item(void) {
heap.push_back(X());
return heap.back().Ivec;
}

int main(void) {
vector<int>::reverse_iterator
ivit, l1rbegin, l1rend, l2rbegin, l2rend;

// create heap level 1: push in integers at the front
vector<int> &ivref1 = create_heap_item();
ivref1.insert(ivref1.begin(), 1);
ivref1.insert(ivref1.begin(), 2);
ivref1.insert(ivref1.begin(), 3);
l1rbegin = ivref1.rbegin();
l1rend = ivref1.rend();

// create heap level 2: push in integers at the front
vector<int> &ivref2 = create_heap_item();

This is where things get screwy. When you call create_heap_item, you
are modifying 'heap'. This means 'heap' can move your first 'X'
somewhere new & that means the 'Ivec' stored in that first 'X' is also
moved. That means 'ivref1' is an invalid reference. Since 'ivref1' is
an invalid reference, that also means that 'l1rbegin' and 'l1rend' are
also invalid references, since they contain references to data stored
in the (now invalid) 'ivref1'.

Hope this helps,
-shez-

[Richard Thompson]

[posted after my previous reply to myself, which hasn't turned up yet]

After re-reading the first set of replies, and looking at my test code
(just posted), it seems to me that some of you have already answered
the question. When I push a new element onto the back of the heap (the
second call to 'create_heap_item') then the heap is presumably
re-allocated, because it's size has just doubled. In the process, the
vector in the first element on the heap is moved, thus invalidating
l1rbegin and l1rend.

I had assumed, somewhere at the back of my mind, that the 'control
structure' (?) for the first vector on the heap would move, but that
the 'real' vector, which is presumably stored somewhere else on the
system heap, wouldn't move. Presumably this is wrong? Are the vector
elements actually stored in struct X, and moved with struct X?

It seems to me that if you're writing library code (as I am), and you
don't know how your classes are going to be used, then you can *never*
rely on your iterators remaining valid? Doesn't this severely restrict
the use of the STL?

Richard

[Shezan Baig]

Richard Thompson wrote:

[posted after my previous reply to myself, which hasn't turned up yet]
I had assumed, somewhere at the back of my mind, that the 'control
structure' (?) for the first vector on the heap would move, but that
the 'real' vector, which is presumably stored somewhere else on the
system heap, wouldn't move. Presumably this is wrong? Are the vector
elements actually stored in struct X, and moved with struct X?
This is implementation defined. STL just says that iterators remain
valid until the next non-const method is called for a container. And
non-constness is transitive, so it can be passed along to containers
stored in containers.

It seems to me that if you're writing library code (as I am), and you
don't know how your classes are going to be used, then you can *never* rely on your iterators remaining valid?

Yes. Personally, I would not store iterators, I would use indices.
But if you absolutely *have* to use iterators (e.g., for non-random
access containers), then I would encapsulate 'heap' in another class
instead of leaving it as a global variable. That way, you can control
access to 'heap' and if any non-const method is called, you just need
to refresh the iterators.

Doesn't this severely restrict the use of the STL?

Not *severely*, no. You just need to use it as it's documented :)

Hope this helps,
-shez-

[Howard Hinnant]

In article <47********************************@4ax.com>,
Richard Thompson <no****@nospam.com> wrote:

[posted after my previous reply to myself, which hasn't turned up yet]

After re-reading the first set of replies, and looking at my test code
(just posted), it seems to me that some of you have already answered
the question. When I push a new element onto the back of the heap (the
second call to 'create_heap_item') then the heap is presumably
re-allocated, because it's size has just doubled. In the process, the
vector in the first element on the heap is moved, thus invalidating
l1rbegin and l1rend.

I had assumed, somewhere at the back of my mind, that the 'control
structure' (?) for the first vector on the heap would move, but that
the 'real' vector, which is presumably stored somewhere else on the
system heap, wouldn't move. Presumably this is wrong? Are the vector
elements actually stored in struct X, and moved with struct X?
vector is nothing more than a convenience wrapper around a contiguous
chunk of memory. When that chunk of memory becomes too small, a bigger
chunk is allocated, and stuff moved into it.
It seems to me that if you're writing library code (as I am), and you
don't know how your classes are going to be used, then you can *never*
rely on your iterators remaining valid? Doesn't this severely restrict
the use of the STL?

No. Each container has well defined semantics on how and when iterators
and references into the container become invalidated. For example
vector's iterators and references become invalidated whenever size()
tries to exceed capacity(). The same is not true for other containers
in the std::lib.

For example std::list iterators and references don't become invalidated
until the element to which they refer to is erased. Substituting list
in for vector in your example (and making some minor changes in the way
the iterators are compared) results in:

Heap has 2 levels
Level 1:
1
2
3
Level 2:
4
5
6

deque would be another option for your example if you trafficked in
references instead of iterators (deque is unique in that it will often
invalidate iterators, but not references or pointers into the container).

You might consider using list for your outer container (heap) and
retaining vector for your inner container. It is only your outer
container that appears to be sensitive to iterator invalidation.

Part of the container's interface is how and when it invalidates
references and iterators, and to effectively use and choose which
container is appropriate for your program, you must know this part of
the interface. Ignoring this part of the interface will probably
"severely restrict the use of the STL".

-Howard

[Richard Thompson]

Hope this helps,
-shez-

Certainly does; thank you.

The longer I spend on C++ the more things I find waiting to jump up
and bite me on the a**e...

Cheers

Richard