c++ - usar - ¿Hay una implementación más eficiente para un mapa bidireccional?

vectores stl en c++

Question

Creé una clase de mapa bidireccional simple que funciona guardando internamente dos instancias std::map , con tipos de clave / valor opuestos, y proporcionando una interfaz fácil de usar:

template<class T1, class T2> class Bimap
{
    std::map<T1, T2> map1;
    std::map<T2, T1> map2;
    // ...
};

• ¿Existe un método más eficiente para implementar un mapa bidireccional que no requiera el doble de memoria?

• ¿Cómo se implementa un bimap?

EDITAR:

• ¿El elemento bimap debe ser mutable o inmutable? (Cambiar un elemento en map1 debería cambiar la clave en map2 , pero las claves son const y eso es imposible, ¿cuál es la solución?)

• La propiedad de los elementos es también otro problema: cuando un usuario inserta un par clave-valor en el bimap, el bimap debe hacer una copia de ese par clave-valor y almacenarlo, luego el segundo mapa interno (con clave / valor invertido) debería no copiar, sino apuntar al par original. ¿Cómo se puede lograr esto?

EDICION 2:

Publiqué una posible implementación que realicé en Code Review.

Answer 1

¿Qué tal esto?

Aquí, evitamos el almacenamiento doble de un tipo (T1). El otro tipo (T2) todavía está almacenado doble.

// Assume T1 is relatively heavier (e.g. string) than T2 (e.g. int family).
// If not, client should instantiate this the other way.
template <typename T1, typename T2>
class UnorderedBimap {

  typedef std::unordered_map<T1, T2> Map1;
  Map1 map1_;

  std::unordered_map<T2, Map1::iterator> map2_;
};

Answer 2

Existe un cierto problema con el almacenamiento doble de sus datos en todas las implementaciones simples de un bimap. Si puedes dividirlo en una bimap de punteros desde el exterior, entonces puedes ignorar esto fácilmente y simplemente mantener ambos mapas de la forma std::map<A*,B*> <A *, B *> como ya sugirió Arkaitz Jiménez (aunque contrario a su respuesta debe preocuparse por el almacenamiento desde el exterior para evitar una búsqueda A->A* ). Pero si tiene los punteros de todos modos, ¿por qué no simplemente almacenar un std::pair<A,B> en el punto en el que almacenaría A y B separado?

Sería bueno tener std::map<A,B*> lugar de std::map<A*,B*> ya que esto permitiría, por ejemplo, la búsqueda de un elemento asociado a una cadena por una cadena creada recientemente con el mismo contenido en lugar del puntero a la cadena original que creó el par. Pero es habitual almacenar una copia completa de la clave con cada entrada y solo confiar en el hash para encontrar el cubo correcto. De esta forma, el artículo devuelto será el correcto incluso en el caso de una colisión hash ...

Si quieres tenerlo rápido y sucio, hay esto

solución hackish:

Cree dos mapas std::map<size_t, A> mapA y std::map<size_t, B> mapB . Tras la inserción hash ambos elementos que se van a insertar para obtener las claves de los respectivos mapas.

void insert(const A &a, const B &b) {
    size_t hashA = std::hash<A>(a);
    size_t hashB = std::hash<B>(b);

    mapA.insert({hashB, a});
    mapB.insert({hashA, b});
}

La búsqueda se implementa de forma análoga.

Usar un multimap lugar de un map y verificar cada elemento que obtienes con una búsqueda en el otro mapa respectivo (obtener candidato b de mapA , hash b y buscar en mapB si coincide con la clave deseada, iterar al siguiente candidato de otra manera) esto es una implementación válida, pero todavía hackear en mi opinión ...

Puede obtener una solución mucho más agradable utilizando las copias de los elementos que se utilizan para comparar las entradas (ver arriba) como solo almacenamiento. Sin embargo, es un poco más difícil entenderlo. Elaborar:

una mejor solución:

