views:

48

answers:

3

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?

+1  A: 

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
    }
}
ereOn
Small mistakes: both numbers are necessary and `itr2` begins one number too early.
Matthieu M.
@Matthieu M.: Fixed, thanks.
ereOn
+5  A: 

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.

Greg S
Although the questioner doesn't say so in text, his code indicates that he doesn't want to see pairs in which the values are equal. So maybe replace `iter2 != myset.end(); ++iter2` with `++iter2 != myset.end();`
Steve Jessop
Apologies I misread what you said. I indeed don't want the same value
zenna
A: 

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

Peter Campion-Bye