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

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

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

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

Со связанной страницы википедии:

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

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

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

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

#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 но просто домашний способ иметь ассоциативный контейнер для поиска как по значению, так и по ключу.

Живой пример

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

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 соответственно, затем:

1. Вставить (X, SZ) в mapA — O (LG SZ)
2. Вставить (Y, SZ) в mapB — O (LG SZ)
3. затем push_back (IterX, IterY) в register — O (1). Здесь IterX и IterY являются итераторами для соответствующего элемента в mapA а также mapB и получены из (1) и (2) соответственно.

Уважать

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

1. Получить Int сопоставлен с X в mapA, — O (LG N)
2. Используйте int для индексации register и получите соответствующую IterY. — O (1)
3. Если у вас есть IterY, вы можете получить Y через IterY->first, — O (1)

Таким образом, обе операции реализованы в O (LG N).

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

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

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

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

Здесь мы избегаем двойного хранения одного типа (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_;
};