STL算法如何识别容器？

Question

STL算法如何识别它正在操作的容器类型？
例如，sort接受迭代器作为参数。
它怎么知道要对哪种容器进行排序呢？

- cppcoder

---

你的第二个问题应该在另一个线程中提出。 - Brian Bi

以下答案假设您已经知道模板和（基本的）模板参数推导的工作原理，但似乎您并不知道。 基本上，“sort（）”不是一个特定的函数，而是一个模板 - 可以在编译时通过替换某些内容（如容器或迭代器类型）自动生成（无限）数量的函数。 如果需要更多信息，请提出问题。 - j_random_hacker

Answer 1

它并不需要 :-) 这就是迭代器的全部意义——对它们进行操作的算法不需要知道底层容器的任何信息，反之亦然。

那么它是如何工作的呢？嗯，迭代器本身具有一定的众所周知的属性。例如，'随机访问'迭代器允许任何算法通过一个常量访问偏移量与迭代器相对应的元素：

std::vector<int> vec = { 1, 2, 3, 4 };
assert(*(vec.begin() + 2) == 3);

为了进行排序，迭代器需要支持随机访问（以任意顺序访问第一个和最后一个迭代器之间的所有元素），并且它们需要是可写的（以便分配或交换值），也被称为“输出”迭代器。

输出迭代器与输入（只读）迭代器的示例：

std::vector<int> vec = { 1, 2, 3, 4 };
*vec.begin() = 9;
assert(vec[0] == 9);

*vec.cbegin() = 10;    // Does not compile -- cbegin() yields a const iterator
                       // that is 'random-access', but not 'output'

- Cameron

---

根据迭代器的类型，排序是如何进行的？ - cppcoder

我已经添加了一个相关的问题。 - cppcoder

@cppcoder：std::swap()可以交换两个任意的东西（它是为通用情况而模板化的，并针对某些类型进行了专门优化以提高速度）。std::vector::swap仅将一个向量的内容与另一个向量的内容交换。 - Cameron

@cppcoder 如果不清楚的话，向量的交换是一种非常高效的O(1)操作。 - juanchopanza

@Cameron 为什么存在 std::vector::swap，而已经有了 std::swap？它提供了什么优势？ - cppcoder

@cppcoder：好问题。我不知道为什么std::vector::swap存在于单独的位置，但是将交换实现作为向量实现的一部分确实是有意义的。对于向量，std::swap只是调用std::vector::swap :-) - Cameron

Answer 2

它不需要知道容器的类型，只需要知道迭代器的类型。

- tillaert

---

我不认为算法需要知道迭代器的类型。编译器需要知道迭代器的类型，以便将模板转换为实际函数（因为C++是静态类型），但算法本身并不关心。它只是盲目地假设迭代器支持它所需的操作，如果不支持，则会出现编译器错误。 - Benjamin Lindley

@Benjamin：嗯，是的，但如果算法在没有给定特定类型的迭代器的情况下无法编译，那么我认为这种隐含的假设/耦合足够强烈，可以称之为“关心”迭代器的类型 :-) - Cameron

Answer 3

正如之前提到的那样，STL 使用迭代器而不是容器。它使用称为“标签分派”的技术来推断适当的算法风格。

例如，STL 有一个名为“advance”的函数，它将给定的迭代器 it 移动 n 个位置。

template<class IteratorType,
    class IntegerDiffType> inline
    void advance(IteratorType& it, IntegerDiffType n)

对于双向迭代器，它需要多次应用 ++ 或 --；对于随机访问迭代器，它可以一次跳跃。此函数用于 std::binary_search、std::lower_bound 和其他一些算法。

在内部，它使用迭代器类型特征来选择策略：

template<class IteratorType,
        class IntegerDiffType> 
        void advance(IteratorType& it, IntegerDiffType n)
{
    typedef typename iterator_traits<IteratorType>::category category;
    advance_impl(it, n, category());
}

当然，STL必须实现重载的“impl”函数：

template<class IteratorType,
        class IntegerDiffType> 
        void advance(IteratorType& it, IntegerDiffType n, bidirectional_iterator_tag)
{   // increment iterator by offset, bidirectional iterators
for (; 0 < n; --n)
    ++it;
for (; n < 0; ++n)
    --it;
}

template<class IteratorType,
        class IntegerDiffType> 
        void advance(IteratorType& it, IntegerDiffType n, random_access_iterator_tag)
{   // increment iterator by offset, random-access iterators
    it += n;
} 

- Michael Simbirsky