алгоритмы lower_bound/ upper_bound
как работает эти lower_bound/ upper_bound с предикатом на следующей задаче ? есть файлик phone.txt. вот с такими данными :
John Doe 345 9483
Nick Bohnam 349 2930
Jane Doe 283 5219
Andrey Gurenkov 899 4423
John Brix 159 4107
необходимо прочитать файл в вектор и найти строчку c John при помощи lower_bound/ upper_bound. Код ниже . при этом я не могу понять:
- верно ли я составил предикаты same и оператор <
- если я сортирую по возрастанию, тогда в силу того , что поиск будет бинарным я должен наверно сделать выбор в пользу одной из : lower_bound/ upper_bound. Другая работать не будет. Какую я должен выбрать ?
- :) в моем коде не работает ни lower_bound/ upper_bound.
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <sstream>
#include <vector>
struct dat {
std::string name;
std::string fname;
int code;
int num;
bool operator<(const dat& r) {
if (name == r.name) return fname < r.fname; else return name < r.name;
}
};
std::ifstream phone("phone.txt");
/* phone.txt :
John Doe 345 9483
Nick Bohnam 349 2930
Jane Doe 283 5219
Andrey Gurenkov 899 4423
John Brix 159 4107
*/
std::string str;
std::vector<dat> DATA;
bool operator<(const dat& l, const dat& r) {
if (l.name == r.name) return l.fname < r.fname; else return l.name < r.name;
}
bool same(const dat& l, const dat& r) {
if (!(l < r) && !(r < l))
return true;
else
return false;
};
int main()
{
while (getline(phone, str)) {
std::istringstream tmp(str);
std::string name;
std::string fname;
int code;
int num;
tmp >> name >> fname >> code >> num;
DATA.push_back({ name,fname,code,num });
}
sort(DATA.begin(), DATA.end());
dat find({ "John" });
std::vector<dat>::iterator fnd= lower_bound(DATA.begin(), DATA.end(), find, same);
if (fnd != DATA.end()) std::cout << fnd->name << fnd->fname << std::endl;
else std::cout << "not found";
}
Источник: Stack Overflow на русском