Какая функция в библиотеке std предназначена для бинарного поиска вектора и поиска элемента?

У меня есть структура узла

struct Node{CString text, int id;};

в отсортированном векторе.

Мне интересно, есть ли в алгоритме функция, которая будет выполнять двоичный поиск вектора и находить элемент.

15.12.2008 18:07:50
Ты уверен насчет запятой между CString? Разве это не точка с запятой?
razeh 5.12.2013 02:25:07
4 ОТВЕТА
РЕШЕНИЕ

std::binary_search() скажет вам, если значение существует в контейнере.

std::lower_bound()/std::upper_bound() вернет итератор к первому / последнему вхождению значения.

Ваши объекты должны быть реализованы, operator<чтобы эти алгоритмы работали.

21
15.12.2008 19:21:09
или вам нужно использовать другую перегрузку для binary_searchи предоставить компаратор для 4-го параметра. Это должен быть тот же компаратор, который вы использовали для сортировки.
KitsuneYMG 4.03.2010 13:07:56
«В отличие от lower_bound, для upper_bound значение, указанное итератором, возвращаемое этой функцией, не может быть эквивалентным val, только больше». Как upper_bound может вернуть последнее вхождение val ??
FReeze FRancis 7.06.2016 05:54:08

Да, есть функция с именем «binary_search» std :: binary_search

Вы даете это первым, последним и значением или предикатом.

Смотрите здесь для образца

Объедините это с оператором Мартина Йорка ==, и все будет в порядке (в качестве альтернативы вы можете написать функтор предиката).

6
23.05.2017 10:29:36
На самом деле для бинарного поиска вам нужен оператор <, а не оператор ==
David Norman 15.12.2008 18:21:58
boost :: bind (& Node :: text, _1) <ключ :)
Johannes Schaub - litb 15.12.2008 18:26:33
Также обратите внимание, что он не находит элемент. Это просто проверка на существование.
Martin York 15.12.2008 18:28:18
да это странно почему он это делает?
Johannes Schaub - litb 15.12.2008 18:29:18
может быть там несколько раз. Вы можете использовать lower_bound и upper_bound, чтобы найти где.
Todd Gamblin 15.12.2008 18:34:52

Вместо отсортированного вектора <Node>
Почему бы не использовать карту. Это отсортированный контейнер. Поэтому любой поиск, выполняемый с помощью std :: find (), автоматически имеет те же свойства, что и бинарный поиск.

0
15.12.2008 18:30:03
Если ваши данные стабильны (нет текущих добавлений / удалений), более эффективно использовать векторную память. Если вам нужно взаимодействовать с другими частями системы, которые ожидают вектора. Или вам нужно получить доступ к данным по индексу. Или данные доступны в узком цикле, где важна локальность памяти.
KeithB 15.12.2008 18:58:20
«Сортированный вектор позволяет вам перебирать содержимое по порядку». Так же, как и карта. (для (std :: map <int> :: iterator i = map.begin (); i! = map.end (); ++ i) ...)
Max Lybbert 15.12.2008 19:54:04
карта также не справляется с несколькими экземплярами ключа.
baash05 15.12.2008 22:11:44
Это позволяет вам повторять в порядке ключа. Более близкая аналогия с отсортированным вектором - std :: multiset.
Steve Jessop 16.12.2008 19:53:47

Используйте, std::equal_rangeчтобы найти диапазон элементов в отсортированном векторе. std::equal_rangeвозвращает a std::pairиз итераторов, давая вам диапазон в векторе элементов, равный аргументу, который вы предоставляете. Если диапазон пуст, то ваш элемент находится не в векторе, а длина диапазона говорит вам, сколько раз ваш элемент появляется в векторе.

Вот пример использования int вместо struct Node:

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

int main(int argc, const char * argv[])
{
    std::vector<int> sorted = { 1, 2, 2, 5, 10 };

    auto range = std::equal_range(sorted.begin(), sorted.end(), 20);
    // Outputs "5 5"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    range = std::equal_range(sorted.begin(), sorted.end(), 5);
    // Outputs "3 4"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    range = std::equal_range(sorted.begin(), sorted.end(), -1);
    // Outputs "0 0"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    return 0;
}

Для того, чтобы это работало с struct Nodeвами, вы должны либо предоставить operator < для, struct Nodeлибо передать компаратор std::equal_range. Вы можете сделать это, предоставив лямбду в качестве аргумента std::equal_rangeдля сравнения своих структур.

std::vector<Node> nodes = { Node{"hello", 5}, Node{"goodbye", 6} };
Node searchForMe { "goodbye", 6 };
auto range = std::equal_range(nodes.begin(), nodes.end(), searchForMe,
                               [](Node lhs, Node rhs) { return lhs.id < rhs.id; });
0
5.12.2013 02:46:10