El mejor contenedor para doble indexación

Question

¿Cuál es la mejor manera (en C++) de configurar un contenedor que permita la doble indexación?Específicamente, tengo una lista de objetos, cada uno indexado por una clave (posiblemente varias por clave).Esto implica un mapa múltiple.El problema con esto, sin embargo, es que significa una búsqueda posiblemente peor que lineal para encontrar la ubicación de un objeto.Prefiero evitar la duplicación de datos, por lo que sería malo que cada objeto mantenga sus propias coordenadas y tenga que moverse en el mapa (¡sin mencionar que mover su propio objeto puede llamar indirectamente a su destructor mientras está en una función miembro!).Preferiría algún contenedor que mantenga un índice tanto por puntero de objeto como por coordenadas, y que los propios objetos garanticen referencias/punteros estables.Entonces cada objeto podría almacenar un iterador del índice (incluida la coordenada), suficientemente abstraído, y saber dónde está.Boost.MultiIndex parece la mejor idea, pero da mucho miedo y no quiero que mis objetos reales deban ser constantes.

¿Qué recomendarías?

EDITAR:Boost Bimap parece bueno, pero ¿proporciona una indexación estable?Es decir, si cambio la coordenada, las referencias a otros elementos deben seguir siendo válidas.La razón por la que quiero usar punteros para la indexación es porque los objetos no tienen un orden intrínseco, y un puntero puede permanecer constante mientras el objeto cambia (lo que permite su uso en un Boost MultiIndex, que, IIRC, proporciona una indexación estable).

Answer 1

Estoy haciendo varias suposiciones basadas en su artículo:

• Las claves son baratas de copiar y comparar.
• Sólo debe haber una copia del objeto en el sistema.
• La misma clave puede referirse a muchos objetos, pero solo un objeto corresponde a una clave determinada (uno a muchos)
• Desea poder buscar de manera eficiente qué objetos corresponden a una clave determinada y qué clave corresponde a un objeto determinado.

Yo sugeriría:

• Utilice una lista vinculada o algún otro contenedor para mantener una lista global de todos los objetos del sistema.Los objetos se asignan en la lista vinculada.
• Crea uno std::multimap<Key, Object *> que asigna claves a punteros de objetos, apuntando a la única ubicación canónica en la lista vinculada.
• Haz uno de:
  • Crea uno std::map<Object *, Key> que permite buscar la clave adjunta a un objeto en particular.Asegúrese de que su código actualice este mapa cuando se cambie la clave.(Esto también podría ser un std::multimap si necesita una relación de muchos a muchos).
  • Agregar una variable miembro al Object que contiene la corriente Key (permitiendo búsquedas O(1)).Asegúrese de que su código actualice esta variable cuando se cambie la clave.

Dado que su artículo mencionó "coordenadas" como claves, es posible que también le interese leer las sugerencias en La forma más rápida de saber si ya se utiliza una coordenada 3D.

Answer 2

Es difícil entender qué estás haciendo exactamente con él, pero parece un impulso. bimapa es lo que quieres.Básicamente, se trata de impulsar el índice múltiple, excepto en un caso de uso específico, y es más fácil de usar.Permite una búsqueda rápida basada en el primer elemento o el segundo elemento.¿Por qué buscas la ubicación de un objeto en un mapa por su dirección?Utilice la abstracción y deje que ella haga todo el trabajo por usted.Solo una nota:la iteración sobre todos los elementos en un mapa es O(N), por lo que se garantizaría O(N) (no peor) para buscar la forma en que está pensando hacerlo.

Answer 3

Una opción sería utilizar dos std::maps que hicieran referencia ashared_ptrs.Algo como esto puede ayudarte:

template<typename T, typename K1, typename K2>
class MyBiMap
{
public:
    typedef boost::shared_ptr<T> ptr_type;

    void insert(const ptr_type& value, const K1& key1, const K2& key2)
    {
        _map1.insert(std::make_pair(key1, value));
        _map2.insert(std::make_pair(key2, value));
    }

    ptr_type find1(const K1& key)
    {
        std::map<K1, ptr_type >::const_iterator itr = _map1.find(key);
        if (itr == _map1.end())
            throw std::exception("Unable to find key");
        return itr->second;
    }

    ptr_type find2(const K2& key)
    {
        std::map<K2, ptr_type >::const_iterator itr = _map2.find(key);
        if (itr == _map2.end())
            throw std::exception("Unable to find key");
        return itr->second;
    }

private:
    std::map<K1, ptr_type > _map1;
    std::map<K2, ptr_type > _map2;
};

Editar:Acabo de notar el requisito de mapas múltiples, esto todavía expresa la idea, así que lo dejaré.