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

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

вроде бы идеально подходит 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 больше ничего не требует. и не более того.


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


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

А зачем что-то копировать?
Просто memcmp (this, &that, sizeof (*this)); вполне достаточно.
Если у тебя там есть не POD члены или даблы или указатели или виртуальные функции (ну, последнее вроде не должно мешать, но я обычно все равно делю), то нужно отделить суп от мух: т.е. сделать POD-структуру с простыми полями, которую включить в класс (или унаследоваться). Это по-любому не вредно для дизайна - отделять простые POD-структуры от сложных

как справедливо заметил volatile в другой теме из-за мусора при выравнивании такое лучше не использовать. Мало того, мне не по всем полям сравнивать надо.


есть (QString), но ради оператора < дробить структуру на две (типа базовая cо сравниваемыми POD'ами и наследник с QString'ом и доп.полями)... ну, может и имеет смысл, но как-то слишком замысловато IMHO

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

из стандарта.


согласен с Earnest по поводу хэш контейнеров.

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

Или так: здесь key - это указатель на строку, идем до ее конца, для массива интов сам напишешь.

Смысл в том, чтобы все хорошенько перемешать. На самом деле, в качестве хэша можно возвращать любое целое число - хоть константу, работать будет (но медленно: свалит все в одну корзину). Или просто использовать одно из твоих полей, наиболее часто меняющееся. Или два.

Добавлено через 3 минуты и 27 секунд

Да, верно, просто я у тебя только инты видела...  видимо, для примера упростил. Кроме того, я обычно POD-структурам делаю базовую инициализацию (ZeroMemory), а уже потом поля пихаю. И никакого мусора.

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

Ну хотя бы подряд ты их расположить можешь? Т.е. стринг либо сзаду, либо спереду, и сравнивать блок. Есть ведь оператор получения офсета мембера - что-то вроде offsetof.

упс. до 25.3 Sorting and related operations как-то не добрался. остановился на std::set и find


хммм... будет работать ??? тогда буду пробовать. да мне быстро и не надо.


уговорили 

спасибо ещё раз всем

тему пока не закрываю - проверю всё - отпишусь.

будет  только сложность будет линейной.


Это сообщение отредактировал(а) azesmcar - 24.6.2011, 15:17

Это только теоретически. А как реализован конкретный контейнер - хз, может и чего-нибудь выкинуть, а я потом виновата буду.
Кроме того, это эквивалентно линейному списку без всякого упорядочивания - т.е. линейный поиск. Для этого дела хэш-контейнер и заводить не стоит.
Короче, это была шутка.   
И я ведь привела тебе пример, как хэш строить.

ну, что ж, уподобимся янки - ВАУ, Работает ! 

я уже говорил, что скорость мне не важна, и можно и руками сделать, но

в принципе hash за небольшим оверхедом - и есть такое решение. исчо раз спасибо.


могу сказать про себя - ты точно не будешь виноватой. Я ж понимаю, что совет на форуме - это хорошо, а проверять, проверять и ещё раз проверять © самизнаетекто - никто не отменял.

Я тут подумал - даже теоретически не важно, как реализован контейнер (главное, чтоб без ошибок), т.к. ведь может такое случиться, что ключи у двух разных структур пересекутся.... А где у двух, там и у трёх, четырёх ---> у всех  Та не, должна работать константа. Тем более такая, как 42 

Не, я так не могу... это же вопиющее нарушение мировой гармонии! Даже если 42!
Вот зачем я тебе про константу сказала! Количество мирового зла в виде кривого кода возросло, а тепловая смерть вселенной и так не за горами... Надеюсь, ты просто попробовал, а делать будешь нормально...

спасибо. В какой-нить другой задаче обязательно воспользуюсь. В данной конкретной у меня будут 20..30 (ну может 50) уникальных структур. А поиск будет инициироваться по кнопке. СтОит ли заморачиваться ?

ну заведи вектор тогда, зачем использовать хэш контейнер не по назначению?  

Над ним обёртки нужны. Не то, чтобы лень писать (делов то - полчаса с отладкой, да и, возможно, так и сделаю в итоге), просто хотелось узнать нет ли решения, которое идеально мне подходит. Убедился, что нет. Тоже результат 

всё-таки решил повелосипедировать, т.к. готового решения конкретно этой задачи нет...
вот что получилось



http://liveworkspace.org/code/33a67804f759...f03796f9ec3c230

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

да уж, зачем это надо? почему бы просто не проверять существование элемента при вставке?