现代C++之容器
现代C++之容器
现代C++之容器
本节将深入学习现代C++实战30讲中的第4节与第5节容器所提到的内容。正文中的一些文字直接引用自上面。
1.string
string 是模板 basic_string 对于 char 类型的特化，可以认为是一个只存放字符 char 类型数据的容器。“真正”的容器类与 string 的最大不同点是里面可以存放任意类型的对象。
string 当然是为了存放字符串。和简单的 C 字符串不同：
- string 负责自动维护字符串的生命周期
- string 支持字符串的拼接操作（如之前说过的 + 和 +=）
- string 支持字符串的查找操作（如 find 和 rfind）
- string 支持从 istream 安全地读入字符串（使用 getline）
- string 支持给期待 const char* 的接口传递字符串内容（使用 c_str）
- string 支持到数字的互转（stoi 系列函数和 to_string）
- 等等
在原文中比较重要的几句话来了：
- 推荐你在代码中尽量使用 string 来管理字符串。
- 对于对外暴露的接口，则不建议。
不建议在接口中使用const string&，除非确知调用者已经持有 string：如果函数里不对字符串做复杂处理的话，使用 const char* 可以避免在调用者只有 C 字符串时编译器自动构造 string，这种额外的构造和析构代价并不低。
反过来，如果实现较为复杂、希望使用 string 的成员函数的话，那就应该考虑下面的策略：
- 如果不修改字符串的内容，使用 const string& 或 C++17 的 string_view 作为参数类型。后者是最理想的情况，因为即使在只有 C 字符串的情况，也不会引发不必要的内存复制。
- 如果需要在函数内修改字符串内容、但不影响调用者的该字符串，使用 string 作为参数类型（自动拷贝）。
- 如果需要改变调用者的字符串内容，使用 string& 作为参数类型（通常不推荐）。
2.vector
2.1 异常安全性
vector 通常保证强异常安全性，如果元素类型没有提供一个保证不抛异常的移动构造函数，vector 通常会使用拷贝构造函数。
因此，对于拷贝代价较高的自定义元素类型，我们应当定义移动构造函数，并标其为 noexcept，或只在容器中放置对象的智能指针。
例如：
#include <iostream>
#include <vector>
using namespace std;
class Obj1 {
public:
Obj1()
{
cout << "Obj1()\n";
}
Obj1(const Obj1&)
{
cout << "Obj1(const Obj1&)\n";
}
Obj1(Obj1&&)
{
cout << "Obj1(Obj1&&)\n";
}
};
class Obj2 {
public:
Obj2()
{
cout << "Obj2()\n";
}
Obj2(const Obj2&)
{
cout << "Obj2(const Obj2&)\n";
}
Obj2(Obj2&&) noexcept
{
cout << "Obj2(Obj2&&)\n";
}
};
int main()
{
vector<Obj1> v1;
v1.reserve(2);
v1.emplace_back();
v1.emplace_back();
v1.emplace_back();
vector<Obj2> v2;
v2.reserve(2);
v2.emplace_back();
v2.emplace_back();
v2.emplace_back();
}
输出：
Obj1()
Obj1()
Obj1()
Obj1(const Obj1&)
Obj1(const Obj1&)
Obj1()
Obj2()
Obj2()
Obj2()
Obj2(Obj2&&)
Obj2(Obj2&&)
头两个在已有空间上成功构造。第三个时发现空间不足，系统会请求更大的空间，大小由实现决定（比如两倍）。有了足够的空间后，就会在新空间的第三个的位置构造（第三个obj1），成功之后再把头两个拷贝或移动过来。
如果调用改为：
vector<Obj1> v1;
v1.emplace_back();
v1.emplace_back();
v1.emplace_back();
v1.emplace_back();
输出就变为：
Obj1()
Obj1()
Obj1(const Obj1&)
Obj1()
Obj1(const Obj1&)
Obj1(const Obj1&)
Obj1()
第一个emplace_back后，容量为1，第二个emplace_back后，构造第二个obj1的时候，容量不够了，分配新的空间，此时空间为原来两倍，在新的空间构造第2个位置构造obj1，再把第一个拷贝或移动到新的空间上。进入第三个v1.emplace_back后，此时容量为2，容量不够了，再次分配重复前面操作，容量变为4，在新容量的第3个位置构造obj1，再把前面两个拷贝到新分配空间。最后一次v1.emplace_back,容量充足，直接构造即可。
vector 的一个主要缺陷是大小增长时导致的元素移动。如果可能，尽早使用 reserve 函数为 vector 保留所需的内存，这在 vector 预期会增长很大时能带来很大的性能提升。
2.2 resize与reserve
两者区别
vector 的reserve增加了vector的capacity，但是它的size没有改变！而resize改变了vector的capacity同时也增加了它的size！
区别1：
（1）reserve是容器预留空间，但在空间内不真正创建元素对象。所以在没有添加新的对象之前，不能引用容器内的元素。加入新的元素时，要调用push_back()/insert()函数。
（2）resize是改变容器的大小，且在创建对象。因此，调用这个函数之后，就可以引用容器内的对象了。因此当加入新的元素时，用operator[]操作符，或者用迭代器来引用元素对象。此时再调用push_back()函数，是加在这个新的空间后面的。
区别2：
两个函数的参数形式也有区别的：
void reserve(size_type __n)
void resize(size_type __new_size, const value_type& __x)
void resize(size_type __new_size)
reserve函数一个参数，即需要预留容器的空间；
resize函数可以有两个参数，第一个参数是容器新的大小， 第二个参数是要加入容器中的新元素，如果这个参数被省略，那么就调用不带第二个参数的resize函数。
例如：
vector<int> myVec;
myVec.reserve( 100 ); // 新元素还没有构造,
// 此时不能用[]访问元素
for (int i = 0; i < 100; i++ )
{
myVec.push_back( i ); //新元素这时才构造
}
myVec.resize( 102 ); // 用元素的默认构造函数构造了两个新的元素
myVec[100] = 1; //直接操作新元素
myVec[101] = 2;
3.list与forward_list
list 是双向链表，从 C++11 开始，前向列表 forward_list 成了标准的一部分。为什么会需要这么一个阉割版的 list 呢？
原因是，在元素大小较小的情况下，forward_list 能节约的内存是非常可观的；在列表不长的情况下，不能反向查找也不是个大问题。提高内存利用率，往往就能提高程序性能，更不用说在内存可能不足时的情况了。
4.queue与stack
（1）为什么 stack（或 queue）的 pop 函数返回类型为 void，而不是直接返回容器的 top（或 front）成员？
因为 stack(queue)为保证强异常安全性，如果元素类型没有提供一个保证不抛异常的移动构造函数， 通常会使用拷贝构造函数。pop作用是释放元素，c++98设计时还没有移动构造的概念，所以如果返回成员，必须要调用拷贝构造函数，这时分配空间可能出错，导致构造失败，要抛出异常，所以没必要返回成员。而c++11后有了移动，在多线程的环境里，移动返回加弹出实际上就变得有用了。
（2）stack与内存管理栈区别？
stack 跟我们前面讨论内存管理时的栈有一个区别：在这里下面是低地址，向上则地址增大；而我们讨论内存管理时，高地址在下面，向上则地址减小，方向正好相反。
5.关联容器
关联容器有 set（集合）、map（映射）、multiset（多重集）和 multimap（多重映射）。跳出 C++ 的语境，map（映射）的更常见的名字是关联数组和字典 ，而在 JSON 里直接被称为对象（object）。在 C++ 外这些容器常常是无序的；在 C++ 里关联容器则被认为是有序的。
与序列容器相比，关联容器没有前、后的概念及相关的成员函数，但同样提供 insert、emplace 等成员函数。此外，关联容器都有 find、lower_bound、upper_bound 等查找函数，结果是一个迭代器：
- find(k) 可以找到任何一个等价于查找键 k 的元素（!(x < k || k < x)）
- lower_bound(k) 找到第一个不小于查找键 k 的元素（!(x < k)）
- upper_bound(k) 找到第一个大于查找键 k 的元素（k < x）
如果你需要在 multimap 里精确查找满足某个键的区间的话，建议使用 equal_range，可以一次性取得上下界（半开半闭）。
示例：
map<string, int> mp{
{"one", 1},
{"two", 2},
{"three", 3},
{"four", 4}
};
cout << mp << endl;
mp.insert({"four", 4});
cout << mp << endl;
cout << (mp.find("four") == mp.end()) << endl;
cout << (mp.find("five") == mp.end()) << endl;
mp["five"] = 5;
cout << mp << endl;
multimap<string, int> mmp{
{"one", 1},
{"two", 2},
{"three", 3},
{"four", 4}
};
cout << mmp << endl;
mmp.insert({"four", -4});
cout << mmp << endl;
cout << (mp.find("four")->second) << endl;
cout << (mp.lower_bound("four")->second) << endl;
cout << (mp.upper_bound("four")->second) << endl;
cout << ((--mp.upper_bound("four"))->second) << endl;
multimap<string, int>::iterator
lower, upper;
std::tie(lower, upper) =
mmp.equal_range("four");
cout << (lower != upper) << endl; // 检测区间非空
cout << lower->second << endl;
cout << (--upper)->second << endl;
通过比较来进行查找、插入和删除，复杂度为对数 O(log(n))，有没有达到更好的性能的方法？
那么就是无序关联容器。
6.无序关联容器
从 C++11 开始，每一个关联容器都有一个对应的无序关联容器，它们是：
- unordered_set
- unordered_map
- unordered_multiset
- unordered_multimap
这些容器和关联容器非常相似，主要的区别就在于它们是“无序”的。这些容器不要求提供一个排序的函数对象，而要求一个可以计算哈希值的函数对象。你当然可以在声明容器对象时手动提供这样一个函数对象类型，但更常见的情况是，我们使用标准的hash 函数对象及其特化。
#include <complex> // std::complex
#include <iostream> // std::cout/endl
#include <unordered_map> // std::unordered_map
#include <unordered_set> // std::unordered_set
#include "output_container.h"
using namespace std;
namespace std {
template <typename T>
struct hash<complex<T>> {
size_t
operator()(const complex<T>& v) const
noexcept
{
hash<T> h;
return h(v.real()) + h(v.imag());
}
};
} // namespace std
int main()
{
unordered_set<int> s{
1, 1, 2, 3, 5, 8, 13, 21
};
cout << s << endl;
unordered_map<complex<double>,
double>
umc{{{1.0, 1.0}, 1.4142},
{{3.0, 4.0}, 5.0}};
cout << umc << endl;
}
输出：
{ 21, 8, 5, 3, 13, 2, 1 }
{ (3,4) => 5, (1,1) => 1.4142 }
上述在 std 名空间中添加了特化，这是少数用户可以向 std 名空间添加内容的情况之一。正常情况下，向 std 名空间添加声明或定义是禁止的，属于未定义行为。
从实际的工程角度，无序关联容器的主要优点在于其性能。关联容器和priority_queue的插入和删除操作，以及关联容器的查找操作，其复杂度都是 O(log(n))，而无序关联容器的实现使用哈希表 ，可以达到平均 O(1)！但这取决于我们是否使用了一个好的哈希函数：在哈希函数选择不当的情况下，无序关联容器的插入、删除、查找性能可能成为最差情况的 O(n)，那就比关联容器糟糕得多了。
7.array
C 数组在 C++ 里继续存在，主要是为了保留和 C 的向后兼容性。C 数组本身和 C++ 的容器相差是非常大的：
- C 数组没有 begin 和 end 成员函数（虽然可以使用全局的begin 和 end 函数）
- C 数组没有 size 成员函数（得用一些模板技巧来获取其长度）
- C 数组作为参数有退化行为，传递给另外一个函数后那个函数不再能获得 C 数组的长度和结束位置在 C 的年代，大家有时候会定义这样一个宏来获得数组的长度：
#define ARRAY_LEN(a) \
(sizeof(a) / sizeof((a)[0]))
void test(int a[8])
{
cout << ARRAY_LEN(a) << endl;
}
如果在一个函数内部对数组参数使用这个宏，结果肯定是错的。现在 GCC 会友好地发出警告：
warning: sizeof on array function parameter will return size of ‘int *’ instead of ‘int [8]’ [-Wsizeof-array-argument]
C++17 直接提供了一个 size 方法，可以用于提供数组长度，并且在数组退化成指针的情况下会直接失败：
#include <iostream> // std::cout/endl
#include <iterator> // std::size
void test(int arr[])
{
// 不能编译
// std::cout << std::size(arr)
// << std::endl;
}
int main()
{
int arr[] = {1, 2, 3, 4, 5};
std::cout << "The array length is "
<< std::size(arr)
<< std::endl;
test(arr);
}
此外，C 数组也没有良好的复制行为。你无法用 C 数组作为 map 或 unordered_map 的键类型。下面的代码演示了失败行为：
#include <map> // std::map
typedef char mykey_t[8];
int main()
{
std::map<mykey_t, int> mp;
mykey_t mykey{"hello"};
mp[mykey] = 5;
// 轰，大段的编译错误
}
如果不用 C 数组的话，我们该用什么来替代呢？
我们有三个可以考虑的选项：
- 如果数组较大的话，应该考虑 vector。vector 有最大的灵活性和不错的性能。
- 对于字符串数组，当然应该考虑 string。
- 如果数组大小固定（C 的数组在 C++ 里本来就是大小固定的）并且较小的话，应该考虑 array。array 保留了 C 数组在栈上分配的特点，同时，提供了 begin、end、size 等通用成员函数。
array 可以避免 C 数组的种种怪异行径。上面的失败代码，如果使用 array 的话，稍作改动就可以通过编译：
#include <array> // std::array
#include <iostream> // std::cout/endl
#include <map> // std::map
#include "output_container.h"
typedef std::array<char, 8> mykey_t;
int main()
{
std::map<mykey_t, int> mp;
mykey_t mykey{"hello"};
mp[mykey] = 5; // OK
std::cout << mp << std::endl;
}