vector erase

[Amadeus W. M.]

I have a vector from which I want to erase elements between iterators i,j.
If i<j, everything works as expected, but if j>i, an insertion is actually
performed. Example:

vector<double> x(10);
vector<double>::iterator i=x.begin()+2, j=x.begin()+6;

x.erase(i,j); // i<j, ok, erases 4 elements.
x.erase(j,i); // j>i, no error, just inserts 4 elements.

This happens with g++ 4.0.2. Is this standard behavior? Why does it work
this way?

[Andre Kostur]

"Amadeus W. M." <am*******@cablespeed.com> wrote in
news:pa****************************@cablespeed.com :

I have a vector from which I want to erase elements between iterators
i,j. If i<j, everything works as expected, but if j>i, an insertion is
actually performed. Example:

vector<double> x(10);
vector<double>::iterator i=x.begin()+2, j=x.begin()+6;

x.erase(i,j); // i<j, ok, erases 4 elements.
x.erase(j,i); // j>i, no error, just inserts 4 elements.

This happens with g++ 4.0.2. Is this standard behavior? Why does it
work this way?

No. It is Undefined Behaviour. When you pass two iterators to erase (and
many other functions taking two iterators), it is your responsibility to
ensure that the second iterator (j) is reachable from the first iterator
(i) only by invoking operator++ on it. Since you tried to pass them
backwards, erase() probably started by attempting to iterate from j to i,
and went flying off the end of the vector.

[Daniel T.]

In article <pa****************************@cablespeed.com>,
"Amadeus W. M." <am*******@cablespeed.com> wrote:

I have a vector from which I want to erase elements between iterators i,j.
If i<j, everything works as expected, but if j>i, an insertion is actually
performed. Example:

vector<double> x(10);
vector<double>::iterator i=x.begin()+2, j=x.begin()+6;

x.erase(i,j); // i<j, ok, erases 4 elements.
x.erase(j,i); // j>i, no error, just inserts 4 elements.

This happens with g++ 4.0.2. Is this standard behavior? Why does it work
this way?

The second erase is undefined behavior, the implementation can do
whatever it wants, including insert elements. I'm curious though how it
can insert elements when it doesn't have access to the vector's
push_back member-function... Are you sure that's what it is doing?

[Andre Kostur]

Andre Kostur <nn******@kostur.net> wrote in
news:Xn*******************************@207.35.177. 135:

"Amadeus W. M." <am*******@cablespeed.com> wrote in
news:pa****************************@cablespeed.com :

I have a vector from which I want to erase elements between iterators
i,j. If i<j, everything works as expected, but if j>i, an insertion
is actually performed. Example:

vector<double> x(10);
vector<double>::iterator i=x.begin()+2, j=x.begin()+6;

x.erase(i,j); // i<j, ok, erases 4 elements.
x.erase(j,i); // j>i, no error, just inserts 4 elements.

This happens with g++ 4.0.2. Is this standard behavior? Why does it
work this way?

No. It is Undefined Behaviour. When you pass two iterators to erase
(and many other functions taking two iterators), it is your
responsibility to ensure that the second iterator (j) is reachable
from the first iterator (i) only by invoking operator++ on it. Since
you tried to pass them backwards, erase() probably started by
attempting to iterate from j to i, and went flying off the end of the
vector.

