Почему бы не реализовать функцию содержит в контейнерах C ++?
Мой начальный вопрос был: почему в C ++ contains() функция отсутствует в Containers?
Поэтому я искал объяснение и нашел кое-что интересное о том, почему некоторые другие функции не реализованы во всех Containers (в основном из-за проблем с производительностью и удобством).
Я знаю, что вы можете использовать find функция от algorithm библиотека или вы можете просто написать свою собственную функцию с Iteratorно то, что я не могу понять, это почему в setнапример, contains функция (где это называется find), тогда как в vector или же queue это не.
Мне также довольно ясно, почему классы-контейнеры не имеют общего интерфейса, такого как Collections делать на Java (спасибо этот ответ) но в этом случае я не могу найти причину, почему бы не реализовать contains() функция во всех классах контейнеров (или, по крайней мере, в некоторых vector).
Спасибо
Решение
Есть веская причина, по которой контейнеры не имеют «общего (унаследованного) интерфейса» (как в Java) и это то, что делает C++ дженерики такие мощные. Зачем писать код для каждого контейнера, если вы можете написать его только один раз для всех контейнеров? Это один из основных принципов STL был построен на.
Если использование контейнеров опирается на функции-члены от общего унаследованный Интерфейс вы должны написать находить функция для каждого контейнера. Это расточительное и плохое проектирование. Хороший дизайн говорит, что если вы можете писать код только в одном месте, вам следует это делать, потому что вам нужно только удалить ошибки из этого одного места, а исправление ошибки в одном месте исправляет ошибку везде.
Таким образом, философия за STL это к отдельный алгоритмы от контейнеры так что вам нужно только написать алгоритм один раз, и это работает для все контейнеры. Однажды алгоритм отлажен, отлажен для все контейнеры.
Муха в этой мази заключается в том, что некоторые контейнеры могут принимать более эффективные решения благодаря своей внутренней структуре. Для этих контейнеров специфичный для типа была добавлена функция, которая будет использовать эту эффективность.
Но большинство функций должен быть отдельным от контейнеры. Это называется развязка и это уменьшает количество ошибок при продвижении повторного использования кода, часто гораздо больше, чем полиморфизм вот что нравится библиотекам Java использование контейнеров (общий унаследованный интерфейс).
Другие решения
Причина по которой std::set реализует свой собственный find это то, что «универсальный» std::find выполняет линейный поиск, а std::set может сделать намного лучше, если поискать его древовидное представление в O (log2 н).
std::vector а также std::list, с другой стороны, не может быть найден быстрее, чем в линейном времени, поэтому они полагаются на std::find реализация.
Обратите внимание, что вы все еще можете подать заявку std::find в std::set искать его линейно; это просто не было бы так эффективно, как использование собственного набора find функция-член.
std::set<int> s {1, 2, 3, 4, 5, 6};
auto res = std::find(s.begin(), s.end(), 3);
std::cout << *res << std::endl; // prints 3
Потому что это плохой шаблон дизайна. Если вы постоянно используете «find» в линейном контейнере, значит, есть проблема с вашим кодом. Средняя и наихудшая временная сложность по-прежнему составляет O (n), что означает, что вы сделали неправильный выбор.
Например, std::map а также std::unordered_map иметь find функции-члены, которые позволяют O (logn) и O (1) поиск. Это связано с тем, что контейнер использует эффективный поиск элементов с помощью этих методов: именно так должен использоваться контейнер.
Если вы взвесили все варианты и решили, что линейный контейнер — лучшая модель для ваших данных, но в редких случаях нужно найти элемент, std::find() позволяет вам сделать это. Вы не должны полагаться на это. Я рассматриваю это как антипаттерн в Python и Java и преимущество в C ++.
Так же, как личное примечание, 3 года назад, когда я был начинающим программистом, я написал if mydict in list: do_something() много. Я подумал, что это хорошая идея, потому что Python делает членство в элементе списка идиоматическим. Я не знал лучше. Это привело меня к созданию ужасного кода, пока я не узнал, почему линейный поиск настолько неэффективен по сравнению с бинарным поиском и поиском по хэш-карте. Язык программирования или фреймворк должны обеспечивать хорошие шаблоны проектирования и предотвращать плохие. Включение линейного поиска — плохой шаблон проектирования.
Другие ответы по какой-то причине фокусируются на сложности обобщенных и отдельных контейнеров. find методы. Однако они не могут объяснить вопрос ОП. Фактическая причина отсутствия полезных служебных методов связана с тем, как классы из разных файлов используются в C ++. Если бы каждый контейнер, который не содержит каких-либо специальных свойств, имел бы contains метод, выполняющий общий поиск с линейной сложностью, мы застряли бы либо в ситуации, когда каждый заголовок контейнера также включает <algorithm> или когда каждый заголовок контейнера переопределяет свой собственный find алгоритм (что еще хуже). И довольно большая сборка документов во время компиляции каждого модуля перевода после включения препроцессора (то есть копирования-вставки) каждого включенного заголовка будет расти еще больше. Компиляция заняла бы еще больше времени. И довольно загадочные сообщения об ошибках компиляции могут стать еще дольше. Этот старый принцип не делать функцию-член, когда функция, не являющаяся членом, может выполнять работу (и включать только то, что вы собираетесь использовать), существует по причине.
Обратите внимание, что недавно было предложение uniform call syntax это может позволить смешивать полезные методы в классах. Если он будет запущен, возможно, будет возможно написать такие функции расширения:
template< typename TContainer, typename TItem > bool
contains(TContainer const & container, TItem const & item)
{
// Some implementation possibly calling container member find
// or ::std::find if container has none...
}
::std::vector< int > registry;
registry.contains(3); // false
detector