STL sets... weird and unresolving...

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.

Quote:

---

Originally Posted by 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.

---

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

Here is a simple example:

Code:

---

#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

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)?

Quote:

---

Originally Posted by 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!

---

No problem.

Quote:

---

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:

Code:

---

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

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.

Quote:

---

Originally Posted by labheshr

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:

Code:

---

#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

---

Quote:

---

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