insert part of a vector into itself

[Stephen Howe]

Is it possible to insert into vector a range of elements that is a part of
the same vector safely?

So

class Something
{
//
};

vector<Something> v;
vector<Something>::iterator it, itStart, itEnd;
:
v.insert(it, itStart, itEnd);

[itStart, itEnd) are a range of valid iterators pointing into v.
it is an iterator pointing into v.
it is not contained within [itStart, itEnd)

To me it seems that as long as the spare capacity is greater than or equal
to itEnd - itStart, is required but is that enough?

Thanks

Stephen Howe

[Igor Tandetnik]

"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
news:eylCp4mQ...@TK2MSFTNGP11.phx.gbl

> Is it possible to insert into vector a range of elements that is a
> part of the same vector safely?

No - it violates the requiremetns of table 67 at 23.1.1/4, namely:

a.insert(p,i,j)
pre: i,j are not iterators into a.
inserts copies of elements in [i,j) before p.

Having said that, I expect it would work with any sane implementation of
std::vector as long as insert() does not cause memory reallocation. If
memory reallocation occurs, it's likely to break spectacularly.
--
With best wishes,
Igor Tandetnik

"For every complex problem, there is a solution that is simple, neat,
and wrong." H.L. Mencken

[P.J. Plauger]

"Igor Tandetnik" <itand...@mvps.org> wrote in message
news:%23jQNvDn...@TK2MSFTNGP09.phx.gbl...

> "Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
> news:eylCp4mQ...@TK2MSFTNGP11.phx.gbl
> > Is it possible to insert into vector a range of elements that is a
> > part of the same vector safely?
>
> No - it violates the requiremetns of table 67 at 23.1.1/4, namely:
>
> a.insert(p,i,j)
> pre: i,j are not iterators into a.
> inserts copies of elements in [i,j) before p.
>
> Having said that, I expect it would work with any sane implementation of
> std::vector as long as insert() does not cause memory reallocation. If
> memory reallocation occurs, it's likely to break spectacularly.

IIRC, we try pretty hard to get insertions right, even when you
insert from elsewhere in a container. At least from about V7 onward.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

[Stephen Howe]

> Having said that, I expect it would work with any sane implementation of
> std::vector as long as insert() does not cause memory reallocation. If
> memory reallocation occurs, it's likely to break spectacularly.

That is what I would expect. But as you say, it is not guaranteed (which I
don't like).

Stephen Howe

[Stephen Howe]

> IIRC, we try pretty hard to get insertions right, even when you
> insert from elsewhere in a container. At least from about V7 onward.

Thanks. Even so, no reallocation must be a requirement, surely?

Stephen Howe

[Igor Tandetnik]

"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message

news:upcbIPnQ...@TK2MSFTNGP10.phx.gbl

>> IIRC, we try pretty hard to get insertions right, even when you
>> insert from elsewhere in a container. At least from about V7 onward.
>
> Thanks. Even so, no reallocation must be a requirement, surely?

Not necessarily. One can allocate a new larger block, copy original
elements over, copy elements to be inserted, and only then deallocate
the old memory block. This will work even when inserting elements from
the same vector. But nothing in the standard says the implementation has
to work this way.

[Doug Harrison [MVP]]

Igor Tandetnik wrote:

>"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
>news:eylCp4mQ...@TK2MSFTNGP11.phx.gbl
>> Is it possible to insert into vector a range of elements that is a
>> part of the same vector safely?
>
>No - it violates the requiremetns of table 67 at 23.1.1/4, namely:
>
>a.insert(p,i,j)
>pre: i,j are not iterators into a.
>inserts copies of elements in [i,j) before p.
>
>Having said that, I expect it would work with any sane implementation of
>std::vector as long as insert() does not cause memory reallocation. If
>memory reallocation occurs, it's likely to break spectacularly.

In addition, it will likely break if the range intersects [p, a.end()).

I think what really tripped up some implementations is not vector but
basic_string, whose modifiers the Standard typically and subtly defines in
terms of temporary strings.

--
Doug Harrison
Microsoft MVP - Visual C++

[P.J. Plauger]

"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message

news:upcbIPnQ...@TK2MSFTNGP10.phx.gbl...

> > IIRC, we try pretty hard to get insertions right, even when you
> > insert from elsewhere in a container. At least from about V7 onward.
>
> Thanks. Even so, no reallocation must be a requirement, surely?

Nope. It's actually easier if there's reallocation. We buy the
new space and set it up while leaving the old array in place.
That way, all iterators into the old space remain valid until
the insert is complete.

[P.J. Plauger]

"Doug Harrison [MVP]" <d...@mvps.org> wrote in message
news:4it6b0h7r1nr0rbso...@4ax.com...

> Igor Tandetnik wrote:
>
> >"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
> >news:eylCp4mQ...@TK2MSFTNGP11.phx.gbl
> >> Is it possible to insert into vector a range of elements that is a
> >> part of the same vector safely?
> >
> >No - it violates the requiremetns of table 67 at 23.1.1/4, namely:
> >
> >a.insert(p,i,j)
> >pre: i,j are not iterators into a.
> >inserts copies of elements in [i,j) before p.
> >
> >Having said that, I expect it would work with any sane implementation of
> >std::vector as long as insert() does not cause memory reallocation. If
> >memory reallocation occurs, it's likely to break spectacularly.
>
> In addition, it will likely break if the range intersects [p, a.end()).

In general you're right. We try to get the right result even with
such pathological cases.

> I think what really tripped up some implementations is not vector but
> basic_string, whose modifiers the Standard typically and subtly defines in
> terms of temporary strings.

Yes. We really had to work hard to get strings to work right with
replaces as well as inserts and assigns from the same container.
But we did.