контейнер один к одному

[Fat-Zer]

есть какой-нить готовый контейнер реализующий связь один к одному? что-то вроде QMap, только с быстрым поиском по значению и контролирующий единственность как ключа, так и значения.

На чём такой разумно было бы реализовывать?

[brankovic]

boost::bimap

[fuCtor]

А чем QMap не подходит?

iterator QMap::insert ( const Key & key, const T & value )

Inserts a new item with the key key and a value of value.

If there is already an item with the key key, that item's value is replaced with value.

If there are multiple items with the key key, the most recently inserted item's value is replaced with value.

Ну либо если не надо заменять, то можно проверку на наличие делать.

Остается лишь вопрос скорости.

[Fat-Zer]

boost::bimap

спасибо... с бустом пока не знаком, но давно хотел поковырять...

А чем QMap не подходит?

вы не поверите... тем что надо ручками проверять и скоростью

[Igors]

Хмм... А Вы можете пояснить как так: если нельзя вставить 1 ключ дважды,

If there is already an item with the key key, that item's value is replaced with value.

То откуда же возьмутся "multiple items with the key key" о которых говорится дальше ? 

If there are multiple items with the key key, the most recently inserted item's value is replaced with value.

вы не поверите... тем что надо ручками проверять и скоростью

Ну вероятно fuCtor имел ввиду 2 QMap (обратные ключ-значение). Это сделать несложно, но может получиться "жирно" (расходно) по ключам.

Кстати давно хотел посмотреть хорошую реализацию ключа-указателя... так что welcome

[Fat-Zer]

Хмм... А Вы можете пояснить как так: если нельзя вставить 1 ключ дважды,

If there is already an item with the key key, that item's value is replaced with value.

То откуда же возьмутся "multiple items with the key key" о которых говорится дальше ? 

If there are multiple items with the key key, the most recently inserted item's value is replaced with value.

следующая строчка в асистенте:

iterator QMap::insertMulti ( const Key & key, const T & value )
Inserts a new item with the key key and a value of value.

If there is already an item with the same key in the map, this function will simply create a new one. (This behavior is different from insert(), which overwrites the value of an existing item.)

Ну вероятно fuCtor имел ввиду 2 QMap (обратные ключ-значение). Это сделать несложно, но может получиться "жирно" (расходно) по ключам.

Кстати давно хотел посмотреть хорошую реализацию ключа-указателя... так что welcome

или так или каждый раз при добавление смотреть, нет ли элемента с таким значением в map'e. а при запросе - искать по значению.

[Karl-Philipp]

Fat-zer, а смотрел ли на QHash? Если да, то чем он не соответствует требованиям, указанным в первом твоем посте?

[Fat-Zer]

Fat-zer, а смотрел ли на QHash? Если да, то чем он не соответствует требованиям, указанным в первом твоем посте?

Так это же теже яица, что и QMap только через Хеш-таблицу. Притензии к нему теже.

[Karl-Philipp]

Fat-zer, а смотрел ли на QHash? Если да, то чем он не соответствует требованиям, указанным в первом твоем посте?

Так это же теже яица, что и QMap только через Хеш-таблицу. Притензии к нему теже.

Я, наверное, неправильно понял тебя, но в Assistant'e про QHash написано:

It stores (key, value) pairs and provides very fast lookup of the value associated with a key.

+

QHash provides faster lookups than QMap. (See Algorithmic Complexity for details.)

[Fat-Zer]

ты, наверное, не правильно понял асистент. он быстро ищет значение по ключу, а обратный поиск(QHash::key()) занимает много времени.

[Karl-Philipp]

наверное)

[fuCtor]

Пропустил пункт про уникальность и значения, тогда можно попробовать сделать финт ушами:
Своя структура, с перегруженным оператором сравнения: только использовать не полное совпадение обоих значений, а частичное. Тогда если если добавлять элемент AB а потом AC, то должен сказать что такое уже есть, и наоборот DC так же выдаст совпадение, а DE без проблем добавиться.
Поиск по ключу производится путем поиска структуры с пустым значением, для значения соответственно наоборот. Тогда может даже можно использовать и QSet.

Работоспособность подхода не проверял и как отразится на скорости пока не особо понятно.

[Igors]

Пропустил пункт про уникальность и значения, тогда можно попробовать сделать финт ушами:
Своя структура, с перегруженным оператором сравнения: только использовать не полное совпадение обоих значений, а частичное. Тогда если если добавлять элемент AB а потом AC, то должен сказать что такое уже есть, и наоборот DC так же выдаст совпадение, а DE без проблем добавиться.
Поиск по ключу производится путем поиска структуры с пустым значением, для значения соответственно наоборот. Тогда может даже можно использовать и QSet.

Работоспособность подхода не проверял и как отразится на скорости пока не особо понятно.

Какие-то сложности, почему не просто так:

Код

C++ (Qt)
struct CDataKey1 {
 bool operator == ( const CDataKey1 & sec ) const;  // сравнивает по 1-му ключу
 bool operator < ( const CDataKey1 & sec ) const;  // сравнивает по 1-му ключу
 
 const MyClass * mData;
};
 
struct CDataKey2 {
 bool operator == ( const CDataKey2 & sec ) const;  // сравнивает по 2-му ключу
 bool operator < ( const CDataKey2 & sec ) const;  // сравнивает по 2-му ключу
 
 const MyClass * mData;
};
 

Ну и те же 2 QSet - и все дела

[fuCtor]

Суть таже, только у меня один контейнер получался. Это уже кому как удобней.

[Fat-Zer]

fuCtor, не сработает... QSet'у нужна функция qHash() и на неё накладывается требование:
a==b => qHash(a)==qHash(b)
для AB==AC такое придупать не получится...
Igors, это может и сработает... в любом случае реализация на двух хеш-таблицах должна работать. Только надо будет причесать.

ЗЫ: Моя подзадача, это применение перестановки в прямом и обратном направлении.