Geek Answers Handbook

How to iterate over unordered pairs inside unordered_set?

What is the short way to iterate over unordered pairs of elements in an unordered_set ?

(Thus, the order does not matter, and the elements must be different)

eg. {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 this is not very convenient with iterators.

+6
source share
2 answers

This should work, given 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 an iterator, equivalent to the following in integers:

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

Here is the solution to the eagles in a semi-tribal 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 universal if you use overloads for custom functors instead of make_tuple and the assignment operator. Standard library algorithms tend to do this. If I wrote this for the library, I would do it too.

+1
source

More articles:


All Articles