Miglior contenitore per la doppia indicizzazione

Question

Qual è il modo migliore (in C++) per impostare un container permettendo a doppia indicizzazione?In particolare, ho una lista di oggetti, ognuno dei quali indicizzato da una chiave (probabilmente più per tasto).Questo implica un multimap.Il problema con questo, però, è che significa che forse sarà peggio-di-lineare di ricerca per trovare la posizione di un oggetto.Preferirei evitare la duplicazione dei dati, in modo da avere ogni oggetto a mantenere il proprio coordinare e disporre di spostarsi nella mappa sarebbe male (per non parlare che muove il proprio oggetto può indirettamente chiamare il distruttore, mentre in una funzione membro!).Vorrei piuttosto un contenitore che mantiene un indice sia dal puntatore all'oggetto e coordinare, e che gli oggetti stessi garanzia di riferimenti stabili/puntatori.Quindi ogni oggetto può memorizzare un iteratore all'indice (comprese le coordinate), sufficientemente astratto, e sanno dove si trova.Boost.MultiIndex sembra l'idea migliore, ma è molto spaventoso e io non wany il mio attuale oggetti devono essere const.

Che cosa mi consiglia?

EDIT:Boost Bimap sembra bello, ma non fornisce stabile di indicizzazione?Cioè, se io cambio le coordinate, i riferimenti ad altri elementi deve rimanere valido.Il motivo per cui voglio utilizzare i puntatori per l'indicizzazione è perché gli oggetti sono altrimenti no intrinseca di ordinazione, e un puntatore può rimanere costante, mentre l'oggetto di modifiche (che permette il suo utilizzo in una Spinta MultiIndex, che, IIRC, fornisce stabile di indicizzazione).

Answer 1

Sto facendo diverse ipotesi sulla base del tuo articolo:

• Le chiavi sono a buon mercato, di copia e di confronto
• Ci dovrebbe essere solo una copia dell'oggetto nel sistema
• La stessa chiave può riferirsi a molte cose, ma solo un oggetto corrisponde a un determinato tasto (uno-a-molti)
• Si vuole essere in grado di in modo efficiente cercare degli oggetti che corrispondono a un determinato tasto e il tasto che corrisponde ad un determinato oggetto

Io suggerirei:

• Utilizzare una lista collegata o qualche altro contenitore per mantenere un elenco globale di tutti gli oggetti del sistema.Gli oggetti sono allocati sulla lista collegata.
• Creare una std::multimap<Key, Object *> che mappe chiavi di puntatori a oggetti, che punta alla singola posizione canonica nella lista collegata.
• Fare uno di questi:
  • Creare una std::map<Object *, Key> che permette di ricercare il tasto collegato a un particolare oggetto.Assicurarsi che il codice che aggiorna la mappa quando la chiave viene modificata.(Questo potrebbe anche essere un std::multimap se avete bisogno di una molti-a-molti relazione).
  • Aggiungere una variabile membro della Object che contiene la corrente Key (permettendo O(1) ricerche).Assicurarsi che il codice gli aggiornamenti di questa variabile quando la chiave viene modificata.

Dal momento che il documento citato "coordinate", come le chiavi, si potrebbe anche essere interessati a leggere i suggerimenti al Modo più veloce per trovare se le coordinate 3D è già utilizzato.

Answer 2

La sua difficile capire che cosa esattamente si sta facendo con esso, ma sembra come boost bimap è ciò che si desidera.Si tratta fondamentalmente di aumentare multi-indice ad eccezione di un caso specifico utilizzo e la facilità d'uso.Consente una ricerca rapida in base al primo elemento o il secondo elemento.Perché cerchi la posizione di un oggetto in una mappa da il suo indirizzo?Utilizzare l'astrazione e lasciar fare tutto il lavoro per voi.Solo una nota:iterazione su tutti gli elementi in una mappa è O(N), e così si sarebbe garantito O(N) (e peggio) per cercare il modo di pensare di farlo.

Answer 3

Una possibilità potrebbe essere quella di utilizzare due std::mappe di riferimento shared_ptrs.Qualcosa come questo può farti andare:

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

Edit:Ho appena notato il multimap requisito, questo esprime ancora l'idea quindi lascio.