C++ STL拟容器和容器适配器

容器适配器

除了顺序容器外，标准库还定义了三个顺序容器适配器（adaptor）：stack、queue 和 priority_queue。
容器、迭代器和函数都有适配器。
本质上，一个适配是一种机制，能使某种事物的行为看起来像另外一种事物一样。

定义一个适配器

每个适配器都定义两个构造函数：
默认构造函数创建一个空对象。

	stack <char> S; //空栈

接受一个容器的构造函数拷贝该容器来初始化适配器。

	deque <int> D{ 1,2,3,4,5 };
	stack <int> S2{ D };
	queue <int> Q{ D };

默认情况下，stack 和 queue 是基于 deque 实现的，priority_queue 是在 vector 之上实现的。
我们可以创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。

	vector <int> V{ 1,2,3,4,5 };
	stack <int,vector<int>> S{ V };
	list <char> L{ 'A','B','C' };
	queue <char,list<char>> Q{ L };

对于一个给定的适配器，可以使用那些容器是有限制的。
所有适配器都要求容器具有添加、删除以及访问尾元素的能力；因此，适配器不能构造在 array 和 forward_list 来构造适配器。

栈适配器

stack 适配器定义在 <stack> 头文件中。
stack 只要求 push_back、pop_back 和 back 操作；因此，可以使用除 arrary 和 forward_list 之外的任何容器类型来构造 stack。

	stack <char> S; //空栈
	S.push('A');    //'A' 入栈 
	S.push('B');    //'B' 入栈 
	S.push('C');    //'C' 入栈 
	cout << S.top() << endl; //获取栈顶 'C'
	S.pop();  //'C' 出栈 
	cout << S.top() << endl; //获取栈顶 'B'

每个容器适配器都基于底层容器类型的操作定义了自己的特殊操作。
我们只可以使用适配器操作，而不能使用底层容器类型的操作。

队列适配器

queue 和 priority_queue 适配器定义在 <queue> 头文件中。
queue 要求 back、push_back、front 和 push_front 操作；因此，可以构造于 list 或 deque 之上，但不能基于 vector 构造。
priority_queue 除了 front、push_back 和 pop_back 操作之外还要求随机访问能力；因此，priority_queue 可以构造于 vector 或 deque 之上，但不能基于 list 构造。

	queue <char> Q; //空队
	Q.push('A'); //'A' 入队 
	Q.push('B'); //'B' 入队 
	Q.push('C'); //'C' 入队 
	cout << Q.front() << endl; //返回队头 'A' 
	cout << Q.back() << endl;  //返回队尾 'C' 
	Q.pop(); //'A' 出队
	cout << Q.front() << endl; //返回队头 'B' 

priority_queue 允许我们为队列中的元素建立优先级，用于控制元素被 top() 获取的顺序。
新加入的元素会排在所有优先级比它低的已有元素之前。
默认情况下，标准库在元素类型上使用<运算符来确定相对优先级。

拟容器

array

array 定义在<array>中，是固定大小的给定类型的元素序列，元素数目在编译时指定。
因此，array 连同其元素可以在栈中、对象内或静态存储中分配空间。
array 在哪个作用域内定义，元素就会在其中分配。

数组的定义和初始化

标准库 array 具有固定大小；定义一个 array 时，必须指定元素类型的同时，还要指定容器大小。
array 的元素数目必须是常量表达式。

1. 在定义数组时对全部数组元素赋予初值。
   例：array <int, 5> arr{ 1,2,3,4,5 };
2. 可以只对一部分元素赋值，剩余未被赋予初值的元素赋予默认值 0。
   例：array <int, 5> arr{ 1,2,3 }; //等价于array <int, 5> arr{ 1,2,3,0,0 };
3. 数组初始化为 0。
   例：array <int, 5> arr { 0 };
4. 数组元素数目可以为零。
   例：array<int, 0> arr;
5. 数组的默认初始化，其中元素值是未定义的。
   例：array<int,5> arr; //arr 内的元素值未定义
6. 不能对内置数组类型进行拷贝或对象赋值操作，但 array 并无此限制：

	array <int, 5> arr1 { 1,2,3,4,5 };
	array <int, 5> arr2 = arr1; //数组拷贝

array 的拷贝要求容器的类型和大小必须相同，容器内元素类型必须相同。

数组的赋值运算

	array <int, 5> arr1{ 1,2,3,4,5 };
	array <int, 5> arr2{ 0 };
	arr2 = arr1;          
	arr2 = { 3,4,5,6,7 }; 
	arr2 = { 3,4 };       //等价于arr2 = { 3,4,0,0,0 };  

array 的赋值要求容器的类型和大小必须相同，容器内元素类型必须相同。

bitset

一个 bitset<N> 就是一个包含 N 个二进制位的数组，它定义在<bitset>中。
bitset 提供了一种位引用（代理）类型，因为用内置指针是不可能寻址一个二进制位的。
如果一个索引（也称位位置）超出范围，会抛出一个 out_of_range 异常。
位位置从右至左编号，与二进制位在机器字中的顺序相同。
bitset 不提供迭代器。

定义和初始化 bitset

当定义一个 bitset 时，需要声明它包含多少个二进制位。

	bitset<8> bit; //声明 bit 包含一个 8 位的二进制数。 

默认初始化

	bitset<8> bit; // 8 个二进制 0

使用一个整型值初始化

	bitset<8> bit1{ 128 };  // bit1 的值为 10000000
	cout << bit1 << endl;
	bitset<8> bit2{ 0xfe }; // bit2 的值为 11111110
	cout << bit2 << endl;

使用一个 string 对象初始化

一个用来初始化 setbit 的 string 对象用字符'1'表示值 1，用字'0'表示值 0；其它字符都会导致抛出 invalid_argument 异常。

	string str{ "11001100" };
	bitset<8> bit{ str }; 
	cout << bit << endl; // bit 的值为 11001100

如果 string 包含的字符数比 bitset 的位数少，则 bitset 的高位被置为 0.

	string str{ "1111" };
	bitset<8> bit{ str };
	cout << bit << endl; // bit 的值为 00001111

从 string 对象的位置 i 开始，拷贝 n 个字符。

	string str{ "10111001" };
	bitset<8> bit1(str, 0, 4); // 从 str[0] 的位置开始，拷贝 4 个字符   
	cout << bit1 << endl;      // bit1 的值为 00001011
	bitset<8> bit2(str,4);     // 从 str[4] 的位置开始，拷贝至 str 的末尾  
	cout << bit2 << endl;      // bit2 的值为 00001001

使用一个字符串字面值初始化

	bitset<8> bit{ "1111" };
	cout << bit << endl; // bit 的值为 00001111

从字符串字面值的起始位置开始，拷贝 n 个字符。

	bitset<8> bit("11001001",5 );
	cout << bit << endl; // bit 的值为 00011001

成员函数	功能
bitset bit{};	N 个二进制 0
bitset bit{n};	用 n 个二进制位初始化，n 是一个 unsigned long long int
bitset bit{s,i,n,z,o};	用 s 中区间[i,i+n)内的 n 个二进制位初始化；s 是一个 basic_string<C,Tr,A>；z 是表示 0 的字符，类型为 C；o 是表示 1 的字符，类型为 C；显示构造函数
bitset bit{s,i,n,z};	bitset bit{s,i,n,z,C{‘1’}};
bitset bit{s,i,n};	bitset bit{s,i,n,C{‘0’},C{‘1’}};
bitset bit{s,i};	bitset bit{s,i,npos,C{‘0’},C{‘1’}};
bitset bit{s};	bitset bit{s,0,npos,C{‘0’},C{‘1’}};
bitset bit{p,n,z,o};	用序列[p,p+n)内的 n 个二进制位初始化；p 是一个类型为C*的 C 风格字符串；z 是表示 0 的字符，类型为 C；o 是表示 1 的字符，类型为 C；显示构造函数
bitset bit{p,n,z};	bitset bit{p,n,z,C{‘1’}};
bitset bit{p,n};	bitset bit{p,n,C{‘0’},C{‘1’}};
bitset bit{p};	bitset bit{p,npos,C{‘0’},C{‘1’}};

nops 位置为string<C>的”尾后位置“，表示“所有字符直至末尾”的含义。

bitset 操作

bitset 提供了访问单独的二进制位和操纵整体位集合的运算符。

访问位

位位置从 0 开始编号，从右至左编号。

	bitset<8> bit{ "00110011" };
	cout << bit[0] << endl;     // 输出 1
	cout << bit.test(7) << endl;// 输出 0；超出范围，抛出 out_of_range

位设置和清除

所有位置 1

	bitset<8> bit{ "00110011" };
	cout << bit.set() << endl; // 输出 11111111

所有位清零

	bitset<8> bit{ "00110011" };
	cout << bit.set() << endl; // 输出 00000000

单独位置 1

	bitset<8> bit{ "11110000" };
	cout << bit.set(0,1) << endl; // 输出 11110001

单独位清零

	bitset<8> bit{ "00001111" };
	cout << bit.set(0,0) << endl; // 输出 00001110
	cout << bit.reset(1) << endl; // 输出 00001100

