C++学习笔记（10）

三、其它操作
1）queue &operator=(const queue<T> &q); // 赋值。
2）void swap(queue<T> &q); // 交换。
3）bool operator == (const queue<T> & q) const; // 重载==操作符。
4）bool operator != (const queue<T> & q) const; // 重载!=操作符。
189、STL 其它容器
一、array（静态数组）
1）物理结构
在栈上分配内存，创建数组的时候，数组长度必须是常量，创建后的数组大小不可变。
template<class T, size_t size>
class array{
private:
T elems_[size]; ……
};
2）迭代器
随机访问迭代器。
3）特点
部分场景中，比常规数组更方便（能用于模板），可以代替常规数组。
4）各种操作
1）void fill(const T & val); // 给数组填充值（清零）。
2）size_t size(); // 返回数组的大小。
3）bool empty() const; // 无意义。
4）T &operator[](size_t n);
5）const T &operator[](size_t n) const; // 只读。
6）T &at(size_t n);
7）const T &at(size_t n) const; // 只读。
8）T *data(); // 返回数组的首地址。
9）const T *data() const; // 返回数组的首地址。
10）T &front(); // 第一个元素。
11）const T &front(); // 第一个元素，只读。
12）const T &back(); // 最后一个元素，只读。
13）T &back(); // 最后一个元素。
示例：
#include <iostream>
#include <array>
using namespace std;
void func(int arr[][6],int len)
//void func(int (* arr)[6], int len)
//{
// for (int ii = 0; ii < len; ii++)
// {
// for (int jj = 0; jj < 6; jj++)
// cout << arr[ii][jj] << " ";
// cout << endl;
// }
//}
//void func(const array < array<int, 5>, 10 >& arr)
//{
// for (int ii = 0; ii < arr.size(); ii++)
// {
// for (int jj = 0; jj < arr[ii].size(); jj++)
// cout << arr[ii][jj] << " ";
// cout << endl;
// }
//}
template <typename T>
void func(const T& arr)
{
for (int ii = 0; ii < arr.size(); ii++)
{
for (int jj = 0; jj < arr[ii].size(); jj++)
cout << arr[ii][jj] << " ";
cout << endl;
}
}
int main()
{
//int aa[11] = {1,2,3,4,5,6,7,8,9,10,11}; // 一维数组。
//array<int, 10> aa = { 1,2,3,4,5,6,7,8,9,10 }; // 一维数组。
//for (int ii = 0; ii < 10; ii++) // 传统的方法。
// cout << aa[ii] << " ";
//cout << endl;
//
//for (int ii = 0; ii < aa.size(); ii++) // 利用 array 的 size()方法。
// cout << aa[ii] << " ";
//cout << endl;
//
//for (auto it= aa.begin(); it < aa.end(); it++) // 使用迭代器。
// cout << *it << " ";
//cout << endl;
//for (auto val : aa) // 基于范围的 for 循环。
// cout << val << " ";
//cout << endl;
//int bb[10][6];
//for (int ii = 0; ii < 10; ii++) // 对二维数组赋值。
//{
// for (int jj = 0; jj < 6; jj++)
// bb[ii][jj] = jj * 10 + ii;
//}
//func(bb,10); // 把二维数组传给函数。
array< array<int, 5>, 10 > bb; // 二维数组，相当于 int bb[10][5]。
for (int ii = 0; ii < bb.size(); ii++) // 对二维数组赋值。
{
for (int jj = 0; jj < bb[ii].size(); jj++)
bb[ii][jj] = jj * 10 + ii;
}
func(bb); // 把二维数组传给函数。
}
二、deque（双端队列）
1）物理结构
deque 容器存储数据的空间是多段等长的连续空间构成，各段空间之间并不一定是连续的。
为了管理这些连续空间的分段，deque 容器用一个数组存放着各分段的首地址。
通过建立数组，deque 容器的分段的连续空间能实现整体连续的效果。
当 deque 容器在头部或尾部增加元素时，会申请一段新的连续空间，同时在数组中添加指向该空间
的指针。
2）迭代器
随机访问迭代器。
3）特点
 提高了在两端插入和删除元素的效率，扩展空间的时候，不需要拷贝以前的元素。
 在中间插入和删除元素的效率比 vector 更糟糕。
 随机访问的效率比 vector 容器略低。
4）各种操作
与 vector 容器相同。 三、forward_list（单链表）
1）物理结构
单链表。
2）迭代器
正向迭代器。
3）特点
比双链表少了一个指针，可节省一丢丢内存，减少了两次对指针的赋值操作。
如果单链表能满足业务需求，建议使用单链表而不是双链表。
4）各种操作
与 list 容器相同。 四、multimap
底层是红黑树。
multimap 和 map 的区别在：multimap 允许关键字重复，而 map 不允许重复。
各种操作与 map 容器相同。
五、set&multiset
底层是红黑树。
set 和 map 的区别在：map 中存储的是键值对，而 set 只保存关键字。
multiset 和 set 的区别在：multiset 允许关键字重复，而 set 不允许重复。
各种操作与 map 容器相同。 六、unordered_multimap
底层是哈希表。
unordered_multimap 和 unordered_map 的区别在：unordered_multimap 允许关键字重复，而
unordered_map 不允许重复。
各种操作与 unordered_map 容器相同。 七、unordered_set&unordered_multiset
底层是哈希表。
unordered_set 和 unordered_map 的 区 别 在 ： unordered_map 中 存 储 的 是 键 值 对 ， 而
unordered_set 只保存关键字。
unordered_multiset 和 unordered_set 的区别在：unordered_multiset 允许关键字重复，而
unordered_set 不允许重复。
各种操作与 unordered_map 容器相同。 八、priority_queue（优先队列）
优先级队列相当于一个有权值的单向队列 queue，在这个队列中，所有元素是按照优先级排列的。
底层容器可以用 deque 和 list。
各种操作与 queue 容器相同。
九、stack（栈）
底层容器可以用 deque 和 list。
191、STL 算法
STL 提供了很多处理容器的函数模板，它们的设计是相同的，有以下特点：
1）用迭代器表示需要处理数据的区间。
2）返回迭代器放置处理数据的结果（如果有结果）。
3）接受一个函数对象参数（结构体模板），用于处理数据（如果需要）。 一、函数对象
很多 STL 算法都使用函数对象，也叫函数符（functor），包括函数名、函数指针和仿函数。
函数符的概念：
1）生成器（generator）：不用参数就可以调用的函数符。
2）一元函数（unary function）：用一个参数可以调用的函数符。
3）二元函数（binary function）：用两个参数可以调用的函数符。
改进的概念：
1）一元谓词（predicate）：返回 bool 值的一元函数。
2）二元谓词（binary predicate）：返回 bool 值的二元函数。 二、预定义的函数对象
STL 定义了多个基本的函数符，用于支持 STL 的算法函数。
包含头文件：#include <functional>
三、算法函数
STL 将算法函数分成四组：
1）非修改式序列操作：对区间中的每个元素进行操作，这些操作不修改容器的内容。
2）修改式序列操作：对区间中的每个元素进行操作，这些操作可以容器的内容（可以修改值，也可
以修改排列顺序）。
3）排序和相关操作：包括多个排序函数和其它各种函数，如集合操作。
4）通用数字运算：包括将区间的内容累积、计算两个容器的内部乘积、计算小计、计算相邻对象差
的函数。通常，这些都是数组的操作特性，因此 vector 是最有可能使用这些操作的容器。
前三组在头文件#include <algorithm>中，第四组专用于数值数据，在#include <numeric>中。
详见《C++ Primer plus》，第六版，从 886 页开始。