Pregunta Forma preferida / idiomática para insertar en un mapa


He identificado cuatro formas diferentes de insertar 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 manera en la que no he pensado?)


74
2017-11-26 15:48


origen


Respuestas:


Ante todo, operator[] y insert las funciones miembro no son funcionalmente equivalentes:

  • los operator[] será buscar para la clave, inserte un construido por defecto valor si no se encuentra, y devolver una referencia a la que le asigna un valor. Obviamente, esto puede ser ineficiente si mapped_type puede beneficiarse de ser inicializado directamente en lugar de predeterminado construido y asignado. Este método también hace que sea imposible determinar si realmente se ha realizado una inserción o si solo se sobrescribió el valor de una clave previamente insertada.
  • los insert función de miembro no tendrá efecto si la clave ya está presente en el mapa y, aunque a menudo se olvida, devuelve un 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, los tres son casi equivalente. Como recordatorio, veamos insert firma en el estándar:

typedef pair<const Key, T> value_type;

  /* ... */

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

Entonces, ¿cómo son las tres llamadas diferentes?

  • std::make_pair se basa en la deducción del argumento de la plantilla y podría (y en este caso será) producir algo de un tipo diferente al real value_type del mapa, que requerirá una llamada adicional a std::pair constructor de plantilla para convertir a value_type (es decir, agregar const a first_type)
  • std::pair<int, int> también requerirá una llamada adicional al constructor de plantilla de std::pair para convertir el parámetro a value_type (es decir, agregar const a first_type)
  • std::map<int, int>::value_type deja absolutamente ningún lugar para la duda, ya que es directamente el tipo de parámetro esperado por el insert funció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 por defecto y asignar el mapped_type, y que no me importa determinar si una nueva clave se ha insertado efectivamente. Cuando usas insert, construyendo un value_type es probablemente el camino a seguir.


67
2017-11-26 16:19



A partir de C ++ 11, tienes dos opciones adicionales principales. Primero, puedes usar insert() con lista de sintaxis de inicialización:

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 otras respuestas han notado, esto tiene varias ventajas sobre las otras formas:

  • los operator[] el enfoque requiere que el tipo mapeado sea asignable, lo que no siempre es el caso.
  • los operator[] el enfoque puede sobrescribir los elementos existentes y no le permite saber si esto sucedió.
  • Las otras formas de insert que la lista implica 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 se puedan copiar, por lo que no funcionaría, por ejemplo, un mapa con unique_ptr valores. Eso se ha corregido en el estándar, pero es posible que la corrección no haya llegado a su implementación de biblioteca estándar.

Segundo, puedes usar el emplace() método:

function.emplace(0, 42);

Esto es más conciso que cualquiera de las formas de insert(), funciona bien con tipos solo de 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 a sus lectores un poco, ya que emplace los métodos generalmente no se usan de esa manera.


73
2017-11-13 00:21



La primera versión:

function[0] = 42; // version 1

puede o no insertar el valor 42 en el mapa. Si la clave 0 existe, luego asignará 42 a esa clave, sobrescribiendo el valor que esa clave tenga. 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 llave 0 ya 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_type es el typedef para std::pair<const int, int>y std::make_pair() obviamente produce un std::pair<> a través de la magia de deducción de la plantilla. El resultado final, sin embargo, debería ser el mismo para las versiones 2, 3 y 4.

¿Cuál usaría? Personalmente prefiero la versión 1; es conciso y "natural". Por supuesto, si su comportamiento de sobreescritura no es deseado, entonces preferiría la versión 4, ya que requiere menos tipeo que las versiones 2 y 3. No sé si hay una sola de facto forma 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());

7
2017-11-26 15:53



He estado haciendo algunas 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 pequeñas.

#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 inserción se pueden descuidar (¡aunque no se realizó una prueba de hipótesis)!

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


3
2018-01-13 15:43



Si desea sobrescribir el elemento con la clave 0

function[0] = 42;

De otra manera:

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

1
2017-11-26 15:53



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

Para simplificar, inserte use boost :: assign library, 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 );

1
2017-11-26 18:32



En breve, [] el operador es más eficiente para actualizar valores porque implica invocar el 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 STL efectivo: 50 formas específicas de mejorar el uso de la biblioteca de plantillas estándar por Scott Meyers, el 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 libre de programación genérica de esto, y el punto es que creo que este paradigma (diferenciando 'agregar' y 'actualizar') es extremadamente útil.


1
2018-03-02 18:58



Solo cambio el problema un poco (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!


0
2018-05-28 11:13