位运算

移位运算符<<和>>

bit << n的值是将 bit 中的位左移 n 位后的结果；每次 bit 的最左端移出一位，bit 的最右端补一个 0 位。

	bitset<8> bit{"11010011"};
	cout << (bit << 2) <<endl; //输出 01001100

bit << n的值是将 bit 中的位右移 n 位后的结果；每次 bit 的最右端移出一位，bit 的最左端补一个 0 位。

	bitset<8> bit{"11010011"};
	cout << (bit >> 2) << endl; //输出 00110100

按位取反运算符~

运算~将每一个 0 替换成 1，将每一个 1 替换成 0。

	bitset<8> bit{ "11010011" };
	cout << (~bit) << endl; //输出 00101100
	bit.flip();             // bit 的值为 00101100
	cout << bit << endl;
	bit.flip(0);            // bit[0] = ~bit[0]
	cout << bit << endl;    //输出 00101101

按位与运算符&

逻辑与&运算：如果参与运算的两个位只要有一个为 1，则该位的结果为 0。

	bitset<8> bit1{ "11010011" };
	bitset<8> bit2{ "10101011" };
	cout << (bit1 & bit2) <<endl; //输出 10000011
	bit1 &= bit2; // bit1 的值为 10000011
	cout << bit1 << endl; 

按位或运算符|

逻辑或|运算：如果参与运算的两个位只要有一个为 1，则该位的结果为 1。

	bitset<8> bit1{ "11010011" };
	bitset<8> bit2{ "10101011" };
	cout << (bit1 | bit2) << endl; //输出 11111011
	bit1 |= bit2; // bit1 的值为 11111011
	cout << bit1 << endl; 

按位异或运算符^

逻辑异或^运算：如果参与运算的两个位值不相同，则该位的结果为 1。

	bitset<8> bit1{ "11010011" };
	bitset<8> bit2{ "10101011" };
	cout << (bit1 ^ bit2) << endl; //输出 01111000
	bit1 ^= bit2; // bit1 的值为 01111000
	cout << bit1 << endl; 

其它常用操作

成员函数	功能
n = bit.to_ulong();	n 是 bit 对应的 unsigned long 值
n = bit.to_ullong();	n 是 bit 对应的 unsigned long long 值
s = bit.to_stirng<C,Tr,A>(c0,c1);	s[i] = (bit[i])?c1:c0；s 是一个 basic_string<C,Tr,A>
s = bit.to_stirng<C,Tr,A>(c0);	s = bit.template_to_string<C,Tr,A>(c0,C{‘1’})
s = bit.to_stirng<C,Tr,A>();	s = bit.template_to_string<C,Tr,A>(C{‘0’},C{‘1’})
n = bit.count();	n 是 bit 中 1 的个数
n = bit.size();	n 是 bit 的二进制位数
bit == bit2	bit 和 bit2 值相等？
bit != bit2	!(bit == bit2)
bit.all();	bit 全为 1 ？
bit.any();	bit 中有 1 ？
bit.none();	bit 没有 1 ？
hash<bitset<N>>;	hash 针对 bitset<N> 的特例化版本

vector<bool>

vector<bool> 是 vector 的一个特例化版本，提供了二进制位（bool 值）的紧凑存储。
与 bitset 不同的是：vector<bool> 具有分配器，也能改变大小；而且，vector<bool> 中索引更大的元素保存在高地址。

元组

标准库提供了两种任意类型的值组成单一对象的方法：

• pair 保存两个值
• tuple 保存零个或多个值

pair

在头文件<utility>中，标准库提供了 pair 类，用来处理对值。
一个 pair 对象保存两个数据成员。

对 pair 的初始化和赋值

当创建一个 pair 对象时，必须提供两个类型名，两个类型不要求一样。

	pair <int, char> p{ 10,'A' }; //指定成员的初始值

可以使用 make_pair 函数生成一个 pair 对象。

	auto p = make_pair(1,'A');    //返回一个指定了成员初始值的 pair

如果未指定成员的初始值，则每个成员都进行值初始化。

	pair <int, char> p;         

成员函数	功能
pair p{};	pair p{T{},U{}}；默认构造函数
pair p{x,y};	p.first 初始化为 x；p.second 初始化为 y
pair p{p2};	从 pair p2 构造对象
pair p{piecewise_construct,t,t2};	用 tuple t 的元素构造 p.first；用 tuple t2 的元素构造 p.second
p = p2	拷贝赋值
p = move(p2)	移动赋值
p.swap(p2)	交换 p 和 p2 的值

