usar - ¿Cómo se implementa el contenedor multimap de C++?

contenedores stl

Question

Por ejemplo, un vector C ++ se implementa utilizando una matriz dinámica donde cada elemento usa espacios de memoria consecutivos.

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

Answer 1

Además de 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 () se define para devolver el primer resultado de la serie, y la iteración posterior lo lleva a través de los elementos restantes. La diferencia de facto entre un mapa y un multimapa es que el multimapa se ordena usando <sobre todo el value_type completo, donde el mapa usa <solo sobre el key_type

Corrección: el estándar de C ++ 11 es explícito 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 multimapa contener dos nodos en los que tanto la clave como el objetivo asignado son iguales? El estándar no parece tomar una posición clara sobre esto, pero es notable que no se requiere un operador de comparación en el tipo mapeado. Si escribe un programa de prueba, encontrará que un multimapa puede asignar X a 1, 2, 1. Es decir: "1" puede aparecer varias veces como destino y las dos instancias no se fusionarán. Para algunos algoritmos es una deficiencia.

Este article 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 a la operación de reequilibrio en realidad no le importan las claves, por lo que puede construir un árbol rb que admita claves duplicadas.

Answer 2

El estándar de C ++ no define cómo deben implementarse los contenedores estándar, solo da ciertas restricciones como la que usted dice para los vectores.

Los multimaps tienen cierta complejidad de 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 de C ++ estándar de GNU.

Answer 3

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

Answer 4

El multimapa, al igual que su versión más simple, es decir, el std :: map, se construye principalmente con árboles negros y rojos. El propio estándar de C ++ no especifica la implementación. Pero en la mayoría de los casos (personalmente verifiqué SGI STL) se usan árboles rojos y negros. Los árboles negros rojos 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)) en el 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 negro rojo (aunque la misma tecla puede aparecer varias veces, como en el caso de la tecla ''b'' continuación). La clave se usa para buscar / buscar el árbol rb. Una vez que se encuentra la clave, se devuelve el 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'';
}

Salida:

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ían 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 utilizando el operador <, por lo que los valores con las mismas claves se almacenan en el orden en que se insertaron.

Entonces, si insertamos primero (clave = ''b'', valor = 20) y luego (clave = ''b'', valor = 10) La inserción se realiza con el operador <, ya que la segunda ''b'' NO es menor que la primera insertada ''b'', se inserta en la ''rama derecha de un árbol binario''.

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