-- TOC --
前面已经有几篇笔记，涉及到了编程中最常用的顺序存储数据结构，在C++中，他们都属于顺序容器：
string，这是以char为类型的类似vector的容器，被抽象成字符串对象。vector，支持任意位置\(O(1)\)访问（内存是一整块，按type大小分割），可动态扩展或收缩容量，在尾部插入删除效率高。deque，如下介绍。array，如下介绍，固定size，支持任意位置\(O(1)\)访问，将普通数组抽象成更通用的array对象，并提供常用操作接口。list，访问任意位置需要\(O(n)\)（双向链表结构），可动态扩展或收缩容量，任意位置插入的效率都很高。forward_list，如下。container adaptor:
queue，如下。stack，如下。priority_queue，如下。std::array是具有固定大小的数组容器，它不支持添加或删除元素等改变大小的操作。当定义一个array时，除了指定元素类型，还要指定容器大小。
既然有了内置的普通数组，为什么还要引入array呢？
内置的数组有很多麻烦的地方，比如无法直接做对象赋值，无法直接拷贝等等，同时内置的数组又有很多比较难理解或容易出错的地方。C++11引入array容器来代替内置数组来降低对程序员的要求。
std::array的接口：
// element access
at
operator[]
front
back
data
// iterators
begin
cbegin
rbegin
crbegin
end
cend
rend
crend
// capacity
empty
size
max_size
// operations
fill
swap
// non-member functions
to_array // creates a std::array object from a built-in array
There is a special case for a zero-length array (N == 0). In that case, array.begin() == array.end(), which is some unique value. The effect of calling front() or back() on a zero-sized array is undefined.
std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. In addition, insertion and deletion at either end of a deque never invalidates pointers or references to the rest of the elements. deque支持indexed access，具体就是可以at或[]。deque在两端做插入和删除都很快，并且插入删除后，不会影响对其它元数的指针或引用。
As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one. deque内部元素并非顺序存储，典型的实现方法为使用独立申请的大小固定的array序列，并配上bookkeeping。因此，indexed access需要做两次指针的dereference。而vector在indexed access的时候，只做一次指针dereference。deque必然需要更多的internal memory cost。
https://en.cppreference.com/w/cpp/container/deque
The std::queue class is a container adaptor that gives the programmer the functionality of a queue - specifically, a FIFO (first-in, first-out) data structure. 这就是所谓的容器适配器。
The class template acts as a wrapper to the underlying container - only a specific set of functions is provided. The queue pushes the elements on the back of the underlying container and pops them from the front. 将地层容器包裹起来，只提供一组特别的接口，外在表现为一个FIFO队列。push为地层容器的push_back，pop为地层容器的pop_front。（deque和list满足，标准默认使用deque）
https://en.cppreference.com/w/cpp/container/queue
std::forward_list is a container that supports fast insertion and removal of elements from anywhere in the container. Fast random access is not supported. It is implemented as a singly-linked list. Compared to std::list this container provides more space efficient storage when bidirectional iteration is not needed. 单向链接队列，当不需要两个方向的操作的时候，forward_list的存储效率更高。内部只有head，因此很多接口都是在head部分操作。
https://en.cppreference.com/w/cpp/container/forward_list
The std::stack class is a container adaptor that gives the programmer the functionality of a stack - specifically, a LIFO (last-in, first-out) data structure. 这是默认包裹在deque上的LIFO容器适配器。
The class template acts as a wrapper to the underlying container - only a specific set of functions is provided. The stack pushes and pops the element from the back of the underlying container, known as the top of the stack.
https://en.cppreference.com/w/cpp/container/stack
A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction. 优先队列，用\(O(1)\)得到（默认）最大的元素。
https://en.cppreference.com/w/cpp/container/priority_queue
本文链接：https://cs.pynote.net/sf/c/cpp/202212081/
-- EOF --
-- MORE --