алгоритмы lower_bound/ upper_bound

Рейтинг: 0Ответов: 0Опубликовано: 06.02.2023

как работает эти 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. Код ниже . при этом я не могу понять:

  1. верно ли я составил предикаты same и оператор <
  2. если я сортирую по возрастанию, тогда в силу того , что поиск будет бинарным я должен наверно сделать выбор в пользу одной из : lower_bound/ upper_bound. Другая работать не будет. Какую я должен выбрать ?
  3. :) в моем коде не работает ни 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";
}

Ответы

Ответов пока нет.