list

​ list，是用环状双向链表实现的。具体的的内存结构如下图：

​ 其中需要解释的地方：1.end()指向的是一空白节点，用以实现STL前闭后开区间。2.前闭后开区间：在STL迭代器中，区间里要访问的元素一般采用[iterator1,iterator2)的表示方法。

​ 一个list类中的数据成员是怎么样的呢？如下（g++,7.2.0)

list_node *next;
list_node *prev;
alignas(size_t) unsigned char _M_storage[sizeof(size_t)];//最终大小是一个size_t的大小，这个是用来，存储链表的大小。

​ 在g++,7.2.0,win64下，sizeof(list) = 24。

list的构造、析构与赋值

构造函数

与vector，deque类似：

赋值

使用等号赋值

使用assgin()赋值

元素访问

at,operator[]

此为非连续空间容器，C++并没有实现这种访问方式。

front,back

迭代器

​ list的迭代器tag为：a bidirectional iterator to value_type。它表示list是一个双向迭代器，另外，deque与vector的迭代器为，random access iterator随机访问迭代器，它同样为双向迭代器。但是随机访问迭代器。这样区别的目的，是因为他们能实现的一些具体操作不一样。如下：

list<int> a{1,2,3};
vector<int> b{1,2,3};
auto it1 = a.begin() + 2;//错误，list<int>(bidirectional iterator)迭代器不支持这种操作
auto it2 = b.begin() + 2;//正确，vector<int>(random access iterator)迭代器支持这种操作

​ 所有支持的操作可以在相关页面进行查询。简而言之，随机访问迭代器就像是指针一样，重载了所有指针支持的运算符，而双向迭代器，并不支持有关的跨对象访问，只能沿着前后方向一个个访问。如下能获取到list正向或反向的迭代器。

容量及其修改

容量

修改

操作

​ 与vector,deque不大一样，list有它一些独有的操作。

​ 注意：merge中的Compare comp,remove_if中的Predicate pred以及sort中的Compare comp，这些指一个函数指针或函数对象（或者叫仿函数----STL源码解析中的称呼，可以理解为一个重载了operator() 的类的对象。）

eg：

class Functor
{
public:
    int operator()(int a, int b)
    {
        return a < b;
    }
};