¿Cómo se implementa el contenedor multimapa de C++?

6 minutos de lectura

Por ejemplo, un vector C++ se implementa mediante una matriz dinámica en la que cada elemento utiliza espacios de memoria consecutivos.

Sé que un mapa múltiple de C++ es una relación de uno a muchos, pero ¿cuál es la estructura interna?

Avatar de usuario de Magnus Hoff
Magnus Hoff

El estándar C++ no define cómo se deben implementar los contenedores estándar, solo brinda ciertas restricciones como la que dice para los vectores.

Los mapas múltiples tienen cierta complejidad en tiempo de ejecución (O(lg n) para las operaciones interesantes) y otras garantías, y se pueden implementar como árboles rojo-negros. Así es como se implementan en la biblioteca C++ estándar de GNU.

  • Y también STL de Dinkumware y, por lo tanto, casi todas las bibliotecas estándar del compilador C ++ comercial, incluido VC.

    – Simón Buchan

    6 de junio de 2011 a las 21:51


  • ¿Qué pasa con los elementos. Supongamos que la Clave A tiene B,C,D,E. ¿Se pueden buscar estos elementos o están agrupados como un nodo en el Árbol?

    usuario656925

    6 de junio de 2011 a las 23:13

  • @Chris: no lo he pensado mucho, pero creo que B, C, D y E podrían agruparse en un nodo o representarse como nodos individuales. Sin embargo, no sé a qué te refieres con “buscable”. Puede iterar sobre ellos, pero como tienen la misma clave, no puede elegir uno de ellos directamente (por cualquier propiedad del valor). Un mapa múltiple solo ofrece búsqueda por clave.

    – Magnus Hoff

    7 de junio de 2011 a las 8:06


  • @Chris: Recientemente eché un vistazo a la implementación de GCC y descubrí que los elementos con la misma clave estaban en nodos separados. Sin embargo, no creo que haya ninguna razón por la que otras implementaciones no elijan agruparlas.

    –Mike Seymour

    7 de junio de 2011 a las 10:34

  • @MikeSeymour: es complicado implementar un iterador que elimine las referencias a las referencias de pares clave/valor a menos que cada nodo tenga su propia clave. Esto también explica lower_bound/upper_bound.

    – Pato mugido

    17 de diciembre de 2011 a las 1:41

Avatar de usuario de Oliver Charlesworth
Oliver Charlesworth

Muy a menudo, un árbol rojo-negro. Ver por ejemplo Árboles rojo-negros de STL del Dr. Dobb’s.

  • +1 si hubieras enfatizado [and explained] “muy a menudo” un poco más. ¡Claramente hay un malentendido que debe rectificarse en esta pregunta!

    – Carreras de ligereza en órbita

    6 de junio de 2011 a las 22:27

  • @Tomalak: ¿No estoy seguro de seguir? Dudo en decir “siempre” (si eso es lo que está insinuando), porque el estándar no lo exige, ¡y no conozco todas las implementaciones de STL!

    –Oliver Charlesworth

    6 de junio de 2011 a las 22:37

  • No, no, exactamente. El OP no parece darse cuenta de que esto no es algo estándar. Siento que su respuesta podría hacer más de eso (como lo hizo Magnus). 🙂 (Y, ejem, tos stdlib!)

    – Carreras de ligereza en órbita

    6 de junio de 2011 a las 22:47


  • Me parece bien; probablemente sería en gran medida inútil intentar robar el protagonismo de alguien que suena como si pudiera ser la identidad secreta de Thor: P

    – Carreras de ligereza en órbita

    6 de junio de 2011 a las 22:49


Avatar de usuario de Jonathan S. Shapiro
Jonathan S. Shapiro

Adición a la respuesta “preferida”, porque SO no me deja comentar:

Dada una clave con valores B, C, D, el comportamiento de los iteradores es mucho más fácil de implementar si cada elemento tiene su propio nodo. Find() está definido para devolver el primer resultado de la serie, y la iteración posterior lo lleva a través de los elementos restantes. los de facto La diferencia entre un mapa y un mapa múltiple es que el mapa múltiple se ordena usando

