企业官网建设流程全解析

一、list的底层结构：双向循环链表

在C++标准库中，std::list是一个双向链表容器，它采用双向循环链表作为底层数据结构。这种设计使得list在任意位置插入和删除元素的时间复杂度都是O(1)，但随机访问的效率较低。

1.1 节点结构定义

list的底层是一个双向循环链表，每个节点通常包含三个部分：

数据域（data)：存储元素值

前驱指针(prev)：指向前一个节点

后继指针(next)：指向后一个节点

在STL实现中，节点结构通常定义如下：

template<typename T> struct list_node { list_node* prev; // 前驱指针 list_node* next; // 后继指针 T data; // 数据域 };

1.2 循环链表设计

list采用循环链表设计，即头节点的prev指向尾节点，尾节点的next指向头节点。这种设计简化了边界条件的处理：

空链表时，头节点指向自身

插入第一个元素时，头尾节点都指向该元素

删除最后一个元素时，恢复为空链表状态

以下是链表节点的实现

namespace lx { template<class T> struct list_node { T _data; list_node<T>*_prev; list_node<T>*_next; list_node(const T&x=T()) :_data(x) ,_prev(nullptr) ,_next(nullptr) {} }; }

二、list的核心接口实现

2.1 构造函数

list提供了多种构造函数，包括默认构造、拷贝构造、范围构造等：

list() //默认构造 { _head= new node; _head->_prev=_head; _head->_next=_head; } list(const list<T>&lt) //拷贝构造 { _head= new node; _head->_prev=_head; _head->_next=_head; for(auto e: lt) { push_back(e); } }

2.2 insert&&push_back

list的插入操作是其核心优势，时间复杂度为O(1)：

// 在指定位置前插入元素 iterator insert(iterator pos, const T & x) { Node *cur=pos.node; Node *prev=cur->_prev; newnode= new Node(x); prev->_next= newnode; //prev newnode pos newnode->_next=cur; cur->_prev=newnode; newnode->_prev=prev; } // push_back实现 void push_back(const T& x) { insert(end(),x); } // push_front实现 void push_front(const T& x) { insert(begin(),x); }

2.3 erase&&pop_back

删除操作同样高效，时间复杂度为O(1)：

// 删除指定位置的元素 iterator erase(iterator pos) { Node<T>* cur=pos.node; Node<T>* prev=cur->_prev; //prev pos next Node<T>* next=cur->_next; prev->_next=next; next->_prev=prev; delete cur; return iterator(next); } // pop_back实现 void pop_back() { if (!empty()) { erase(--end()); } } // pop_front实现 void pop_front() { if (!empty()) { erase(begin()); } }

2.4 clear

clear函数用于清空list中的有效元素

void clear() { iterator it =begin(); while(it!=end()) { it=erase(it); } }

三、迭代器设计

3.1 普通迭代器

list的迭代器是双向迭代器，支持前向和后向移动：

template<class T,class Ref> struct list_iterator { using Self =list_iterator<T,Ref>; using Node=list_node<T>; Node*_node; list_iterator(Node*node) :_node(node) {} Ref operator*() { return _node->_data; } Self&operator++() { _node=_node->_next; return *this; } Self&operator++(int) { Self tmp(*this); _node=_node->_next; return tmp; } Self&operator--() { _node=_node->_prev; return *this; } Self&operator--(int) { Self tmp(*this); _node=_node->_prev; return tmp; } bool operator!=(const Self&s)const { return _node!=s._node; } bool operator==(const Self&s)const { return _node==s._node; } };

3.2 const迭代器

const迭代器是容器内部定义的只读迭代器，本质是一个“指向常量的指针”可以移动它但不能通过它修改所指向的元素。

template<class T,class Ref> struct __list_iterator { typedef list_node<T> Node; Node*_node; typedef __list_iterator<T,Ref> self; __list_iterator(Node*_node); : _node(node) {} const self& operator*() { return _node->_data; } self& operator++() { _node=_node->_next; return *this; } self&operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } self&operator--() { _node=_node->_prev; return *this; } Self& operator--(int) { Self tmp(*this);//浅拷贝 _node = _node->prev; return *this; } bool operator!=(const Self& it)const { return _node != it._node; } bool operator==(const Self& it)const { return _node == it._node; } };

3.3 迭代器失效问题

list的迭代器在以下情况下不会失效：

插入元素：所有迭代器保持有效

删除元素：只有指向被删除元素的迭代器失效，其他迭代器保持有效

这是list相对于vector和deque的一个重要优势。

四、list的优缺点总结

6.1 优点

高效的插入删除：任意位置O(1)时间复杂度

迭代器稳定性：插入删除不会使其他迭代器失效

动态大小：不需要预分配内存

支持双向遍历：可以从前往后或从后往前遍历

6.2 缺点

随机访问慢：需要遍历，时间复杂度O(n)

内存开销大：每个元素需要额外存储两个指针

缓存不友好：节点分散在内存中，缓存命中率低

空间局部性差：连续访问性能不如vector

6.3 适用场景

1.需要频繁在中间位置插入删除元素的场景

2.元素大小较大，移动成本高的场景

3.需要稳定迭代器的场景

4.不需要随机访问的场景

五、与vector和deque的对比