Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.63/30: Рейтинг темы: голосов - 30, средняя оценка - 4.63
4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
1

std::sort + std::lower_bound

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

Author24 — интернет-сервис помощи студентам
тема такая: есть класс 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();
}
сортировка работает только по имени, и при любом вводе выдает первый элемент. как исправить?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.01.2012, 22:26
Ответы с готовыми решениями:

Отличие std::sort От std::qsort
Пишу доклад по программированию, собственно выбрал тему сортировок. вот сейчас хочу расписать...

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

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

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

20
Эксперт С++
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
23.01.2012, 22:39 2
Цитата Сообщение от Healius Посмотреть сообщение
сортировка работает только по имени
Оно и понятно, ведь предикат у вас сравнивает имена.

Цитата Сообщение от Healius Посмотреть сообщение
при любом вводе выдает первый элемент
lower_bound выдаёт первую позицию в последовательности, в которую можно вставить его третий аргумент так, чтобы последовательность осталась отсортированной. Вы уверены, что вам именно этот эффект нужен?
1
DU
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
DU
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,
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 сета делать, или переделывать каждый раз при поиске.
0
DU
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&); // вроде должен у вас быть такой.
если критерии отличаются, то поиск не будет корректным.
в общем с этими критериями все хитрожопо.

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;
}
этот код печатает две пятерки.
1
4 / 4 / 2
Регистрация: 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;
    }
печатает два раза первый элемент отсортированного вектора ("Артемов") хотя ищу "Сергеев"
0
DU
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
23.01.2012, 23:42 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 в этой кодировке предшествует символу А).
У вас Сергеев в контейнере точно присутствует? Проверте правильность задания имен в коде. А то ведь может оказаться так, что вместо русской буквы С вы написали латинскую С. Один раз долго искал подобную ошибку.
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
Любитель чаепитий
3742 / 1798 / 566
Регистрация: 24.08.2014
Сообщений: 6,016
Записей в блоге: 1
12.01.2017, 10:56 20
Цитата Сообщение от AIMP Посмотреть сообщение
Как мне узнать местоположение какого-то елемента на множестве(set)?
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <set>
#include <algorithm>
 
int main()
{
    std::set<int> s{ 1, 2, 3, 4, 5, 6, 0 };
    auto it = s.find(0);
    std::cout << std::distance(s.begin(), it) << '\n';
    it = s.find(3);
    std::cout << std::distance(s.begin(), it) << '\n';
}
Только вот нафига это нужно?
0
12.01.2017, 10:56
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.01.2017, 10:56
Помогаю со студенческими работами здесь

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

Std::begin() ,std::end(),std::copy
...// int main() { std::vector&lt;double&gt; data;//Работает cout &lt;&lt; std::begin(data); ...

Std::bind, std::mem_fun, std::mem_fn
В чем разница между функциями std::bind, std::mem_fun, std::mem_fn?

std::sort
Достоинства и недостатки делаю таблицу, достоинств и недостатков std::Sort. собственно, не...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru