数据结构学习笔记-2.2：C++ STL 容器、关联容器、容器适配器

⚪ 本文内容主要讲解C++ STL容器在竞赛中的使用

⚪ 本文参考资料：Cppreference (受支持的C++规范均已标明)

array` (C++11)

std::array 是 STL 提供的 内存连续的 、 固定长度 的数组数据结构。其本质是对原生数组的直接封装。

为什么要用 array

array 实际上是 STL 对数组的封装。它相比 vector 牺牲了动态扩容的特性，但是换来了与原生数组几乎一致的性能（在开满优化的前提下）。因此如果能使用 C++11 特性的情况下，能够使用原生数组的地方几乎都可以直接把定长数组都换成 array ，而动态分配的数组可以替换为 vector 。

成员函数

隐式定义的成员函数

函数	作用
operator=	以来自另一 array 的每个元素重写 array 的对应元素

元素访问

函数	作用
at	访问指定的元素，同时进行越界检查
operator[]	访问指定的元素， 不 进行越界检查
front	访问第一个元素
back	访问最后一个元素
data	返回指向内存中数组第一个元素的指针

at 若遇 pos >= size() 的情况会抛出 std::out_of_range 。

容量

函数	作用
empty	检查容器是否为空
size	返回容纳的元素数
max_size	返回可容纳的最大元素数

由于每个 array 都是固定大小容器， size() 返回的值等于 max_size() 返回的值。

操作

函数	作用
fill	以指定值填充容器
swap	交换内容

注意，交换两个 array 是 Θ ( size ) \Theta(\text{size}) Θ(size) 的，而非与常规 STL 容器一样为 O ( 1 ) O(1) O(1) 。

非成员函数

函数	作用
operator== 等	按照字典序比较 array 中的值
std::get	访问 array 的一个元素
std::swap	特化的 std::swap 算法

下面是一个 array 的使用示例：

// 1. 创建空array，长度为3; 常数复杂度
std::array v0;
// 2. 用指定常数创建array; 常数复杂度
std::array v1{1, 2, 3};

v0.fill(1);  // 填充数组

// 访问数组
for (int i = 0; i != arr.size(); ++i) cout ”间有一个空格。如果没有空格，编译器会将其误认为“>>”运算符而无法正确编译。 
q.push(a)：使a入队。
q.top()：返回优先级最高的元素，但不会移除元素。
q.pop()：移除优先级最高的元素。该函数没有返回值。
q.empty()：判断队列是否为空。
q.size()：返回队列中已有元素的个数。
 
如果需要使用自己的结构体，你需要重载复制构造函数和“>”（“