español - map c++

¿Hay un iterador en claves únicas en std:: multimap?

Question

¿Existe una forma 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 en {1, "a"} entonces el incremento apuntaría a {2, "peacock"} y luego, al volver a incrementar, apuntaría a {3, "angel"} ?

Answer 1

Como se señala en la respuesta seleccionada, el uso repetido de multimap::upper_bound conduce a un multimap::upper_bound O (n log n) del mapa. El uso de la función externa upper_bound le otorga O (n). Sin embargo, debes asegurarte de que solo comparas 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 el mismo que la solución del usuario3701170, es decir, la búsqueda lineal, pero ponemos el paso de incremento en la instrucción for adecuada, no en el cuerpo del bucle. Además de poner el incremento donde "normalmente" vive, esto también significa que cualquier instrucción continue en el ciclo se comportará como se espera.

Answer 2

El uso de upper_bound daría como resultado un bucle fácil de leer, pero cada llamada realizará una búsqueda en árbol binario, lo que dará como resultado un recorrido O (n log n) en lugar de O (n) . Si la diferencia en eficiencia importa, puede estructurar su cruce de esta 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

Pruebe equal_range :

http://en.cppreference.com/w/cpp/container/multimap/equal_range

Esa debe ser una coincidencia exacta.

Answer 4

Puede usar upper_bound para incrementar la posición del 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;
}

Esto resulta en :

1 a
2 peacock
3 angel

Answer 5

si tiene que pasar todas las claves únicas rápidamente, puede usar std :: map en su 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 puedes hacer eso muy templado:

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 prueba completo se ve de la siguiente manera:

#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 6

Ejemplo ejecutable

Esta es una ligera mejora con respecto a https://.com/a/24212648/895245 con una prueba de unidad ejecutable:

#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}));
}