13 算法

C++11：更多算法，如move、copy_if和is_sorted等

13.1 引言

数据结构（如动态数组、链表等）本身并没有什么用，它们的价值在于对其中元素的访问（如插入、删除等）。而且，仅仅将对象保存到表示这些数据结构的容器中，是毫无意义的，只有能够对它们进行搜索、排序、拆分、合并等操作，才能满足实际应用程序开发的需要。因此，标准库在提供了一系列最常用的容器之外，还为这些容器提供了一系列最常用的算法。借助这些算法，只需编写寥寥数行代码，即可高效地实现对Entry型vector的排序，并将其中元素不重复地复制到list中。例如：

xxxxxxxxxx
7
1
vector<Entry> phoneBook;
2
...
3
sort(phoneBook.begin(), phoneBook.end());
4
...
5
list<Entry> uniquePhoneBook(phoneBook.size());
6
...
7
unique_copy(phoneBook.begin(), phoneBook.end(), uniquePhoneBook.begin());

其中，sort函数在排序过程中，会用“<”操作符对容器中的元素做顺序性比较，以获得升序序列。unique_copy函数在复制过程中，会用“==”操作符对有序序列中的元素做相等性比较，以跳过相邻的重复元素。因此需要为Entry类型定义“<”和“==”操作符函数。例如：

xxxxxxxxxx
11
1
struct Entry {
2
    ...
3
    bool operator<(const Entry& e) const {
4
        return name < e.name; // 按姓名排序
5
    }
6
    ...
7
    bool operator==(const Entry& e) const {
8
        return name == e.name && number == e.number; // 根据姓名和电话号码判断是否相等
9
    }
10
    ...
11
};

标准库算法都被描述为在一个左闭右开区间上的操作。该区间由一对迭代器表示，分别指向区间中的第一个元素，和最后一个元素的下一个位置，记作：[begin:end)。

在上面的例子中，传递给sort函数的两个参数，分别为phoneBook对象的begin和end两个成员函数的返回值。它们是分别指向phoneBook中的第一个元素和最后一个元素的下一个位置的迭代器。因此这个操作是对phoneBook容器中的所有元素做排序。对于输出数据的操作，往往只需给出指向首位置的迭代器即可，比如unique_copy函数的第三个参数。所输出的内容会从首位置开始，依次覆盖后面的位置，前提是这些位置应该都有实际的元素。代码中的“list<Entry> uniquePhoneBook(phoneBook.size())”就是为了保证这一点。

标准库没有提供足够的抽象，以支持对容器进行带范围检查的写入。为此，不妨定义一个这样的迭代器：

xxxxxxxxxx
50
1
template<typename C>
2
class CheckedIter {
3
public:
4
    using value_type = typename C::value_type;
5
    using difference_type = int;
6

7
    CheckedIter() {
8
        throw "missing container";
9
    }
10

11
    CheckedIter(C& c) : m_c{ &c } {}
12

13
    CheckedIter(C& c, typename C::iterator p) : m_c{ &c }, m_p{ p } {}
14

15
    CheckedIter& operator++() {
16
        checkEnd();
17
        ++m_p;
18
        return *this;
19
    }
20

21
    CheckedIter operator++(int) {
22
        checkEnd();
23
        auto t{ *this };
24
        ++m_p;
25
        return t;
26
    }
27

28
    value_type& operator*() const {
29
        checkEnd();
30
        return *m_p;
31
    }
32

33
    bool operator==(const CheckedIter& ci) const {
34
        return m_p == ci.m_p;
35
    }
36

37
    bool operator!=(const CheckedIter& ci) const {
38
        return m_p != ci.m_p;
39
    }
40

41
private:
42
    void checkEnd() const {
43
        if (m_p == m_c->end())
44
            throw "overflow";
45
    }
46

47
    C* m_c{};
48

49
    typename C::iterator m_p{ m_c->begin() };
50
};

显然，这不是标准库质量的代码，但它表明了这样的思想：

xxxxxxxxxx
10
1
vector v1{ 1, 2, 3 }, v2{ 4, 5 };
2

3
copy(v1.begin(), v1.end(), v2.begin()); // 溢出
4

5
try {
6
    copy(v1.begin(), v1.end(), CheckedIter{ v2 }); // overflow
7
}
8
catch (const char* ex) {
9
    cerr << ex << endl;
10
}

