¿Cuál es la forma preferida / idiomática de insertar en un mapa?

He identificado cuatro formas diferentes de insertar elementos en un std::map:

std::map<int, int> function;

function[0] = 42;
function.insert(std::map<int, int>::value_type(0, 42));
function.insert(std::pair<int, int>(0, 42));
function.insert(std::make_pair(0, 42));

¿Cuál de esas es la forma preferida / idiomática? (¿Y hay otra forma en la que no he pensado?)

En primer lugar, operator[]y insertfunciones miembro no son funcionalmente equivalentes:

• El operator[]va a buscar la llave, inserte un defecto construida valor si no se encuentra, y devolver una referencia a la que se asigna un valor. Obviamente, esto puede ser ineficaz si mapped_typepuede beneficiarse de la inicialización directa en lugar de la construcción y asignación predeterminada. Este método también hace que sea imposible determinar si se ha realizado una inserción o si solo ha sobrescrito el valor de una clave insertada previamente
• La insertfunción miembro no tendrá ningún efecto si la clave ya está presente en el mapa y, aunque a menudo se olvida, devuelve una std::pair<iterator, bool>que puede ser de interés (sobre todo para determinar si la inserción se ha realizado realmente).

De todas las posibilidades enumeradas para llamar insert, las tres son casi equivalentes. Como recordatorio, echemos un vistazo a la insertfirma en el estándar:

typedef pair<const Key, T> value_type;

  /* ... */

pair<iterator, bool> insert(const value_type& x);

Entonces, ¿en qué se diferencian las tres llamadas?

• std::make_pairse basa en la deducción del argumento de la plantilla y podría (y en este caso lo hará ) producir algo de un tipo diferente al real value_typedel mapa, lo que requerirá una llamada adicional al std::pairconstructor de la plantilla para convertir a value_type(es decir: agregar consta first_type)
• std::pair<int, int>también requerirá una llamada adicional al constructor de la plantilla std::pairpara convertir el parámetro a value_type(es decir: agregar consta first_type)
• std::map<int, int>::value_typeNo deja lugar a dudas, ya que es directamente el tipo de parámetro esperado por la insertfunción miembro.

Al final, evitaría usar operator[]cuando el objetivo es insertar, a menos que no haya un costo adicional en la construcción y asignación predeterminada mapped_type, y que no me importe determinar si una nueva clave se insertó efectivamente. Cuando se usa insert, construir un value_typees probablemente el camino a seguir.

A partir de C ++ 11, tiene dos opciones adicionales importantes. Primero, puede usar insert()con la sintaxis de inicialización de lista:

function.insert({0, 42});

Esto es funcionalmente equivalente a

function.insert(std::map<int, int>::value_type(0, 42));

pero mucho más conciso y legible. Como han señalado otras respuestas, esto tiene varias ventajas sobre las otras formas:

• El operator[]enfoque requiere que el tipo mapeado sea asignable, lo que no siempre es el caso.
• El operator[]enfoque puede sobrescribir elementos existentes y no le da forma de saber si esto ha sucedido.
• Las otras formas insertque enumera implican una conversión de tipo implícita, lo que puede ralentizar su código.

El mayor inconveniente es que este formulario solía requerir que la clave y el valor fueran copiables, por lo que no funcionaría, por ejemplo, con un mapa con unique_ptrvalores. Eso se ha corregido en el estándar, pero es posible que aún no haya llegado a la implementación de su biblioteca estándar.

En segundo lugar, puede utilizar el emplace()método:

function.emplace(0, 42);

Esto es más conciso que cualquiera de las formas de insert(), funciona bien con tipos de solo movimiento como unique_ptr, y teóricamente puede ser un poco más eficiente (aunque un compilador decente debería optimizar la diferencia). El único gran inconveniente es que puede sorprender un poco a sus lectores, ya que los emplacemétodos no se suelen utilizar de esa forma.

La primera versión:

function[0] = 42; // version 1

puede o no puede insertar el valor 42 en el mapa. Si la clave 0existe, asignará 42 a esa clave, sobrescribiendo cualquier valor que tuviera esa clave. De lo contrario, inserta el par clave / valor.

Las funciones de inserción:

function.insert(std::map<int, int>::value_type(0, 42));  // version 2
function.insert(std::pair<int, int>(0, 42));             // version 3
function.insert(std::make_pair(0, 42));                  // version 4

por otro lado, no hagas nada si la clave 0ya existe en el mapa. Si la clave no existe, inserta el par clave / valor.

