lower_bound () в C ++ - PullRequest
Новая
       9

lower_bound () в C ++

1 голос
/ 23 марта 2020

Из чтения из Inte rnet я понимаю, что метод lower_bound() в C ++ используется для возврата итератора, указывающего на первый элемент в диапазоне [first, last), который имеет значение не меньше значения. Это означает, что функция возвращает индекс следующего наименьшего числа, которое больше этого числа.

Итак, для приведенного ниже кода я понял, что вывод равен 3. Но, поскольку есть повторение 6. Как Могу ли я получить индекс последних 6, используя lower_bound(). Я могу реализовать свой собственный binary_search() для этого, но я хочу знать, как это сделать, lower_bound(). 

#include <iostream> 
#include <algorithm>
#include <vector> 

using namespace std; 

int main () 
{ 
    int array[] = {5,6,7,7,6,5,5,6}; 

    vector<int> v(array,array+8); // 5 6 7 7 6 5 5 6 

    sort (v.begin(), v.end()); // 5 5 5 6 6 6 7 7 

    vector<int>::iterator lower,upper; 
    lower = lower_bound (v.begin(), v.end(), 6); 
    upper = upper_bound (v.begin(), v.end(), 6); 

    cout << "lower_bound for 6 at position " << (lower- v.begin()) << '\n'; 
    return 0; 
}

Ответы [ 4 ]

4 голосов
/ 23 марта 2020

Используйте пару lower_bound и upper_bound. Или один equal_range - это было бы более оптимальным.

И upper_bound, и верхняя часть equal_range будут после последней "6". Так же, как end не последний, он мимо последний.

1 голос
/ 23 марта 2020

Вы можете снова использовать lower_bound, обновляя начало и значение: 

auto lower = std::lower_bound (v.cbegin(), v.cend(), 6); 
auto upper = std::lower_bound (lower, v.cend(), 6 + 1);

std::cout << "Number of values found: " << std::distance(lower, upper) << '\n';
1 голос
/ 23 марта 2020

Если массив отсортирован, итерируя между lower_bound и upper_bound, вы получите все элементы, которые равны вашей точке вращения: 

lower = lower_bound(v.begin(), v.end(), 6);
upper = upper_bound(v.begin(), v.end(), 6);

for (auto it = lower; it != upper; it++) {
    assert(6 == *it);
}

Вопрос, который вы задаете, т. Е. Каков индекс last 6, не имеет соответствующей функции в стандартной библиотеке, поскольку плохо определено в случае, когда диапазон не содержит 6. Во всех других случаях, поскольку у вас есть контейнер произвольного доступа, вы можете получить итератор до последнего 6, удалив его из upper_bound (upper - 1 в вашем коде), так же, как вы получите последний индекс массива удалив 1 из длины. Тем не менее, я предлагаю вам избегать полагаться на положение последнего элемента равным при разработке вашего алгоритма Также обратите внимание, что если вам нужна нижняя и верхняя границы, вы можете получить оба одновременно с equal_range, который может даже работать лучше, потому что он может быть оптимизирован для обхода структуры данных только один раз: 

std::tie(lower,upper) = equal_range(v.begin(), v.end(), 6);

for (auto it = lower; it != upper; it++) {
    assert(6 == *it);
}
1 голос
/ 23 марта 2020

Вы можете использовать обратные итераторы в векторе, но затем, чтобы выполнить требование упорядочения для std::lower_bound, вам нужно инвертировать сравнение, поэтому вам нужно использовать std::greater вместо значения по умолчанию std::less. Это, однако, также означает, что теперь вы на самом деле ищете не нижнюю границу, а верхнюю границу относительно этой функции сравнения, поэтому: 

auto upper = std::upper_bound(v.rbegin(), v.rend(), 6, std::greater{});
...