回到最开始的例子，从vector向list做不重复拷贝的代码，还有另一种写法：

xxxxxxxxxx
7
1
vector<Entry> phoneBook;
2
...
3
sort(phoneBook.begin(), phoneBook.end());
4
...
5
list<Entry> uniquePhoneBook;
6
...
7
unique_copy(phoneBook.begin(), phoneBook.end(), back_inserter(uniquePhoneBook));

这种写法的好处是不需要为list预分配元素空间。back_inserter函数创建并返回一个后插迭代器，这种迭代器能将新元素追加到容器元素序列的末尾，并自动扩展容器空间以容纳新元素。标准库容器加上back_inserter函数，这是一个堪称完美的解决方案，它使人们彻底摆脱了，借助realloc这个极易出错的C语言函数，显式地动态扩展内存的困扰。标准库的list和vector一样，也有转移构造和转移赋值，从函数中返回list对象非常高效，即使其中包含着成千上万个元素。

如果认为类似“sort(phoneBook.begin(), phoneBook.end())”这样的写法太过冗长，可以定义范围版本的算法，这样代码就可以被简化为类似“sort(phoneBook)”这个样子。这两个版本是完全等价的。类似地，基于范围的for循环：

xxxxxxxxxx
3
1
for (auto& e : c) {
2
    ...
3
}

也大致相当于直接使用迭代器的传统循环：

xxxxxxxxxx
3
1
for (auto p = c.begin(); p != c.end(); ++p) {
2
    ...
3
}

除了更简单，更不容易出错以外，基于范围的for循环通常也更高效。

13.2 使用迭代器

每个容器都包括一些特殊的迭代器，比如从begin函数返回的指向第一个元素的迭代器，和从end函数返回的指向最后一个元素的下一个位置的迭代器等。此外，很多算法函数也会返回迭代器。例如，标准库的find函数，在一个序列中查找一个与给定值匹配的元素，并返回指向该元素的迭代器：

xxxxxxxxxx
5
1
// 判断一个字符串中是否包含某个给定字符
2

3
bool has(const string& s, char c) {
4
    return find(s.begin(), s.end(), c) != s.end();
5
}

find函数以返回传递给它的第二个参数，其指向查找范围之后的第一个位置的迭代器，作为向调用者报告“未找到”的方式。使用find函数的范围版本，代码会更简洁：

xxxxxxxxxx
3
1
bool has(const string& s, char c) {
2
    return ranges::find(s, c) != s.end();
3
}

下面的函数用于找出某个字符在一个字符串中出现的所有位置。其返回值的类型为vector<string::iterator>。通过vector返回由多个值组成的集合是很高效的，因为vector支持转移语义：

xxxxxxxxxx
9
1
vector<string::iterator> findAll(string& s, char c) {
2
    vector<string::iterator> res;
3

4
    for (auto p = s.begin(); p != s.end(); ++p)
5
        if (*p == c)
6
            res.push_back(p);
7

8
    return res;
9
}

这段代码用一个常规的for循环遍历字符串中的每一个字符。每次执行完循环体之后，通过“++”操作符，将迭代器自增移至下一个元素的位置。在循环体中，通过迭代器的“*”操作，访问其目标元素。findAll函数功能如图所示：

xxxxxxxxxx
5
1
Hello, World!
2
    ^   ^
3
 ___|___|___
4
|   * | *   |
5
|_____|_____|

标准库算法在所有标准库容器上的工作方式都是相同的，前提是该容器能够满足算法对迭代器的要求。因此可以将findAll函数进一步泛化为函数模板，使其能够适用于除string和char以外的数据类型。例如：

xxxxxxxxxx
10
1
template<typename C, typename V>
2
vector<typename C::iterator> findAll(C& c, V v) {
3
    vector<typename C::iterator> res;
4

5
    for (auto p = c.begin(); p != c.end(); ++p)
6
        if (*p == v)
7
            res.push_back(p);
8

9
    return res;
10
}

“typename C::iterator”中的typename是必要的，它告知编译器C中的iterator是个数据类型，而非静态成员变量。findAll函数也可以不返回迭代器的集合，而返回元素指针的集合。例如：

