Форум программистов, компьютерный форум CyberForum.ru

std::sort + std::lower_bound - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.62
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
23.01.2012, 22:26     std::sort + std::lower_bound #1
тема такая: есть класс person:
C++
1
2
3
4
5
class Person{
private:
    string name_;
    string adress_;
    long phone_;
есть вектор объектов этого класса. надо сделать быстрый поиск по полям этого класса в векторе
решил делать сортировку вектора с предикатами по каждому полю, слияния, а потом lower_bound
C++
1
2
3
4
5
void search_name(string name){
        std::sort(pV.begin(),pV.end(),compare_name);
        vector<Person>::iterator i=lower_bound(pV.begin(),pV.end(),Person(name,"",0));
        cout<<*i<<endl;
        }
предикат:
C++
1
2
3
bool compare_name(Person& obj1,Person& obj2){
    return obj1.get_name()<obj2.get_name();
}
сортировка работает только по имени, и при любом вводе выдает первый элемент. как исправить?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.01.2012, 22:26     std::sort + std::lower_bound
Посмотрите здесь:

C++ std::sort()
Сортировка индексов алгоритмом std::sort C++
C++ algorithm std::sort
Отличие std::sort От std::qsort C++
C++ std::sort
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
23.01.2012, 22:39     std::sort + std::lower_bound #2
Цитата Сообщение от Healius Посмотреть сообщение
сортировка работает только по имени
Оно и понятно, ведь предикат у вас сравнивает имена.

Цитата Сообщение от Healius Посмотреть сообщение
при любом вводе выдает первый элемент
lower_bound выдаёт первую позицию в последовательности, в которую можно вставить его третий аргумент так, чтобы последовательность осталась отсортированной. Вы уверены, что вам именно этот эффект нужен?
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
23.01.2012, 22:41     std::sort + std::lower_bound #3
не совсем понятно что вы хотите сделать. скажу лишь что критерии сортировки и поиска должны совпадать для правильной работы алгоритма.
если интервал отсортирован по имени, то быстрый поиск будет правильно работать если предикат проверяет эквивалентность имен, а не других полей или их кобминацию.
при сортировке интервала по имени, аглоритм быстрого поиска по адресу или номеру телефона работать не будет.
более академично это звучит так:
критерии эквивалентности для элементов при сортировке и поиске должны совпадать.
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
23.01.2012, 22:41  [ТС]     std::sort + std::lower_bound #4
вопрос с сортировкой по полям решил

мне нужен быстрый поиск. идея в том что если итератор i - результат lower_bound, то (i++) - искомый элемент
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
23.01.2012, 22:44     std::sort + std::lower_bound #5
Healius, почему бы не использовать std::binary_search после сортировки? Зачем изобретать велосипед?
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
23.01.2012, 22:45  [ТС]     std::sort + std::lower_bound #6
silent_1991, так binary_search же булевский и выдает в результате есть ли искомый элемент, а не его самого?

ЗЫ: да, я в алгоритмах не очень
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
23.01.2012, 22:49     std::sort + std::lower_bound #7
Healius, да, действительно, запамятовал это... Ну тогда вы всё правильно делали, нужно использовать std::lower_bound.
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
23.01.2012, 22:53  [ТС]     std::sort + std::lower_bound #8
silent_1991, проблема в том что в результате lower_bound всегда указывает на первый элемент в отсортированном векторе.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
23.01.2012, 22:56     std::sort + std::lower_bound #9
Healius, приведите здесь исходный вектор и искомый элемент.
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
23.01.2012, 22:58  [ТС]     std::sort + std::lower_bound #10
silent_1991, Петров,Иванов,Сергеев,Козлов,Яковлев,Исаенко,Артемов
ищу допустим Козлова
возвращает Артемова
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
23.01.2012, 22:58     std::sort + std::lower_bound #11
так не получится. lower_bound ищет первый элемент, не старшый указанному.
например есть последовательность. 12356. мы ищем 4. так вот вернется итератор на тройку. iterator++ будет указывать на пятерку. а мы искали 4.
нужно использовать equal_range и сравнивать полученные итераторы. если они не равны, значит мы нашли что искали. если нет, то не нашли.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
23.01.2012, 23:06     std::sort + std::lower_bound #12
Вообще, вот что скажу. Если нужен быстрый поиск - выкидываем к чёрту вектор и юзаем std::set. Ну а если быстрый не нужен - std::find в руки и вперёд.
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
23.01.2012, 23:09  [ТС]     std::sort + std::lower_bound #13
DU,
C++
1
2
3
4
5
6
7
    void search_name(string name){
        std::sort(pV.begin(),pV.end(),compare_name);
        //print(pV);
        pair<vector<Person>::iterator,vector<Person>::iterator> i=equal_range(pV.begin(),pV.end(),Person(name,"",0));
        if(i.first==i.second)
            cout<<*(i.first)<<endl;
    }
все равно в результате выдает первый элемент отсортированного вектора

Добавлено через 2 минуты
silent_1991, так set же изначально отсортирован по какому то одному признаку, ибо на красно-черных деревьях, а мне надо по трем разным. это придется или 3 сета делать, или переделывать каждый раз при поиске.
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
23.01.2012, 23:13     std::sort + std::lower_bound #14
1. я сперва маленько описался. если мы нашли что-то то итераторы будут отличатся. причем i.first
2. потом еще раз криво написал про то, что lower_bound вернет итератор на тройку
будет указывать на первый нужный из найденного интервала.
потом у вас критерии сортировки и поиска разные.
критерий сортировки: compare_name.
критерий поиска: operator < (const Person&, const Person&); // вроде должен у вас быть такой.
если критерии отличаются, то поиск не будет корректным.
в общем с этими критериями все хитрожопо.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main ()
{
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(5);
  v.push_back(6);
 
  vector<int>::iterator l = std::lower_bound(v.begin(), v.end(), 4);
  vector<int>::iterator u = std::upper_bound(v.begin(), v.end(), 4);
 
  std::cout << *l << std::endl;
  std::cout << *u << std::endl;
 
  return 0;
}
этот код печатает две пятерки.
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
23.01.2012, 23:20  [ТС]     std::sort + std::lower_bound #15
DU,
C++
1
2
3
    bool Person::operator<(const Person &obj)const{
        return this->name_<obj.name_;
    }
это критерий поиска, в классе Person прописан
C++
1
2
3
4
5
6
7
    void search_name(string name){
        std::sort(pV.begin(),pV.end(),compare_name);
        vector<Person>::iterator i=std::lower_bound(pV.begin(),pV.end(),Person(name,"",0));
        vector<Person>::iterator j=std::upper_bound(pV.begin(),pV.end(),Person(name,"",0));
        cout<<*i<<endl;
        cout<<*j<<endl;
    }
печатает два раза первый элемент отсортированного вектора ("Артемов") хотя ищу "Сергеев"
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
23.01.2012, 23:42     std::sort + std::lower_bound #16
ну хз что у вас. вот такой код работает как надо
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main ()
{
  typedef vector<string> Vector;
  typedef Vector::iterator Iterator;
 
  Vector v;
  v.push_back("aa");
  v.push_back("bb");
  v.push_back("cc");
  v.push_back("ee");
  v.push_back("ff");
 
  Iterator l = lower_bound(v.begin(), v.end(), string("cc"));
  Iterator u = upper_bound(v.begin(), v.end(), string("cc"));
 
  cout << *l << endl; // печатает сс
  cout << *u << endl; // печатает ee
 
  return 0;
}
Раз итераторы у вас равны, алгоритм не нашел то, что вы ищете.
Раз итераторы указывают на Алехина, значит Сергеев должен был бы быть перед Алехиным (с точки зрения алгоритма).
Либо я что-то не вижу, либо сортировка с кирилицей вот такие фокусы показывает (типа символ C в этой кодировке предшествует символу А).
У вас Сергеев в контейнере точно присутствует? Проверте правильность задания имен в коде. А то ведь может оказаться так, что вместо русской буквы С вы написали латинскую С. Один раз долго искал подобную ошибку.
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
23.01.2012, 23:47  [ТС]     std::sort + std::lower_bound #17
DU, да, с латинскими символами все работает! спасибо!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.01.2012, 00:02     std::sort + std::lower_bound
Еще ссылки по теме:

Абстрактный класс и std::sort C++
Сортировка списка с использованием std::sort C++
Сортировка массива c++ std :: sort() C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
silent_1991
24.01.2012, 00:02     std::sort + std::lower_bound
  #18

Не по теме:

Тьфу ты, я даже внимание не обратил на то, что русские символы используются

Yandex
Объявления
24.01.2012, 00:02     std::sort + std::lower_bound
Ответ Создать тему
Опции темы

Текущее время: 04:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru