C++ => std :: map

Observaciones

Para usar cualquiera de std::map o std::multimap debe incluir el archivo de encabezado <map> .
std::map y std::multimap mantienen sus elementos ordenados según el orden ascendente de las teclas. En el caso de std::multimap , no se produce una clasificación para los valores de la misma clave.
La diferencia básica entre std::map y std::multimap es que std::map one no permite valores duplicados para la misma clave que std::multimap .
Los mapas se implementan como árboles binarios de búsqueda. Entonces search() , insert() , erase() toma Θ (log n) tiempo en promedio. Para una operación de tiempo constante use std::unordered_map .
size() funciones size() y empty() tienen una complejidad de tiempo Θ (1), el número de nodos se almacena en caché para evitar recorrer el árbol cada vez que se llama a estas funciones.

Elementos de acceso

Un std::map toma pares (key, value) como entrada.

Considere el siguiente ejemplo de std::map initialization:

std::map < std::string, int > ranking { std::make_pair("stackoverflow", 2), 
                                        std::make_pair("docs-beta", 1) };

En un std::map , los elementos se pueden insertar de la siguiente manera:

ranking["stackoverflow"]=2;
ranking["docs-beta"]=1;

En el ejemplo anterior, si el stackoverflow llaves ya está presente, su valor se actualizará a 2. Si no está ya presente, se creará una nueva entrada.

En un std::map , se puede acceder a los elementos directamente dando la clave como un índice:

std::cout << ranking[ "stackoverflow" ] << std::endl;

Tenga en cuenta que usar el operator[] en el mapa insertará un nuevo valor con la clave consultada en el mapa. Esto significa que no puede usarlo en un const std::map , incluso si la clave ya está almacenada en el mapa. Para evitar esta inserción, verifique si el elemento existe (por ejemplo, utilizando find() ) o use at() como se describe a continuación.

C ++ 11

Se puede acceder at() elementos de un std::map con at() :

std::cout << ranking.at("stackoverflow") << std::endl;

Tenga at() cuenta que at() lanzará una excepción std::out_of_range si el contenedor no contiene el elemento solicitado.

En ambos contenedores std::map y std::multimap , se puede acceder a los elementos utilizando los iteradores:

C ++ 11

// Example using begin()
std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
                                         std::make_pair(1, "docs-beta"),
                                         std::make_pair(2, "stackexchange")  };
auto it = mmp.begin();
std::cout << it->first << " : " << it->second << std::endl; // Output: "1 : docs-beta"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackoverflow"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackexchange"

// Example using rbegin()
std::map < int, std::string > mp {  std::make_pair(2, "stackoverflow"),
                                    std::make_pair(1, "docs-beta"),
                                    std::make_pair(2, "stackexchange")  };
auto it2 = mp.rbegin();
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "2 : stackoverflow"
it2++;
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "1 : docs-beta"

Inicializando un std :: map o std :: multimap

std::map y std::multimap pueden inicializarse proporcionando pares clave-valor separados por comas. Los pares clave-valor pueden ser proporcionados por {key, value} o pueden ser creados explícitamente por std::make_pair(key, value) . Como std::map no permite claves duplicadas y el operador de coma se realiza de derecha a izquierda, el par a la derecha se sobrescribiría con el par con la misma tecla a la izquierda.

std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
                                     std::make_pair(1, "docs-beta"),
                                     std::make_pair(2, "stackexchange")  };
// 1 docs-beta
// 2 stackoverflow
// 2 stackexchange

std::map < int, std::string > mp {  std::make_pair(2, "stackoverflow"),
                                std::make_pair(1, "docs-beta"),
                                std::make_pair(2, "stackexchange")  }; 
// 1 docs-beta
// 2 stackoverflow

Ambos podrían inicializarse con iterador.

// From std::map or std::multimap iterator
std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {6, 8}, {3, 4}, 
                               {6, 7} };
                       // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 8}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); //moved cursor on first {6, 5}
std::map< int, int > mp(it, mmp.end()); // {6, 5}, {8, 9}

