Как алгоритм STL работает независимо от типа Итератора?

Question

Как алгоритм STL работает независимо от типа Итератора?

Answer 1

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

Трюк простой.Вот очень простой пример:

template <typename T>
void say_hello(const T& t) {
  t.hello();
}

Функция say_hello не заботится о типе аргумента.Это не должно происходить из интерфейса или давать какие-либо другие "обещания" о том, что это такое.Все, что имеет значение, это то, что тип работает в этом контексте.Все, что мы делаем с типом, это вызываем его hello функцию.Это означает, что этот код будет компилироваться для любого типа, который имеет функцию-член hello.

Алгоритмы STL работают аналогично.Вот простая реализация std::for_each:

template <typename iter_type, typename func_type>
void for_each(iter_type first, iter_type last, func_type f){
  for (iter_type cur = first; cur != last; ++cur) {
    f(*cur);
  }
}

Этот код будет компилироваться всякий раз, когда типы шаблонов соответствуют предъявляемым к ним требованиям;iter_type должен иметь преинкрементный оператор ++ -.Он должен иметь конструктор копирования и оператор! =, А также оператор * -dereference.

func_type должен реализовывать оператор вызова функции, принимая тот же аргументвведите, как вы получите, разыменовывая объект типа iter_type.Если я вызову for_each с типами, которые удовлетворяют этим требованиям, код скомпилируется.iter_type может быть любого типа, который удовлетворяет этим требованиям.В коде нет ничего, что говорило бы: «это должно работать с векторными итераторами, итераторами списков и итераторами карт».Но пока итераторы vector, list или map реализуют используемые нами операторы, это будет работать.

Answer 2

Алгоритм STL - это шаблонные функции, что означает, что их можно вызывать с любым типом.

При вызове функции с определенным типом компилятор попытается скомпилировать экземпляр функции для этого конкретного типа и сообщить о любой ошибке компиляции (отсутствующие методы, ошибки проверки типа и т. Д.)

Для алгоритмов STL, пока используемый тип ведет себя как итератор (поддерживает ++, разыменование), он будет работать. Вот почему эти алгоритмы работают и с нативными указателями, потому что они поддерживают тот же тип операций, что и итераторы (именно так они были спроектированы в первую очередь).

Answer 3

Любой алгоритм STL генерируется автоматически компилятором для каждого типа итератора, с которым вы его используете.

Это называется шаблонами C ++ или статическим полиморфизмом.

Answer 4

Полиморфизм

Answer 5

Каждый алгоритм STL является функцией шаблона, которая принимает тип итератора в качестве параметра шаблона.

Answer 6

Не все алгоритмы контейнера / итератора STL обладают такой независимостью. Те, что делают, называют общими алгоритмами, но обычно их называют просто алгоритмами STL.

Только с итераторами вы можете:

• проверьте последовательность, чтобы вы могли выполнять такие действия, как поиск, подсчет, for_each,…
• измените значение ссылок итератора, чтобы вы могли выполнять такие операции, как преобразование, копирование, вращение, замена, замена,…
• изменить порядок значений итераторов, чтобы вы могли выполнять такие операции, как сортировка, слияние, nth_element.

Некоторые неуниверсальные алгоритмы можно разбить на 2 этапа: общая часть STL и зависимая от контейнера часть. Таким образом, чтобы уничтожить все значения, которые больше 7 в векторе, мы можем сделать remove_if (универсальная часть, которая сортирует только элементы) с последующим удалением (неуниверсальная часть, которая уничтожает значение).