Лучший контейнер для двойной индексации

Question

Каков наилучший способ (на C++) создать контейнер для двукратного индексирования? В частности, у меня есть список объектов, каждый из которых индексируется ключом (возможно, несколькими ключами). Это подразумевает мультимап. Проблема с этим, однако, заключается в том, что это означает, что, возможно, хуже, чем линейный поиск, чтобы найти местоположение объекта. Я бы предпочел избежать дублирования данных, поэтому, чтобы каждый объект поддерживал свою собственную координату и должен был перемещаться по карте, было бы плохо (не говоря уже о том, что перемещение вашего собственного объекта может косвенно вызвать вашего деструктора в то время как в функции-члене!). Я предпочел бы некоторый контейнер, который поддерживает индекс как указателем на объект, так и координатой, и что сами объекты гарантируют стабильные ссылки/указатели. Затем каждый объект может хранить итератор в индексе (включая координату), достаточно абстрагироваться и знать, где он находится. Boost.MultiIndex кажется лучшей идеей, но это очень страшно, и я не хочу, чтобы мои фактические объекты нуждались в const.

Что вы посоветуете?

EDIT: Boost Bimap кажется приятным, но обеспечивает ли он стабильное индексирование? То есть, если я изменяю координату, ссылки на другие элементы должны оставаться действительными. Причина, по которой я хочу использовать указатели для индексирования, состоит в том, что объекты в противном случае не имеют внутреннего порядка, и указатель может оставаться постоянным, пока объект изменяется (что позволяет использовать его в Boost MultiIndex, который, IIRC, обеспечивает стабильную индексацию).

Answer 1

Я делаю несколько предположений на основе вашей рецензии:

• Ключи дешевы, чтобы скопировать и сравнить
• Там должна быть только одна копия объекта в системе
• тот же ключ может обратитесь ко многим объектам, но только одному объекту соответствует данный ключ (один ко многим)
• Вы хотите иметь возможность эффективно искать, какие объекты соответствуют заданному ключу, и какая клавиша соответствует данному объекту

Я хотел бы предложить:

• Используйте связанный список или какой-либо другой контейнер, чтобы поддерживать глобальный список всех объектов в системе. Объекты размещаются в связанном списке.
• Создайте один std::multimap<Key, Object *>, который отображает ключи указателей объектов, указывая на единственное каноническое местоположение в связанном списке.
• Выполните одно из:
  • Создать один std::map<Object *, Key>, что позволяет глядя вверх ключ, прикрепленный к определенному объекту. Убедитесь, что ваш код обновляет эту карту при изменении ключа. (Это также может быть std::multimap, если вам нужно отношение «многие ко многим».)
  • Добавить переменную-член в Object, которая содержит текущий Key (позволяющий искать O (1)). Убедитесь, что ваш код обновляет эту переменную при изменении ключа.

Поскольку ваша рецензия упоминается «координаты» в качестве ключей, вы также можете быть заинтересованы в чтении предложения в Fastest way to find if a 3D coordinate is already used.

Answer 2

Его трудно понять, что именно вы с ним делаете, но похоже, что форсирование bimap - это то, что вы хотите. Это в основном повышает мультииндекс, за исключением конкретного варианта использования, и проще в использовании. Это позволяет быстро искать на основе первого элемента или второго элемента. Почему вы просматриваете местоположение объекта на карте по его адресу? Используйте абстракцию и позволяйте ей делать всю работу за вас. Просто примечание: итерация по всем элементам на карте равна O (N), поэтому было бы гарантировано, что O (N) (не хуже), чтобы посмотреть, как вы думаете, как это сделать.

Answer 3

Одним из вариантов было бы использовать две std :: maps, на которые ссылаются shared_ptrs. Нечто подобное может получить ты:

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: Я просто заметил, что требование Multimap, это по-прежнему выражает идею, так что я оставлю его.