Какая функция в библиотеке std существует для двоичного поиска вектора и нахождения элемента?
-
21-08-2019 - |
Вопрос
У меня есть структура узла
struct Node{CString text, int id;};
в отсортированном векторе.
Мне интересно, есть ли в алгоритме функция, которая будет выполнять двоичный поиск вектора и находить элемент.
Решение
std::binary_search()
сообщит вам, существует ли значение в контейнере.
std::lower_bound()/std::upper_bound()
вернет итератор к первому / последнему вхождению значения.
Ваши объекты необходимо реализовать operator<
чтобы эти алгоритмы работали.
Другие советы
Да, есть функция под названием "binary_search" std::binary_search
Вы указываете ему первое, последнее и значение или предикат.
Видишь здесь для образца
Объедините это с У Мартина Йорка operator== и у вас должно быть все в порядке (в качестве альтернативы вы можете написать функтор предиката
Вместо отсортированного вектора<Node>
Почему бы не воспользоваться картой?Это отсортированный контейнер.Таким образом, любой поиск, выполняемый по этому с помощью std::find(), автоматически имеет те же свойства, что и двоичный поиск.
Использование 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; });