xxxxxxxxxx
10
1
template<typename C, typename V>
2
auto findAll(C& c, V v) {
3
    vector<ranges::range_value_t<C>*> res;
4

5
    for (auto& e : c)
6
        if (e == v)
7
            res.push_back(&e);
8

9
    return res;
10
}

这里用基于范围的for循环简化了代码，用标准库中范围库的range_value_t从容器中提取元素的类型。range_value_t简化版本的定义如下：

xxxxxxxxxx
2
1
template<typename T>
2
using range_value_t = T::value_type;

无论使用哪个版本的findAll函数，调用代码都是一样的。例如：

xxxxxxxxxx
24
1
string s = "Hello, World!";
2
char c = 'o';
3

4
...
5

6
for (auto p : findAll(s, c))
7
    cout << *p << ' ';
8
cout << endl;
9

10
list<int> l{ 3, 2, 11, 7, 2, 19, 13 };
11
for (auto p : findAll(l, 2))
12
    cout << *p << ' ';
13
cout << endl;
14

15
vector<string> v{ "red", "blue", "green", "blue", "yellow", "red", "gray"};
16
for (auto p : findAll(v, "red"))
17
    cout << *p << ' ';
18
cout << endl;
19

20
for (auto p : findAll(v, "red"))
21
    *p = "black";
22
for (const auto& e : v)
23
    cout << e << ' ';
24
cout << endl;

迭代器的价值在于使算法可以独立于容器，即不必为每一种容器都实现一遍相同的算法。算法通过迭代器操作容器中的元素，而对容器乃至元素的数据类型却一无所知。反之亦然，容器对于算法如何操作其中的元素，同样一无所知，它所要做的只是提供满足特定需求的迭代器。

这种将数据处理与数据存储相分离的设计，催生出非常通用且灵活的软件构型。

C++11：容器的转移语义

13.3 迭代器类型

迭代器的本质是什么？首先，任何一种特定的迭代器都是某种类型的对象。不过，迭代器的类型非常多，因为每种类型的迭代器都是与某种类型的容器相关联的，所以它需要保存一些与容器有关的信息，以便访问或操作其中的元素。因此，有多少种容器就有多少种迭代器，有多少种特殊要求就有多少种迭代器。例如，vector的迭代器可能就是一个普通的指针，因为通过指针访问vector中的元素，是一种非常自然而合理的方式：

xxxxxxxxxx
4
1
Hello, World! - 动态数组
2
       ^
3
       |
4
       p - 迭代器

或者vector的迭代器也可以是一个类类型的对象，其中包含指向首元素的指针，和目标元素相对于首元素的偏移量，这样的迭代器更有利于范围检查：

xxxxxxxxxx
5
1
|-- 7--|
2
Hello, World! - 动态数组
3
^      ^
4
|      |
5
|____[p,7] - 迭代器

list的迭代器注定是某种比平凡指针更复杂的东西。list中的元素并不知道它的下一个元素在哪里，因此list的迭代器指向的其实并非元素本身，而应该是包含元素和链接的节点：

各种类型的迭代器，其语义和操作的命名都非常相似。例如，对任何迭代器执行“++”操作，都会令其指向下一个元素，而对它执行“*”操作，则会得到目标元素本身。实际上，任何符合这套操作规则的对象都可以称为迭代器。因此，迭代器是一个泛型，也是一个概念，不同类型的迭代器都以标准库概念的形式提供，如forward_iterator、random_access_iterator等。事实上，用户很少需要确切知道某种迭代器的具体类型。每种容器都定义了自己的迭代器类型，并赋予其规范化的名称，如iterator、const_iterator等。例如，list<Entry>::iterator就是list<Entry>容器的迭代器类型。用户并不需要知道这个迭代器是如何定义的。

当然，迭代器也不都是成员类型。因此标准库提供了iterator_t<C>，用于提取容器中的迭代器类型，以获得形式统一的接口。iterator_t<C>对于任何定义了迭代器的类型都可用。

13.3.1 流迭代器

迭代器是处理容器中元素序列的一个很有用的通用概念，但元素序列并不仅仅出现在容器中。例如，向输出流写入值序列，或从输入流读取值序列。这里虽然没有容器，但面向I/O流的序列化操作，仍然可以借助迭代器实现。这样的迭代器称为流迭代器。

在创建ostream_iterator时，需要告知其输出对象的类型和使用哪个流。例如：

xxxxxxxxxx
1
1
ostream_iterator<string> coutit{ cout }; // string类型的标准输出流迭代器

这样向“*coutit”赋值，就会将值写到cout中。例如：

xxxxxxxxxx
3
1
*coutit++ = "Hello, ";
2
*coutit++ = "World!";
3
*coutit++ = "\n";

这是一种向标准输出写入信息的新方法。其中，形如“*coutit++ = ...”的操作，酷似通过一个指针或普通迭代器，向数组或标准库容器写入值。因此，那些基于迭代器的标准库算法函数，也同样适用于面向输出流的操作。例如：

xxxxxxxxxx
2
1
vector<string> v{ "Hello, ", "World!", "\n" };
2
ranges::copy(v, coutit); // 范围版本

类似地，借助istream_iterator，可以将输入流视作一个只读容器，同样需要告知其输入对象的类型和使用哪个流。例如：

xxxxxxxxxx
1
1
istream_iterator<int> cinit{ cin }; // int类型的标准输入流迭代器

这样从“*cinit”取值，就会将值从cin中读出。例如：

xxxxxxxxxx
3
1
int x = *cinit++;
2
int y = *cinit++;
3
int z = *cinit++;

其中，形如“... = *cinit++”的操作，酷似通过一个指针或普通迭代器，从数组或标准库容器读取值。那些基于迭代器的标准库算法函数，也同样适用于面向输入流的操作。例如：

xxxxxxxxxx
2
1
list<int> l;
2
copy(cinit, istream_iterator<int>{}, back_inserter(l)); // 迭代器版本

其中“istream_iterator<int>{}”用于构造一个表示输入结束的终止迭代器。

事实上，很少象上面代码中“*coutit++”或者“*cinit++”这样直接操作流迭代器，更多是象调用copy函数那样，将它们作为参数，传递给标准库算法函数。例如下面的代码，从一个文件中读取单词，排序排重后，写入另一个文件：

xxxxxxxxxx
14
1
string from, to;
2
cin >> from >> to; // 获取源文件和目标文件名
3

4
ifstream ifs{ from }; // 对应源文件的输入文件流
5
istream_iterator<string> ifsit{ ifs }; // string类型的输入文件流迭代器
6
istream_iterator<string> eofit{}; // 文件尾迭代器
7

8
ofstream ofs{ to }; // 对应目标文件的输出文件流
9
ostream_iterator<string> ofsit{ ofs, " "}; // string类型的输出文件流迭代器
10

11
vector<string> words{ ifsit, eofit }; // 读取源文件中的单词序列
12
ranges::sort(words); // 对单词序列排序
13

14
ranges::unique_copy(words, ofsit); // 将有序单词序列排重后写入目标文件

这里使用了范围版本的sort和unique_copy函数，其实也可以使用它们的迭代器版本，比如“sort(words.begin(), words.end())”和“unique_copy(words.begin(), words.end(), ofsit)”。这样的写法在旧式代码中很常见。

注意，如果要同时使用标准库算法的迭代器版本（位于std命名空间中）和范围版本（位于std::ranges命名空间中），需要显式加上命名空间前缀，或者使用using声明，而不要使用using指令。例如：

xxxxxxxxxx
6
1
using namespace std;
2
using namespace std::ranges; // using指令
3
...
4
copy(v, coutit); // 编译错误
5
...
6
copy(cinit, istream_iterator<int>{}, back_inserter(l)); // 编译错误

正确的写法是：

xxxxxxxxxx
5
1
using namespace std;
2
...
3
ranges::copy(v, coutit); // 范围版本
4
...
5
copy(cinit, istream_iterator<int>{}, back_inserter(l)); // 迭代器版本

或者：

xxxxxxxxxx
6
1
using namespace std;
2
...
3
using ranges::copy; // using声明
4
copy(v, coutit); // 范围版本
5
...
6
copy(cinit, istream_iterator<int>{}, back_inserter(l)); // 迭代器版本

ifstream是可以绑定到文件的istream，ofstream是可以绑定到文件的ostream，它们分别用于创建istream_iterator和ostream_iterator。其中ostream_iterator的构造函数的第二个参数，表示输出多个数据项时的分隔符字符串，本例使用单个空格作为分隔符。

以上代码先将从源文件中读到的单词放到一个vector中，然后对vector做排序（sort），最后将vector中的有序序列以排重拷贝（unique_copy）的方式写入目标文件。更简洁的方案是使用set作为存放单词的容器，set中的元素本身就是有序且唯一的。例如：

xxxxxxxxxx
12
1
string from, to;
2
cin >> from >> to; // 获取源文件和目标文件名
3

4
ifstream ifs{ from }; // 对应源文件的输入文件流
5
istream_iterator<string> ifsit{ ifs }; // string类型的输入文件流迭代器
6
istream_iterator<string> eofit{}; // 文件尾迭代器
7

8
ofstream ofs{ to }; // 对应目标文件的输出文件流
9
ostream_iterator<string> ofsit{ ofs, " "}; // string类型的输出文件流迭代器
10

11
set<string> words{ ifsit, eofit }; // 读取源文件中的单词序列，有序且唯一
12
ranges::copy(words, ofsit); // 将有序且唯一的单词序列写入目标文件

这里的ifsit、eofit和ofsit三个流迭代器，都只用了一次。这种情况下，代之以匿名变量会令代码更加精炼。例如：

xxxxxxxxxx
10
1
string from, to;
2
cin >> from >> to; // 获取源文件和目标文件名
3

4
ifstream ifs{ from }; // 对应源文件的输入文件流
5
ofstream ofs{ to }; // 对应目标文件的输出文件流
6

7
set<string> words{ istream_iterator<string>{ ifs },
8
    istream_iterator<string>{} }; // 读取源文件中的单词序列，有序且唯一
9
ranges::copy(words,
10
    ostream_iterator<string>{ ofs, " " }); // 将有序且唯一的单词序列写入目标文件

至于最终的简化版本，在代码可读性方面，究竟是增强了还是削弱了？这其实是个仁者见仁智者见智的问题，在很大程度上取决于阅读者的个人偏好和编程经验。

13.4 使用谓词

前面有关算法的讨论，但凡涉及对序列中元素的判定，都只是基于某种简单的内置规则。但在实际应用中，常常需要将元素的判定规则本身参数化，以体现更加灵活的处理逻辑。譬如find_if函数，用于在一个给定的序列中，查找满足特定条件的元素，而关于这个条件的判定是可以被参数化的，此即谓词（predicate）。

如何在一个类型为“map<string, int>”的容器中，找到第一个值小于60的元素？

xxxxxxxxxx
1
1
auto p = ranges::find_if(scores, LessThan{ 60 });

其中“LessThan{ 60 }”是一个函数对象，即可以被当做函数调用的对象，该对象实例化自一个实现了“()”操作符的类。find_if函数返回一个迭代器，该迭代器指向一个“pair<string, int>”类型的元素，以该元素为参数，调用“LessThan{ 60 }”函数对象，得到的返回值为true。LessThan的定义如下：

xxxxxxxxxx
11
1
class LessThan {
2
public:
3
    LessThan(int greater) : m_greater{ greater } {}
4

5
    bool operator()(const pair<string, int>& elem) const {
6
        return elem.second < m_greater;
7
    }
8

9
private:
10
    int m_greater;
11
};

LessThan对象通过构造函数接受用于比较的值（60）并保存在成员变量m_greater中。每次对该对象的调用，其实都是在调用其名为“operator()”的成员函数。当该函数接收到一个“map<string, int>”类型的容器中的“pair<string, int>”类型的元素时，若其中int类型的值小于成员变量m_greater（60），则返回true，否则返回false。这里也可以使用匿名函数作为谓词，与函数对象等价。例如：

xxxxxxxxxx
1
1
auto p = ranges::find_if(scores, [](const auto& elem) { return elem.second < 60; });

注意，谓词不能改变其所接受的元素。

13.5 标准库算法概览

算法究竟是什么？有关算法的更一般性的定义应该是：一个有限的规则集合，给出明确的操作序列，用于求解一组特定的问题。算法必须同时满足五个基本特性：有限性、确定性、可输入性、可输出性和有效性。在C++标准库的语境中，算法就是操作元素序列的函数模板。

标准库提供了很多算法，它们被定义在std命名空间中，通过头文件<algorithm>和<numeric>提供给使用者。这些标准库算法都以序列作为输入，该序列通过一个从b到e的左闭右开区间“[b:e)”给出，b和e分别为指向序列中第一个元素和最后一个元素下一个位置的迭代器。下表列出了<algorithm>头文件中的部分算法：

