Существует ли более эффективная реализация для двунаправленной карты?

Ответ 1

Существует определенная проблема с двойным хранением ваших данных во всех простых реализациях бимапа. Если вы можете разбить его на бимак указателей снаружи, то вы можете легко проигнорировать это и просто сохранить обе карты формы std::map<A*,B*>, как уже предлагал Аркаитц Хименес (хотя, вопреки его ответу, вы должны заботиться о хранилище от снаружи, чтобы избежать поиска A->A*). Но если у вас есть указатели в любом случае, почему бы просто не сохранить std::pair<A,B> в том месте, где вы в противном случае хранили бы A и B отдельно?

Было бы неплохо иметь std::map<A,B*> вместо std::map<A*,B*>, поскольку это позволило бы, например, искать элемент, связанный с строкой, с помощью вновь созданной строки с тем же содержимым вместо указателя на исходную строку, которая создал пару. Но принято хранить всю копию ключа с каждой записью и полагаться только на хэш, чтобы найти нужное ведро. Таким образом, возвращаемый элемент будет правильным даже в случае хэш-столкновения...

Если вы хотите, чтобы это было быстро и грязно, есть этот

хакерское решение:

Создайте две карты std::map<size_t, A> mapA и std::map<size_t, B> mapB. После вставки хеш оба элемента, которые нужно вставить, чтобы получить ключи к соответствующим картам.

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

Поиск выполняется аналогично.

Используя multimap вместо map и проверяя каждый элемент, который вы получаете с помощью поиска по другой карте (получите кандидат B из mapA, хеш B и посмотрите mapB, если он соответствует желаемому ключу, итерации к следующему кандидату b в противном случае), это действительная реализация, но по-прежнему хакерская по моему мнению...

Вы можете получить гораздо более приятное решение, используя копии элементов, которые используются для сравнения записей (см. выше) как хранилище. Это немного тяжелее, чтобы обдумать это. Чтобы уточнить:

более приятное решение:

Создайте два набора пар как std::set<pair<A, B*>> и std::set<pair<B, A*>> и перегрузите operator< и operator==, чтобы принять во внимание только первый элемент пары (или предоставить соответствующий класс сравнения). Необходимо создавать наборы пар вместо карт (которые внешне выглядят одинаково), потому что нам нужна гарантия того, что A и B всегда будут находиться в одинаковых положениях в памяти. При вставке pair<A,B> мы разбиваем его на два элемента, которые вписываются в указанные выше множества.

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

Теперь поиск можно просто выполнить простым поиском std::set и разыменованием указателя.

Это более приятное решение похоже на решение, которое увеличивает использование - хотя они используют некоторые аннонизированные указатели как второстепенные элементы пар и, следовательно, должны использовать reinterpret_cast s.

Обратите внимание, что пара элементов .second должна быть изменчивой (поэтому я не уверен, что std::pair можно использовать), или вам нужно добавить еще один слой абстракции (std::set<pair<B, A**>> mapA) даже для этого простого вставки. В обоих решениях вам нужны временные элементы для возврата неконстантных ссылок на элементы.

Ответ 2

Было бы более удобно хранить все элементы в векторе и иметь 2 карты <T1*,T2*> и <T2*,T1*> таким образом, чтобы у вас не было всего, что было скопировано дважды.

Как я вижу, вы пытаетесь сохранить 2 вещи, сами элементы и отношения между ними, если вы нацелены на скалярные типы, вы можете оставить их как 2 карты, но если вы нацелены на лечение сложных типов, это делает больше смысла отделять хранилище от отношений и обрабатывать отношения вне хранилища.

Ответ 3

Boost Bimap использует Boost Mutant Idiom.

Из связанной страницы wikipedia:

Идущий мутант Boost использует reinterpret_cast и сильно зависит от предположения, что макеты памяти двух разных структур с идентичными элементами данных (типы и порядок) взаимозаменяемы. Хотя стандарт С++ не гарантирует этого свойства, практически все компиляторы удовлетворяют этому.

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

Реализация в форсированных источниках, конечно, довольно волосатая.

Ответ 4

Если вы создаете набор пар для ваших типов std::set<std::pair<X,Y>>, вы в значительной степени реализуете свою функциональность и правила относительно мутабилити и константы preset (возможно, настройки не то, что вы хотите, а твики могут быть сделаны). Итак, вот код:

#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

Использование примера

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

ПРИМЕЧАНИЕ. Все это примерный эскиз кода того, что было бы полной реализацией, и даже после полировки и расширения кода я не подразумеваю, что это будет альтернативой boost::bimap, но просто home способ иметь ассоциативный контейнер, который можно найти как по значению, так и по ключу.

Живой пример

Ответ 5

Одна возможная реализация, использующая промежуточную структуру данных и косвенную:

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.

Вставка

Предположим, вам нужно вставить (X, Y), где X, Y - экземпляры A и B соответственно, затем:

• Вставить (X, sz) в mapA --- O (lg sz)
• Вставить (Y, sz) в mapB --- O (lg sz)
• Затем push_back (IterX, IterY) в register --- O (1). Здесь IterX и IterY являются итераторами соответствующего элемента в mapA и mapB и получаются из (1) и (2) соответственно.

Поиск

Поиск изображения элемента X, типа A:

• Получите int, сопоставленный с X в mapA. --- O (lg n)
• Используйте int для индексации в register и получите соответствующий IterY. --- O (1)
• Как только у вас есть IterY, вы можете получить Y через IterY->first. --- O (1)

Итак, обе операции реализованы в O (lg n).

Пробел. Все копии объектов A и B должны храниться только один раз. Существует, однако, много бухгалтерского материала. Но когда у вас есть большие объекты, это также будет незначительным.

Примечание. Эта реализация основана на том факте, что итераторы карты никогда не признаются недействительными. Следовательно, содержимое register всегда справедливо.

Более сложную версию этой реализации можно найти здесь

Ответ 6

Как насчет этого?

Здесь мы избегаем двойного хранения одного типа (T1). Другой тип (T2) сохраняется еще дважды.

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