Cree dos conjuntos de pares como std::set<pair<A, B*>> y std::set<pair<B, A*>> y sobrecargue el operator< y el operator== para tomar solo el primer elemento del pares en cuenta (o proporcionar una clase comparion correspondiente). Es necesario crear conjuntos de pares en lugar de mapas (que internamente se ven de manera similar) porque necesitamos una garantía de que A y B siempre estarán en las mismas posiciones en la memoria. Tras la inserción de un pair<A,B> lo dividimos en dos elementos que encajan en los conjuntos anteriores.

  std::set<pair<B, A*>> mapA;
  std::set<pair<A, B*>> mapB;

  void insert(const A &a, const B &b) {
      auto aitr = mapA.insert({b, nullptr}).first; // creates first pair
      B *bp = &(aitr->first);  // get pointer of our stored copy of b
      auto bitr = mapB.insert({a, bp}).first; 
      // insert second pair {a, pointer_to_b}
      A *ap = &(bitr->first);  // update pointer in mapA to point to a
      aitr->second = ap;
  }

La búsqueda ahora se puede hacer simplemente mediante una simple búsqueda std::set y una referencia de puntero.

Esta solución más agradable es similar a la solución que usa boost, aunque utilizan algunos punteros anonimizados como segundos elementos de los pares y, por lo tanto, deben usar reinterpret_cast s.

Tenga en cuenta que la .second parte de los pares debe ser mutable (por lo que no estoy seguro de que se pueda usar std::pair ), o debe agregar otra capa de abstracción ( std::set<pair<B, A**>> mapA ) incluso para esta simple inserción. En ambas soluciones necesita elementos temporales para devolver referencias no constantes a los elementos.

Answer 3

Sería más eficiente almacenar todos los elementos en un vector y tener 2 mapas de <T1*,T2*> y <T2*,T1*> esa manera no tendría todo copiado dos veces.

De la forma en que lo veo, estás tratando de almacenar 2 cosas, elementos en sí mismos y la relación entre ellos, si estás apuntando a tipos escalares podrías dejarlo como son 2 mapas, pero si pretendes tratar tipos complejos, tiene más sentido separe el almacenamiento de las relaciones y maneje las relaciones fuera del almacenamiento.

Answer 4

Si creas un conjunto de pares para tus tipos std::set<std::pair<X,Y>> prácticamente tienes tu functionallity implementada y reglas sobre mutabillity y constness preestablecido (OK, tal vez las configuraciones no son lo que quieres pero se pueden hacer ajustes). Así que aquí está el código:

#ifndef MYBIMAP_HPP
#define MYBIMAP_HPP

#include <set>
#include <utility>
#include <algorithm>

using std::make_pair;

template<typename X, typename Y, typename Xless = std::less<X>, 
                     typename Yless = std::less<Y>>
class bimap
{
    typedef std::pair<X, Y>                             key_type;
    typedef std::pair<X, Y>                             value_type;
    typedef typename std::set<key_type>::iterator       iterator;
    typedef typename std::set<key_type>::const_iterator const_iterator;

    struct Xcomp
    {
        bool operator()(X const &x1, X const &x2)
        {
            return !Xless()(x1, x2) && !Xless()(x2, x1);
        }
    };
    struct Ycomp
    {
        bool operator()(Y const &y1, Y const &y2)
        {
            return !Yless()(y1, y2) && !Yless()(y2, y1);
        }
    };
    struct Fless 
    { // prevents lexicographical comparison for std::pair, so that 
        // every .first value is unique as if it was in its own map
        bool operator()(key_type const &lhs, key_type const &rhs)
        {
            return Xless()(lhs.first, rhs.first);
        }
    };
    /// key and value type are interchangeable
    std::set<std::pair<X, Y>, Fless> _data;

public:
    std::pair<iterator, bool> insert(X const &x, Y const &y)
    {
        auto it = find_right(y);
        if (it == end()) { // every .second value is unique
            return _data.insert(make_pair(x, y));
        }
        return make_pair(it, false);
    }
    iterator find_left(X const &val)
    {
        return _data.find(make_pair(val,Y()));
    }
    iterator find_right(Y const &val)
    {
        return std::find_if(_data.begin(), _data.end(), 
            [&val](key_type const &kt)
        {
            return Ycomp()(kt.second, val);
        });
    }
    iterator end()   { return _data.end();   }
    iterator begin() { return _data.begin(); }
};

#endif

Ejemplo de uso

