算法

一个数据结构，例如表或向量，仅就自身而言也没有太大用处。为了使用它们，我们就需要有最基本的访问操作，例如加入或者删除元素等。进一步说，我们也很少只是将元素存储进去，而是需要对它们进行排序，打印它们，抽取某些子集，删除一些元素，检索特定的对象，如此等等。正因为此，标准库提供了各种最常用的容器类型之外，还提供了一批用于这些容器的最常用的算法。例如，下面程序对一个 vector 排序，并将该 vector 中元素复制到一个 list，其中的重复元素只复制惟一的副本：

    void f(vector<Entry>& ve, list<Entry>& le)
    {
        sort(ve.begin(), ve.end());   // #include <algorithm>
        unique_copy(ve.begin(), ve.end(), le.begin());
    }

标准算法将在第18章描述，它们都是基于元素的序列（2.7.2节）表述的。一个序列由一对迭代器表示，一个描述其首元素，另一个描述超出序列末端一个位置的元素。在上面这个例子里，sort() 对由 ve.begin() 到 ve.end() 的序列做排序，这也正好就是该 vector 的所有元素。为了向序列里写，你只要描述需要写的第一个元素。如果要写进去的元素不止一个，那么跟随在这个初始元素之后的一些元素也将被复写。

如果我们想在一个容器的最后增加新元素，那就应该写：

    void f(vector<Entry>& ve, list<Entry>& le)
    {
        sort(ve.begin(), ve.end());    // #include <algorithm>
        unique_copy(ve.begin(), ve.end(), back_inserter(le));    // 附到le之后
    }

back_inserter() 在容器的最后增加元素，并根据需要扩充这个容器，以便为新增加的元素提供空间（19.2.4）节。这样，标准容器和 back_inserter() 的结合使我们能避免去使用极易出错的，采用 realloc() (16.3.5节)的C风格存储管理。如果要在后面附加元素，但却忘记用 back_inserter() 就会导致错误。例如，

    void f(vector<Entry>& ve, list<Entry>& le)
    {
        copy(ve.begin(), be.end(), le); // 错误❌;le不是迭代器
        copy(ve.begin(), be.end()， le.end()); // 糟糕❌；写超出结束位置
        copy(ve.begin(), ve.end(), le.begin()); // ⚠️覆盖掉一些元素
    }

🔚