Как использвать lower_bound и upper_bound для поиска по интервалу?

Question

Имеется map, нужно с помощью двух функций lower_bound и upper_bound задать интервал поиска для ключевых значений.

#include <iostream>
#include <map>
#include <locale.h>
#include <stdlib.h>
using namespace std;

int main()
{
    //Одноаспектный поиск по совпадению
    setlocale(LC_ALL, "RUS");
    struct info
    {
        int numbers[2]; //значение объёма массива для всех значений должен быть const
        char CHAR;
    };
    char name;
    int i, n;
    map <char, info> mp = { {'H', {1 , 5, 'h'}}, 
                            {'K', {2 , 3, 'k'}},
                            {'A', {2 , 4, 'a'}},
                            {'C', {5 , 6, 'c'}},
                            {'D', {9 , 0, 'd'}},
                            {'S', {3 , 4, 's'}} };

    cin >> name;
    for (i = 0; i <= 2-1; i++)
        cout << mp[name].numbers[i] << " ";
    cout << mp[name].CHAR;
    //Одноаспектный поиск по интервалу  
    
    return 0;
}

Answer 1

Как известно std::map содержит элементы с уникальным ключом(не более одного элемента с тем же ключом). Поэтому для поиска не имеет смысла попытка нахождения нижней и верхней границы элементов с одинаковым ключом.

Но если все же хотите проводить испытания, то нужно помнить, что std::lower_bound ищет элемент, не меньший указанного объекта, а std::upper_bound найдет первый элемент, который точно больше. То есть, если алгоритм std::lower_bound вернул итератор For, указывающий не за конец карты, то std::upper_bound для std::map вернет ++For, так что тут использование сразу двух алгоритмов есть бессмысленная трата времени. Но все же, вернемся к вашему вопросу. Насколько я понял, вы хотите что то вроде:

   //порядок аргументов предикатов важен
   auto   pred1 = 
    [](const std::pair<char, info> p, const char key)
    { return p.first < key; };
   auto   pred2 = 
    [](const char key, const std::pair<char, info> p)
    {return  key < p.first; };
//для удобства записи, определим макрос
#define ARGS  mp.begin(), mp.end(), name  
    auto 
    lb = std::lower_bound(ARGS, pred1),
    ub = std::upper_bound(ARGS, pred2);
#undef ARGS
    if (lb != mp.end())
        cout << "info  corresponding to the key\n"
        << lb->second.numbers[0] << ' '
        << lb->second.numbers[1]
        << ' ' << lb->second.CHAR;
    if (ub != mp.end())
        cout  << "\ninfo from next object\n"
        << ub->second.numbers[0] << ' ' 
        << ub->second.numbers[1]
        << ' ' << ub->second.CHAR;

БЛОГ НА HUSL

Как использвать lower_bound и upper_bound для поиска по интервалу?

Ответы (1 шт):