У меня возник вопрос при работе с set. В нем для упорядочивания элементов по умолчанию вроде используется std::less, а если оно не устраивает, можно создать свой объект с функцией.

Я не могу понять как set определяет, что объект при вставке(insert) не повторяется. (или при поиске find найден подходящий объект)
По идее фукция ищет по упорядоченному списку объектов, и когда его не находит в set, то вставляет, иначе нет. А как функция определяет, что эти объекты равны или не равны?

Это типа в объекте нада перегрузить фуекцию operator == ?

Это сообщение отредактировал(а) Killerman - 25.8.2009, 17:12

Скорее функция определяет, эквивалентны элементы, или же нет. Равность и эквивалентность разные вещи.

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

Здесь проверяется отношение эквивалентности, критерием сравнения используется std::less<T>.


При find элементы сравниваются, то есть используется operator ==.

equal можно получить опираясь на less :

  

Это сообщение отредактировал(а) mes - 27.8.2009, 01:09

спасибо. попробую

Я в шоке! при 100 объектах в массиве set.find по ключу int ищет на 2-ве секунды дольше чем при последовательном переборе. Это нормально?

(имелось ввиду при множественном колличестве операций поиска)

Это сообщение отредактировал(а) Killerman - 27.8.2009, 01:06

Это ваще не нормально! Две секунды, для компа вечность  

ну это может на нескольких десятках тысяч операций поиска. точно не скажу. факт в том что ищет по дереву медленнее чем простым перебором в лоб. и что с этим делать?
может есть какой то другой адекватный класс может в другой библиотеке?

у меня в массиве указатели на объекты, а поиск нужно вести по элементу этих объектов (в данном случае по int члену класса).

Это сообщение отредактировал(а) Killerman - 27.8.2009, 01:38

Посмотри на это: http://www.google.ru/search?hl=ru&neww...ash+map+c%2B%2B
И в часности на это: http://www.epsilon-delta.net/code/hashmap.html

Добавлено @ 01:58
Если используешь компилятор от микрософт, посмотри на: http://msdn.microsoft.com/en-us/library/6x7w9f6z(VS.80).aspx
Я так понял, что hash_map<> в стандарт не входит.

Это сообщение отредактировал(а) andrew_121 - 27.8.2009, 01:58

Нет, это ненормально, в set поиск имеет логарифмическую сложность, а значит поиск в нем будет намного быстрее чем последовательный перебор (который имеет линейную сложность).

Покажи свой код.

Код примерно такой:

/////////////////////////////////////
Может просто объектов слишком мало в set (рост списка шел от 0-ля до 110), чтобы видить преимущество такого поиска.

Но у меня сначало был список не set, а vector, так при работе с вставкой и поиском суммарное время было большим, а когда я переделал в set - стало еще больше!!!

Может это связано и с тем что вставка в vector  идет быстро (в произвольном месте), а при вставке в set происходит тот же поиск как при set.find, чтобы вычеслить куда вставлять элемент.

Я считал общее время вставки и поиска, так как алгоритм сам создает элементы, вставляет их, потом ищет, сравнивает и т.д.

Killerman

Да, вставка в set медленнее чем в vector (если не учитывать reallocation-а в векторе), но вопрос был про поиск а не про вставку. 

что-то ты не договариваешь или не показываешь всего...покажи мне код, который у тебя на две секунды дольше работает, это с 110 элементами??? О каких секундах идет речь?  

Это весь код с использованием set. просто там закручены разные усдовия что типа если нашло - то делать то, если нет то то. Алгоритм программы не имеет отношения к реализации set и list.

если тупо заменить list на set, ничего не меняя больше (только в list вместо find перебирались все элементы и сравнивались с одним, и еще в list вставлялись в конце, а в set - через insert ) то программа с list выполняется 67 секунд, а с set 69.

Killerman, все прелести сложных объектов вроде set могут быть обнаружены при большом количестве объектов. А в большинстве случаев рекомендуется пользоваться vector.

  
Один мужик ищет под фонарем - рубль потерял. Другой вызвался ему помочь. 
Через некоторе время второй уточняет : " а где именно ты потерял ?".
Первый, показывая в даль рукой, говорит "где то там..."
Второй : "ну а почему мы здесь то ищем ?!"
Первый: "так тут светлей !.."

Это к слову о том, что обвиняя find, Вы забыли об упоминании inserta, который судя по всему и служит тормозом в вашем случае.



Это сообщение отредактировал(а) mes - 28.8.2009, 10:20

Killerman

1. Как я уже сказал - insert в list-е быстрее чем insert в set -е, но вопрос был про поиск, а поиск у set -а быстрее работает
2. Если говорят что алгоритм эффективнее, это не значит что он ВСЕГДА будет работать быстрее, если будешь искать элемент, который в списке первый, то линейный обход списка будет быстрее. 

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