How to get unique pairs of values from a stl set

Question

I have a stl set of integers and I would like to iterate through all unique pairs of integer values, where by uniqueness I consider val1,val2 and val2,val1 to be the same and I should only see that combination once.

I have written this in python where I use the index of a list (clusters):

for i in range(len(clusters) - 1):
    for j in range(i+1,len(clusters)):
       #Do something with clusters[i],clusters[j])

but without an index I am not sure how I can achieve the same thing with a stl set and iterators. I tried out:

for (set<int>::iterator itr = myset.begin(); itr != myset.end()-1; ++itr) {
    cout << *itr;
}

but this fails as an iterator doesn't have a - operator.

How can I achieve this, or must I use a different container?

Answer 1

You don't need to do end() - 1 since end() is an iterator that points after the last element in the container.

The corrected code is:

for (set<int>::iterator itr = myset.begin(); itr != myset.end(); ++itr) {
    for (set<int>::iterator itr2 = itr + 1; itr2 != myset.end(); ++itr2) {
        // Do whatever you want with itr and itr2
    }
}

Answer 2

How about something along the following lines:

for(set<int>::const_iterator iter1 = myset.begin(); iter1 != myset.end(); ++iter1) {
    for(set<int>::const_iterator iter2 = iter1; ++iter2 != myset.end();) {
    {
        std::cout << *iter1 << " " << *iter2 << "\n"; 
    }
}

This yields all N*(N-1)/2 unique pairs, where N is the number of integers in your set.

As an aside: use a const_iterator whenever you iterate over a container without modifying anything, it's good style and might have better performance.

EDIT: Modified the code to reflect the suggestion made by Steve Jessop.

Answer 3

Put your data in a boost::bimap, then iterate it both ways, copying the results into a standard STL map which will enforce uniqueness.