День добрый !
Есть задачка: имеется структура

нужно хранить в некоем контейнере такие структуры, но только уникальные.
Т.е. чтобы выполнялось условие (псевдокод)

вроде бы идеально подходит std::set, но он требует operator< для структуры, а меня это не устраивает по двум причинам:
1. Мне совершенно не важно, будут ли структуры храниться в отсортированном виде, т.к. их количество будет 20...30 и добавление в контейнер будет происходить только в начале программы. А время поиска конкретного элемента для данной задачи совершенно не критично.
2. Я не знаю как сравнить две структуры на предмет меньше ли одна или нет, т.к. оба поля в принципе равнозначны.

Смотрел на QSet (Qt), но он требует ф-цию хеша из моей структуры, а я тем более не представляю, как её сделать...

Можно, конечно, повелосипедировать: аггрегировать вектор и написать ф-цию добавления и поиска... но хочется сначала выяснить, нет ли готового решения

Спасибо.

P.S. boost просьба не предлагать соответствующего coder'а прошу не обижаться 

Это сообщение отредактировал(а) borisbn - 24.6.2011, 10:41

Если есть поддержка C++0x

а для него хеш не нужно реализовывать?   

Это сообщение отредактировал(а) Sahab - 24.6.2011, 10:51

Точно... это же не POD.
Спасибо за поправку.

мне только непонятно... если 


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

потому что a и b - несут независимую информацию
например а - масса, b - высота
какой объект больше? - тот что тяжелее, или выше?

в принципе, я уже дошёл до этого, но, т.к. мне действительно не важно, то можно и return true сделать...
то, что можно так заюзать set - я уже понял (мало того, уже сделал), но хотелось бы выяснить не будет ли это overhead'ом? Нет ли стандартного (специально обученного, заточенного) решения для этой задачи.

ни в коем случае.

azesmcar, спасибо. Я правильно понял, что return true нельзя, т.к. set (ну или там алгоритмы поиска - не важно) может вместо operator== создать собственный

и тогда он просто не найдёт нужный мне элемент, а при return false будет всегда находить первый ?

Что тогда посоветуете ?

P.S. Откуда цитата ?

Это сообщение отредактировал(а) borisbn - 24.6.2011, 13:21

Это неправильно, нужно так: 

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

Есть много случаев, когда упорядочивание нужно чисто для хранения. 
Логический смысл тогда не важен, главное, чтобы упорядочивание было однозначным и непротиворечивым.
Если POD, как у тебя, и не содержит double, тогда я не парюсь, а просто использую memcmp. Условие, которое привел
azesmcar, автоматически выполняется. Кстати, можно тогда не писать свой == (потому что он уже есть - !< && !>).

Кстати, если определить свою структуру через std::pair (вместо именованных членов), то оператор сравнения генерируется автоматически, именно как я написала. Естественно, если сравнение для членов не определено, возникают проблемы...
Другое дело, если стандартный оператор < не подходит, как например для даблов... 

Для засовывания в хэш-контейнеры таких структур (из 2 чисел, можно и double) использую комбинацию с простыми числами, типа

Могут быть и другие числа (не помню уже откуда, давно содрала и с тех пор счастливо использую); разбрасывает замечательно, даже если точки близки.
Но только имей в виду, что хэш обычно жрет памяти побольше, чем просто map\set. Если это важно.

Earnest, я для примера вривёл 2 поля. На самом деле у меня их 6. Представляешь, что за монстр получится в операторе < ?


не то, чтобы можно, а бессмысленно, т.к., судя по всему, std::set использует только меньше. Говорю это потому, что определил только оператор меньше, и у меня всё скомпилялось и добавление и поиск...

это и ежу понятно...
но в данном контексте это было не важно

важно
Sahab, 

тем, что если a1 < a2, а b1 > b2, то обе структуры будут считаться больше другой. Может и зацикливание произойти.


Это сообщение отредактировал(а) borisbn - 24.6.2011, 14:24

Скомпилировалось - не значит правильно работает. Чего бы не скомпилироваться, если формальный синтаксис соблюден.
Еще раз, приведенный в самом начале оператор < - неправильный, потому что не транзитивный. Можешь нарваться не сразу, и будешь долго ломать голову, откуда лажа.
Грубо говоря, даже уникальность хранения может нарушаться при таком операторе: все зависит от того, в каком состоянии будет дерево и по какому пути пойдет сравнение.
Если членов много, и это POD, можно использовать memcmp, как я писала.

set действительно использует только "меньше". Я имела в виду, что может сравнение на равенство нужно тебе зачем-то еще. 


Да не намного страшнее, чем оператор проверки равенства - принцип тот же, упорядочиваешь по первой, если она равна - по второй и т.д.
Только удобнее записать немного по-другому:

Ну или хэш-контейнеры использовать.

хммммм. а ведь идея:


Добавлено через 9 минут и 19 секунд

это то понятно (чай не первый раз замужем). под "скомпилировалось" я имел в виду, что std::set больше ничего не требует. и не более того.


теперь ясно. нет. не нужен.


тогда такой вопрос: