Sequence not ordered

[tonyg362]

I'm trying to set a vector equal to the intersection of itself and another vector, iteratively. So I have something like:

vector<int> set1;
vector<int> set2;

vector<int>::inter_it;

//initialize set1;

for(;;;){
  sort(set1.begin(), set1.end());

  //call function to find some new values for set2
  sort(set2.begin(), set2.end());

  if(!set2.empty()){

    inter_it = set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), set1.begin());

    set1.erase((inter_it + 1), set1.end());
    set2.clear();
  }
}

I get a sequence not ordered error with VS 2008. My question is this, are there some restrictions to using set intersection? Do the sets have to be the same size? Can I not set the last parameter as the beginning set1? i.e. set1.begin()? It compiles fine with g++, but my program output is incorrect and I suspect this may be causing the bug.

[moorecm]

Iteratively?

[tonyg362]

Note the for loop.

[moorecm]

Line 18 erases any remaining elements beyond the intersection (also note that vector::erase invalidates all iterators past the first argument). Line 19 clears set2. What is the next iteration expected to do?

For reference:
http://www.cplusplus.com/reference/algorithm/set_intersection/

EDIT: The set_intersection algorithm returns an iterator past the end of the intersection that begins where specified (set1.begin(), in this case), not a copy of the intersection. See the example in the link above. Typo on line 4?

[tonyg362]

I get rid of the entries beyond the set intersection so they will not remain during the next iterations. I call a function which will place new values into set2, that's what I meant by the comment on line 11. Basically I start with set1 containing all possible values set2 can take, and I want only the values that set2 contains during each iteration to remain when the loop is finished. It's possible for set1 to be empty in the end, which would mean set2 never contained a certain value for every iteration. For example if my universe is {1 2 3}, and I did two iterations and set2 = {1 2} during loop 1, and set2 = {1 3} during loop 2, I would want my output to be set1 = {1}.

[moorecm]

A few typos aside, your code (manually unwrapped rather than the infinite loop) using the test data mentioned above worked as expected on my machine.

Here's what I used:

#include <vector>
#include <iostream>
#include <iterator>
using namespace std;

int main( int argc, char ** argv )
{
    vector<int> set1;
    vector<int> set2;

    vector<int>::iterator inter_it;

    //initialize set1;
    set1.push_back( 2 );
    set1.push_back( 3 );
    set1.push_back( 1 );

// 1st iteration

    sort(set1.begin(), set1.end());

    //find some new values for set2
    set2.push_back( 3 );
    set2.push_back( 1 );
    sort(set2.begin(), set2.end());

    if(!set2.empty()){

        inter_it = set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), set1.begin());

        set1.erase((inter_it + 1), set1.end());
        set2.clear();
    }

// 2nd iteration

    sort(set1.begin(), set1.end());

    //find some new values for set2
    set2.push_back( 1 );
    set2.push_back( 2 );
    sort(set2.begin(), set2.end());

    if(!set2.empty()){

        inter_it = set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), set1.begin());

        set1.erase((inter_it + 1), set1.end());
        set2.clear();
    }

// output result

    copy( set1.begin(), inter_it, ostream_iterator<int>( cout, " " ) );

    return 0;
}

> make
g++ -c -o test.o test.C
g++ -o test test.o
> ./test
1
> g++ --version
g++ (GCC) 3.2.3 20030502 (Red Hat Linux 3.2.3-52)
Copyright (C) 2002 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.