//From std::pair array
std::pair< int, int > arr[10];
arr[0] = {1, 3};
arr[1] = {1, 5};
arr[2] = {2, 5};
arr[3] = {0, 1};
std::map< int, int > mp(arr,arr+4); //{0 , 1}, {1, 3}, {2, 5}

//From std::vector of std::pair
std::vector< std::pair<int, int> > v{ {1, 5}, {5, 1}, {3, 6}, {3, 2} };
std::multimap< int, int > mp(v.begin(), v.end()); 
                        // {1, 5}, {3, 6}, {3, 2}, {5, 1}

Borrando elementos

Eliminando todos los elementos:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
mmp.clear(); //empty multimap

Eliminando elementos de algún lugar con la ayuda de iterador:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); // moved cursor on first {6, 5}
mmp.erase(it); // {1, 2}, {3, 4}, {3, 4}, {6, 7}, {8, 9}

Eliminando todos los elementos en un rango:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
auto it2 = it;
it++; //moved first cursor on first {3, 4}
std::advance(it2,3);  //moved second cursor on first {6, 5}
mmp.erase(it,it2); // {1, 2}, {6, 5}, {6, 7}, {8, 9}

Eliminando todos los elementos que tengan un valor proporcionado como clave:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
mmp.erase(6); // {1, 2}, {3, 4}, {3, 4}, {8, 9}

Eliminando elementos que satisfacen un pred predicado:

std::map<int,int> m;
auto it = m.begin();
while (it != m.end())
{
   if (pred(*it))
       it = m.erase(it);
   else
       ++it;
}

Insertando elementos

Un elemento se puede insertar en un std::map solo si su clave ya no está presente en el mapa. Dado por ejemplo:

std::map< std::string, size_t > fruits_count;

Un par clave-valor se inserta en un std::map través de la función miembro insert() . Requiere un pair como argumento:
```
fruits_count.insert({"grapes", 20});
fruits_count.insert(make_pair("orange", 30));
fruits_count.insert(pair<std::string, size_t>("banana", 40));
fruits_count.insert(map<std::string, size_t>::value_type("cherry", 50));
```
La función insert() devuelve un pair consiste en un iterador y un valor bool :
- Si la inserción fue exitosa, el iterador apunta al elemento recién insertado, y el valor bool es true .
- Si ya existía un elemento con la misma key , la inserción falla. Cuando eso sucede, el iterador apunta al elemento que causa el conflicto, y el valor de bool es false .
El siguiente método se puede utilizar para combinar la inserción y la operación de búsqueda:
```
auto success = fruits_count.insert({"grapes", 20});
if (!success.second) {           // we already have 'grapes' in the map
    success.first->second += 20; // access the iterator to update the value
}
```
Para mayor comodidad, el contenedor std::map proporciona el operador de subíndices para acceder a los elementos del mapa e insertar otros nuevos si no existen:
```
fruits_count["apple"] = 10;
```
Aunque es más simple, evita que el usuario verifique si el elemento ya existe. Si falta un elemento, std::map::operator[] crea implícitamente, inicializándolo con el constructor predeterminado antes de sobrescribirlo con el valor suministrado.

insert() se puede usar para agregar varios elementos a la vez usando una lista de pares. Esta versión de insert () devuelve void:
```
fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}}); 
```
insert() también se puede usar para agregar elementos mediante el uso de iteradores que denotan el comienzo y el final de los valores de value_type valor:
```
std::map< std::string, size_t > fruit_list{ {"lemon", 0}, {"olive", 0}, {"plum", 0}};
fruits_count.insert(fruit_list.begin(), fruit_list.end()); 
```

Ejemplo:

std::map<std::string, size_t> fruits_count;
std::string fruit;
while(std::cin >> fruit){
    // insert an element with 'fruit' as key and '1' as value
    // (if the key is already stored in fruits_count, insert does nothing)
    auto ret = fruits_count.insert({fruit, 1});
    if(!ret.second){            // 'fruit' is already in the map 
        ++ret.first->second;    // increment the counter
    }
}

La complejidad del tiempo para una operación de inserción es O (log n) porque std::map se implementa como árboles.

C ++ 11

Un pair puede construirse explícitamente usando make_pair() y emplace() :

