C++ list 容器全解析：从构造到模拟实现的深度探索----《Hello C++ Wrold!》(16)--(C/C++)

前言

在 C++ 标准模板库（STL）的众多容器中，list 以其独特的双向链表结构占据着重要地位。与 vector 的连续内存布局不同，list 通过节点间的指针连接实现元素存储，这使得它在插入、删除操作上具备无可替代的优势，但也带来了访问方式和迭代器特性上的差异。

本文将围绕 list 容器展开全方位解析，从最基础的构造方法讲起，深入剖析其迭代器的特性与分类，详细介绍各类常用接口的功能与使用注意事项，更会带你直击 list 的底层实现逻辑 —— 通过模拟实现来理解其节点设计、迭代器重载及核心成员函数的工作原理。无论是初学者想要掌握 list 的基本用法，还是有经验的开发者希望深入理解其底层机制，本文都将为你提供清晰且系统的知识框架，助你彻底搞懂这个 “灵活多变” 的容器。

构造list的几种方法

list的迭代器

begin+end

rbegin+rend

cbegin+cend(就是在原来begin+end基础上不让对迭代器进行修改了)

crbegin+crend(就是在原来rbegin+rend基础上不让对迭代器进行修改了)

注意:list这里迭代器: it = c.begin();//假设c是list<int>类型的while(it!=c.end()) {it++;}这里不能写成it<c.end();!因为不连续

引申:STL中不同容器的迭代器

单向(只能++): forward_list  unordered_set/map
双向(++或--):list map set
随机(++或--或+或-): vector/string/deque

可以从这里看出来，这个迭代器是双向迭代器

list容器的其他接口

list没有[]了，只能用迭代器去访问了

empty size还在,但是没有capacity

front–返回第一个节点中 值的引用

st.front()   假设st是list<int>类型的

back–返回list最后一个节点中 值的引用

push_front 在首元素前插入值为val的元素

pop_front 删除第一个元素

push_back 在尾部插入值为val的元素

pop_back 删除最后一个元素

insert（它的形参迭代器不会失效） erase(他的形参迭代器会失效，但是其返回值是下一个元素的迭代器)

clear

swap–交换两个list中的元素

sort reverse(reverse一般习惯还是用算法库里面的,但是list不能用算法库里面的sort–底层原因)

list的sort接口

只在数据量小并且只排几次的情况下用

在数据量大并且频繁排序的情况下，list的sort还没有把数据转移到vector去排序完再转回来的所用时间短(release下是这样的)

引申:所以处理数据要选择对的容器!

list的模拟实现

list是含头节点的双向循环链表(头节点不存数据哈)

namespace renshen
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}};
//T() 是值初始化表达式，主要用于创建一个类型为 T 的 “默认值” 对象template<class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> Node;//不能直接类名拿过来，要加模板参数<T>
//没有模板参数的话，类名是可以当作类型使用的//下面是迭代器的模拟实现:typedef __list_iterator<T, Ref, Ptr> iterator;
//这里的iterator有时也写成self--自己喜欢写成iteratorNode* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}//迭代器解引用得到的是值Ptr operator->(){return &_node->_val;}iterator& operator++(){_node = _node->_next;return *this;}iterator operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}iterator& operator--(){_node = _node->_prev;return *this;}iterator operator--(int){iterator tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const iterator& it) const{return _node != it._node;}bool operator==(const iterator& it) const{return _node == it._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;
//typedef放在public里面的话，在外面eg:main里面list<int>::iterator it = ....这样也能用typedef __list_iterator<T, const T&, const T*> const_iterator;
//const_iterator是想指向的内容不被修改，但是自己本身能被修改// typedef const __list_iterator<T> const_iterator;// 这样设计是迭代器本身不能修改iterator begin(){return _head->_next;}
//本来应该是return iterator(_head->next);
//但是iterator有单参数的构造函数->所以支持隐式类型转换
//其实也就是只有一个参数的就可以iterator end(){return _head;}//这个end其实是在哨兵位const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}list(){empty_init();}list(const list<T>& lt)//list(const list& lt)--拷贝构造{empty_init();for (auto& e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);//理解这里swap会把什么给交换了std::swap(_size, lt._size);}list<T>& operator=(list<T> lt)//list& operator=(list lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}//只清除数据，没有清除空间void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}// pos位置之前插入iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++_size;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;}size_t size(){/*size_t sz = 0;iterator it = begin();while (it != end()){++sz;++it;}return sz;*/return _size;}//---size的两种实现方法
//一种就是注释了的部分，另一种就是_size搞成成员变量，会变动容量的函数里面都对_size进行改动private:Node* _head;size_t _size;};

注意:

1.拷贝构造和赋值时，类型可以直接写类的名字,不用加模板参数(那些容器的模拟实现也是这样的，比如:vector)–自己不建议用

引申:

1.多用前置++,少用后置++（效率问题–自定义类型有这个问题）

2.指针是->，实例化的对象是.

3.自己重载的运算符的优先级是跟内置的运算符本身是一样的

4.函数里面用new这些开辟的空间，在函数外面也是可以使用的

迭代器不要eg: int* it  = v.begin();这样，因为迭代器不一定是原生指针
(这里举的v是vector<int>类型的)

一个补充知识

struct A
{A(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;
};void test_list1()
{list<A> lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " " << (*it)._a2 << endl;cout << it->_a1 << " " << it->_a2 << endl;++it;}cout << endl;
}

这里的it->_a2严格来说，应该写成it->->a2才是符合语法的
但是运算符重载要求可读性，所以这里规定了编译器会特殊处理，所以可以省略一个->

作业部分

对于list有迭代器it, 当erase(it)后，说法错误的是(C)
A.当前迭代器it失效
B.it前面的迭代器仍然有效
C.it后面的迭代器失效
D.it后面的迭代器仍然有效

下面有关vector和list的区别，描述正确的是(AB)A.vector拥有一段连续的内存空间，因此支持随机存取，如果需要高效的随机读取，应该使用vector
B.list拥有一段不连续的内存空间，如果需要大量的插入和删除，应该使用list

下面有关vector和list的区别，描述正确的是(A)
A.两者在尾部插入的效率一样高
B.两者在头部插入的效率一样高
C.两者都提供了push_back和push_front方法原因:vector由于在头部插入数据效率很低，所以没有提供push_front方法