Corrección: el estándar C ++ 11 es explícito en que los nuevos pares (clave, mapeo) se insertan al final de cualquier valor existente que tenga la misma clave. Esto plantea una pregunta que no había considerado: ¿puede un mapa múltiple contener dos nodos en los que tanto la clave como el objetivo asignado sean iguales? El estándar no parece tomar una posición clara al respecto, pero cabe señalar que no se requiere ningún operador de comparación en el tipo asignado. Si escribe un programa de prueba, encontrará que un mapa múltiple puede asignar X a 1, 2, 1. Es decir: “1” puede aparecer varias veces como objetivo y las dos instancias no fusionarse Para algunos algoritmos eso es una deficiencia.

Este artículo del Dr. Dobbs habla sobre la implementación subyacente de rb-tree que se usa comúnmente. El punto principal a tener en cuenta es que la operación de reequilibrio en realidad no se preocupa por las claves en absoluto, por lo que puede construir un árbol rb que admita claves duplicadas.

avatar de usuario de avi007
avi007

El multimapa, al igual que su versión más simple, es decir, el std::map, se construye principalmente usando árboles rojos y negros. El estándar C++ en sí mismo no especifica la implementación. Pero en la mayoría de los casos (revisé personalmente SGI STL) se usan árboles rojos y negros. Los árboles Red Black son árboles de altura equilibrada y, por lo tanto, siempre se garantiza que la operación de búsqueda / lectura en ellos sea O (log (n)) tiempo. Pero si se pregunta cómo se almacenan los valores de la clave. cada key->pair se guarda como un nodo separado en el árbol rojo y negro (aunque la misma clave puede aparecer varias veces, como en el caso de la clave 'b' abajo). La clave se utiliza para buscar/buscar en el árbol rb. Una vez que se encuentra la clave, se devuelve su valor almacenado en el nodo.

  std::multimap<char,int> mmp;

  mmp.insert(std::pair<char,int>('a',10));
  mmp.insert(std::pair<char,int>('b',20));
  mmp.insert(std::pair<char,int>('b',10));
  mmp.insert(std::pair<char,int>('b',15));
  mmp.insert(std::pair<char,int>('b',20));
  mmp.insert(std::pair<char,int>('c',25));
  mmp.insert(std::pair<char,int>('a',15));
  mmp.insert(std::pair<char,int>('a',7));


for (std::multimap<char,int>::iterator it=mmp.begin(); it!=mmp.end(); ++it){

    std::cout << (*it).first << " => "  << (*it).second << " . Address of (*it).second = " << &((*it).second) << '\n';
}

Producción :

a => 10 . Address of (*it).second = 0x96cca24
a => 15 . Address of (*it).second = 0x96ccae4
a => 7 . Address of (*it).second = 0x96ccb04
b => 20 . Address of (*it).second = 0x96cca44
b => 10 . Address of (*it).second = 0x96cca64
b => 15 . Address of (*it).second = 0x96cca84
b => 20 . Address of (*it).second = 0x96ccaa4
c => 25 . Address of (*it).second = 0x96ccac4

Inicialmente pensé que los valores de una sola clave como ‘b’ podría almacenarse en un std::vector .

template <class K, class V>
struct Node {
  K key;
  std::vector<V> values; 
  struct Node* left;
  struct Node* right;
}

Pero luego me di cuenta de que eso violaría el tiempo de recuperación garantizado de O(log(n)). Además, la impresión de las direcciones de los valores confirma que los valores con una clave común no son contiguos.

Las claves se insertan mediante operator

Entonces, si insertamos primero (clave = ‘b’, valor = 20) y luego (clave = ‘b’, valor = 10) La inserción se realiza usando operator

El compilador que he usado es gcc-5.1 (C++14).

¿Ha sido útil esta solución?