Or... it probably starting copying from j+1 onto i (and j+2 to i+1, etc)
until (again) it eventually walked off the end of the vector. Then by
happenstance it stopped before actually crashing your problem (or perhaps
a debug-mode version of the standard library that checked to make sure
that you don't iterate off the end of a container). In either case, it's
still Undefined Behaviour.

[loquacious]

Andre Kostur wrote:

Or... it probably starting copying from j+1 onto i (and j+2 to i+1, etc)
until (again) it eventually walked off the end of the vector. Then by
happenstance it stopped before actually crashing your problem (or perhaps
a debug-mode version of the standard library that checked to make sure
that you don't iterate off the end of a container). In either case, it's
still Undefined Behaviour.

Implementation of erase(iterator::start, itertaor::end) first does a
copy from [iterator::end, vector::end()] in to vector starting at
iterator::start. So when iterator::end > iterator::start world is fine.
But when iterator::start > iterator::end then it would actuall copy
from iterator::start (which is greater than iterator::end till
vector::end() ) to vector::end() starting from iterator::end. Hence
instead of deleting it adds to the end first and then deletes from the
difference.

Below is one the implementation of vector::erase() which I thought
might be usefull in understanding the behaviour.

iterator __i(std::copy(__last, end(), __first));
std::_Destroy(__i, end());
this->_M_impl._M_finish = this->_M_impl._M_finish - \
(__last - __first);
return __first;

I am not sure as to why it was done this way but I think it's
developers responsibility to ensure that iterator::end >
iterator::start.

I did try out the example posted.
$ cat vec.cpp
#include <vector>
#include <iostream>

int main(int argc, char** argv) {
std::vector<int> x(10);
std::vector<int>::iterator i=x.begin()+2, j=x.begin()+6;

std::cout << "Size of vector " << x.size() << std::endl;
x.erase(i,j);
std::cout << "Size of vector " << x.size() << std::endl;
x.erase(j,i);
std::cout << "Size of vector " << x.size() << std::endl;
return 0;
}
$ ./a.out
Size of vector 10 [ Before deletion ]
Size of vector 6 [ After deletion ]
Size of vector 10 [ Adds 8 and then deletes 4 ]
$

Thank you,
Nitin Motgi (nmotgi)

[loquacious]

Andre Kostur wrote:

Or... it probably starting copying from j+1 onto i (and j+2 to i+1, etc)
until (again) it eventually walked off the end of the vector. Then by
happenstance it stopped before actually crashing your problem (or perhaps
a debug-mode version of the standard library that checked to make sure
that you don't iterate off the end of a container). In either case, it's
still Undefined Behaviour.

Implementation of erase(iterator::start, itertaor::end) first does a
copy from [iterator::end, vector::end()] in to vector starting at
iterator::start. So when iterator::end > iterator::start world is fine.
But when iterator::start > iterator::end then it would actuall copy
from iterator::start (which is greater than iterator::end till
vector::end() ) to vector::end() starting from iterator::end. Hence
instead of deleting it adds to the end first and then deletes from the
difference.

Below is one the implementation of vector::erase() which I thought
might be usefull in understanding the behaviour.

iterator __i(std::copy(__last, end(), __first));
std::_Destroy(__i, end());
this->_M_impl._M_finish = this->_M_impl._M_finish - \
(__last - __first);
return __first;

I am not sure as to why it was done this way but I think it's
developers responsibility to ensure that iterator::end >
iterator::start.

I did try out the example posted.
$ cat vec.cpp
#include <vector>
#include <iostream>

int main(int argc, char** argv) {
std::vector<int> x(10);
std::vector<int>::iterator i=x.begin()+2, j=x.begin()+6;

std::cout << "Size of vector " << x.size() << std::endl;
x.erase(i,j);
std::cout << "Size of vector " << x.size() << std::endl;
x.erase(j,i);
std::cout << "Size of vector " << x.size() << std::endl;
return 0;
}
$ ./a.out
Size of vector 10 [ Before deletion ]
Size of vector 6 [ After deletion ]
Size of vector 10 [ Adds 8 and then deletes 4 ]
$

Thank you,
Nitin Motgi (nmotgi)

[Amadeus W. M.]

On Thu, 26 Jan 2006 20:54:38 -0500, Amadeus W. M. wrote:

I have a vector from which I want to erase elements between iterators i,j.
If i<j, everything works as expected, but if j>i, an insertion is actually
performed. Example:

vector<double> x(10);
vector<double>::iterator i=x.begin()+2, j=x.begin()+6;

x.erase(i,j); // i<j, ok, erases 4 elements.
x.erase(j,i); // j>i, no error, just inserts 4 elements.

This happens with g++ 4.0.2. Is this standard behavior? Why does it work
this way?

After looking at the code, it's no wonder that the result looks like an
insertion. In fact, I only tried on a vector with all elements the same.
On a random vector it won't look like an insertion.

I just wanted to know whether or not it was standard. It would have been
nice to throw an exception or something. Here is the code:

template<typename _Tp, typename _Alloc>
typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::
erase(iterator __first, iterator __last)
{
iterator __i(std::copy(__last, end(), __first));
std::_Destroy(__i, end(), this->get_allocator());
this->_M_impl._M_finish = this->_M_impl._M_finish - (__last - __first);
return __first;
}

Very informative this open source thing!

[P.J. Plauger]

"Amadeus W. M." <am*******@cablespeed.com> wrote in message
news:pa****************************@cablespeed.com ...

On Thu, 26 Jan 2006 20:54:38 -0500, Amadeus W. M. wrote:

I have a vector from which I want to erase elements between iterators
i,j.
If i<j, everything works as expected, but if j>i, an insertion is
actually
performed. Example:

vector<double> x(10);
vector<double>::iterator i=x.begin()+2, j=x.begin()+6;

x.erase(i,j); // i<j, ok, erases 4 elements.
x.erase(j,i); // j>i, no error, just inserts 4 elements.

This happens with g++ 4.0.2. Is this standard behavior? Why does it work
this way?

After looking at the code, it's no wonder that the result looks like an
insertion. In fact, I only tried on a vector with all elements the same.
On a random vector it won't look like an insertion.

I just wanted to know whether or not it was standard. It would have been
nice to throw an exception or something. Here is the code:

template<typename _Tp, typename _Alloc>
typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::
erase(iterator __first, iterator __last)
{
iterator __i(std::copy(__last, end(), __first));
std::_Destroy(__i, end(), this->get_allocator());
this->_M_impl._M_finish = this->_M_impl._M_finish - (__last -
__first);
return __first;
}

Very informative this open source thing!

Yeah, one of the benefits of template libraries is that they pretty
much have to show all their code in publicly readable headers.
(Export templates haven't quite caught on yet, if they every will.)
So if by "open source" you mean code that you can see, then *all*
implementations of the Standard C++ library are pretty open, at
least the STL part.

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

[Stefan Näwe]

P.J. Plauger schrieb:

Very informative this open source thing!

Yeah, one of the benefits of template libraries is that they pretty
much have to show all their code in publicly readable headers.
(Export templates haven't quite caught on yet, if they every will.)
So if by "open source" you mean code that you can see, then *all*
implementations of the Standard C++ library are pretty open, at
least the STL part.

RMS would love this!
This shows exactly the difference between "Open Source" and "Free As in Speech" software.

/S
--
Stefan Naewe
naewe.s_AT_atlas_DOT_de

[Pete Becker]

loquacious wrote:

Below is one the implementation of vector::erase() which I thought
might be usefull in understanding the behaviour.

To what end? The behavior is undefined, so whatever some implementation
does is simply what that implementation does. If you want to rely on
that behavior, so be it. But that's dangerous here, because conceptually
what's being done doesn't make sense, since the range to be erased isn't
a valid range.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)