¿Cómo se debería usar std :: map con un valor que no tiene un constructor predeterminado?

Question

Tengo un tipo de valor que quiero poner en un mapa. Tiene un buen constructor de copia predeterminado, pero no tiene un constructor predeterminado.

Creo que siempre que me mantenga alejado de usar operator[] que todo estará bien.

Sin embargo, termino con construcciones bastante feas como esta para insertar un objeto. (creo que la inserción simplemente falla si ya hay un valor para esa clave).

// equivalent to m[5]=x but without default construction 

std::map<int,X>::iterator it = m.find(5); 
if(it != m.end()) 
{ 
    m->second = x; 
} 
else 
{ 
    m->insert(std::make_pair(5,x)); 
} 

Lo que creo escaneará el mapa dos veces, y también se ve bastante feo.

¿Hay alguna manera más clara/más eficiente de hacer esto?

Answer 1

Usted puede simplemente "insert-o-sobrescribir" con la norma insert función:

auto p = mymap.insert(std::make_pair(key, new_value)); 

if (!p.second) p.first->second = new_value; // overwrite value if key already exists 

Si desea pasar los elementos por rerference, hacer que el par explícito:

insert(std::pair<K&, V&>(key, value)); 

Si tiene un typedef para el mapa como map_t, puede decir std::pair<map_t::key_type &, map_t::mapped_type &>, o cualquier variación adecuada sobre este tema.

---

Tal vez esto es lo mejor envuelto en un ayudante:

template <typename Map> 
void insert_forcefully(Map & m, 
         typename Map::key_type const & key, 
         typename Map::mapped_type const & value) 
{ 
    std::pair<typename Map::iterator, bool> p = m.insert(std::pair<typename Map::key_type const &, typename Map::mapped_type const &>(key, value)); 
    if (!p.second) { p.first->second = value; } 
} 

Answer 2

Primero puede obtener la posición para insertar el par con lower_bound, luego verifique si ya está allí, y si no, insértelo, proporcionando al iterador dónde insertarlo. Algo en esa línea.

Answer 3

hay dos cosas que no ha visto en la interfaz de map (y similares):

• insert(value_type) devuelve una std::pair<iterator, bool>, el miembro .first apunta al elemento con la clave que intentó insertar y el miembro .second indica si es realmente el elemento que intentado insertar u otro que anteriormente estaba en el contenedor.
• insert(iterator, value_type) le permite dar una pista sobre dónde insertar

Esta última no es necesariamente útil en su situación sin embargo.

typedef std::map<int,X> Map; 

// insert and check 
std::pair<Map::iterator, bool> const result = 
    map.insert(std::make_pair(5, x));   // O(log N) 

if (not result.second) 
{ 
    result->first.second = x;     // O(1) 
    // OR 
    using std::swap; 
    swap(result->first.second, x); 
} 

Si escribe no permite la asignación y no hay intercambio, sin embargo, es necesario hacer de tripas corazón:

// locate and insert 
Map::iterator position = map.lower_bound(5);   // O(log N) 
if (position != map.end() and position->first == 5) 
{ 
    position = map.erase(position);     // O(1) 
} 
map.insert(position, std::make_pair(5, x));   // O(log N) if rebalancing 

En C++ 11, se duplican los métodos insert:

• insert(value_type const&) // inserción por copia
• insert(P&&) // inserción por el movimiento

y con reenvío perfecto obtenemos el nuevo método emplace. Similar a insert, pero que construye el elemento en su lugar reenviando los argumentos a su constructor. Sin embargo, para mí es un misterio cómo diferenciar los argumentos a favor de la clave y el valor.