473,597 Members | 2,040 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Under what circumstances can the STL move a vector?

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_ite m() {
...
heap.push_back( X(...));
return heap.back().wve c;
}

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

vector<wibble>& wref = create_heap_ite m();
wref.insert(wre g.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
Jul 23 '05 #1
11 2889

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_ite m() {
...
heap.push_back( X(...));
return heap.back().wve c;
}

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

vector<wibble>& wref = create_heap_ite m();
wref.insert(wre g.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


Jul 23 '05 #2

"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_ite m() {
...
heap.push_back( X(...));
return heap.back().wve c;
}
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_ite m, you're returning
a reference to a local variable - i.e., a dangling reference.

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

vector<wibble>& wref = create_heap_ite m();
wref.insert(wre g.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

Jul 23 '05 #3
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
Jul 23 '05 #4
"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_ite m() {
...
heap.push_back( X(...));
How is 'heap' declared?
return heap.back().wve c;
}

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

vector<wibble>& wref = create_heap_ite m();
wref.insert(wre g.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
Jul 23 '05 #5
"Richard Thompson" <no****@nospam. com> wrote in message
news:8n******** *************** *********@4ax.c om...
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_ite m() {
...
heap.push_back( X(...));
return heap.back().wve c;
} The routine which calls 'create_heap_it em' gets a reference to wvec,
and uses it to insert items into wvec:

vector<wibble>& wref = create_heap_ite m();
wref.insert(wre g.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(wre f.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.
Jul 23 '05 #6
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_it em(void) {
heap.push_back( X());
return heap.back().Ive c;
}

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

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

// create heap level 2: push in integers at the front
vector<int> &ivref2 = create_heap_ite m();
ivref2.insert(i vref2.begin(), 4);
ivref2.insert(i vref2.begin(), 5);
ivref2.insert(i vref2.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;
}

Jul 23 '05 #7

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_it em(void) {
heap.push_back( X());
return heap.back().Ive c;
}

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

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

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

This is where things get screwy. When you call create_heap_ite m, 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-

Jul 23 '05 #8
[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_it em') 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
Jul 23 '05 #9

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-

Jul 23 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
12590
by: William Payne | last post by:
(This post is related to "recent files menu"-post below. If I should have kept this in that thread, I apologise.) Hello, I have a function that adds a std::string to a std::vector. New entries are added at the front (index 0) of the vector. If the vector contains a certain amount of elements, the element at the back is removed when a new one is added. If one tries to add a string already stored in the vector, that string is supposed to...
1
1722
by: Mike Hutton | last post by:
I need some help. I am trying to set up our development environment so as to make life easy for my fellow developers (none of whom have used ASP.NET or VS.NET before). We are developing our intranet which will comprise basic content with a number of small data-driven ASP.NET applications. I need to keep things simple, so I need to avoid stuff which needs too much in-depth knowledge to work.
8
3139
by: Jack | last post by:
Hi, This code I inherited worked under VC7 now fails under VC8 with error: error C2664: 'memcpy' : cannot convert parameter 1 from 'std::_Vector_iterator<_Ty,_Alloc>' to 'void *' vector <png_color> vPalette; .. .. ..
5
3539
by: levent | last post by:
Hi, Is it possible (with STL) to move the contents of a vector into a list? Obviously this would be a linear complexity operation (number of elements in vector), but is it possible to do this w/o copy constructing every element into list and destructing the vector contents?
35
3008
by: Frederick Gotham | last post by:
(Before I begin, please don't suggest to me to use "std::vector" rather than actual arrays.) I understand that an object can have resources (e.g. dynamically allocated memory), and so we have to copy an object properly via copy- construction rather than using memcpy. However, is it okay to move an object manually (i.e. by using memcpy or memmove)?
2
2810
by: Igor Kravtchenko | last post by:
Hi! We have an application using Python that is intended to work both under Win32 and Linux. Since some parts of the code need to be different depending whether we are under Win32 or Linux, we use the traditional: if os.name == "posix": some Linux code
10
2836
by: sandraz444 | last post by:
I have an expression in the query under my form to autofill the date under a certain condition but it wont write to the underlying table?? The date shows in the form but not the table. Does anyone know a solution for this? Thanks!
7
2355
by: In a little while | last post by:
i have a block of data -- integer type, i need to move them to some given addresses, is this possible ? thanks
1
5587
Banfa
by: Banfa | last post by:
So the basic sequenced C++ containers are vector - holds data in a contiguous memory block that has the same memory footprint as a classical array. Expensive to insert or delete at the front or in the middle as it involves copying to maintain the memory layout, can be expensive to append to the end if it involves reallocating memory, never releases memory once allocated without user intervention. Has random access and therefore random...
0
7965
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8380
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
8258
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
6686
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
5847
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5426
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
3923
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2399
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1493
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.