Чем std::find отличается от std::binarysearch?
C++Уровень: ПрактикаSTL Containers & Iterators
Чем std::find отличается от std::binary_search?
Подсказки
- Уточните типы, время жизни объектов и то, что определяется на этапе компиляции.
- Проверьте гарантии стандарта отдельно от поведения конкретного компилятора.
Ответ
find линейно ищет первое равное значение и возвращает итератор либо end(). find_if/find_if_not ищут по предикату. binary_search проверяет наличие в подходящим образом упорядоченном диапазоне и возвращает bool; число сравнений логарифмическое. Для позиции используют lower_bound, upper_bound или equal_range. У ассоциативных контейнеров предпочтительны собственные методы find, учитывающие внутреннюю структуру. Стоимость перемещения итераторов также зависит от их категории.
Примеры из источника:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector v{1, 2, 3, 4, 5};
auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) {
std::cout << "Found: " << *it << "\n";
}
}
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector v{1, 2, 3, 4, 5};
auto even = std::find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
auto odd = std::find_if_not(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
std::cout << "First even: " << *even << "\n"; // 2
std::cout << "First odd: " << *odd << "\n"; // 1
}
#include <algorithm>
#include <vector>
int main() {
std::vector v{1, 2, 3, 4, 5};
bool found = std::binary_search(v.begin(), v.end(), 3);
// lower_bound: first element >= value
auto lb = std::lower_bound(v.begin(), v.end(), 3);
// upper_bound: first element > value
auto ub = std::upper_bound(v.begin(), v.end(), 3);
// equal_range: pair of lower_bound and upper_bound
auto [lo, hi] = std::equal_range(v.begin(), v.end(), 3);
}
Материалы источника:
Источник и лицензия: C/C++ Interview Cheatsheet — Chang Ning Tsai · MIT · перевод: Quantoros