vector::insert invalidates end()?

[Marc]

Hello,

[vector.modifiers] says about vector::insert: "If no reallocation happens, all the iterators and references before the insertion point remain valid." This doesn't seem to guarantee anything about the iterator *at* the point of insertion.

The question comes from people asking if the following is valid, assuming a sufficient call to reserve() was done first:

v.insert(v.end(), v.begin(), v.end());

It could fail for an implementation using a sentinel for the end of the vector, but I don't know of any (it would be quite inconvenient). And for any implementation using a simple position as iterator (pointer (possibly in a wrapper), or base+offset), this is needlessly restrictive. The fact that this alternative:

v.insert(v.end(), &v[0], &v[0]+v.size())

is valid (again assuming a large enough reserve()) makes it a bit confusing that the first version isn't.

Then we might as well say that vector iterators act as positions, and that after a reallocation-free insertion an iterator points to the same position, whatever may be there now...

[Daniel Krügler]

I tend to agree with what you wrote above. Would you please submit a
corresponding LWG issue to the lwgchair address as of

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html

?

Thanks,

- Daniel

[Vlad from Moscow]

By the way should this construction v.insert( v.end(), v.begin(), v.end() ); be well-formed? I did not find that it has something as undefined behaviour. However GCC and MS VC++ 2010 give wrong result for this code

std::vector<std::string> v { "1", "2", "3" };

v.insert( v.end(), v.begin(), v.end() );

воскресенье, 19 октября 2014 г., 1:17:18 UTC+4 пользователь Daniel Krügler написал:

[Marc]

Le dimanche 19 octobre 2014 08:43:58 UTC+2, Vlad from Moscow a écrit :

By the way should this construction v.insert( v.end(), v.begin(), v.end() ); be well-formed? I did not find that it has something as undefined behaviour.

The standard only says that iterators before the insertion point remain valid. Depending on what invalidating means exactly, you can take it to imply that the last argument becomes invalid during the insertion, and it doesn't know when to stop iterating anymore.
 

However GCC and MS VC++ 2010 give wrong result for this code

std::vector<std::string> v { "1", "2", "3" };

v.insert( v.end(), v.begin(), v.end() );

You are missing v.reserve(6); in between. Of course it can't work if insert needs a reallocation.

[Vlad from Moscow]

I can not aggree with your "of course".

Either the C++ Standard explicitly says that this construction is invalid in some cases or it is valid. I do not see any reason to implement the function such a way that it will behave correct when a reallocation is required.

воскресенье, 19 октября 2014 г., 13:46:44 UTC+4 пользователь Marc написал:

[Howard Hinnant]

> Then we might as well say that vector iterators act as positions, and that after a reallocation-free insertion an iterator points to the same position, whatever may be there now…

With sufficient capacity, all implementations I’m aware of will give you the expected result for your example.

However the C++98/11/14 standards explicit call out this code as undefined behavior. Table 100 — Sequence container requirements, in [sequence.reqmts], has a row:

a.insert(p, i, j)

There is a precondition on this operation that i and j are not iterators into a.

Howard

[Marc]

Le dimanche 19 octobre 2014 18:51:35 UTC+2, Howard Hinnant a écrit :

On Oct 18, 2014, at 4:54 PM, Marc <marc....@gmail.com> wrote:

> [vector.modifiers] says about vector::insert: "If no reallocation happens, all the iterators and references before the insertion point remain valid." This doesn't seem to guarantee anything about the iterator *at* the point of insertion.
>
> The question comes from people asking if the following is valid, assuming a sufficient call to reserve() was done first:
>
> v.insert(v.end(), v.begin(), v.end());
>
> It could fail for an implementation using a sentinel for the end of the vector, but I don't know of any (it would be quite inconvenient). And for any implementation using a simple position as iterator (pointer (possibly in a wrapper), or base+offset), this is needlessly restrictive. The fact that this alternative:
>
> v.insert(v.end(), &v[0], &v[0]+v.size())
>
> is valid (again assuming a large enough reserve()) makes it a bit confusing that the first version isn't.
>
> Then we might as well say that vector iterators act as positions, and that after a reallocation-free insertion an iterator points to the same position, whatever may be there now…

With sufficient capacity, all implementations I’m aware of will give you the expected result for your example.

Good.

 

However the C++98/11/14 standards explicit call out this code as undefined behavior.  Table 100 — Sequence container requirements, in [sequence.reqmts], has a row:

a.insert(p, i, j)

There is a precondition on this operation that i and j are not iterators into a.

 
I tend to interpret this section as documenting a sequence concept (although it actually lists specific properties of specific containers at the same time). It is perfectly fine for a container satisfying this concept to provide "better" functions, with stronger postconditions or weaker preconditions, as they provide at least the more limited guarantees in the concept.

I may even interpret the current standard (taking the documentation of vector over the generic one for sequences) as saying that v.insert(p,i,j), with p, i, j iterators into the vector v, is legal as long as i<=j<p and the capacity is large enough. And I am trying to relax that to allow j==p.