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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.62
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
#1

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

23.01.2012, 22:26. Просмотров 3013. Ответов 20
Метки нет (Все метки)

тема такая: есть класс 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::qsort - C++
Пишу доклад по программированию, собственно выбрал тему сортировок. вот сейчас хочу расписать отлчиие + и - двух сортировок. но инфу...

Не воспринимает ни std::cout, ни std::cin. Вобщем ничего из std. Также не понимает iostream - C++
Здравствуйте! Я хотел начать изучать язык C++. Набрал литературы. Установил Microsoft Visual C++ 2005 Express Edition. Образ диска...

ошибка error: cannot convert 'std::string {aka std::basic_string<char>}' to 'std::string* {aka std::basic_stri - C++
на вод поступают 2 строки типа string. определить количество вхождений строки 2 в строку 1 ошибка error: cannot convert 'std::string {aka...

STL std::set, std::pair, std::make_pair - C++
Я не знаю как описать тему в двух словах, поэтому не обращайте внимание на название темы. Собственно перейдем к нашим баранам: есть...

На основе исходного std::vector<std::string> содержащего числа, создать std::vector<int> с этими же числами - C++
подскажите есть вот такая задача. Есть список . Создать второй список, в котором будут все эти же числа, но не в виде строк, а в виде...

std::sort - C++
Достоинства и недостатки делаю таблицу, достоинств и недостатков std::Sort. собственно, не нащёл нечего про это в википедии

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
23.01.2012, 22:39 #2
Цитата Сообщение от Healius Посмотреть сообщение
сортировка работает только по имени
Оно и понятно, ведь предикат у вас сравнивает имена.

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

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

ЗЫ: да, я в алгоритмах не очень
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
23.01.2012, 22:49 #7
Healius, да, действительно, запамятовал это... Ну тогда вы всё правильно делали, нужно использовать std::lower_bound.
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
23.01.2012, 22:53  [ТС] #8
silent_1991, проблема в том что в результате lower_bound всегда указывает на первый элемент в отсортированном векторе.
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
23.01.2012, 22:56 #9
Healius, приведите здесь исходный вектор и искомый элемент.
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
23.01.2012, 22:58  [ТС] #10
silent_1991, Петров,Иванов,Сергеев,Козлов,Яковлев,Исаенко,Артемов
ищу допустим Козлова
возвращает Артемова
DU
1483 / 1059 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
23.01.2012, 22:58 #11
так не получится. lower_bound ищет первый элемент, не старшый указанному.
например есть последовательность. 12356. мы ищем 4. так вот вернется итератор на тройку. iterator++ будет указывать на пятерку. а мы искали 4.
нужно использовать equal_range и сравнивать полученные итераторы. если они не равны, значит мы нашли что искали. если нет, то не нашли.
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
23.01.2012, 23:06 #12
Вообще, вот что скажу. Если нужен быстрый поиск - выкидываем к чёрту вектор и юзаем std::set. Ну а если быстрый не нужен - std::find в руки и вперёд.
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
23.01.2012, 23:09  [ТС] #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
1483 / 1059 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
23.01.2012, 23:13 #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  [ТС] #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;
    }
печатает два раза первый элемент отсортированного вектора ("Артемов") хотя ищу "Сергеев"
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.01.2012, 23:20
Привет! Вот еще темы с ответами:

std::sort() - C++
Доброго времени суток! Есть некая структура: struct member { int latency; std::vector&lt;int&gt;child; };

algorithm std::sort - C++
Почему так делать нельзя? #include &lt;algorithm&gt; using namespace std; class T { private: int arr;

Сортировка массива c++ std :: sort() - C++
Дан двумерный массив символов char M, надо отсортировать его при помощи std :: sort(), построчно, т.е. допустим было 00011 11111 ...

Абстрактный класс и std::sort - C++
Добрый день, Не компилируется строка: std::vector&lt;mtl::io::QtFile*&gt; *vec; ... mtl::misc::Sort(vec); // ЭТА СТРОКА ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
23.01.2012, 23:20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru