4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
|
||||||||||||||||
1 | ||||||||||||||||
std::sort + std::lower_bound23.01.2012, 22:26. Показов 6217. Ответов 20
Метки нет (Все метки)
тема такая: есть класс person:
решил делать сортировку вектора с предикатами по каждому полю, слияния, а потом lower_bound
0
|
23.01.2012, 22:26 | |
Ответы с готовыми решениями:
20
Отличие std::sort От std::qsort Не воспринимает ни std::cout, ни std::cin. Вобщем ничего из std. Также не понимает iostream ошибка error: cannot convert 'std::string {aka std::basic_string<char>}' to 'std::string* {aka std::basic_stri STL std::set, std::pair, std::make_pair |
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
23.01.2012, 22:39 | 2 |
Оно и понятно, ведь предикат у вас сравнивает имена.
lower_bound выдаёт первую позицию в последовательности, в которую можно вставить его третий аргумент так, чтобы последовательность осталась отсортированной. Вы уверены, что вам именно этот эффект нужен?
1
|
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
|
|
23.01.2012, 22:41 | 3 |
не совсем понятно что вы хотите сделать. скажу лишь что критерии сортировки и поиска должны совпадать для правильной работы алгоритма.
если интервал отсортирован по имени, то быстрый поиск будет правильно работать если предикат проверяет эквивалентность имен, а не других полей или их кобминацию. при сортировке интервала по имени, аглоритм быстрого поиска по адресу или номеру телефона работать не будет. более академично это звучит так: критерии эквивалентности для элементов при сортировке и поиске должны совпадать.
0
|
4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
|
|
23.01.2012, 22:41 [ТС] | 4 |
вопрос с сортировкой по полям решил
мне нужен быстрый поиск. идея в том что если итератор i - результат lower_bound, то (i++) - искомый элемент
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
23.01.2012, 22:44 | 5 |
Healius, почему бы не использовать std::binary_search после сортировки? Зачем изобретать велосипед?
0
|
4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
|
|
23.01.2012, 22:45 [ТС] | 6 |
silent_1991, так binary_search же булевский и выдает в результате есть ли искомый элемент, а не его самого?
ЗЫ: да, я в алгоритмах не очень
1
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
23.01.2012, 22:49 | 7 |
Healius, да, действительно, запамятовал это... Ну тогда вы всё правильно делали, нужно использовать std::lower_bound.
0
|
4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
|
|
23.01.2012, 22:53 [ТС] | 8 |
silent_1991, проблема в том что в результате lower_bound всегда указывает на первый элемент в отсортированном векторе.
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
23.01.2012, 22:56 | 9 |
Healius, приведите здесь исходный вектор и искомый элемент.
0
|
4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
|
|
23.01.2012, 22:58 [ТС] | 10 |
silent_1991, Петров,Иванов,Сергеев,Козлов,Яковлев,Исаенко,Артемов
ищу допустим Козлова возвращает Артемова
0
|
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
|
|
23.01.2012, 22:58 | 11 |
так не получится. lower_bound ищет первый элемент, не старшый указанному.
например есть последовательность. 12356. мы ищем 4. так вот вернется итератор на тройку. iterator++ будет указывать на пятерку. а мы искали 4. нужно использовать equal_range и сравнивать полученные итераторы. если они не равны, значит мы нашли что искали. если нет, то не нашли.
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
23.01.2012, 23:06 | 12 |
Вообще, вот что скажу. Если нужен быстрый поиск - выкидываем к чёрту вектор и юзаем std::set. Ну а если быстрый не нужен - std::find в руки и вперёд.
1
|
4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
|
||||||
23.01.2012, 23:09 [ТС] | 13 | |||||
DU,
Добавлено через 2 минуты silent_1991, так set же изначально отсортирован по какому то одному признаку, ибо на красно-черных деревьях, а мне надо по трем разным. это придется или 3 сета делать, или переделывать каждый раз при поиске.
0
|
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
|
||||||
23.01.2012, 23:13 | 14 | |||||
1. я сперва маленько описался. если мы нашли что-то то итераторы будут отличатся. причем i.first
2. потом еще раз криво написал про то, что lower_bound вернет итератор на тройку будет указывать на первый нужный из найденного интервала. потом у вас критерии сортировки и поиска разные. критерий сортировки: compare_name. критерий поиска: operator < (const Person&, const Person&); // вроде должен у вас быть такой. если критерии отличаются, то поиск не будет корректным. в общем с этими критериями все хитрожопо.
1
|
4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
|
|||||||||||
23.01.2012, 23:20 [ТС] | 15 | ||||||||||
DU,
0
|
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
|
||||||
23.01.2012, 23:42 | 16 | |||||
ну хз что у вас. вот такой код работает как надо
Раз итераторы указывают на Алехина, значит Сергеев должен был бы быть перед Алехиным (с точки зрения алгоритма). Либо я что-то не вижу, либо сортировка с кирилицей вот такие фокусы показывает (типа символ C в этой кодировке предшествует символу А). У вас Сергеев в контейнере точно присутствует? Проверте правильность задания имен в коде. А то ведь может оказаться так, что вместо русской буквы С вы написали латинскую С. Один раз долго искал подобную ошибку.
2
|
4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
|
|
23.01.2012, 23:47 [ТС] | 17 |
DU, да, с латинскими символами все работает! спасибо!
0
|
silent_1991
|
24.01.2012, 00:02
#18
|
Не по теме: Тьфу ты, я даже внимание не обратил на то, что русские символы используются :wall:
0
|
0 / 0 / 0
Регистрация: 10.12.2016
Сообщений: 4
|
|
12.01.2017, 08:09 | 19 |
Как мне узнать местоположение какого-то елемента на множестве(set)?
0
|
Любитель чаепитий
|
||||||
12.01.2017, 10:56 | 20 | |||||
0
|
12.01.2017, 10:56 | |
12.01.2017, 10:56 | |
Помогаю со студенческими работами здесь
20
На основе исходного std::vector<std::string> содержащего числа, создать std::vector<int> с этими же числами Std::begin() ,std::end(),std::copy Std::bind, std::mem_fun, std::mem_fn std::sort Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |