К содержанию
Quantoros

Чем 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

Похожие вопросы