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

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

6 голосов
/ 15 декабря 2008

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

struct Node{CString text, int id;};

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

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

Ответы [ 4 ]

21 голосов
/ 15 декабря 2008

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

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

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

6 голосов
/ 15 декабря 2008

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

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

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

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

0 голосов
/ 05 декабря 2013

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

Вот пример использования целых вместо 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 голосов
/ 15 декабря 2008

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

...