template<typename X, typename Y, typename In>
void PrintBimapInsertion(X const &x, Y const &y, In const &in)
{
    if (in.second) {
        std::cout << "Inserted element (" 
              << in.first->first << ", " << in.first->second << ")/n";
    }
    else {
        std::cout << "Could not insert (" << x << ", " << y 
                      << ") because (" <<  in.first->first << ", " 
                      << in.first->second << ") already exists/n";
    }
}


int _tmain(int argc, _TCHAR* argv[])
{
    bimap<std::string, int> mb;
    PrintBimapInsertion("A", 1, mb.insert("A", 1) );
    PrintBimapInsertion("A", 2, mb.insert("A", 2) );
    PrintBimapInsertion("b", 2, mb.insert("b", 2));
    PrintBimapInsertion("z", 2, mb.insert("z", 2));

    auto it1 = mb.find_left("A");
    if (it1 != mb.end()) {
        std::cout << std::endl << it1->first << ", " 
                      << it1->second << std::endl;
    }

    auto it2 = mb.find_right(2);
    if (it2 != mb.end()) {
        std::cout << std::endl << it2->first << ", " 
                      << it2->second << std::endl;
    }

    return 0;
}

NOTA : Todo esto es un bosquejo de código aproximado de lo que sería una implementación completa e incluso después de pulir y extender el código, no estoy implicando que esto sería una alternativa para boost::bimap sino simplemente una forma casera de tener un contenedor asociativo se puede buscar tanto por el valor como por la clave.

Ejemplo en vivo

Answer 5

Una posible implementación que utiliza una estructura de datos intermedia y una indirección es:

int sz;  // total elements in the bimap

std::map<A, int> mapA;
std::map<B, int> mapB;

typedef typename std::map<A, int>::iterator iterA;
typedef typename std::map<B, int>::iterator iterB;

std::vector<pair<iterA, iterB>> register;  
// All the operations on bimap are indirected through it.

Inserción

Supongamos que tiene que insertar (X, Y) donde X, Y son instancias de A y B respectivamente, luego:

1. Insertar (X, sz) en el mapA --- O (lg sz)
2. Insertar (Y, sz) en mapB --- O (lg sz)
3. Luego push_back (IterX, IterY) en el register --- O (1). Aquí IterX e IterY son iteradores del elemento correspondiente en mapA y mapB y se obtienen de (1) y (2) respectivamente.

Buscar

Buscar la imagen de un elemento, X, de tipo A:

1. Obtenga el int mapeado a X en mapA . --- O (lg n)
2. Usa el int para indexar en el register y obtén el IterY correspondiente. --- O (1)
3. Una vez que tienes IterY, puedes obtener Y a través de IterY->first . --- O (1)

Entonces ambas operaciones se implementan en O (lg n).

Espacio : todas las copias de los objetos de A y B deben almacenarse solo una vez. Sin embargo, hay muchas cosas de contabilidad. Pero cuando tienes objetos grandes, eso tampoco sería muy significativo.

Nota : Esta implementación se basa en el hecho de que los iteradores de un mapa nunca se invalidan. Por lo tanto, los contenidos del register son siempre válidos.

Una versión más elaborada de esta implementación se puede encontrar here

Answer 6

Boost Bimap hace uso de Boost Mutant Idiom .

Desde la página wikipedia vinculada:

La expresión idiomática de Boost hace uso de reinterpret_cast y depende en gran medida de la suposición de que los diseños de memoria de dos estructuras diferentes con miembros de datos idénticos (tipos y orden) son intercambiables. Aunque el estándar de C ++ no garantiza esta propiedad, prácticamente todos los compiladores lo satisfacen.

template <class Pair>
struct Reverse
{
    typedef typename Pair::first_type  second_type;
    typedef typename Pair::second_type first_type;
    second_type second;
    first_type first;
};

template <class Pair>
Reverse<Pair> & mutate(Pair & p)
{
  return reinterpret_cast<Reverse<Pair> &>(p);
}

int main(void)
{
  std::pair<double, int> p(1.34, 5);

  std::cout << "p.first = " << p.first << ", p.second = "  << p.second << std::endl;
  std::cout << "mutate(p).first = " << mutate(p).first << ", mutate(p).second = "  << mutate(p).second << std::endl;
}

La implementación en las fuentes de impulso es, por supuesto, bastante más peluda.