Come eseguire iterazioni su coppie non ordinate all'interno di un set non ordinato?

Question

Qual è un modo conciso per iterare su coppie di elementi non ordinati in unordered_set?

(Quindi ordine non ha importanza e gli elementi dovrebbe essere diverso)

esempio {1, 2, 3} => (1, 2) (2, 3) (1, 3)

I miei tentativi iniziali erano qualcosa di simile

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

Ma questo non è super-conveniente con iteratori.

Answer 1

Questo dovrebbe funzionare, dato un 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 
    } 
} 

Questo è fondamentalmente l'iteratore equivalente di quanto segue in numeri interi:

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

Answer 2

Ecco la soluzione di orlp in forma semi-generiche.

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.

Si potrebbe, ovviamente, renderlo più generico avendo sovraccarichi per funtori personalizzato da utilizzare al posto del make_tuple e l'operatore di assegnazione. Gli algoritmi di libreria standard tendono a farlo. Se scrivessi questo per una biblioteca, probabilmente lo farei anche io.