449,173 Members | 1,079 Online
Need help? Post your question and get tips & solutions from a community of 449,173 IT Pros & Developers. It's quick & easy.

# Unexpected behavior in STL "includes" algorithm

 P: n/a 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 bool includes(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2); template 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 #include #include using namespace std; #define TRACE_STMT cout << "\nLine: " <<__LINE__ << endl; int main() { vector v1; vector v2; for(int i = 1; i < 7; i++) v1.push_back(i); TRACE_STMT copy(v1.begin(), v1.end(), ostream_iterator (cout, " ")); for(int i = 3; i < 6; i++) v2.push_back(i); vector::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 (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 Nov 2 '05 #1
4 Replies

 P: n/a Generic Usenet Account wrote: int main() { vector v1; vector v2; for(int i = 1; i < 7; i++) v1.push_back(i); TRACE_STMT copy(v1.begin(), v1.end(), ostream_iterator (cout, " ")); for(int i = 3; i < 6; i++) v2.push_back(i); vector::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. -- Valentin Samko - http://www.valentinsamko.com Nov 2 '05 #2

 P: n/a Valentin Samko wrote: 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 Nov 2 '05 #3

 P: n/a Generic Usenet Account wrote: 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 bool includes(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2); template 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 #include #include using namespace std; #define TRACE_STMT cout << "\nLine: " <<__LINE__ << endl; int main() { vector v1; vector v2; for(int i = 1; i < 7; i++) v1.push_back(i); TRACE_STMT copy(v1.begin(), v1.end(), ostream_iterator (cout, " ")); for(int i = 3; i < 6; i++) v2.push_back(i); vector::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 (cout, " ")); return 0; } Jonathan Nov 2 '05 #4

 P: n/a wrote in message news:11**********************@z14g2000cwz.googlegr oups.com... Valentin Samko wrote: Once you call std::vector erase member function, all the iterators may be invalidated. I.e. you have UB here. 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) Also, the second range you pass to std::includes is empty, thus the result. -- 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 void my_algorithm(Iter begin, Iter end) { for ( ; begin != end; ++begin) { /* ... */ } } Ali Nov 2 '05 #5

### This discussion thread is closed

Replies have been disabled for this discussion.