std::map< std::string , int > runs;
runs.emplace("Babe Ruth", 714);
runs.insert(make_pair("Barry Bonds", 762));

Si sabemos dónde se insertará el nuevo elemento, entonces podemos usar emplace_hint() para especificar una hint iterador. Si el nuevo elemento se puede insertar justo antes de la hint , entonces la inserción se puede hacer en un tiempo constante. De lo contrario, se comporta de la misma manera que emplace() :

std::map< std::string , int > runs;
auto it = runs.emplace("Barry Bonds", 762); // get iterator to the inserted element
// the next element will be before "Barry Bonds", so it is inserted before 'it'
runs.emplace_hint(it, "Babe Ruth", 714);

Iterando sobre std :: map o std :: multimap

std::map o std::multimap se puede recorrer de las siguientes maneras:

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                               
//Range based loop - since C++11
for(const auto &x: mmp) 
    std::cout<< x.first <<":"<< x.second << std::endl;

//Forward iterator for loop: it would loop through first element to last element
//it will be a std::map< int, int >::iterator
for (auto it = mmp.begin(); it != mmp.end(); ++it)
std::cout<< it->first <<":"<< it->second << std::endl; //Do something with iterator

//Backward iterator for loop: it would loop through last element to first element
//it will be a std::map< int, int >::reverse_iterator
for (auto it = mmp.rbegin(); it != mmp.rend(); ++it)
std::cout<< it->first <<" "<< it->second << std::endl; //Do something with iterator

Mientras se recorre un std::map o un std::multimap , se prefiere el uso de auto para evitar conversiones implícitas inútiles (consulte esta respuesta SO para obtener más detalles).

Buscando en std :: map o en std :: multimap

Hay varias formas de buscar una clave en std::map o en std::multimap .

Para obtener el iterador de la primera aparición de una clave, se puede usar la función find() . Devuelve end() si la clave no existe.

  std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
  auto it = mmp.find(6);
  if(it!=mmp.end())
      std::cout << it->first << ", " << it->second << std::endl; //prints: 6, 5
  else
      std::cout << "Value does not exist!" << std::endl;

  it = mmp.find(66);
  if(it!=mmp.end())
      std::cout << it->first << ", " << it->second << std::endl; 
  else
      std::cout << "Value does not exist!" << std::endl; // This line would be executed.

Otra forma de averiguar si existe una entrada en std::map o en std::multimap es usar la función count() , que cuenta cuántos valores están asociados con una clave determinada. Como std::map asocia solo un valor con cada tecla, su función count() solo puede devolver 0 (si la tecla no está presente) o 1 (si lo está). Para std::multimap , count() puede devolver valores mayores que 1 ya que puede haber varios valores asociados con la misma clave.
```
 std::map< int , int > mp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
 if(mp.count(3) > 0) // 3 exists as a key in map
     std::cout << "The key exists!" << std::endl; // This line would be executed.
 else
     std::cout << "The key does not exist!" << std::endl;
```
Si solo le importa si existe algún elemento, find es estrictamente mejor: documenta su intención y, para los multimaps , puede detenerse una vez que se haya encontrado el primer elemento coincidente.
En el caso de std::multimap , podría haber varios elementos que tengan la misma clave. Para obtener este rango, se utiliza la función equal_range() que devuelve std::pair con un límite inferior (inclusivo) del iterador y un límite superior (exclusivo) respectivamente. Si la clave no existe, ambos iteradores apuntarían a end() .
```
  auto eqr = mmp.equal_range(6);
  auto st = eqr.first, en = eqr.second;
  for(auto it = st; it != en; ++it){
      std::cout << it->first << ", " << it->second << std::endl; 
  }
      // prints: 6, 5
      //         6, 7
```

Comprobando el número de elementos

El contenedor std::map tiene una función miembro empty() , que devuelve true o false , dependiendo de si el mapa está vacío o no. El size() función miembro size() devuelve el número de elementos almacenados en un contenedor std::map :

std::map<std::string , int> rank {{"facebook.com", 1} ,{"google.com", 2}, {"youtube.com", 3}};
if(!rank.empty()){
    std::cout << "Number of elements in the rank map: " << rank.size() << std::endl;
}
else{
    std::cout << "The rank map is empty" << std::endl;
}

