Bizarre vector insertion behavior - can someone please enlighten?

[ckfan.painter]

I've run into a seemingly bizarre problem with insert() for
std::vector. (This was done on Microsoft Visual C++ 2005 express
version 8...maybe it is a compiler specific bug?)

Here's the code:

//===================

// vector tester 3.cpp : main project file.

#include "stdafx.h"
#include<vector>

int main(array<System::String ^^args)
{
std::vector<intvectorList;

for (unsigned int i = 0; i < 45; ++i) // works if 45 is
replaced with smaller value.
vectorList.push_back(i);

unsigned int aBegin = 25;
unsigned int aEnd = 35; // works if 35 is replaced with 34.

vectorList.insert(vectorList.begin() + 35, // works if 35 is
replaced by 36, 37, 38 ...
// but not if 35 is replaced by 34, 33, 32...
vectorList.begin() + aBegin, vectorList.begin() + aEnd);

return 0;
}

//========================

When this is run, an error occurs during the insertion about
incompatible vector iterators.
At first I thought, maybe this is happening because I'm trying to
insert into the range that I am copying...but, if the size of the
vector is just changed from 45 elements long to 44 elements long...the
program works! I think that is just bizarre.

Does anybody understand what is going on here? It would be crazy to
write code that might fail whenever it encounters a vector.insert() so
I would like to understand the reason this code fails but when the 45
is replaced with 44, it works.

Any insight appreciated!

CK

[Victor Bazarov]

ck***********@gmail.com wrote:

I've run into a seemingly bizarre problem with insert() for
std::vector. (This was done on Microsoft Visual C++ 2005 express
version 8...maybe it is a compiler specific bug?)

Here's the code:

//===================

// vector tester 3.cpp : main project file.

#include "stdafx.h"

You might want to consider weeding MS-isms out before posting here.

#include<vector>

int main(array<System::String ^^args)

That's not Standard C++, sorry. For managed extensions, try MS
newsgroups.

{
std::vector<intvectorList;

for (unsigned int i = 0; i < 45; ++i) // works if 45 is
replaced with smaller value.

What "works"? By extension, what "doesn't"?

vectorList.push_back(i);

unsigned int aBegin = 25;
unsigned int aEnd = 35; // works if 35 is replaced with 34.

vectorList.insert(vectorList.begin() + 35, // works if 35 is
replaced by 36, 37, 38 ...
// but not if 35 is replaced by 34, 33, 32...
vectorList.begin() + aBegin, vectorList.begin() + aEnd);

Any insertion into the middle of the vector can invalidate _all_
of its iterators (the one returned by 'begin()' included). Your
program most likely has undefined behaviour.

You can avoid that if you reserve memory in the vector:

vectorList.reserve(vectorList.size() + how_many_to_insert);

>
return 0;
}

//========================

When this is run, an error occurs during the insertion about
incompatible vector iterators.

"incompatible"? I don't think this is a Standard term.

At first I thought, maybe this is happening because I'm trying to
insert into the range that I am copying...but, if the size of the
vector is just changed from 45 elements long to 44 elements long...the
program works! I think that is just bizarre.

It isn't. See above.

Does anybody understand what is going on here? It would be crazy to
write code that might fail whenever it encounters a vector.insert() so
I would like to understand the reason this code fails but when the 45
is replaced with 44, it works.

Do not insert the elements of a vector into itself without reserving
first.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[ckfan.painter]

Hi Victor,

Thank you for your tips about posting here. It was my first post to
this newsgroup.

I thought of the reserve possibility, and it doesn't fix the problem.
When the code is run, I get:

Debug Assertion Failed!

Program:...
File: C:\Program Files\Microsoft Visual Studio 8\VC\include\vector
Line: 238

Expression: vector iterators incompatible
I took a look at Stroustrup's examples with fruit (3rd ed., p. 453),
and noticed that he avoids inserting a segment of a vector into
itself. However, Microsoft's own help on vector insert does use an
example of such an insertion. Also Stroustrup does not mention any
concern with self-insertion.

