How to iterate on unordered pairs inside an unordered_set?

Question

What's a concise way to iterate on unordered-pairs of elements in unordered_set?

(So order doesn't matter and elements should be different)

e.g. {1, 2, 3} => (1, 2) (2, 3) (1, 3)

My initial attempts were something like

for (i = 0; i < size - 1; i++) {
  for (j = i + 1; j < size; j++) {
    ...
  }
}

But that's not super-convenient with iterators.

Obit

@arainone Possible case of 'I didn't read the question'. – Lamonica

So for some set X you want {(x1,x2) | x1,x2 ∈ X, x1 ≠ x2}? Did I read that right? – Moderato

Should the overlap([0,1],[1,2][2,3]...) or do you want [0,1],[2,3][4,5]...? – Lucilelucilia

@Lucilelucilia Seems overlap is desired. – Stow

So you want all combinations of size 2 of the std::unordered_set? – Stow

Answer 1

This should work, given an std::unordered_set s:

auto set_end = s.end();
for (auto ai = s.begin(); ai != set_end; ++ai) {
    for (auto bi = std::next(ai); bi != set_end; ++bi) {
        // *ai, *bi
    }
}

This is basically the iterator equivalent of the following in integers:

for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
        // i, j
    }
}

Lamonica

I would suggest std::for_each over an old-fashioned for loop. – Proof

@Proof std::for_each does not give iterators, and the inner loop depends on the iterator of the outer loop. – Lamonica

Just as a matter of curiosity, is there a reason you used set_end instead of s.end() in the loops? – Stow

@caps, there is nothing old-fashoned with for loop. In fact, it is for_each which is old fashined! – Tray

@Stow Efficiency, end() may or may not be repeatedly computed depending on your compiler. – Lamonica

@Stow Your edit is unnecessary, less performant, and possibly incorrect depending on overloading/type. To see why, mentally do the integer version :) – Lamonica

@Tray std::for_each implicitly does the set_end capture optimization that orlp implemented, and it does it more cleanly. However, orlp is correct about the iterators not being passed through, so he could only do std::for_each on the inner loop. – Proof

@caps, it is moot to compare iterator-aware loop (which uses iterators like in provided example) with for_each, since for_each doesn't allow iterator access. However, range based for loop is much better than for_each. – Tray

@Tray Yes. :) Range-based for is marginally better than std::for_each. It is almost the same thing. However, you can't use range-based for in this case without building a custom range. You could do conveniently with boost::make_range or somesuch, but it's the same (or less) boilerplate to just use std::for_each. – Proof

just for my curiosity could we early-stop the first loop one before the end? how would one do that? – Obit

@Obit We can't because std::set iterators are ForwardIterators, which can not be decremented. – Lamonica

Answer 2

Here is orlp's solution in semi-generic form.

template<typename ForwardIterator, typename DestItr>
auto cartesian_product(ForwardIterator b, ForwardIterator e, DestItr d) -> DestItr {
    using std::next;
    using std::for_each;
    for (; b != e; ++b) {
        for_each(next(b), e, [&](auto right){
            *d++ = std::make_tuple(*b, right);
        });
    }
    return d;
}

template<typename ForwardRange, typename DestItr>
auto cartesian_product(ForwardRange r, DestItr d) -> DestItr {
    using std::begin;
    using std::end;
    return cartesian_product(begin(r), end(r), d);
}

Live on Coliru.

You could, of course, make it more generic by having overloads for custom functors to use instead of make_tuple and the assignment operator. The standard library algorithms tend to do so. Were I writing this for a library, I'd probably do so as well.

Proof

Don't name this cartesian_product, because this is definitely not the cartesian product. It's the 2-combinations of a set with itself. – Lamonica

Hmm. Something like... self_combination? self_permutations_combination? – Proof