Unexpected behavior in STL "includes" algorithm

[Generic Usenet Account]

I am seeing some unexpected behavior while using the STL "includes"
algorithm. I am not sure if this is a bug with the template header
files in our STL distribution, or if this is how it should work.

For your benefit, let me first quote from the STL Standard Reference
(Stepanov & Lee):

template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1
last1,InputIterator2 first2, InputIterator2 last2);

template <class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, Compare comp);


includes returns true if every element in the range [first2, last2) is
contained in the range [first1, last1). It returns false otherwise.

At most ((last1 - first1) + (last2 - first2)) * 2 - 1 comparisons are
performed.




I have been able to reproduce my problem with a much more simplified
example. Here's my sample source code:

////////////////// SRC BEGIN /////////////////////////
#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

#define TRACE_STMT cout << "\nLine: " <<__LINE__ << endl;

int
main()
{
vector<int> v1;
vector<int> v2;

for(int i = 1; i < 7; i++)
v1.push_back(i);

TRACE_STMT
copy(v1.begin(), v1.end(), ostream_iterator<int> (cout, " "));

for(int i = 3; i < 6; i++)
v2.push_back(i);

vector<int>::iterator itor;

for(itor = v1.begin(); itor != v1.end(); itor++)
if(!includes(v2.begin(), v2.end(), itor, itor))
v1.erase(itor);

TRACE_STMT
copy(v1.begin(), v1.end(), ostream_iterator<int> (cout, " "));

return 0;
}
////////////////// SRC END /////////////////////////


I am expecting elements 3, 4 & 5 to be erased from vector v1, but that
is not happening. The only thing "wierd" about this example is that
"first2" and "last2" have the same value here. However, the STL
Reference Manual does not mention that "first2" and "last2" have to be
distinct.

Any pointers will be appreciated....


Thanks,
Gus

 

[Valentin Samko]

int
main()
{
vector<int> v1;
vector<int> v2;

for(int i = 1; i < 7; i++)
v1.push_back(i);

TRACE_STMT
copy(v1.begin(), v1.end(), ostream_iterator<int> (cout, " "));

for(int i = 3; i < 6; i++)
v2.push_back(i);

vector<int>::iterator itor;

for(itor = v1.begin(); itor != v1.end(); itor++)
if(!includes(v2.begin(), v2.end(), itor, itor))
v1.erase(itor);

Once you call std::vector erase member function, all the iterators may be invalidated.
I.e. you have UB here.

Also, the second range you pass to std::includes is empty, thus the result.

 

[usenet]

Once you call std::vector erase member function, all the iterators may be invalidated.
I.e. you have UB here.

Sets show the exact same bahavior. Are iterators invalidated upon
calling the erase member function for sets as well? (That may very
well be true, but that is not what Josuttis' book says)

Also, the second range you pass to std::includes is empty, thus the result.

Why would the range itor-itor be considered empty? (Not a challenge,
just a query)

Thanks,
Gus

 

[Jonathan Mcdougall]

I am seeing some unexpected behavior while using the STL "includes"
algorithm. I am not sure if this is a bug with the template header
files in our STL distribution, or if this is how it should work.

For your benefit, let me first quote from the STL Standard Reference
(Stepanov & Lee):

template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1
last1,InputIterator2 first2, InputIterator2 last2);

template <class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, Compare comp);


includes returns true if every element in the range [first2, last2) is
contained in the range [first1, last1). It returns false otherwise.

At most ((last1 - first1) + (last2 - first2)) * 2 - 1 comparisons are
performed.




I have been able to reproduce my problem with a much more simplified
example. Here's my sample source code:

////////////////// SRC BEGIN /////////////////////////
#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

#define TRACE_STMT cout << "\nLine: " <<__LINE__ << endl;

int
main()
{
vector<int> v1;
vector<int> v2;

for(int i = 1; i < 7; i++)
v1.push_back(i);

TRACE_STMT
copy(v1.begin(), v1.end(), ostream_iterator<int> (cout, " "));

for(int i = 3; i < 6; i++)
v2.push_back(i);

vector<int>::iterator itor;

for(itor = v1.begin(); itor != v1.end(); itor++)
if(!includes(v2.begin(), v2.end(), itor, itor))

Watch out, includes works with ranges and ranges in the C++ standard
library are open-ended. That means it does not include the last element
of the range. If both the begin and end positions are the same, the
range is empty.

This is useful. If a collection is empty, begin() == end(). You can
iterate from begin(), while itor != end(). Just imagine if end()
returned something else.

v1.erase(itor);

itor is invalidated by erase. Do

for(itor = v1.begin(); itor != v1.end(); /*nothing here*/ )
{
if(!includes(v2.begin(), v2.end(), itor, itor+1))
{
v1.erase(itor++);
}
else
{
++itor;
}
}

TRACE_STMT
copy(v1.begin(), v1.end(), ostream_iterator<int> (cout, " "));

return 0;
}

Jonathan

 

[=?iso-8859-1?Q?Ali_=C7ehreli?=]

More specifically, "Invalidates all the iterators and references after the
point of the erase." (23.2.4.2/3). Any operation that may resize the vector
invalides all the iterators though...

Sets show the exact same bahavior. Are iterators invalidated upon
calling the erase member function for sets as well? (That may very
well be true, but that is not what Josuttis' book says)

No, erasing an element of an associative container (e.g. set) and also
std::list; invalidates only the iterator(s) pointing the erased element(s).
(23.1.2/8)

Why would the range itor-itor be considered empty?

That's how the ranges work. The second iterator is "one past the end" of the
range; i.e. it's out of the range.

Think about passing such a range to a linear algorithm:

template <class Iter>
void my_algorithm(Iter begin, Iter end)
{
for ( ; begin != end; ++begin)
{
/* ... */
}
}

Ali