¿hay un iterador entre las claves únicas en std :: multimap?

Question

¿Hay una manera simple o estándar de tener un iterador multimap que itere a través de claves únicas en un multimap?

es decir, para un conjunto que se parece a: {1, "a"}, {1, "lemon"}, {2, "peacock"}, {3, "angel"} un iterador que comenzaría a continuación {1, "a"} incrementar apuntaría a {2, "peacock"} y luego incrementando nuevamente apuntaría a {3, "angel"}?

Answer 1

Puede utilizar upper_bound para incrementar la posición de iterador en lugar de ++:

#include <map> 
#include <string> 
#include <iostream> 

using namespace std; 

int main() 
{ 
    multimap<int,string> mm; 
    mm.insert(make_pair(1, "a")); 
    mm.insert(make_pair(1, "lemon")); 
    mm.insert(make_pair(2, "peacock")); 
    mm.insert(make_pair(3, "angel")); 

    for(auto it = mm.begin(), end = mm.end(); 
     it != end; 
     it = mm.upper_bound(it->first) 
) 
    cout << it->first << ' ' << it->second << endl; 
    return 0; 
} 

Answer 2

Usando upper_bound resultaría en un bucle fácil de leer, pero cada llamada llevará a cabo un árbol binario de búsqueda, lo que resulta en una O (n log n) en lugar de O (n) recorrido. Si la diferencia en materia de eficiencia, puede estructurar su recorrido de la siguiente manera:

typedef std::multimap<std::string, int> MapType; 
MapType container; 
for (MapType::iterator it = container.begin(); it != container.end();) { 
    std::string key = it->first; 

    doSomething(key); 

    // Advance to next non-duplicate entry. 
    do { 
    ++it; 
    } while (it != container.end() && key == it->first); 
} 

Answer 3

si tiene que pasar por encima de todas las claves únicas de forma rápida, puede utilizar std :: mapa del lugar;

typedef std::map< KeyType, std::list<ValueType> > MapKeyToMultiValue; 

La inserción sería más difícil. Sin embargo, puede iterar sobre todas las teclas sin tener que preocuparse por las entradas duplicadas. La inserción se vería de la siguiente manera:

void insert_m(MapKeyToMultiValue &map, const KeyType key, const ValueType value) 
{ 
    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< MapKeyToMultiValue::iterator, bool > ret = 
     map.insert(MapKeyToMultiValue::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 

o se puede hacer que esa misma plantilla:

template<typename KeyType, typename ValueType, 
    typename MapType = std::map< KeyType, std::list<ValueType> > > 
void insert_multi(MapType &map, const KeyType key, const ValueType value) 
{ 

    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< typename MapType::iterator, bool > ret = 
     map.insert(typename MapType::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 

El programa de pruebas completo es el siguiente:

#include <map> 
#include <list> 
#include <string> 
#include <stdio.h> 

typedef std::string KeyType; 
typedef int ValueType; 

typedef std::map< KeyType, std::list<ValueType> > MapKeyToMultiValue; 

void insert_m(MapKeyToMultiValue &map, const KeyType key, const ValueType value) 
{ 
    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< MapKeyToMultiValue::iterator, bool > ret = 
     map.insert(MapKeyToMultiValue::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 


template<typename KeyType, typename ValueType, 
    typename MapType = std::map< KeyType, std::list<ValueType> > > 
void insert_multi(MapType &map, const KeyType key, const ValueType value) 
{ 

    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< typename MapType::iterator, bool > ret = 
     map.insert(typename MapType::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 


int main() 
{ 
    MapKeyToMultiValue map; 


    insert_m(map, std::string("aaa"), 1); 
    insert_m(map, std::string("aaa"), 2); 
    insert_m(map, std::string("bb"), 3); 
    insert_m(map, std::string("cc"), 4); 


    insert_multi(map, std::string("ddd"), 1); 
    insert_multi(map, std::string("ddd"), 2); 
    insert_multi(map, std::string("ee"), 3); 
    insert_multi(map, std::string("ff"), 4); 


    for(auto i = map.begin(); i != map.end(); ++i) 
    { 
     printf("%s\n", i->first.c_str()); 
    } 


    return 0; 
} 

Answer 4

Esta es una ligera mejora sobre https://stackoverflow.com/a/24212648/895245 con:

• una "prueba de unidad"

#include <cassert> 
#include <map> 
#include <vector> 

int main() { 

    // For testing. 
    auto m = std::multimap<int, int>{ 
     {1, 2}, 
     {1, 3}, 
     {2, 4} 
    }; 
    std::vector<int> out; 

    // The algorithm. 
    auto it = m.begin(); 
    auto end = m.end(); 
    while (it != end) { 
     auto key = it->first; 

     // Do what you want to do with the keys. 
     out.push_back(key); 

     do { 
      if (++it == end) 
       break; 
     } while (it->first == key); 
    } 

    // Assert it worked. 
    assert(out == std::vector<int>({1, 2})); 
} 

Answer 5

Como se señaló en la respuesta seleccionada, el uso repetido de multimap::upper_bound conduce a una O (n log n) de recorrido del mapa. El uso de la función externa upper_bound le otorga O (n). Sin embargo, es necesario asegurarse de que sólo se compara la clave del mapa:

std::multimap<int, std::string> myMap = ... ; 
const auto compareFirst = [](const std::pair<const int, std::string>& lhs, const std::pair<const int, std::string>& rhs) { 
    return lhs.first < rhs.first; 
}; 

for(auto it = myMap.begin(); it != myMap.end(); it = std::upper_bound(it, myMap.end(), *it, compareFirst)) { 
    // Do stuff... 

} 

El enfoque subyacente es esencialmente la misma que la solución de user3701170 - es decir, búsqueda lineal - pero poner el paso de incremento en la cuenta de for adecuada, no el cuerpo del bucle Además de poner el incremento donde "normalmente" vive, esto también significa que cualquier declaración continue en el ciclo se comportará como se espera.