当前位置：首页 > news >正文

C++：STL中list的使用和模拟实现

news 2025/7/31 8:07:14

C++中的list是标准模板库（STL）提供的双向链表容器，支持高效的元素插入和删除操作。在上一篇中讲解了vector的使用和模拟实现，vector是具有连续的空间，迭代器是可以随机的，而list却于vector不同，list是带头双向循环链表，迭代器是双向的，空间并不是连续的，所以在底层实现上比vector复杂一点。与vector 不同，list 在任意位置插入或删除元素的时间复杂度为 O(1)，但随机访问的性能较差（时间复杂度为 O(n)）。

list的介绍

list的使用

list的构造

list的插入和删除

list访问元素

list的大小和容量

list迭代器的使用

list的模拟实现

迭代器中的函数

list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

list的使用

list是带头双向循环链表，如果迭代器要进行++、--、*（解引用）等操作是否跟vector一样呢，当然不是，两者的结构不同注定迭代器也不一样，但是为了方便大家使用将list的迭代器进行了封装，依然是lis<T>iterator来进行各种操作，list的空间不是连续的，所以在实现++、--、*等操作就需要进行运算符重载来定义该运算符的行为，在使用上迭代器vector和list没什么两样，但是在底层却大大不同。

list的构造

list (size_type n, const value_type& val = value_type()) //构造的list中包含n个值为val的元素list() //构造空的listlist (InputIterator ﬁrst, InputIterator last) //用[ﬁrst, last)区间中的元素构造list

使用list需要包含头文件。初始化的方式包括默认构造、指定大小初始化、通过迭代器范围初始化等。

示例：

#include <list>
#include <iostream>
using namespace std;int main() {list<int> l1; // 空列表list<int> l2(5, 10); // 包含5个值为10的元素list<int> l3 = {1, 2, 3, 4, 5}; // 列表初始化return 0;
}

list的插入和删除

push_back(val)：在末尾插入元素。

push_front(val)：在头部插入元素。

pop_back(val)：删除末尾元素。

pop_front(val)：删除头部元素。

insert(pos,val)：在指定位置插入元素。

erase(pos)：在指定位置删除元素。

示例：

std::list<int> l = {1, 2, 3};
l.push_back(4); // {1, 2, 3, 4}
l.push_front(0); // {0, 1, 2, 3, 4}
l.pop_back(); // {0, 1, 2, 3}
l.pop_front(); // {1, 2, 3}
auto it = l.begin();
it++;
l.insert(it, 10); // {1, 10, 2, 3}
l.erase(it); // {1, 10, 3}

list访问元素

front()：返回第一个元素。

back()：返回最后一个元素。

由于list的结构不支持operator【】或者at()随机访问。

示例：

std::list<int> l = {1, 2, 3};
std::cout << l.front() << std::endl; // 输出1
std::cout << l.back() << std::endl; // 输出3

list的大小和容量

在vector中扩容是很常见的，扩容之后需要拷贝，而在list中就不存在这样的问题，当插入一个值就new一个节点再链接起来，不需要拷贝，按需申请。

size()：返回元素数量。

empty()：判断是否为空。

示例：

std::list<int> l = {1, 2, 3};
std::cout << l.size() << std::endl; // 输出3
std::cout << l.empty() << std::endl; // 输出0（false）

list 提供了一些特有操作：

sort()：排序（默认升序，可自定义比较函数）。
merge(other_list)：合并两个有序列表。
splice(pos, other_list)：将另一个列表的元素移动到指定位置。
unique()：删除连续重复元素。

示例：

std::list<int> l1 = {3, 1, 2};
std::list<int> l2 = {5, 4, 6};
l1.sort(); // {1, 2, 3}
l2.sort(); // {4, 5, 6}
l1.merge(l2); // l1: {1, 2, 3, 4, 5, 6}, l2为空
l1.unique(); // 删除重复元素

list迭代器的使用

list提供双向迭代器，有begin()、end()、rbegin()、和rend()。

std::list<int> l = {1, 2, 3};
for (auto it = l.begin(); it != l.end(); it++) {std::cout << *it << " ";
}
// 输出：1 2 3

想知道更多list的更多接口可以看这里：https://legacy.cplusplus.com/reference/list/list/?kw=list

list的模拟实现