pair 对象的数据成员

pair 对象的两个数据成员是 public 的，两个成员分别命名为 first 和 second，使用普通的成员访问运算符来访问它们。

	pair <int, char> p{ 10,'A' };
	cout << p.first << endl;  //输出 10
	cout << p.second << endl; //输出 A

pair 的辅助函数

成员函数	功能
p = make_pair{x,y};	p 是一个 pair<decltype(x),<decltype(y)>，保存 x 和 y；若可能，会移动 x 和 y
p == p2	p.first == p2.first && p.second == p2.second
p != p2	!(p == p2)
p < p2	p.first < p2.first
p > p2	p2 < p
p <= p2	!(p > p2)
p >= p2	!(p < p2)
tuple_size<T>::value;	类型 T 的 pair 大小
tuple_element<N,T>::type;	若 N == 0，得到 first 的类型，若 N == 1，得到 second 的类型
get<N>§;	pair p 的第 N 个元素的引用；N 必须是 0 或 1

tuple

在<tuple>中，标准库提供了 tuple 类和各种支持组件。
一个 tuple 对象就是一个包含 N 个任意类型元素的序列。

对 tuple 的初始化和赋值

当定义一个 tuple 对象时，需要指出每个成员的类型，这个构造函数是 explicit 的。

	tuple<int, char,string> tup {10,'A',"Hello"};

可以使用 make_tuple 函数生成 tuple 对象。

	auto tup = make_tuple(10, 'A', "Hello");

如果未指定成员的初始值，则每个成员都进行值初始化。

	tuple<int, char,string> tup;

可以用另一个 tuple 对象初始化一个 tuple 对象。

	tuple<int, char, string> t1 { 10, 'A', "Hello" };
	tuple<int, char, string> t2{ t1 };

成员函数	功能
tuple t{};	空 tuple；默认构造函数
tuple t{args};	用 args 的元素初始化 t 的元素；显示构造函函数
tuple t{t2};	用 tuple t2 构造 t
tuple t{p};	用 pair p 构造 t
tuple t{allocator_arg_t,a,args};	用 args 和 分配器 a 构造 t
tuple t{allocator_arg_t,a,t2};	用 tuple t2 和 分配器 a 构造 t
tuple t{allocator_arg_t,a,p};	用 pair p 和 分配器 a 构造 t
t = t2	拷贝赋值 tuple t2
t = move(t2)	移动赋值 tuple t2
t = p	拷贝赋值 pair p
t = move§	移动赋值 pair p
t.swap(t2)	交换 tuple t 和 t2 的值；不抛出异常

tuple 的辅助函数

访问 tuple 的成员
尖括号中的值必须是一个整型常量表达式，且从 0 开始计数。

	tuple<int, char, string> t { 10, 'A', "Hello" };
	cout << get<0>(t) << endl; //输出 10
	cout << get<1>(t) << endl; //输出 A
	cout << get<2>(t) << endl; //输出 Hello

查询 tuple 成员的数量和类型

	tuple<int, char, string> t { 10, 'A', "Hello" };
	auto N = tuple_size<decltype(t)>::value;
	tuple_element<0, decltype(t)>::type T = get<0>(t);

函数 tie() 可以用来从 tuple 中抽取元素

	tuple<int, char, string> t { 10, 'A', "Hello" };
	int i;
	char c;
	string str;
	tie(i, c, str) = t;
	cout << i << endl;   //输出 10
	cout << c << endl;   //输出 A
	cout << str << endl; //输出 Hello

成员函数	功能
t = make_tuple{args};	用 args 创建 tuple
t = forward_as_tuple{args};	t 是一个 tuple，包含指向 args 中元素的右值引用，因此可以利用 t 转发 args 中的元素
t = tie{args};	t 是一个 tuple，包含指向 args 中元素的左值引用，因此可以利用 t 向 args 中的元素赋值
t = tuple_cat{args};	连接 tuple：args 是一个或多个 tuple；args 中 tuple 的成员按序保存在 t 中
tuple_size<T>::value;	tuple T 的元素数
tuple_element<N,T>::type;	tuple T 的第 N 个元素的类型
get<N>(t);	tuple t 的第 N 个元素的引用
t == t2	t 和 t2 的所有元素都相等？
t != t2	!(t == t2)
t < t2	在字典序中 t < t2 ?
t > t2	t2 < t
t <= t2	!(t > t2)
t >= t2	!(t < t2)
uses_allocator<T,A>::value	一个 tuple<T> 可以用一个类型为 A 的分配器进行分配吗？
swap(t,t2)	t.swap(t2)