Tipos de mapas

Mapa regular

Un mapa es un contenedor asociativo, que contiene pares clave-valor.

#include <string>
#include <map>
std::map<std::string, size_t> fruits_count;

En el ejemplo anterior, std::string es el tipo de clave , y size_t es un valor .

La clave actúa como un índice en el mapa. Cada clave debe ser única y debe ser ordenada.

Si necesita elementos múltiples con la misma clave, considere usar el multimap (que se explica a continuación)

Si su tipo de valor no especifica ningún pedido, o si desea anular el orden predeterminado, puede proporcionar uno:

#include <string>
#include <map>
#include <cstring>
struct StrLess {
    bool operator()(const std::string& a, const std::string& b) {
        return strncmp(a.c_str(), b.c_str(), 8)<0;
               //compare only up to 8 first characters
    }
}
std::map<std::string, size_t, StrLess> fruits_count2;

Si el comparador StrLess devuelve false para dos claves, se consideran iguales incluso si sus contenidos reales difieren.

Multi-Mapa

Multimap permite que múltiples pares clave-valor con la misma clave se almacenen en el mapa. De lo contrario, su interfaz y creación es muy similar al mapa regular.

 #include <string>
 #include <map>
 std::multimap<std::string, size_t> fruits_count;
 std::multimap<std::string, size_t, StrLess> fruits_count2;

Hash-Map (Mapa desordenado)

Un mapa hash almacena pares clave-valor similares a un mapa normal. Sin embargo, no ordena los elementos con respecto a la clave. En su lugar, se utiliza un valor hash para la clave para acceder rápidamente a los pares clave-valor necesarios.

#include <string>
#include <unordered_map>
std::unordered_map<std::string, size_t> fruits_count;

Los mapas desordenados suelen ser más rápidos, pero los elementos no se almacenan en ningún orden predecible. Por ejemplo, iterar sobre todos los elementos en un unordered_map da los elementos en un orden aparentemente aleatorio.

Creando std :: map con tipos definidos por el usuario como clave

Para poder utilizar una clase como la clave en un mapa, todo lo que se requiere de la clave es que sea copiable y assignable . El orden dentro del mapa se define por el tercer argumento de la plantilla (y el argumento del constructor, si se usa). Por defecto, este es std::less<KeyType> , que por defecto es el operador < , pero no hay ningún requisito para usar los valores por defecto. Simplemente escriba un operador de comparación (preferiblemente como un objeto funcional):

struct CmpMyType
{
    bool operator()( MyType const& lhs, MyType const& rhs ) const
    {
        //  ...
    }
};

En C ++, el predicado de "comparación" debe ser un ordenamiento estricto y débil . En particular, compare(X,X) debe devolver false para cualquier X es decir, si CmpMyType()(a, b) devuelve true, CmpMyType()(b, a) debe devolver false, y si ambos devuelven false, los elementos se consideran iguales (miembros de la misma clase de equivalencia).

Ordenamiento estricto y débil

Este es un término matemático para definir una relación entre dos objetos.
Su definición es:

Dos objetos x e y son equivalentes si f (x, y) y f (y, x) son falsos. Tenga en cuenta que un objeto es siempre (por la invariante irreflexividad) equivalente a sí mismo.

En términos de C ++, esto significa que si tiene dos objetos de un tipo determinado, debe devolver los siguientes valores en comparación con el operador <.

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

La forma en que defina el equivalente / menor depende totalmente del tipo de su objeto.

Modified text is an extract of the original Stack Overflow Documentation

Licenciado bajo CC BY-SA 3.0

No afiliado a Stack Overflow

C++
std :: map

Buscar..

Observaciones

Elementos de acceso

Inicializando un std :: map o std :: multimap

Borrando elementos

Insertando elementos

Iterando sobre std :: map o std :: multimap

Buscando en std :: map o en std :: multimap

Comprobando el número de elementos

Tipos de mapas

Mapa regular

Multi-Mapa

Hash-Map (Mapa desordenado)

Creando std :: map con tipos definidos por el usuario como clave

Ordenamiento estricto y débil