[C/C++]отношение один к одному

multimap, не?

Только у нее поиск вроде как уже не O(ln(n)), или гоню?

Еще как варант ТС-у можно предложить держать 2 мапа, по 1 в каждом направлении, и ручками поддерживать их когерентное состояние, правда тогда уже по хорошему надо оборачивать value в обьекты обеспечивающие единичную копию данных с подсчетом ссылок, тобишь в tr1::shared_ptr

Как раз нет. Там для каждго <key> может быть несколько <value>, что мне совсем не нужно.

А, я просто не совсем понял что нужно.

Насчет 2-х мапов уже думал. Только памяти уйдет в 2 раза больше, а это все для embeded, так что с лишней памятью там не особо.

Два мапа, в качестве значения хранить указатель на элемент во втором map'е. Изврат + получается 2 указателя на пару, но ничего лучше придумать сходу не могу.

Если сильно припрет, то в бусте есть Bimap - что вам надо

К сожалению, ради одного Bimap'а такую огромную библиотеку добавлять в проект совсем не хочется. Может быть есть что-то более легкое?

Может оказаться, что всё не так страшно. Оно разве не header-only?

> в качестве значения хранить указатель на элемент во втором map'е

по яйцам надо за такое бить

bcp примените и посмотрите что на деле.

> К сожалению, ради одного Bimap'а такую огромную библиотеку добавлять в проект совсем не хочется. Может быть есть что-то более легкое?

Не факт, что оно будет намного тяжелее stl'овских контейнеров.

В С делают просто.
Один объект - пара <key,value> помещается сразу в две мапы - в одну для сортировки по ключу, в другую - для сортировки по значению.
Наподобие:
struct _my_pair {
struct _rbtree_entry key_tree_entry;
struct _rbtree_entry value_tree_entry;
struct _key key;
struct _value value;
};
Ну а далее осталось реализовать функции по вставке, удалению, поиску и т.д., короче например см. linux-2.6.35/include/linux/rbtree.h и linux-2.6.35/lib/rbtree.c или любую другую реализацию красно-черного дерева.
По скорости - не хуже std::map, по памяти - лучше.
Вообще, такой подход позволяет запихнуть один объект во много разных спиков и мап.