ejemplo - string map c++

std:: map insert() hint location: diferencia entre c++ 98 y c++ 11

Question

En la entrada de cplusplus en map :: insert () leí acerca de la ubicación que se podría agregar como una sugerencia para la función de que la función "optimiza su tiempo de inserción si la position apunta al elemento que precederá al elemento insertado" para c ++ 98, mientras que para c ++ 11 la optimización se produce "si la position apunta al elemento que seguirá al elemento insertado (o al final, si fuera el último)".

¿Significa esto que el rendimiento de los fragmentos de código de la siguiente forma (que abundan en el código heredado en el que estoy trabajando y modelado después del "Efectivo STL" de Scott Meyer , artículo 24) se vio afectado al cambiar a C ++? ¿Compilador 11 compatible?

auto pLoc = someMap.lower_bound(someKey);
if(pLoc != someMap.end() && !(someMap.key_comp()(someKey, pLoc->first)))
    return pLoc->second;
else
    auto newValue = expensiveCalculation();
    someMap.insert(pLoc, make_pair(someKey, newValue));  // using the lower bound as hint
    return newValue;

¿Cuál sería la mejor manera de mejorar este patrón para usarlo con C ++ 11?

Answer 1

Estoy pensando que la inserción correcta de la sugerencia de estilo C ++ 11 podría ser la siguiente:

iterator it = table.upper_bound(key);   //upper_bound returns an iterator pointing to the first element that is greater than key
if (it == table.begin() || (--it)->first < key) {
    // key not found path
    table.insert(it, make_pair(key, value));
}
else {
    // key found path
    it->second = value;
}

Answer 2

La especificación C ++ 98 es un defecto en el estándar. Vea la discusión en el número 233 y N1780 .

Recuerde que lower_bound devuelve un iterador al primer elemento con una clave no inferior a la clave especificada, mientras que upper_bound devuelve un iterador al primer elemento con una clave mayor que la clave especificada. Si no hay una clave equivalente a la clave especificada en el contenedor, lower_bound y upper_bound devuelven lo mismo, un iterador al elemento que estaría después de la clave si estuviera en el mapa.

Entonces, en otras palabras, su código actual ya funciona correctamente bajo la especificación de C ++ 11, y de hecho sería incorrecto bajo la especificación defectuosa de C ++ 98.

Answer 3

Sí, afectará la complejidad. Dar la sugerencia correcta hará que insert() tenga una complejidad constante amortizada, mientras que dar una sugerencia incorrecta obligará al mapa a buscar la posición desde el principio, dando complejidad logarítmica. Básicamente, una buena sugerencia hace que la inserción se realice en un tiempo constante, sin importar qué tan grande sea su mapa; con un mal indicio, la inserción será más lenta en los mapas más grandes.

La solución es, aparentemente, buscar la sugerencia con upper_bound lugar de lower_bound .

Answer 4

una instantánea de la función lambda de trabajo para su referencia.

    auto create_or_get_iter = [this] (const K& key) {

        auto it_upper = m_map.upper_bound(key);
        auto it_effective = it_upper == m_map.begin() ? it_upper : std::prev(it_upper);
        auto init_val = it_effective->second;

        if (it_effective == m_map.begin() || it_effective->first < key) {
            return m_map.insert(it_effective, std::make_pair(key, init_val));
        } else {
            it_effective->second = init_val;
            return it_effective;
        }

    };