c++ - populares - hashtags instagram 2018

Simultáneamente iterando y modificando un conjunto desordenado?

Question

Considera el siguiente código:

unordered_set<T> S = ...;

for (const auto& x : S)
   if (...)
       S.insert(...);

Esto está roto, ¿correcto? Si insertamos algo en S, los iteradores pueden ser invalidados (debido a un refrito), lo que romperá el rango, porque bajo el capó está usando S.begin ... S.end.

¿Hay algún patrón para lidiar con esto?

Una forma es:

unordered_set<T> S = ...;

vector<T> S2;

for (const auto& x : S)
   if (...)
       S2.emplace_back(...);

for (auto& x : S2)
    S.insert(move(x));

Esto parece torpe. ¿Hay alguna forma mejor de que me esté perdiendo?

(Específicamente, si estuviera usando una tabla hash enrollada a mano y pudiera bloquearla para que no vuelva a lavarse hasta el final del ciclo, sería seguro usar la primera versión).

Actualizar:

De http://en.cppreference.com/w/cpp/container/unordered_map/insert

Si se produce un reinicio debido a la inserción, todos los iteradores se invalidan. De lo contrario los iteradores no se ven afectados. Las referencias no son invalidadas. El reaprovisionamiento solo se produce si la nueva cantidad de elementos es mayor que max_load_factor() * bucket_count() .

¿Podrías meterse con max_load_factor alguna manera para evitar el reajuste?

Answer 1

¿Podrías meterte con max_load_factor de alguna manera para evitar que vuelva a funcionar?

Sí, puede configurar el max_load_factor() a infinito para asegurarse de que no se produzca un nuevo lavado:

#include <iostream>
#include <limits>
#include <unordered_set>

int main()
{
    // initialize
    std::unordered_set<int> S;

    for (int i = 0; i < 8; ++i)
        S.insert(i);

    std::cout << "buckets: " << S.bucket_count() << std::endl;

    // infinite max load factor => never need to rehash
    const auto oldLoadFactor = S.max_load_factor();
    S.max_load_factor(std::numeric_limits<float>::infinity());

    for (const auto& x : S)
    {
        if (x > 2)
            S.insert(x * 2);
    }

    // restore load factor, verify same bucket count
    S.max_load_factor(oldLoadFactor);
    std::cout << "buckets: " << S.bucket_count() << std::endl;

    // now force rehash
    S.rehash(0);
    std::cout << "buckets: " << S.bucket_count() << std::endl;
}

Tenga en cuenta que simplemente establecer un nuevo factor de carga no se vuelve a realizar, por lo que son operaciones baratas.

El bit de rehash(0) funciona porque es una solicitud que: 1) Obtengo al menos n depósitos, y 2) Tengo suficientes max_load_factor() para satisfacer mi max_load_factor() . Simplemente usamos cero para indicar que no nos importa una cantidad mínima, solo queremos reabastecer para satisfacer nuestro factor "nuevo", como si nunca hubiera cambiado al infinito.

Por supuesto, esto no es a prueba de excepciones; Si algo se lanza entre las llamadas a max_load_factor() , nuestro factor anterior se pierde para siempre. Se arregla fácilmente con su utilidad de protección de alcance favorita o una clase de utilidad.

Tenga en cuenta que no obtendrá garantías si iterará sobre los nuevos elementos. Recorrerá los elementos existentes, pero podrá o no repetirse sobre los elementos nuevos. Si eso está bien (que según nuestro chat debería ser), entonces esto funcionará.

Por ejemplo, considere que itera sobre un conjunto no ordenado de entero y para cada entero par x , inserte x * 2 . Si los inserta siempre justo después de su posición actual (por casualidad de detalles de implementación y estado del contenedor), nunca terminará el ciclo, excepto a través de excepciones.

Si necesita algunas garantías, necesita una solución de almacenamiento alternativa.

Answer 2

La modificación de cualquier contenedor mientras está iterando sobre él tiende a volverse peluda, incluso si es una estructura más simple que un hash, o incluso si puede evitar que se vuelva a hash, re-balanceo o lo que sea.

Por cierto, incluso si funcionó, hay una ambigüedad: ¿deberían iterarse los miembros recién insertados o no? ¿Está bien incluirlos en esta iteración solo a veces (es decir, solo si terminan después del iterador actual)?

Si necesita hacer esto mucho, podría envolver el contenedor en un adaptador genérico que difiere todas las inserciones hasta el final, pero realmente está encontrando una manera de ocultar el código que ya tiene.

Answer 3

Me di cuenta de que conceptualmente es lo mismo que lo que propusiste, pero creo que se ve bastante bien:

std::vector<T> tmp;
std::copy_if(S.begin(), S.end(), std::back_inserter(tmp),
             [](T const& value) { return ...; });
S.insert(std::make_move_iterator(tmp.begin()),
         std::make_move_iterator(tmp.end()));