Las tres funciones de inserción son casi idénticas. std::map<int, int>::value_typees el typedefpara std::pair<const int, int>, y std::make_pair()obviamente produce una std::pair<>deducción mágica a través de la plantilla. Sin embargo, el resultado final debería ser el mismo para las versiones 2, 3 y 4.

¿Cuál usaría? Yo personalmente prefiero la versión 1; es conciso y "natural". Por supuesto, si no se desea su comportamiento de sobrescritura, preferiría la versión 4, ya que requiere menos escritura que las versiones 2 y 3. No sé si hay una única forma de facto de insertar pares clave / valor en un std::map.

Otra forma de insertar valores en un mapa a través de uno de sus constructores:

std::map<int, int> quadratic_func;

quadratic_func[0] = 0;
quadratic_func[1] = 1;
quadratic_func[2] = 4;
quadratic_func[3] = 9;

std::map<int, int> my_func(quadratic_func.begin(), quadratic_func.end());

Si desea sobrescribir el elemento con la tecla 0

function[0] = 42;

De otra manera:

function.insert(std::make_pair(0, 42));

Dado que C ++ 17 std::map ofrece dos nuevos métodos de inserción: insert_or_assign()y try_emplace(), como también se menciona en el comentario de sp2danny .

insert_or_assign()

Básicamente, insert_or_assign()es una versión "mejorada" de operator[]. A diferencia de operator[], insert_or_assign()no requiere que el tipo de valor del mapa sea construible por defecto. Por ejemplo, el siguiente código no se compila porque MyClassno tiene un constructor predeterminado:

class MyClass {
public:
    MyClass(int i) : m_i(i) {};
    int m_i;
};

int main() {
    std::map<int, MyClass> myMap;

    // VS2017: "C2512: 'MyClass::MyClass' : no appropriate default constructor available"
    // Coliru: "error: no matching function for call to 'MyClass::MyClass()"
    myMap[0] = MyClass(1);

    return 0;
}

Sin embargo, si reemplaza myMap[0] = MyClass(1);por la siguiente línea, entonces el código se compila y la inserción se realiza según lo previsto:

myMap.insert_or_assign(0, MyClass(1));

Además, al igual que insert(), insert_or_assign()devuelve a pair<iterator, bool>. El valor booleano es truesi se produjo una inserción y falsesi se realizó una asignación. El iterador apunta al elemento que se insertó o actualizó.

try_emplace()

Similar a lo anterior, try_emplace()es una "mejora" de emplace(). A diferencia de emplace(), try_emplace()no modifica sus argumentos si la inserción falla debido a una clave que ya existe en el mapa. Por ejemplo, el siguiente código intenta colocar un elemento con una clave que ya está almacenada en el mapa (ver *):

int main() {
    std::map<int, std::unique_ptr<MyClass>> myMap2;
    myMap2.emplace(0, std::make_unique<MyClass>(1));

    auto pMyObj = std::make_unique<MyClass>(2);    
    auto [it, b] = myMap2.emplace(0, std::move(pMyObj));  // *

    if (!b)
        std::cout << "pMyObj was not inserted" << std::endl;

    if (pMyObj == nullptr)
        std::cout << "pMyObj was modified anyway" << std::endl;
    else
        std::cout << "pMyObj.m_i = " << pMyObj->m_i <<  std::endl;

    return 0;
}

Salida (al menos para VS2017 y Coliru):

pMyObj no se insertó
pMyObj se modificó de todos modos

Como puede ver, pMyObjya no apunta al objeto original. Sin embargo, si lo reemplaza auto [it, b] = myMap2.emplace(0, std::move(pMyObj));por el siguiente código, la salida se verá diferente, porque pMyObjpermanece sin cambios:

auto [it, b] = myMap2.try_emplace(0, std::move(pMyObj));

Salida:

pMyObj no se insertó
pMyObj pMyObj.m_i = 2

Código en Coliru

Tenga en cuenta: traté de que mis explicaciones fueran lo más breves y simples posible para encajarlas en esta respuesta. Para una descripción más precisa y completa, recomiendo leer este artículo sobre Fluent C ++ .

He estado realizando comparaciones de tiempo entre las versiones mencionadas anteriormente:

function[0] = 42;
function.insert(std::map<int, int>::value_type(0, 42));
function.insert(std::pair<int, int>(0, 42));
function.insert(std::make_pair(0, 42));

Resulta que las diferencias de tiempo entre las versiones de inserción son mínimas.

