473,325 Members | 2,771 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,325 software developers and data experts.

Unexpected behavior in STL "includes" algorithm

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

Nov 2 '05 #1
4 1740
Generic Usenet Account wrote:
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.

--

Valentin Samko - http://www.valentinsamko.com
Nov 2 '05 #2
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
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 <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

Nov 2 '05 #4
<us****@sta.samsung.com> 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 <class Iter>
void my_algorithm(Iter begin, Iter end)
{
for ( ; begin != end; ++begin)
{
/* ... */
}
}

Ali

Nov 2 '05 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

25
by: Nitin Bhardwaj | last post by:
Well, i'm a relatively new into C( strictly speaking : well i'm a student and have been doing & studying C programming for the last 4 years).....and also a regular reader of "comp.lang.c" I...
175
by: Ken Brady | last post by:
I'm on a team building some class libraries to be used by many other projects. Some members of our team insist that "All public methods should be virtual" just in case "anything needs to be...
13
by: royaltiger | last post by:
I am trying to copy the inventory database in Building Access Applications by John L Viescas but when i try to run the database i get an error in the orders form when i click on the allocate...
28
by: Jess | last post by:
Hello, It is said that if I implement a "swap" member function, then it should never throw any exception. However, if I implement "swap" non- member function, then the restriction doesn't...
1
by: Tension | last post by:
Hi, I have written a development automation tool that needs to be distributed to 20-odd developers using Windows XP workstations. Is there a free Perl distribution that includes "Win32::OLE" by...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.