The only way I have of getting around this error that I hope is a
consistent fix is to do the following:

std::vector<inttemp;
temp.assign(vectorList.begin() + aBegin, vectorList.begin() +
aEnd);
vectorList.insert(vectorList.begin() + 35, temp.begin(),
temp.end());

Does the code I posted earlier run without the error on other
compilers? Sorry about the MS-isms.

CK

[Kai-Uwe Bux]

Victor Bazarov wrote:

ck***********@gmail.com wrote:

[snip}

> std::vector<intvectorList;

for (unsigned int i = 0; i < 45; ++i) // works if 45 is
replaced with smaller value.

What "works"? By extension, what "doesn't"?

> vectorList.push_back(i);

unsigned int aBegin = 25;
unsigned int aEnd = 35; // works if 35 is replaced with 34.

vectorList.insert(vectorList.begin() + 35, // works if 35 is
replaced by 36, 37, 38 ...
// but not if 35 is replaced by 34, 33, 32...
vectorList.begin() + aBegin, vectorList.begin() + aEnd);

[snip]

>Does anybody understand what is going on here? It would be crazy to
write code that might fail whenever it encounters a vector.insert() so
I would like to understand the reason this code fails but when the 45
is replaced with 44, it works.

Do not insert the elements of a vector into itself without reserving
first.

Actually, that can be phrased more general: never use

a.insert(p,i,j) // p : iterator into the vector
// i,j : iterators

to insert elements of a vector into itself. The precondition for this method
is stated in Table 67 as: pre: i,j are not iterators into a.
Best

Kai-Uwe Bux

[Thorsten Kiefer]

Hi,
I'm not sure, but I think the iterator doesn't keep a pointer to
its vector, but a pointer to the vector's data (which is an array).
Now I think, when you insert into the vector and the vector has
to reallocate its data array, the pointer in the iterator becomes
invalid. Maybe it works for values lower than 35, because reallocation
doesn't happen then. But that's just a wild guess.

Regards
Thorsten

[Victor Bazarov]

ck***********@gmail.com wrote:

[..]
Does the code I posted earlier run without the error on other
compilers? [..]

I am not even going to try. It has undefined behaviour, and
as such can cause nasal demons to take to the air.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[ckfan.painter]

Thanks to all for their replies.

It seems that the lesson I have to learn is that an official reference
to the standard template library would be valuable.

Is that what the "Table 67" is from that Kae-Uwe Bux refers to? Could
you please provide the name of the reference source? I googled it and
did find a Table 67 in a gcc.gnu.org website. Is that the source?

CK

[Victor Bazarov]

ck***********@gmail.com wrote:

Thanks to all for their replies.

It seems that the lesson I have to learn is that an official reference
to the standard template library would be valuable.

Is that what the "Table 67" is from that Kae-Uwe Bux refers to? Could
you please provide the name of the reference source? I googled it and
did find a Table 67 in a gcc.gnu.org website. Is that the source?

The Standard document. Table 67 is titled "Sequence requirements (in
addition to container)". See FAQ or search the archives on how to get
a copy of the Standard.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Dave Steffen]

ck***********@gmail.com writes:

Thanks to all for their replies.

It seems that the lesson I have to learn is that an official reference
to the standard template library would be valuable.

Every C++ programmer should have Josuttis' "The C++ Standard Library"
on their desk, among others.

----------------------------------------------------------------------
Dave Steffen, Ph.D. Disobey this command!
Software Engineer IV - Douglas Hofstadter
Numerica Corporation
dg@steffen a@t numerica d@ot us (remove @'s to email me)

[Alan Johnson]

ck***********@gmail.com wrote:

Thanks to all for their replies.

It seems that the lesson I have to learn is that an official reference
to the standard template library would be valuable.

Is that what the "Table 67" is from that Kae-Uwe Bux refers to? Could
you please provide the name of the reference source? I googled it and
did find a Table 67 in a gcc.gnu.org website. Is that the source?

CK

Not "official", but this is a quite good reference:
http://www.sgi.com/tech/stl/table_of_contents.html

--
Alan Johnson