how - recorrer map c++

Qué sucedió cuando call std:: map''s operator[] o insert

Question

Tengo el siguiente código:

#include <functional>   // std::less
#include <map>
#include <iostream>
using namespace std;

class Key
{
public:
        Key() {cout << "Key Constructor" << endl;}
        ~Key() {cout << "Key Destructor" << endl;}
        Key(const Key& key) {cout << "Key Copy Constructor" << endl;}

        bool operator < (const Key& k1) {return true;}
};
int main()
{
        map<Key, int> mymap;
        Key k;

        cout << "operator[]"<<endl;
        mymap[k] = 1;

        map<Key, int> mymap2;
        cout << "insert"<<endl;
        mymap2.insert(std::make_pair(k, 1));
        cout << "=========" << endl;

}

Y la salida es:

$ g++ test.cpp -fpermissive
$ ./a.out
Key Constructor
operator[]
Key Copy Constructor
Key Copy Constructor
Key Destructor
insert
Key Copy Constructor
Key Copy Constructor
Key Copy Constructor
Key Copy Constructor
Key Destructor
Key Destructor
Key Destructor
=========
Key Destructor
Key Destructor
Key Destructor

¿Podría alguien explicar por qué mymap [k] = 1; invocar 2 copy constructor y mymap2.insert (std :: make_pair (k, 1)); invoca el constructor de 4 copias? y ¿eso significa que el operador [] es mucho más eficiente que insertar?

Gracias.

Resumen:

Gracias al usuario 6502 y petersohn por su visión, ahora supongo que la razón del constructor de 2 copias adicionales para insertar es la siguiente:

• make_pair es una función, primero hace una copia dentro de la función y luego devuelve la copia, que es una copia adicional
• make_pair (k, 1) creará un pair<Key, int> , pero el value_type requerido es pair<const& Key, int> , la conversión de tipo causará otra copia adicional

Entonces en el caso 2, si uso:

mymap2.insert(std::pair<const Key, int>(k, 1));

El número de constructores de copia que se llamará será el mismo que el del operador []

Como notó 6502, el siguiente reclamo ha sido cambiado, por lo tanto, ya no es verdad:

Una llamada a esta función (operador []) es equivalente a: (* ((this-> insert (make_pair (x, mapped_type ()))) first)). Second

operator [] se implementa de forma diferente para evitar una copia adicional introducida por make_pair ()

Answer 1

El problema con la inserción es que make_pair creará un par del tipo incorrecto, por lo que el objeto pasado necesitará una conversión a un tipo de par adecuado para pasarlo a insert .

En realidad, en una versión anterior, el map::operator[] obligatorio de C ++ map::operator[] comporta como insert (lo que obliga a una implementación ineficiente). Más tarde, el texto se relajó permitiendo una mejor implementación.

Tenga en cuenta que, de todos modos, para los contenedores estándar, los elementos se consideran "valores", es decir, la implementación es libre de copiar cosas y no se garantiza el número de copias que se realizarán.

Puede ver el problema make_pair cambiando el código a

    mymap2.insert(std::pair<const Key, int>(k, 1));

Explicación más larga

El problema es que make_pair creará un valor std::pair<Key, int> pero insert signature quiere en su lugar un const std::pair<const Key, int>& (tenga en cuenta que std::map::value_type es un par con un primer elemento const ).

Estos dos tipos son incompatibles y no están relacionados, de modo que para poder realizar la llamada, se debe crear otro par copiando la clave y el valor, y aquí es donde se produce una duplicación de clave adicional.

Incluso si pudiera ser aparentemente "lógico" que un pair<X, Y> debería ser directamente utilizable donde se espera el pair<const X, Y> esto no es cierto en C ++ y es uno de los problemas lógicos del concepto de corrección de const (no escala por composición).

Answer 2

Es por make_pair . Tienes que copiar k en el par, además hay una llamada de función extra. Es posible que se reduzca el número de copias habilitando la optimización (no lo intenté). Sin embargo, si hace esto, tendrá exactamente el mismo número de copias que con el operador []:

mymap2.insert(std::pair<const Key&, int>(k, 1));

Sin embargo, en C ++ 11 las cosas comienzan a mejorar. Si compila su código con C ++ 11, obtendrá dos copias con inserción. Aún mejor, si Key tiene un constructor de movimientos, obtendrá una copia y un movimiento para insertar (mientras que dos copias con el operador []). Si usa mi línea anterior en C ++ 11, incluso ahorrará el movimiento y solo obtendrá una copia.

Curiosamente, con el operador [], siempre recibo dos copias, por lo que no sé la razón exacta.