#include <map>
#include <vector>
#include <boost/date_time/posix_time/posix_time.hpp>
using namespace boost::posix_time;
class Widget {
public:
    Widget() {
        m_vec.resize(100);
        for(unsigned long it = 0; it < 100;it++) {
            m_vec[it] = 1.0;
        }
    }
    Widget(double el)   {
        m_vec.resize(100);
        for(unsigned long it = 0; it < 100;it++) {
            m_vec[it] = el;
        }
    }
private:
    std::vector<double> m_vec;
};


int main(int argc, char* argv[]) {



    std::map<int,Widget> map_W;
    ptime t1 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W.insert(std::pair<int,Widget>(it,Widget(2.0)));
    }
    ptime t2 = boost::posix_time::microsec_clock::local_time();
    time_duration diff = t2 - t1;
    std::cout << diff.total_milliseconds() << std::endl;

    std::map<int,Widget> map_W_2;
    ptime t1_2 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W_2.insert(std::make_pair(it,Widget(2.0)));
    }
    ptime t2_2 = boost::posix_time::microsec_clock::local_time();
    time_duration diff_2 = t2_2 - t1_2;
    std::cout << diff_2.total_milliseconds() << std::endl;

    std::map<int,Widget> map_W_3;
    ptime t1_3 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W_3[it] = Widget(2.0);
    }
    ptime t2_3 = boost::posix_time::microsec_clock::local_time();
    time_duration diff_3 = t2_3 - t1_3;
    std::cout << diff_3.total_milliseconds() << std::endl;

    std::map<int,Widget> map_W_0;
    ptime t1_0 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W_0.insert(std::map<int,Widget>::value_type(it,Widget(2.0)));
    }
    ptime t2_0 = boost::posix_time::microsec_clock::local_time();
    time_duration diff_0 = t2_0 - t1_0;
    std::cout << diff_0.total_milliseconds() << std::endl;

    system("pause");
}

Esto da respectivamente para las versiones (ejecuté el archivo 3 veces, de ahí las 3 diferencias de tiempo consecutivas para cada una):

map_W.insert(std::pair<int,Widget>(it,Widget(2.0)));

2198 ms, 2078 ms, 2072 ms

map_W_2.insert(std::make_pair(it,Widget(2.0)));

2290 ms, 2037 ms, 2046 ms

 map_W_3[it] = Widget(2.0);

2592 ms, 2278 ms, 2296 ms

 map_W_0.insert(std::map<int,Widget>::value_type(it,Widget(2.0)));

2234 ms, 2031 ms, 2027 ms

Por lo tanto, los resultados entre diferentes versiones de insertos pueden ignorarse (aunque no realicé una prueba de hipótesis).

La map_W_3[it] = Widget(2.0);versión toma aproximadamente un 10-15% más de tiempo para este ejemplo debido a una inicialización con el constructor predeterminado para Widget.

En resumen, el []operador es más eficiente para actualizar valores porque implica llamar al constructor predeterminado del tipo de valor y luego asignarle un nuevo valor, mientras que insert()es más eficiente para agregar valores.

El fragmento citado de Effective STL: 50 formas específicas de mejorar el uso de la biblioteca de plantillas estándar de Scott Meyers, artículo 24, podría ayudar.

template<typename MapType, typename KeyArgType, typename ValueArgType>
typename MapType::iterator
insertKeyAndValue(MapType& m, const KeyArgType&k, const ValueArgType& v)
{
    typename MapType::iterator lb = m.lower_bound(k);

    if (lb != m.end() && !(m.key_comp()(k, lb->first))) {
        lb->second = v;
        return lb;
    } else {
        typedef typename MapType::value_type MVT;
        return m.insert(lb, MVT(k, v));
    }
}

Puede decidir elegir una versión genérica sin programación de esto, pero el punto es que encuentro este paradigma (diferenciando 'agregar' y 'actualizar') extremadamente útil.

Si desea insertar un elemento en std :: map, use la función insert (), y si desea encontrar el elemento (por clave) y asignarle algo, use el operador [].

Para simplificar la inserción, use la biblioteca boost :: assign, así:

using namespace boost::assign;

// For inserting one element:

insert( function )( 0, 41 );

// For inserting several elements:

insert( function )( 0, 41 )( 0, 42 )( 0, 43 );

Solo cambio un poco el problema (mapa de cadenas) para mostrar otro interés de inserción:

std::map<int, std::string> rancking;

rancking[0] = 42;  // << some compilers [gcc] show no error

rancking.insert(std::pair<int, std::string>(0, 42));// always a compile error

el hecho de que el compilador no muestra ningún error en "rancking [1] = 42;" puede tener un impacto devastador!