Как перебирать неупорядоченные пары внутри unordered_set?

Question

Что такое краткий способ итерации по неупорядоченным парам элементов в unordered_set?

(Так порядок не имеет значения, и элементы должны быть различными)

например, {1, 2, 3} => (1, 2) (2, 3) (1, 3)

Мои первые попытки были чем-то вроде

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

Но это не супер-удобно с итераторы.

Answer 1

Это должно работать, дается std::unordered_sets:

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 
    } 
} 

В основном это итератор эквивалент следующих в целых числах:

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

Answer 2

Вот решение orlp в полу-родовой форме.

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.

Вы могли бы, конечно, сделать его более универсальным, имея перегрузки для пользовательских функторов использовать вместо make_tuple и оператора присваивания. Стандартные библиотечные алгоритмы имеют тенденцию делать это. Если бы я написал это для библиотеки, я бы, наверное, так поступил.