Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > std::set find, insert - работа


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

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

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

Автор: IKM2007 25.8.2009, 17:25
Цитата(Killerman @  25.8.2009,  17:10 Найти цитируемый пост)
А как функция определяет, что эти объекты равны или не равны?

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

Добавлено через 4 минуты и 29 секунд
Цитата(Killerman @  25.8.2009,  17:10 Найти цитируемый пост)
то объект при вставке(insert) не повторяется

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

Цитата(Killerman @  25.8.2009,  17:10 Найти цитируемый пост)
или при поиске find найден подходящий объект

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

Автор: mes 25.8.2009, 17:47
Цитата(Killerman @  25.8.2009,  16:10 Найти цитируемый пост)
Это типа в объекте нада перегрузить фуекцию operator == ?

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


bool is_equal (const A& lhs, const A& rhs)
{
     return ! (lhs < rhs || rhs < lhs); 
}

 smile 

Автор: Killerman 25.8.2009, 18:17
спасибо. попробую

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

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

Автор: andrew_121 27.8.2009, 01:30
Цитата(Killerman @  27.8.2009,  00:54 Найти цитируемый пост)
Это нормально?

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

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

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

Автор: andrew_121 27.8.2009, 01:50
Посмотри на это: http://www.google.ru/search?hl=ru&newwindow=1&q=hash+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<> в стандарт не входит.

Автор: azesmcar 27.8.2009, 08:44
Цитата(Killerman @  27.8.2009,  00:54 Найти цитируемый пост)
Я в шоке! при 100 объектах в массиве set.find по ключу int ищет на 2-ве секунды дольше чем при последовательном переборе. Это нормально?


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

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

Автор: Killerman 27.8.2009, 15:05
Код примерно такой:

Код

//класс для поиска
    class less_myClass
  {      
   public:
      bool operator() (SetObj * c1, SetObj * c2)
    {
         return (c1->i < c2->i);
    }      
 };


std::set<SetObj *,less_myClass> arrayofSetObj;


//потом вставка идет как:

arrayofSetObj.insert(PtrsetObj1);

//а поиск как:

std::set<SetObj *,less_myClass>::const_iterator Iter1 = arrayofSetObj.find(PtrsetObj2);
if(Iter == arrayofSetObj.end())
   return false;



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

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

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

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

Автор: azesmcar 27.8.2009, 15:13
Killerman

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

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

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

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

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

Автор: mes 27.8.2009, 15:51
Цитата(Killerman @  27.8.2009,  14:42 Найти цитируемый пост)
только в list вместо find перебирались все элементы и сравнивались с одним, и еще в list вставлялись в конце, а в set - через insert )

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

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

Автор: azesmcar 27.8.2009, 15:54
Killerman

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

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

Автор: livo 5.7.2011, 12:34
Всем привет! Есть один вопрос по множеству. Нужно провести создание множества уникальних ключей и соответствующих им объектов. Но как подобрать уникальний ключ? В общем, у меня вот так это сделано:
Код

unsigned __fastcall TS::Create(TSu **pptr)
{
 //создаем объект для вставки в множество
 TSetEl se;
 se.id=1;
 se.ptr_su=new TSu;//связанный объект
 se.ptr_su->OnChange=on_change_su;
 while(sus.find(se)!=sus.end())se.id++;//подбираем уникальный ключ
 TSus::iterator i=sus.insert(se).first;//вставляем
 //возврат данных
 if(pptr)*pptr=i->ptr_su;
 changed=1;
 return se.id;
}

Но мне хотелось бы иначе оформить вставку. Ну например:
Код

//...
while(!sus.insert(se).second)se.id++;
//...

А как получить указатель на вставленный объект? Может есть какой-то тип итераторов, чтобы сохранить возвращенное значение функцией insert?

Автор: boostcoder 5.7.2011, 12:39
livo, не хорошо постить в чужую тему. при том, теме уже около двух лет ;)

Добавлено через 1 минуту и 1 секунду
Цитата(livo @  5.7.2011,  12:34 Найти цитируемый пост)
создание множества уникальних ключей и соответствующих им объектов

http://cplusplus.com/reference/stl/map/ ?

Автор: livo 5.7.2011, 13:21
Цитата(boostcoder @  5.7.2011,  12:39 Найти цитируемый пост)
не хорошо постить в чужую тему

Учту.
Цитата(boostcoder @  5.7.2011,  12:39 Найти цитируемый пост)
std::map

Похоже здесь есть сразу то, что мне надо. Отличный вариант!
Ну а по множеству... Есть ли все-таки подходящий тип итераторов для сохранения результата функции insert множества?

Автор: boostcoder 5.7.2011, 13:25
Цитата(livo @  5.7.2011,  13:21 Найти цитируемый пост)
Есть ли все-таки подходящий тип итераторов для сохранения результата функции insert множества?

ну так insert и возвращает тебе пару, в которой есть и итератор указывающий на вставленный элемент: http://cplusplus.com/reference/stl/set/insert/

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)