Hay dos maneras en que puedo hacer fácilmente una clave, atribución de valor en C++ STL: mapas y conjuntos de pares. Por ejemplo, podría haber¿Cuál es la diferencia entre el conjunto <pair> y el mapa en C++?
map<key_class,value_class>
o
set<pair<key_class,value_class> >
En términos de complejidad del algoritmo de codificación y el estilo, ¿cuáles son las diferencias entre estos usos?
Fije los elementos no pueden ser modificados mientras que están en el conjunto. set 's iterator y const_iterator son equivalentes. Por lo tanto, con set<pair<key_class,value_class> >, no puede modificar el value_class en contexto. Debe eliminar el valor anterior del conjunto y agregar el nuevo valor. Sin embargo, si value_class es un puntero, esto no le impide modificar el objeto al que apunta.
Con map<key_class,value_class>, puede modificar el value_class in situ, suponiendo que tiene una referencia no constante al mapa.
La diferencia básica es que para el conjunto la clave es el par, mientras que para el mapa la clave es key_class - esto hace que buscar cosas por key_class, que es lo que quiere hacer con los mapas, difícil para el conjunto.
Ambos se implementan típicamente con la misma estructura de datos (normalmente un árbol binario equilibrado rojo-negro), por lo que la complejidad de los dos debe ser la misma.
Eso no es exactamente cierto. find_if seguirá funcionando en un conjunto. –
Puedo usar lower_bound y upper_bound para encontrar un valor para el conjunto. –
Son semánticamente diferente. Consideremos:
#include <set>
#include <map>
#include <utility>
#include <iostream>
using namespace std;
int main() {
pair<int, int> p1(1, 1);
pair<int, int> p2(1, 2);
set< pair<int, int> > s;
s.insert(p1);
s.insert(p2);
map<int, int> m;
m.insert(p1);
m.insert(p2);
cout << "Set size = " << s.size() << endl;
cout << "Map size = " << m.size() << endl;
}
Salida:
tamaño Conjunto size = 2
Mapa = 1
¡Buena respuesta! +1 –
Sería aún más completo para publicar también la salida resultante + visión de 1 línea. +1 sin embargo. –
mapa no permite duplicados de la clave – Daniel
map<key_class,value_class> clasificará en key_class y permitir que no hay duplicados de key_class.
set<pair<key_class,value_class> > clasificará en key_class y luego value_class si las instancias key_class son iguales, y permitirá múltiples valores para key_class
std::map actúa como una estructura de datos asociativa. En otras palabras, le permite consultar y modificar valores usando su clave asociada.
A std::set<pair<K,V> > se puede hacer que funcione así, pero debe escribir código adicional para la consulta utilizando una clave y más código para modificar el valor (es decir, eliminar el par antiguo e insertar otro con la misma clave y otro valor). También debe asegurarse de que no haya más de dos valores con la misma clave (lo adivinó, más código).
En otras palabras, puede intentar zapatear una bocina std::set para que funcione como std::map, pero no hay ninguna razón para hacerlo.
de hecho, simplemente usaría std :: map luego: p – 4pie0
Utilicé un conjunto
Para comprender la complejidad algorítmica, primero debe comprender la implementación.
std :: map se implementa utilizando RB-tree, donde como hash_map se implementan utilizando matrices de la lista vinculada. std :: map proporciona O (log (n)) para la operación insertar/borrar/buscar, hash_map es O (1) es el mejor de los casos y o (n) en el peor de los casos, dependiendo de las colisiones hash.
¿Qué es 'hash_map'? ¿No se trata de comparar 'map' con' set', no 'map' con' hash_map'? – cnst
visualizar que diferencia semántica Philipp mencionó después de recorrer el código, tenga en cuenta la forma del mapa de teclado es un const int y cómo no se insertó p2 en m:
Tal vez significaba para preguntar sobre multimap en lugar de mapa? –
@RobKennedy: Tal vez quiso decir multiset y multimap ... – einpoklum
No en ese momento, @Einpoklum. Quise decir que para usar un mapa para mantener todos los mismos valores que un 'set' puede contener, necesitarías que el mapa fuera un 'multimap'. Lo que no consideré fue que para mantener todos los valores que un 'multimap' puede contener, usted a su vez necesita que el conjunto sea un' multiset '. Gracias por traer eso a mi atención. –