在实现list之前我们需要知道list的结构是带头双向循环链表，迭代器也是和vector不一样，需要去实现封装迭代器，list迭代器需要和vector的迭代器有一样的功能，所以需要定义一个结构体迭代器在该结构体中去实现迭代器的各种行为。而迭代器还有const修饰的迭代器，所以模版参数可不止一个，需要注意的是const修饰的迭代器本身是可以进行++等操作的，而迭代器指向的内容是只读不可写的。只要对迭代器的实现完善好接下来的工作就十分好做，模拟实现list的重难点就在于如何去实现迭代器。

代码展示：

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){}};template<class T, class Ref, class ptr>//迭代器struct _list_iterator {typedef list_node<T> Node;//节点类型typedef _list_iterator<T, Ref, ptr> Self;Node* _node; \\指向当前链表节点的指针\\构造函数：初始化迭代器指向特定节点_list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}ptr operator->(){return &_node->_val;}Self& operator++()//前置{_node = _node->_next;return *this;}Self& operator++(int)//后置{_list_iterator<T> 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& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};

模版参数：

T:链表元素的类型（如：int、string），与节点定义中的T一致。

Ref：引用类型，用于operator*的返回类型。通常为T&（非const迭代器）或者const T& （const迭代器）

ptr：指针类型，用于operator->的返回类型。通常为T*（非const）或者const T*（const）

对于内部typedef：

typedef list_node<T> Node; 定义节点类型。

typedef _list_iterator<T, Ref, ptr> Self; 定义自身类型，方便使用。

迭代器中的函数

Ref operator*():解引用运算符，返回当前节点值的引用。

作用：允许*it的语法访问元素值。例如it是迭代器，*it就可以获取节点储存的值。

ptr operator->()：成员访问运算符，返回指向节点值的指针。

作用：支持it->member语法。例如，如果T是结构体类型，it->member访问其成员。

Self& operator++()（前置递增）：移动到下一个节点，并返回更新后的迭代器引用。

作用：用于++it语法。效率高，因为直接修改并返回自身。

Self operator++(int)（后置递增）：返回当前迭代器的副本，然后移动到下一个节点。

作用：用于it++语法。参数int是占位符，用于区分前置和后置版本。注意返回类型是Self（值类型），不是引用，因为返回的是临时副本。

Self& operator--()（前置递减）：移动到前一个节点，并返回更新后的迭代器引用。

作用：用于--it语法。正确利用了双向链表的_prev指针

Self operator--(int)（后置递减）：返回当前迭代器的副本，然后移动到前一个节点。

作用：用于it--语法。

bool operator!=(const Self& it)：检查两个迭代器是否指向不同节点。

作用：用于it1 != it2语法。例如，在循环中判断是否到达结尾。

此迭代器实现是STL风格双向链表的核心部分：它封装了节点指针，提供统一的元素访问和遍历接口。通过模板参数，优雅地支持const和非const迭代器。运算符重载使迭代器用法类似原生指针（如*it、it->、++it）。

list代码：

template<class T>//双向循环链表class list {typedef list_node<T> Node;public:typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T,const T&,const T*> const_iterator;//const T* ptr //const 修饰的是指针指向的内容，不能修改//T* const ptr // const 修饰的是指针，指针不能修改list(){head = new Node;head->_next = head;head->_prev = head;n = 0;}list(const list<T>& lt){head = new Node;head->_next = head;head->_prev = head;n = 0;for (auto& e : lt){push_back(e);}}~list(){clear();}iterator begin(){return head->_next;}iterator end(){return head;}const_iterator begin() const{return const_iterator(head->_next);}const_iterator end() const{return const_iterator(head);}void push_back(const T& x){Node* tail = head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;head->_prev = newnode;newnode->_next = head;n++;//insert(--end(),x);}void pop_back(){erase(--end());}void push_front(const T* x){insert(begin(), x);}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* cur = pos._node->_prev;newnode->_next = cur->_next;newnode->_prev = cur;cur->_next->_prev = newnode;cur->_next = newnode;n++;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node->_next;Node* prev = pos._node->_prev;cur->_prev = prev;prev->_next = cur;/*pos._node->_next = pos._node->_prev = nullptr;*/delete pos._node;n--;return cur;}void swap(list<T>& lt){std::swap(head, lt.head);std::swap(n, lt.n);}list<T>& operator=(list<T> lt){swap(lt);return *this;}void clear(){/*Node* cur = head->_next;while (cur != head){Node* next = cur->_next;delete cur;cur = next;}head->_next = head;head->_prev = head;n = 0;*/iterator it = begin();while (it != end()){it = erase(it);}}size_t size(){return n;}private:Node* head;size_t n;};

查看全文

http://www.lryc.cn/news/604702.html