Здравствуйте.
Нужно в контейнере set произвести поиск объектов. 
Но встроенный std::set::find не устраивает, т.к. он ищет точное соответствие по ключу, а мне нужно определённое мной сравнение.
У меня при поиске два объекта будут равны друг другу, если поля double d  обоих объектов отличаются друг от друга не более, чем на 50%.
Как это сделать? Заранее спасибо.
***
В принципе я могу использовать find_if из algorithm, но тогда я потеряю логарифмическое время поиска в сравнении с std::set::find, чего не хотелось бы...



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

•  Переделываешь bool operator<(const CompoundObject &lhs, const CompoundObject &rhs)  что бы сравнение по вещественной части было в конце
•  Вычисляешь диапазон CompoundObject :: d для поиска
•  С помощью lower_bound ищешь начало объектов в set
•  Далее линейный перебором шагаешь до конца диапазона

Это сообщение отредактировал(а) xvr - 23.11.2009, 14:20

достигается за счет того, что элементы в set уже упорядочены по определенному (заданному Вами!) закону. для использования другого способа упорядочения c сохранением эффективного поиска потребуется построить новую структуру данных.
если задача поиска по разным критериям имеет систематический характер, можно использовать boost::multi_index.

если в данном случае сравнение с 50% точностью должно производиться всегда, то достаточно модифицировать 

на 



Это сообщение отредактировал(а) baldina - 23.11.2009, 14:22

В таком случае придется set заменить на multiset, т.к. ключи начнут дублироваться

согласен, начнут. но по определению zim22 это означает что ключи одинаковы, а если нет разницы, зачем хранить больше?   
кстати, алгоритм с поиском lower_bound имеет трудоемкость O(n); худший случай, когда все ключи отличаются не более чем на 50%. 

если знать задачу поподробней, можно было бы подумать как лучше организовать

они эквивалентны при выборе подходящих вариантов обмена квартир. однако в самом set дубликаты не допускаются.

без проблем  





Это сообщение отредактировал(а) zim22 - 23.11.2009, 14:43

ну, дык, оно самое.  и есть ключ. дубликатов не будет: карточка либо добавляется, либо выводится и удаляется.
т.е. оператор сравнения должен сравнивать количество комнат и этажность точно, а площадь с 10% точностью.

Добавлено через 1 минуту и 15 секунд
zim22, где такие программы заставляют писать? прост любопытно

Добавлено через 5 минут и 29 секунд
вообще-то задание либо не полно, либо противоречиво. дело в том, что при вводе (by design, ввиду требования использовать set) производится поиск карточки; при совпадении ключей добавления не будет. с другой стороны при поиске выводится единственный вариант.
это скорее всего означает, что поиск варианта и ввод суть одна операция.

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

никто не заставляет. это я нашёл на просторах интернета лабораторную из института. мне она понравилась - я решил реализовать 
я таким способом проверяю свой прогресс в С++ - спустя пару месяцев потом посмотрю на эту лабу и если захочется плеваться от кода - значит всё нормально, иначе - это плохо, т.к. ничего нового я за это время не узнал.


Это сообщение отредактировал(а) zim22 - 23.11.2009, 15:07

Это означает, что поиск вернет ВСЕ ключи. Так что тут O(n) скорее всего не применимо. В общем случае все же будет log(n)

в задании не сказано... 
ну тогда искать стандартным find-ом или, как предложил xvr, слегка оптимизировать процесс, в среднем поиск будет эффективнее, чем линейный.

2xvr, 

если поиск вернет все ключи, то алгоритм затратит линейное время: алгоритм не может иметь зависимость времени работы меньше, чем объем обрабатываемых данных. если требуется вывести n ключей, то алгоритм не может затратить времени меньше, чем с*n.
что такое "в общем"? есть понятия в лучшем, худшем и среднем случае. в среднем, возможно (и так кажется интуитивно), будет порядок роста log(N), однако это требует доказательства.

M bsa

zim22, вопросы тебе, думаю, следует задавать в другом разделе, а то тебе ответить могут только форумчане со статусом не ниже "опытный". А новички так вообще не поймут.

Это сообщение отредактировал(а) bsa - 23.11.2009, 15:50

некрасиво. если действительно в результате получается диапазон, то lower_bound/upper_bound дают результат наиболее эффективно, это простое и красивое решение.

хорошо. буду перебираться в "С++ общие вопросы" 

Алгоритм должен ВЕРНУТЬ все ключи. А это значит, что каким бы он не был, ему придется их перебрать все. Т.е. данный случай - вырожденный. При ЛЮБОМ алгоритме поиска будет затрачено O(n) времени для ВОЗВРАТА ключей.

Можно разделить процедуру на 2 части: поиск начала возвращаемых данных и перебор для собственно возврата данных. Первая часть делается за log(n) (для lower_bound) и зависит от алгоритма поиска, вторая не зависит от алгоритма поиска а целиком зависит от данных.

Угу, поиск начала - log(n), а выдача значений от алгоритма не зависит (хотя она и O(n))

Я имел в виду эффективность поиска, это приблизительно 'в среднем случае'

хороший вариант. мне нравится.

только как я понял, все рассуждения базируются на этом:

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

но код мне показался слишком громоздким и я от них отказался в пользу этого: