罗剑锋的C++实战笔记学习（二）：容器、算法库、多线程

4、容器

1）、容器的通用特性

所有容器都具有的一个基本特性：它保存元素采用的是值（value）语义，也就是说，容器里存储的是元素的拷贝、副本，而不是引用

容器操作元素的很大一块成本就是值的拷贝。所以，如果元素比较大，或者非常多，那么操作时的拷贝开销就会很高，性能也就不会太好

一个解决办法是，尽量为元素实现转移构造和转移赋值函数，在加入容器的时候使用std::move()来转移，减少元素复制的成本：

#include <iostream>
#include <vector>class Point {
public:Point(int x, int y) : x_(x), y_(y), data("Expensive resource") {std::cout << "Point constructor called." << std::endl;}Point(const Point &other) : x_(other.x_), y_(other.y_), data(other.data) {std::cout << "Copy constructor called." << std::endl;}Point(Point &&other) noexcept: x_(other.x_), y_(other.y_), data(std::move(other.data)) {std::cout << "Move constructor called." << std::endl;}private:int x_, y_;std::string data; // 假设这是一个昂贵的资源
};int main() {// 不使用移动语义,直接拷贝{Point p(1, 2);std::vector<Point> v;v.push_back(p); // 这里会调用拷贝构造函数std::cout << "---- After normal push_back ----" << std::endl;}// 使用移动语义{Point p(3, 4);std::vector<Point> v;v.push_back(std::move(p)); // 这里会调用移动构造函数std::cout << "---- After move semantics push_back ----" << std::endl;}return 0;
}

输出：

Point constructor called.
Copy constructor called.
---- After normal push_back ----
Point constructor called.
Move constructor called.
---- After move semantics push_back ----

也可以使用C++11为容器新增加的emplace操作函数，它可以就地构造元素，免去了构造后再拷贝、转移的成本，不但高效，而且用起来也很方便：

#include <iostream>
#include <vector>
#include <string>class Point {
public:Point(int x, int y) : x_(x), y_(y), data("Expensive resource") {std::cout << "Point constructor called." << std::endl;}Point(const Point &other) : x_(other.x_), y_(other.y_), data(other.data) {std::cout << "Copy constructor called." << std::endl;}Point(Point &&other) noexcept: x_(other.x_), y_(other.y_), data(std::move(other.data)) {std::cout << "Move constructor called." << std::endl;}private:int x_, y_;std::string data; // 假设这是一个昂贵的资源
};int main() {std::vector<Point> v;v.reserve(2);  // 预分配足够的空间,避免内部扩展// 使用emplace_back直接在容器内构造对象v.emplace_back(1, 2); // 这里不会调用拷贝或移动构造函数v.emplace_back(3, 4);// 当std::vector需要扩容时,会触发之前对象的移动构造函数v.emplace_back(5, 6);return 0;
}

输出：

Point constructor called.
Point constructor called.
Point constructor called.
Move constructor called.
Move constructor called.

还可以在容器里存放元素的指针，来间接保存元素。这里建议使用智能指针unique_ptr/shared_ptr，让它们帮你自动管理元素，一般情况下，shared_ptr是一个更好的选择，它的共享语义与容器的值语义基本一致

2）、顺序容器

顺序容器就是数据结构里的线性表，一共有5种：array、vector、deque、list、forward_list

按照存储结构，这5种容器又可以再细分成两组

连续存储的数组：array、vector和deque
指针结构的链表：list和forward_list

数组：

array和vector直接对应C的内置数组，内存布局与C完全兼容，所以是开销最低、速度最快的容器。它们两个的区别在于容量能否动态增长。array是静态数组，大小在初始化的时候就固定了，不能再容纳更多的元素。而vector是动态数组，虽然初始化的时候设定了大小，但可以在后面随需增长，容纳任意数量的元素

#include <array>
#include <vector>int main() {std::array<int, 2> arr;assert(arr.size() == 2);std::vector<int> v(2);for (int i = 0; i < 10; i++) {v.emplace_back(i);}assert(v.size() == 12);return 0;
}

deque也是一种可以动态增长的数组，它和vector的区别是，它可以在两端高效地插入删除元素，而vector则只能用push_back在末端追加元素

#include <deque>int main() {std::deque<int> d;d.emplace_back(9); // 末端添加一个元素d.emplace_front(1); // 前端添加一个元素assert(d.size() == 2);return 0;
}

链表：

vector和deque里的元素因为是连续存储的，所以在中间的插入删除效率就很低，而list和forward_list是链表结构，插入删除操作只需要调整指针，所以在任意位置的操作都很高效

链表的缺点是查找效率低，只能沿着指针顺序访问，这方面不如vector随机访问的效率高。list是双向链表，可以向前或者向后遍历，而forward_list是单向链表，只能向前遍历，查找效率就更低了

链表结构比起数组结构还有一个缺点，就是存储成本略高，因为必须要为每个元素附加一个或者两个的指针，指向链表的前后节点

扩容机制：

vector/deque和list/forward_list都可以动态增长来容纳更多的元素，但它们的内部扩容机制却是不一样的

当vector的容量到达上限的时候（capacity），它会再分配一块两倍大小的新内存，然后把旧元素拷贝或者移动过去。这个操作的成本是非常大的，所以，在使用vector的时候最好能够预估容量，使用reserve提前分配足够的空间，减少动态扩容的拷贝代价

deque、list会按照固定的步长（例如N个字节、一个节点）去增加容量。但在短时间内插入大量数据的时候就会频繁分配内存，效果反而不如vector一次分配来得好

如何选择：

如果没有什么特殊需求，首选的容器就是array和vector，它们的速度最快、开销最低，数组的形式也令它们最容易使用，搭配算法也可以实现快速的排序和查找

剩下的deque、list和forward_list则适合对插入删除性能比较敏感的场合，如果还很在意空间开销，那就只能选择非链表的deque了

3）、有序容器

顺序容器的特点是，元素的次序是由它插入的次序而决定的，访问元素也就按照最初插入的顺序。而有序容器则不同，它的元素在插入容器后就被按照某种规则自动排序，所以是有序的

标准库里一共有四种有序容器：set/multiset和map/multimap（底层是通过红黑树实现）。有multi前缀的容器表示可以容纳重复的key

在定义有序容器的时候必须要指定key的比较函数。只不过这个函数通常是默认的less，表示小于关系，不用特意写出来

C++里的int、string等基本类型都支持比较排序，但很多自定义类型没有默认的比较函数，需要重载<或者自定义模板参数

比如说有一个Point类，它是没有大小概念的，但只要给它重载<操作符，就可以放进有序容器里了：

#include <iostream>
#include <set>class Point {
public:Point(int x, int y) : x_(x), y_(y) {}bool operator<(const Point &other) const {if (x_ != other.x_) {return x_ < other.x_;} else {return y_ < other.y_;}}friend std::ostream &operator<<(std::ostream &os, const Point &p) {os << "(" << p.x_ << ", " << p.y_ << ")";return os;}private:int x_;int y_;
};int main() {std::set<Point> points;points.emplace(7, 2);points.emplace(3, 5);for (const auto &point: points) {std::cout << point << std::endl;}return 0;
}

另一种方式是编写专门的函数对象或者lambda表达式，然后在容器的模板参数里指定。这种方式更灵活，而且可以实现任意的排序准则：

#include <iostream>
#include <set>template<typename Iter>
void printRangeWithCommas(Iter begin, Iter end) {if (begin == end) return;for (Iter it = begin; it != end; ++it) {std::cout << *it;if (std::next(it) != end) {std::cout << ",";}}std::cout << "\n";
}int main() {std::set<int> s = {7, 3, 9};printRangeWithCommas(s.begin(), s.end()); // 调用函数打印集合,输出: 3,7,9auto comp = [](auto a, auto b) {return a > b;};std::set<int, decltype(comp)> gs(comp);std::copy(s.begin(), s.end(), std::inserter(gs, gs.end()));printRangeWithCommas(gs.begin(), gs.end()); // 再次调用函数打印另一个集合,输出: 9,7,3return 0;
}

4）、无序容器

无序容器也有四种，名字里也有set和map，只是加上了unordered（无序）前缀，分别是unordered_set/unordered_multiset、unordered_map/unordered_multimap

无序容器用法上与有序容器几乎是一样的，区别在于内部数据结构：它不是红黑树，而是散列表（也叫哈希表，hash table）

因为它采用散列表存储数据，元素的位置取决于计算的散列值，没有规律可言，所以就是无序的

#include <iostream>
#include <unordered_map>int main() {using map_type =std::unordered_map<int, std::string>;map_type dict;dict[1] = "one";dict.emplace(2, "two");dict[10] = "ten";for (auto &x: dict) { // 遍历顺序不确定,既不是插入顺序，也不是大小序std::cout << x.first << "=>"<< x.second << ",";}return 0;
}

无序容器要求key具备两个条件，一是可以计算hash值，二是能够执行相等比较操作。第一个是因为散列表的要求，只有计算hash值才能放入散列表，第二个则是因为hash值可能会冲突，所以当hash值相同时，就要比较真正的key值

#include <iostream>
#include <unordered_set>class Point {
public:Point(int x, int y) : x_(x), y_(y) {}int getX() const { return x_; }int getY() const { return y_; }// 重载operator==用于比较bool operator==(const Point &other) const {return x_ == other.x_ && y_ == other.y_;}// 为了使用Point作为std::unordered_set或std::unordered_map的键,需要定义哈希函数struct Hash {std::size_t operator()(const Point &p) const noexcept {std::size_t h1 = std::hash<int>{}(p.getX());std::size_t h2 = std::hash<int>{}(p.getY());return h1 ^ (h2 << 1);}};// 重载operator<<以便可以直接输出Point对象friend std::ostream &operator<<(std::ostream &os, const Point &p) {return os << "(" << p.x_ << ", " << p.y_ << ")";}private:int x_, y_;
};int main() {std::unordered_set<Point, Point::Hash> pointSet;pointSet.insert(Point(1, 2));pointSet.insert(Point(3, 4));// 尝试插入重复的点,不会成功pointSet.insert(Point(1, 2));for (const auto &point: pointSet) {std::cout << point << std::endl;}return 0;
}

5）、小结

标准容器可以分为三大类，即顺序容器、有序容器和无序容器
所有容器中最优先选择的应该是array和vector，它们的速度最快，开销最低
list是链表结构，插入删除的效率高，但查找效率低
有序容器是红黑树结构，对key自动排序，查找效率高，但有插入成本
无序容器是散列表结构，由hash值计算存储位置，查找和插入的成本都很低
有序容器和无序容器都属于关联容器，元素有key的概念，操作元素实际上是在操作key，所以要定义对key的比较函数或者散列函数

5、算法库

1）、迭代器

迭代器常用的函数如下：

begin()、end()：得到表示两个端点的迭代器
distance()：计算两个迭代器之间的距离
advance()：前进或者后退 N 步
next()、prev()：计算迭代器前后的某个位置

#include <array>int main() {std::array<int, 5> arr = {0, 1, 2, 3, 4}; // array静态数组容器auto b = begin(arr); // 全局函数获取迭代器,首端auto e = end(arr); // 全局函数获取迭代器,末端assert(std::distance(b, e) == 5); // 迭代器的距离auto p = std::next(b); // 获取下一个位置assert(std::distance(b, p) == 1); // 迭代器的距离assert(std::distance(p, b) == -1); // 反向计算迭代器的距离std::advance(p, 2); // 迭代器前进两个位置,指向元素3assert(*p == 3);assert(p == std::prev(e, 2)); // 是末端迭代器的前两个位置return 0;
}

2）、for_each

#include <iostream>
#include <vector>int main() {std::vector<int> v = {3, 5, 1, 7, 10};for (const auto &x: v) { // range for循环std::cout << x << ",";}std::cout << "\n";auto print = [](const auto &x) // 定义一个lambda表达式{std::cout << x << ",";};for_each(cbegin(v), cend(v), print); // for_each算法std::cout << "\n";for_each( // for_each算法,内部定义lambda表达式cbegin(v), cend(v), // 获取常量迭代器[](const auto &x) // 匿名lambda表达式{std::cout << x << ",";});std::cout << "\n";return 0;
}

3）、排序算法

sort()是经典的快排算法，示例如下：

#include <iostream>
#include <vector>int main() {std::vector<int> v = {3, 5, 1, 7, 10};auto print = [](const auto &x) // lambda表达式输出元素{std::cout << x << ",";};std::sort(begin(v), end(v)); // 快速排序for_each(cbegin(v), cend(v), print);return 0;
}

一些常见问题对应的算法：

要求排序后仍然保持元素的相对顺序，应该用stable_sort，它是稳定的
选出前几名（TopN），应该用partial_sort
选出前几名，但不要求再排出名次（BestN），应该用nth_element
中位数（Median）、百分位数（Percentile），还是用nth_element
按照某种规则把元素划分成两组，用partition
第一名和最后一名，用minmax_element

#include <iostream>
#include <vector>template<typename Iter>
void printRangeWithCommas(const std::string &prefix, Iter begin, Iter end) {if (begin == end) return;std::cout << prefix;for (auto it = begin; it != end; ++it) {std::cout << (it == begin ? "" : ",") << *it;}std::cout << '\n';
}int main() {std::vector<int> v = {3, 5, 1, 7, 10};// top3std::partial_sort(begin(v), next(begin(v), 3), end(v)); // 取前3名printRangeWithCommas("top3: ", v.begin(), next(begin(v), 3));// best3std::nth_element(begin(v), next(begin(v), 3), end(v)); // 最好的3个printRangeWithCommas("best3: ", v.begin(), next(begin(v), 3));// medianauto mid_iter = // 中位数的位置next(begin(v), v.size() / 2);std::nth_element(begin(v), mid_iter, end(v)); // 排序得到中位数std::cout << "median: " << *mid_iter << std::endl;// partitionauto pos = std::partition( // 找出所有大于9的数begin(v), end(v), [](const auto &x) // 定义一个lambda表达式{return x > 9;});printRangeWithCommas("values > 9: ", v.begin(), pos);// min/maxauto [minIt, maxIt] = std::minmax_element( // 找出第一名和倒数第一cbegin(v), cend(v));std::cout << "min value: " << *minIt << ", max value: " << *maxIt << std::endl;return 0;
}

在使用这些排序算法时，对迭代器要求比较高，通常都是随机访问迭代器（minmax_element除外），所以最好在顺序容器array/vector上调用

4）、查找算法

binary_search：在已经排好序的区间里执行二分查找，但它只返回一个bool值，告知元素是否存在

#include <vector>int main() {std::vector<int> v = {3, 5, 1, 7, 10, 99, 42};std::sort(begin(v), end(v)); // 快速排序// 二分查找,只能确定元素在不在bool found = binary_search(cbegin(v), cend(v), 7);assert(found);return 0;
}

想要在已序容器上执行二分查找，要用算法lower_bound，它返回第一个大于或等于值的位置

#include <vector>int main() {std::vector<int> v = {3, 5, 1, 7, 10, 99, 42};std::sort(begin(v), end(v));// 找到第一个>=7的位置auto pos = std::lower_bound(cbegin(v), cend(v), 7);bool found = (pos != cend(v)) && (*pos == 7); // 可能找不到,所以必须要判断assert(found); // 7在容器里// 找到第一个>=9的位置pos = std::lower_bound(cbegin(v), cend(v), 9);found = (pos != cend(v)) && (*pos == 9); // 可能找不到,所以必须要判断assert(!found); // 9不在容器里return 0;
}

lower_bound的返回值是一个迭代器，需要做判断才能知道是否真的找到了。判断的条件有两个，一个是迭代器是否有效，另一个是迭代器的值是不是要找的值

upper_bound算法：返回第一个大于值的元素（也是在已序容器上执行二分查找）

对于有序容器set/map，就不需要调用这三个算法了，它们有等价的成员函数find/lower_bound/upper_bound，效果是一样的

#include <iostream>
#include <set>int main() {std::multiset<int> s = {3, 5, 1, 7, 7, 7, 10, 99, 42};auto pos = s.find(7); // 二分查找,返回迭代器assert(pos != s.end());auto lower_pos = s.lower_bound(7); // 获取区间的左端点auto upper_pos = s.upper_bound(7); // 获取区间的右端点auto print = [](const auto &x) {std::cout << x << ",";};// 输出7,7,7std::for_each(lower_pos, upper_pos, print);return 0;
}

标准库里还有一些查找算法可以用于未排序的容器，这些算法以find和search命名，其中用于查找区间的find_first_of/find_end

#include <vector>
#include <array>int main() {std::vector<int> v = {1, 9, 11, 3, 5, 7};// 查找算法,找到第一个出现的位置auto pos = std::find(begin(v), end(v), 3);assert(pos != end(v));// 查找算法,用lambda判断条件pos = std::find_if(begin(v), end(v),[](auto x) {return x % 2 == 0;});assert(pos == end(v));std::array<int, 2> arr = {3, 5};// 查找一个子区间pos = std::find_first_of(begin(v), end(v),begin(arr), end(arr));assert(pos != end(v));return 0;
}

5）、小结

算法是专门操作容器的函数，是一种智能for循环，它的最佳搭档是lambda表达式
算法通过迭代器来间接操作容器，使用两个端点指定操作范围，迭代器决定了算法的能力
for_each算法是for的替代品，以函数式编程替代了面向过程编程
有多种排序算法，最基本的是sort，但应该根据实际情况选择其他更合适的算法，避免浪费
在已序容器上可以执行二分查找，应该使用的算法是lower_bound
list/set/map提供了等价的排序、查找函数，更适应自己的数据结构
find/search是通用的查找算法，效率不高，但不必排序也能使用

6、多线程

1）、仅调用一次

要先声明一个once_flag类型的变量，最好是静态、全局的（线程可见），作为初始化的标志。然后调用专门的call_once()函数，以函数式编程的方式，传递这个标志和初始化函数。这样C++就会保证，即使多个线程重入call_once()，也只能有一个线程会成功运行初始化

#include <iostream>
#include <thread>int main() {static std::once_flag flag; // 全局的初始化标志auto f = []() {std::call_once(flag, // 仅一次调用,注意要传flag[]() { // 匿名lambda,初始化函数,只会执行一次std::cout << "only once" << std::endl;});};// 使用vector管理线程,确保所有线程执行完毕后再退出mainstd::vector<std::thread> threads;for (int i = 0; i < 2; ++i) {threads.emplace_back(f);}// 等待所有线程完成for (std::thread &t: threads) {t.join();}return 0;
}

2）、线程局部存储

有thread_local标记的变量在每个线程里都会有一个独立的副本，是线程独占的

#include <iostream>
#include <thread>int main() {thread_local int n = 0; // 线程局部存储变量auto f = [&](int x) {n += x; // 使用线程局部变量,互不影响std::cout << n << std::endl;};// 使用vector管理线程,确保所有线程执行完毕后再退出mainstd::vector<std::thread> threads;threads.emplace_back(f, 10);threads.emplace_back(f, 20);// 等待所有线程完成for (std::thread &t: threads) {t.join();}return 0;
}

在程序执行后，可以看到两个线程分别输出了10和20，互不干扰

3）、原子变量

目前，C++只能让一些最基本的类型原子化，比如atomic_int、atomic_long等。这些原子变量都是模板类atomic的特化形式，包装了原始的类型，具有相同的接口，用起来和bool、int几乎一模一样，但却是原子化的，多线程读写不会出错

原子变量和原始的类型一个重要的区别是：原子变量禁用了拷贝构造函数，所以在初始化的时候不能用=的赋值形式，只能用圆括号或者花括

#include <iostream>
#include <thread>void incrementAtomicInt(std::atomic_int &counter, int numIterations) {for (int i = 0; i < numIterations; ++i) {++counter;}
}void incrementAtomicLong(std::atomic_long &counter, long numIterations) {for (long i = 0; i < numIterations; ++i) {counter += 10;}
}int main() {const int numThreads = 4;const int iterationsPerThread = 100;std::atomic_int x{0};std::atomic_long y{1000L};std::vector<std::thread> threads;// 对x进行递增操作的线程for (int i = 0; i < numThreads; ++i) {threads.emplace_back(incrementAtomicInt, std::ref(x), iterationsPerThread);}// 对y进行递增操作的线程for (int i = 0; i < numThreads; ++i) {threads.emplace_back(incrementAtomicLong, std::ref(y), iterationsPerThread / 10); // 注意调整迭代次数以匹配期望的增量}// 等待所有线程完成for (std::thread &t: threads) {t.join();}std::cout << "final value of x: " << x << std::endl;std::cout << "final value of y: " << y << std::endl;assert(x == numThreads * iterationsPerThread);assert(y == 1000L + numThreads * (iterationsPerThread / 10) * 10);return 0;
}

除了模拟整数运算，原子变量还有一些特殊的原子操作，比如store、load、fetch_add、fetch_sub、exchange、compare_exchange_weak/compare_exchange_strong以及CAS（Compare And Swap）操作

4）、线程

C++标准库里有专门的线程类thread，使用它就可以简单地创建线程，在名字空间std::this_thread里，还有yield()、get_id()、sleep_for()、sleep_until()等几个方便的管理函数

#include <iostream>
#include <chrono>
#include <thread>int main() {static std::atomic_flag flag{false};static std::atomic_int n;auto f = [&]() {auto value = flag.test_and_set(); // TAS检查原子标志量if (value) {std::cout << "flag has been set." << std::endl;} else {std::cout << "set flag by " << std::this_thread::get_id() << std::endl; // 输出线程id}n += 100; // 原子变量加法运算std::this_thread::sleep_for(std::chrono::milliseconds(n.load() * 10));std::cout << n << std::endl;};std::vector<std::thread> threads;for (int i = 0; i < 2; ++i) {threads.emplace_back(f);}for (std::thread &t: threads) {t.join();}return 0;
}

函数async()含义是异步运行一个任务，隐含的动作是启动一个线程去执行，但不绝对保证立即启动（也可以在第一个参数传递 std::launch::async，要求立即启动线程）

#include <iostream>
#include <chrono>
#include <thread>
#include <future>int main() {auto task = [](auto x) {std::this_thread::sleep_for(std::chrono::milliseconds(x));std::cout << "sleep for " << x << std::endl;return x;};auto f = std::async(task, 10);// 启动一个异步任务f.wait(); // 等待任务完成assert(f.valid());// 确实已经完成了任务std::cout << f.get() << std::endl; // 获取任务的执行结果return 0;
}

async()会返回一个future变量，如果任务有返回值，就可以用成员函数get()获取。不过要特别注意，get()只能调一次，再次获取结果会发生错误，抛出异常 std::future_error

这里还有一个很隐蔽的坑，如果不显式获取async()的返回值（即future对象），它就会同步阻塞直至任务完成（由于临时对象的析构函数）。所以，即使不关心返回值，也总要用auto来配合async()，避免同步阻塞