¿Cuál es una forma concisa de iterar sobre pares de elementos desordenados en unordered_set?

(Entonces el orden no importa y los elementos deben ser diferentes)

p.ej. {1, 2, 3} => (1, 2) (2, 3) (1, 3)

Mis intentos iniciales fueron algo como

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

Pero eso no es muy conveniente con los iteradores.

6
Uri 25 ene. 2016 a las 20:55

2 respuestas

La mejor respuesta

Esto debería funcionar, dado un 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
    }
}

Este es básicamente el iterador equivalente de lo siguiente en números enteros:

for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
        // i, j
    }
}
7
orlp 25 ene. 2016 a las 18:16

Aquí está la solución de orlp en forma semi-genérica.

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

Vive en Coliru.

Por supuesto, podría hacerlo más genérico al tener sobrecargas para que los functores personalizados usen en lugar de make_tuple y el operador de asignación. Los algoritmos de biblioteca estándar tienden a hacerlo. Si estuviera escribiendo esto para una biblioteca, probablemente también lo haría.

1
caps 25 ene. 2016 a las 19:05