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;
}
Pero ¿qué pasa con la complejidad de O (n log n) que esto conlleva, en lugar de la O (n) transversal normal, como se menciona en la respuesta de @ user3701170. – ddevienne
@ddevienne tristemente, hoy en día todo el mundo elige la elegancia sobre el rendimiento. – GreenScape