STL 算法如何独立于 Iterator 类型工作？

Question

STL 算法如何独立于 Iterator 类型工作？

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 必须具有预自增 ++ 运算符。 它必须有一个复制构造函数，必须有 != 运算符，并且必须有 *-取消引用运算符。

func_type 必须实现函数调用运算符，并采用与通过取消引用 iter_type 类型的对象所获得的相同类型的参数。 如果我使用满足这些要求的类型调用 for_each ，代码将编译。 iter_type 可以是满足这些要求的任何类型。 代码中没有任何内容表明“这适用于向量迭代器、列表迭代器和映射迭代器”。 但只要向量、列表或映射迭代器实现我们使用的运算符，它就可以工作。

Answer 2

STL算法是模板函数，这意味着它们可以用任何类型调用。

当调用特定类型的函数时，编译器将尝试编译该特定类型的函数实例，并报告任何编译错误（缺少方法、类型检查错误等）。

对于 STL 算法，只要使用的类型行为就像一个迭代器（支持 ++、取消引用），它会起作用。 这就是为什么这些算法也适用于本机指针，因为它们支持与迭代器相同类型的操作（这就是它们最初的设计方式）。

Answer 3

多态性

Answer 4

任何 STL 算法都是由编译器为您使用的每种迭代器类型自动生成的。

它称为 C++ 模板或静态多态性。

Answer 5

每个STL算法都是一个模板函数，它以迭代器类型作为其模板参数。

Answer 6

并非所有 STL 容器/迭代器算法都具有这种独立性。 这样做的算法称为通用算法，但这些算法通常简称为 STL 算法。

使用迭代器，您只能：

• 检查序列，以便您可以执行诸如查找、计数、for_each 等操作，
• 更改迭代器引用的值，以便您可以执行诸如变换、复制、旋转、交换、替换等操作，...
• 重新排序值迭代器，因此您可以执行排序、合并、nth_element 等操作。

一些非通用算法可以分为 2 个阶段：STL 通用部分和容器相关部分。 因此，为了销毁向量中大于 7 的所有值，我们可以执行remove_if（仅对元素进行排序的通用部分），然后执行擦除（销毁该值的非通用部分）。