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

Question

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

Что бы вы порекомендовали?

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

Answer 1

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

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

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

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

Поскольку ваша рецензия упоминает «координаты» в качестве ключей, вам также может быть интересно прочитать предложения на Самый быстрый способ узнать, если 3D-координата уже используется .

Answer 2

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

Answer 3

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