每个以起止迭代器参数表示处理范围的算法，都有对应的范围版本。当然，如果要同时使用迭代器版本和范围版本，需要显式加上std::ranges命名空间前缀，或者使用using声明。

这些算法和其它很多算法，都可以用于容器、string和内置数组。

某些算法，比如replace和sort，它们会修改元素的值，但没有任何一种算法会向容器中添加元素，或从容器中删除元素。之所以会这样，是因为算法并不了解容器的底层结构，也不应该依赖容器的底层结构，否则就无法做到通用。如果需要添加或删除容器中的元素，可以直接调用容器的底层接口，如push_back或earse，或者使用封装了这些底层接口的迭代器，如back_inserter等。

匿名函数经常作为传递给算法的参数（f），用于指定需要执行的操作。例如：

xxxxxxxxxx
5
1
vector<int> v{ 0, 1, 2, 3, 4, 5 };
2
...
3
ranges::for_each(v, [](int& x) { x = x * x; });
4
...
5
for_each(v.begin(), v.begin() + 3, [](int& x) { x = sqrt(x); });

标准库算法（如for_each）在设计、规范和实现上通常比自己编写的（如基于循环的）版本更好，因此应该充分了解标准库算法，尽可能使用现成的函数，而不是凡事都亲自动手，另起炉灶。

13.6 并行算法

在需要对不同数据元素执行相同处理任务的情况下，存在两种并发机制：

• 向量化执行：借助向量处理器，在单个线程中同时处理多个数据，亦称SIMD（单指令多数据）

• 并行执行：借助多核处理器，在多个线程中同时处理多个数据

标准库对上述两种并发机制都提供支持，可以通过<execution>头文件execution命名空间中的如下参数，显式指明希望采用哪种执行策略：

• seq：顺序执行，不使用并行，默认策略

• par：并行执行（如果可能）

• unseq：向量化执行（如果可能）

• par_unseq：并行和向量化执行（如果可能）

例如：

xxxxxxxxxx
7
1
using namespace std::execution;
2
...
3
sort(v.begin(), v.end());
4
sort(seq, v.begin(), v.end());
5
sort(par, v.begin(), v.end());
6
sort(unseq, v.begin(), v.end());
7
sort(par_unseq, v.begin(), v.end());

是否值得向量化执行或者并行执行，在很大程度上取决于算法、序列中元素的数量、硬件以及程序对该硬件的利用率。因此，算法函数中的执行策略参数，仅表示一种期望，而非强制。编译器或运行时调度器负责决定使用何种程度的并发。这体现了一个重要准则：在未经测量的前提下，不要做出任何有关效率的决定。

截止目前，范围版本的并行算法还没有被正式纳入标准。当然，如果需要，也可以手动定义。例如：

xxxxxxxxxx
3
1
void sort(auto poly, ranges::random_access_range auto& range) {
2
    sort(poly, range.begin(), range.end());
3
}

大多数标准库算法都可以申请并行执行，比如调用sort函数时，第一个参数传par或者par_unseq。但是equal_range函数不行，因为到目前为止，还没有适用于该函数的并行算法。

很多并行算法只适用于数字类型的数据元素。

采用并行策略时，还需要规避竞争和死锁的风险。

C++17：并行算法

13.7 建议

• STL标准库算法是一套用于操作一个或多个序列中的元素的函数模板

• 标准库算法的输入序列用一个左闭右开区间表示，该区间通过一对迭代器定义

• 必要时可以自己定义迭代器以满足特殊需求

• 借助于流迭代器，可将许多算法应用于输入和输出操作

• 当执行搜索类操作时，算法通常以返回终止迭代器（指向搜索范围内最后一个元素的下一个位置）的方式表示没找到

• 对于参数序列，算法并不直接在其中添加元素，或删除其中的元素

• 在编写循环代码时，应考虑它是否可被简化为一个通用算法函数的调用

• 借助using类型别名清理杂乱的符号

• 谓词和其它函数对象使标准库算法具有更宽泛的语义

• 谓词不能修改传递给它的参数

• 了解标准库算法，尽量使用它们，而不是在自己编写的，基于循环的代码中，完成相同的任务