Некоторые контейнеры в stl не имеют функции поиска

Ответ 1

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

Контейнеры, имеющие элемент find, представляют собой контейнеры, которые имеют более эффективный механизм поиска элементов, а затем линейный поиск, выполняемый в std::find. Например, двоичные деревья поиска, такие как std::set и std::map, или хеш-таблицы, такие как их сопоставления unordered.

Ответ 2

find, lower_bound и upper_bound функции-члены предоставляются только тогда, когда эффективнее, чем использование нечленов-эквивалентов или когда нечлены не могут работать, учитывая открытый API-интерфейс контейнера

Обратите внимание, в частности, что std::string имеет функцию find, которая предоставляет std::find() -подобные средства линейного поиска для поиска символов и std::search() -подобные объекты для поиска подстроки: в то время как версии, не являющиеся членами, могут иметь с той же эффективностью большой O, они могут быть менее эффективными, поскольку специальные инструкции машинного кода часто доступны для поиска по строкам. Существуют также исторические, удобные и легко переносимые факторы.

Помимо вопроса об эффективности, следует отметить, что некоторые контейнеры:

• по своей сути либо отсортированы (multi - set, map), либо несортированы (unordered_map, unordered_set), обычно несортированы (например, std::string), или легко либо (std::vector)

• публично поддерживать форвардную итерацию и/или произвольный доступ

• возможно конфиденциально поддерживать двоичный поиск

• имеют такой специализированный публичный API для доступа к элементу, что потенциальное повторное использование алгоритма относительно ограничено (например, unordered_map::bucket/::begin(n) et al)

Интересно также, что поиск в vector может быть выполнен с использованием большого количества алгоритмов:

• std::find выполняет линейный поиск O (n) грубой силы, который сначала "найдет" элементы нижнего индекса,

• std::binary_search требует отсортированного вектора, но перескакивает для достижения сложности O (log2n).

• могут быть применимы другие параметры, такие как поиск и хэширование экстраполяции

Как бы вы выбрали, какие из них реализовать и добавить в качестве членов? Кажется немного произвольным. Тем не менее выбор, который можно использовать, может быть важным для производительности: для миллиона элементов find составляет в среднем полмиллиона элементов сравнения перед совпадением и полный миллион всякий раз, когда элемент не существует, а binary_search обычно принимает ~ 20 сравнений в любом случае.

Контейнеры с find обычно не обеспечивают такую ​​гибкость, а предоставляемые find и/или lower_bound/upper_bound могут рассматриваться как замены для эквивалентов, не являющихся членами, и, вероятно, единственные разумный способ поиска контейнеров.

Ответ 3

Потому что существует std::find функция algorithm, которая применяется для них.

Обычно контейнеры, такие как std::vector и std::list, имеют сложность линейного поиска. Как таковой, присоединение к ним функции-члена find является избыточным, потому что уже существует std::find. Для других контейнеров (например, std::set или std::map и т.д.) Существует лучший способ (т.е. Быстрее, чем линейная сложность) для реализации поиска. Таким образом, разработчики реализовали этот более быстрый алгоритм поиска в качестве функций-членов.

Ответ 4

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

Другие, как и те, которые вы указали, позволят поиск диапазона с помощью std:: find, но не имеют функции поиска потому что у него было бы нет алгоритмического преимущества над std:: find (кроме отсортированных/специальных случаев)

Ответ 5

Использование одной и той же функции для различных контейнеров делает более понятным API, вам не нужно изучать особенности каждого из контейнеров, просто как применять одну функцию, которую вы используете для всех из них.

Это также для повторного использования кода - вы используете алгоритм, который принимает итераторы из любого из контейнеров, которые их предоставляют, поэтому алгоритм не должен полагаться на контейнер, являющийся std::vector, std::list и т.д.

Ответ 6

Такие контейнеры, как std::vector, std::list, std::forward_list и некоторые другие, являются последовательными контейнерами. Нет ничего лучше, чем последовательный поиск, который может быть применен к этим контейнерам. Поэтому нет необходимости переписывать последовательный поиск для каждого последовательного контейнера, если он одинаковый для всех этих контейнеров.

Исключением является класс std::basic_string, который первоначально моделирует C-строки, которые уже имеют специальные функции поиска, такие как strchr, strstr и другие.

Ответ 7

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

Однако преимущества первого заключаются в том, что он сделает API между всеми контейнерами согласованным и сделает код клиента менее подробным. Это повысит обучаемость и удобочитаемость (это выгодно для пользователей библиотеки). Кроме того, совместимый API позволит писать общий код. Рассмотрим это:

template <typename Container, typename T>
void foo(const Container& c, const T& x) {
    if (std::find(c.begin(), c.end(), x) != c.end()) {
        // ...
    }
}

Вышеуказанное неэффективно, когда Container является std::map или std::set. Чтобы сделать его эффективным, нам нужно будет сделать:

template <typename Container, typename T>
void foo(const Container& c, const T& x) {
    if (c.find(x) != c.end()) {
        // ...
    }
}

Но тогда он не компилируется для std::vector и std::list. Это накладывает нагрузку на пользователей библиотеки, чтобы написать свою собственную универсальную функцию, специализированную вручную/перегруженную для каждого типа, который они хотят поддерживать:

template <typename T>
bool contains(const std::vector<T>& c, const T& x) {
    return std::find(c.begin(), c.end(), x) != c.end();
}

template <typename T>
bool contains(const std::set<T>& c, const T& x) {
    return c.find(x) != c.end();
}

template <typename Container, typename T>
void foo(const Container& c, const T& x) {
    if (contains(c, x)) {
        // ...
    }
}

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

_{(Я имею в виду, давайте, контейнер по определению содержит что-то, что содержит вещи. Для пользователей должно быть тривиально писать общую и эффективную функцию "содержит". Фактически, я бы сказал, что это должно быть добавлен в концепцию Container, но я отвлекаюсь.)}