почему нет поиска для вектора в C ++

Question

какая альтернатива?

Должен ли я писать сам?

Answer 1

Существует алгоритм std::find(), который выполняет линейный поиск в диапазоне итераторов, например,

std::vector<int> v;

// Finds the first element in the vector that has the value 42:
// If there is no such value, it == v.end()
std::vector<int>::const_iterator it = std::find(v.begin(), v.end(), 42);

Если ваш вектор отсортирован, вы можете использовать std::binary_search(), чтобы проверить, присутствует ли значение в векторе, и std::equal_range(), чтобы получить начальные и конечные итераторы для диапазона элементов в векторе, которые имеют это значение.

Answer 2

Причина, по которой нет vector::find, заключается в том, что нет алгоритмического преимущества перед std::find (std::find равно O(N) и, в общем, вы не можете добиться большего успеха для векторов).

Но причина того, что у вас есть map::find, в том, что он может быть более эффективным (map::find - это O(log N), поэтому вы всегда хотели бы использовать это значение выше std::find для карт).

Answer 3

Кто тебе это сказал? В C ++ есть алгоритм «поиска» для vector. По иронии судьбы По совпадению, это называется std::find. Или, может быть, std::binary_search. Или что-то еще, в зависимости от свойств данных, хранящихся в вашем векторе.

Контейнеры получают свои собственные конкретные версии универсальных алгоритмов (реализованных в виде контейнерных методов), только когда эффективная реализация алгоритма каким-то образом связана с внутренними деталями контейнера. std::list<>::sort будет одним из примеров.

Во всех остальных случаях алгоритмы реализуются автономными функциями.

Answer 4

Функциональность 'find' в классе контейнера нарушает ' SRP ' (принцип единой ответственности). Основная функциональность контейнера заключается в предоставлении интерфейсов для хранения, поиска элементов в контейнере. «Поиск», «Сортировка», «Итерация» и т. Д. Не являются основными функциями любого контейнера и, следовательно, не являются частью его прямого интерфейса.

Однако, как говорится в «* Herb» в Принцип пространства имен , «find» является частью интерфейса, поскольку определяется в том же пространстве имен, что и «vector», а именно «std».

Answer 5

Используйте std::find(vec.begin(), vec.end(), value).

И не забудьте включить <algorithm>

Answer 6

какая альтернатива?

Стандарт предлагает std :: find для последовательного поиска по произвольным последовательностям похожих элементов (или что-то в этом роде).

Это может применяться ко всем контейнерам, поддерживающим итераторы, но для внутренне отсортированных контейнеров (например, std::map) поиск может быть оптимизирован. В этом случае контейнер предлагает свою собственную find функцию-член.

почему нет поиска для вектора в C ++?

Не было никакого смысла в создании std::vector<???>::find, так как реализация была бы идентична std::find(vector.begin(), vector.end(), value_to_find);.

Должен ли я писать сам?

Нет. Если у вас нет особых ограничений или требований, вы должны по возможности использовать реализацию STL.