Cuál es la forma más rápida de cambiar una clave de un elemento dentro de std:: map
Entiendo las razones por las que uno no puede simplemente hacer esto (reequilibrio y esas cosas):
iterator i = m.find(33);
if (i != m.end())
i->first = 22;
Pero hasta ahora la única manera (que conozco) de cambiar la clave es eliminar el nodo del árbol todos juntos y luego insertar el valor de nuevo con una clave diferente:
iterator i = m.find(33);
if (i != m.end())
{
value = i->second;
m.erase(i);
m[22] = value;
}
Esto me parece bastante ineficiente por más razones:
- atraviesa el árbol tres veces (+ balance) en lugar de dos veces (+balance)
- una copia más innecesaria del valor
- innecesario desasignación y luego reasignación de un nodo dentro del árbol
Encuentro que la asignación y la desasignación son las peores de esas tres. Me estoy perdiendo algo o hay una manera más eficiente de hacerlo?
ACTUALIZAR: Creo que, en teoría, debería ser posible, así que no creo que cambiar por una estructura de datos diferente esté justificado. Aquí está el pseudo algoritmo que tengo en mente:
- encuentra el nodo en el árbol cuya clave quiero cambiar.
- separar si de el árbol (no desasignar)
- reequilibrio
- cambiar la clave dentro del nodo separado
- inserte el nodo de nuevo en el árbol
- reequilibrio
6 answers
En C++17, el nuevo map::extract la función le permite cambiar la tecla.
Ejemplo:
std::map<int, std::string> m{ {10, "potato"}, {1, "banana"} };
auto nodeHandler = m.extract(10);
nodeHandler.key() = 2;
m.insert(std::move(nodeHandler)); // { { 1, "banana" }, { 2, "potato" } }
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-07-25 13:47:34
Propuse su algoritmo para los contenedores asociativos hace unos 18 meses aquí:
Http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839
Busca el comentario marcado: [2009-09-19 Howard añade:].
En ese momento, estábamos demasiado cerca de FDIS para considerar este cambio. Sin embargo creo que es muy útil (y aparentemente estás de acuerdo), y me gustaría ponerlo en TR2. Tal vez podría ayudar encontrando y notificando a su Organismo Nacional de C++ representante de que esta es una característica que le gustaría ver.
Update
No es seguro, pero creo que hay una buena posibilidad de que veamos esta característica en C++17! :-)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-03-11 15:55:10
Puede omitir la copia del valor ;
const int oldKey = 33;
const int newKey = 22;
const iterator it = m.find(oldKey);
if (it != m.end()) {
// Swap value from oldKey to newKey, note that a default constructed value
// is created by operator[] if 'm' does not contain newKey.
std::swap(m[newKey], it->second);
// Erase old key-value from map
m.erase(it);
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-07-14 09:09:22
Las claves en los mapas STL deben ser inmutables.
Parece que tal vez una estructura o estructuras de datos diferentes podrían tener más sentido si tiene tanta volatilidad en el lado clave de sus emparejamientos.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-04-21 11:52:41
No puedes.
Como has notado, no es posible. Se organiza un mapa para que pueda cambiar el valor asociado a una clave de manera eficiente, pero no al revés.
Echa un vistazo a Boost.Multiíndice, y en particular su Emulando Secciones de Contenedores estándar. Impulsar.Los contenedores MultiIndex cuentan con una actualización eficiente.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-04-21 11:51:42
Debe dejar la asignación al asignador. :-)
Como usted dice, cuando la clave cambia puede haber mucho reequilibrio. Así es como funciona un árbol. Tal vez 22 es el primer nodo en el árbol y 33 el último? ¿Qué sabemos?
Si evitar las asignaciones es importante, tal vez debería probar un vector o un deque? Se asignan en trozos más grandes, por lo que ahorran en el número de llamadas al asignador, pero potencialmente desperdician memoria en su lugar. Todos los contenedores tienen sus compensaciones y depende de usted decidir cuál tiene la ventaja principal que necesita en cada caso (suponiendo que importe en absoluto).
Para los aventureros:
Si sabes con seguridad que cambiar la clave no afecta el orden y nunca, nunca cometes un error, un pequeño const_cast te permitiría cambiar la clave de todos modos.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-04-21 12:04:40