STL sets... weird and unresolving...

[labheshr]

Hi Guys:

I am trying to solve a larger problem a part of which is using 2 sets.

lets get down to the code:

set<long> LongSet;

LongSet A, B;

LongSet::iterator it1,it2;

set A is a superset of set B. I have to find numbers in set A which are not present in set B and call a function (lets say func1() )for them.

i tried 2 ways to do this:

1. Using idea that elements in set are sorted by < order.

for(it1=A.find(*B.begin( ) ) , it2=B.begin( ); it1!=A.end( ); ++it1) //As A is superset of B, find the beginning element of set B in set A, iterate from that to end of set A. Note: Set A and Set B have same end element values...

{
if(*it1==*it2) //if element in set A = element in set B , increment it2 -iterator for set B.
it2++;

else{ func1 (*it1); } //otherwise if there is an element missing in Set B , it2> it1 and we need to call the func1 for missing element in set B, to which it1 is pointing to in set A.

} // for...

2. Using find method defined for sets...

for(it1=A.find(*B.begin( ));it1 !=A.end( ); ++it1)

{
if(B.find(*it1) == B.end( ) //for element in Set A, search for it in Set B, if not present call func1 for it pointing to that element...
func1(it1);
}//for....

Problems:

method 1: it gives me missing values upto certain extent and then starts to give wrong missing values i.e values that are not missing are also reported by it.

with method 2: it gives me only some missing values, not all....

Both the sets will have large number of elements say between 100-900 values each. Also no duplicates are present - set does'nt allow them either!

Any help regarding this wud be greatly appreciated. If you think there is a syntax error- do mention it , ive tried my best to code it as accurately as possible -

Thanks in advace!

-Labhesh.

[Paul McKenzie]

Hi Guys:

I am trying to solve a larger problem a part of which is using 2 sets.

lets get down to the code:

set<long> LongSet;

LongSet A, B;

LongSet::iterator it1,it2;

set A is a superset of set B. I have to find numbers in set A which are not present in set B and call a function (lets say func1() )for them.

Drop your current code and use the set_difference() algorithm.

Here is a simple example:

#include <set>
#include <algorithm>
#include <iterator>
#include <iostream>

using namespace std;

int main()
{
    set<long> Set1;
    set<long> Set2;

    Set1.insert(1);
    Set1.insert(2);
    Set1.insert(3);
    Set1.insert(4);
    Set1.insert(5);

    Set2.insert(1);
    Set2.insert(3);
    Set2.insert(5);

    std::set<long> output;
    set_difference(Set1.begin(), Set1.end(), Set2.begin(), Set2.end(), 
        inserter(output, output.begin()));

    cout << "The number of elements in set1 not in set2: " 
         << output.size() << "\n";

    cout << "The elements in set1 that are not in set 2 are:\n";
    std::set<long>::iterator it = output.begin();
    while (it != output.end())
    {
        cout << (*it) << "\n";
        ++it;
    }
}

Output:
The number of elements in set1 not in set2: 2
The elements in set1 that are not in set 2 are:
2
4

The set_difference finds elements in the first range not in the second range. The last argument is an iterator pointing to those items that are not in the second range.

I used the inserter adapter to populate another set with the results of the set_difference.

Regards,

Paul McKenzie

[labheshr]

Thanks a lot Paul ! Looks like this algorithm was god sent for me! Now I can call func1 for all elements in output set. Thanks again!

Cheers!
Labhesh

P.S: Just for curosity, could someone tell me wat is wrong in the approach I was following? Does it have something to do with how sets are represented in memory (i know as B-trees)?

[Paul McKenzie]

Thanks a lot Paul ! Looks like this algorithm was god sent for me! Now I can call func1 for all elements in output set. Thanks again!

No problem.

P.S: Just for curosity, could someone tell me wat is wrong in the approach I was following? Does it have something to do with how sets are represented in memory (i know as B-trees)?

The second approach has a for loop that looks overly complex. It could have just been this:

std::set<long>::iterator itA;
std::set<long>::iterator itB;

for(itA = A.begin(); itA != A.end(); ++itA)
{
    itB = B.find(*itA);
    if ( itB == B.end() )
       func(*itA);
}

Regards,

Paul McKenzie

[labheshr]

Well, thats done on purpose. This is because Set A is superset of Set B and i need to first find the begin element of set B in set A and then start looking for missing elements in Set B.

Example:

Set A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Set B = {3,4,7,9,10}

The output required is: 5, 6, 8 and NOT 1, 2, 5, 6, 8. This is because Set B "begins" from 3. However, both sets have same end elements - 10.

I think the set-difference mentioned before also lands me in same problem.

Also is there a way to "free" iterators like how we delete/free pointers in C++?

Thanks;
Labhesh.

[Paul McKenzie]

The output required is: 5, 6, 8 and NOT 1, 2, 5, 6, 8. This is because Set B "begins" from 3. However, both sets have same end elements - 10.

I think the set-difference mentioned before also lands me in same problem.

No. Look at the first and third parameters. You can start the search anywhere in either set. So in your case, you want to start at the element in set A that is greater than or equal to the first element in set B.

You can find the starting iterator of A by using lower_bound to set the starting position in A, given the first item in B:

#include <set>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    set<long> Set1;
    set<long> Set2;

    Set1.insert(1);
    Set1.insert(2);
    Set1.insert(3);
    Set1.insert(4);
    Set1.insert(5);

    Set2.insert(3);
    Set2.insert(5);
    
    std::set<long> output;
    set_difference(lower_bound(Set1.begin(), Set1.end(), *Set2.begin()), 
                   Set1.end(), Set2.begin(), Set2.end(), 
                   inserter(output, output.begin()));

    cout << "The number of elements in set1 not in set2: " 
         << output.size() << "\n";

    cout << "The elements in set1 that are not in set 2 are:\n";
    std::set<long>::iterator it = output.begin();
    while (it != output.end())
    {
        cout << (*it) << "\n";
        ++it;
    }
}

Output:
The number of elements in set1 not in set2: 1
The elements in set1 that are not in set 2 are:
4

Also is there a way to "free" iterators like how we delete/free pointers in C++?

I don't understand your question. Iterators are not allocated.

Regards,

Paul McKenzie