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

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

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

6 ответов

Существует алгоритм 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);
</int></int>

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


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

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


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

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

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


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

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


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

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


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

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

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

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

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

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

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

licensed under cc by-sa 3.0 with attribution.