C++STL之list
·
目录
C++ STL list 详解
1. list 概述
list 是 C++ STL 中的双向链表容器，底层实现为带头双向循环链表。支持快速插入和删除（O(1)时间复杂度），不支持随机访问（不能使用下标操作），插入和删除操作不会使迭代器失效（除了被删除元素的迭代器）
与 vector 和 deque 相比，list 在任意位置的插入删除性能更优，但随机访问性能较差。
2. 常用接口说明（含函数原型）
2.1 构造函数
// 默认构造函数 list<T> lst; // 创建空list // 填充构造函数 list<T> lst(size_type n, const T& value = T()); // n个元素，值为value // 范围构造函数 list<T> lst(InputIterator first, InputIterator last); // 拷贝构造函数 list<T> lst(const list& other); // 初始化列表构造函数 list<T> lst(initializer_list<T> init);
示例：
list<int> lst1; // 空list list<int> lst2(5, 10); // {10, 10, 10, 10, 10} list<int> lst3(lst2.begin(), lst2.end()); // 拷贝lst2 list<int> lst4{1, 2, 3, 4, 5}; // 初始化列表
2.2 元素访问
// 访问第一个元素 reference front(); const_reference front() const; // 访问最后一个元素 reference back(); const_reference back() const;
示例：
list<int> lst = {1, 2, 3, 4, 5}; cout << lst.front(); // 输出: 1 cout << lst.back(); // 输出: 5 lst.front() = 10; // 修改第一个元素 lst.back() = 50; // 修改最后一个元素
2.3 容量操作
// 判断是否为空 bool empty() const; // 返回元素个数 size_type size() const; // 返回可容纳的最大元素数 size_type max_size() const;
2.4 修改操作
插入操作
// 在头部插入 void push_front(const T& value); // 在尾部插入 void push_back(const T& value); // 在指定位置插入 iterator insert(iterator pos, const T& value); void insert(iterator pos, size_type n, const T& value); void insert(iterator pos, InputIterator first, InputIterator last);
示例：
list<int> lst = {1, 2, 3}; lst.push_front(0); // 头部插入: {0, 1, 2, 3} lst.push_back(4); // 尾部插入: {0, 1, 2, 3, 4} auto it = lst.begin(); advance(it, 2); // 迭代器前进2位 lst.insert(it, 99); // 在位置2插入: {0, 1, 99, 2, 3, 4}
删除操作
// 删除头部元素 void pop_front(); // 删除尾部元素 void pop_back(); // 删除指定位置元素 iterator erase(iterator pos); iterator erase(iterator first, iterator last); // 删除所有元素 void clear(); // 删除特定值 void remove(const T& value); // 删除满足条件的元素 template<class Predicate> void remove_if(Predicate pred);
示例：
list<int> lst = {1, 2, 3, 4, 5}; lst.pop_front(); // 删除头部: {2, 3, 4, 5} lst.pop_back(); // 删除尾部: {2, 3, 4} auto it = lst.begin(); advance(it, 1); lst.erase(it); // 删除位置1: {2, 4} lst.remove(2); // 删除所有2: {4}
2.5 迭代器操作
// 获取指向第一个元素的迭代器 iterator begin(); const_iterator begin() const; // 获取指向末尾的迭代器（最后一个元素的下一个位置） iterator end(); const_iterator end() const; // 反向迭代器 reverse_iterator rbegin(); const_reverse_iterator rbegin() const; reverse_iterator rend(); const_reverse_iterator rend() const;
2.6 特殊操作（list特有）
拼接操作
// 将另一个list拼接到指定位置 void splice(iterator pos, list& other); void splice(iterator pos, list& other, iterator it); void splice(iterator pos, list& other, iterator first, iterator last);
示例：
list<int> lst1 = {1, 2, 3}; list<int> lst2 = {4, 5, 6}; auto it = lst1.begin(); advance(it, 1); lst1.splice(it, lst2); // lst1: {1, 4, 5, 6, 2, 3}
排序和去重
// 排序 void sort(); template<class Compare> void sort(Compare comp); // 去重（需要先排序） void unique(); template<class BinaryPredicate> void unique(BinaryPredicate pred); // 合并两个有序list void merge(list& other); template<class Compare> void merge(list& other, Compare comp);
示例：
list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6}; lst.sort(); // 排序: {1, 1, 2, 3, 4, 5, 6, 9} lst.unique(); // 去重: {1, 2, 3, 4, 5, 6, 9} list<int> lst2 = {0, 7, 8}; lst.merge(lst2); // 合并: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
反转
void reverse(); // 反转链表
3. 性能特点
C++ STL 中的 list 在频繁插入和删除的场景下表现出色，这得益于其底层实现的带头双向循环链表结构。由于链表节点在内存中非连续存储，插入和删除操作只需调整相邻节点的指针，无需移动其他元素，因此时间复杂度为 O(1)。不过，这种结构也导致 list 不支持随机访问，查找元素必须从头或从尾遍历，效率为 O(n)。此外，每个元素除了存储数据外还需维护两个指针，存在一定的内存开销，但其迭代器稳定性高，插入和删除不会影响其他元素的迭代器，非常适合动态操作频繁的应用场景。
4. 适用场景
list 特别适用于那些需要频繁在序列中间或两端进行插入和删除操作的场景，例如实现任务调度队列、维护有序数据集合但需动态调整顺序、或构建需要频繁重排的元素列表。在文本编辑器中管理每一行内容、游戏开发中维护动态对象列表，或是高频交易系统中处理不断变化的订单队列时，list 都能够提供高效的性能支持。相反，如果应用场景中需要频繁按位置随机访问元素，或对内存连续性有较高要求，则应优先考虑 vector 或 deque 等其他容器。
list vs vector
| 特性 | list | vector |
|---|---|---|
| 内存布局 | 非连续 | 连续 |
| 随机访问 | O(n) | O(1) |
| 头部插入删除 | O(1) | O(n) |
| 尾部插入删除 | O(1) | O(1)（平摊） |
| 中间插入删除 | O(1) | O(n) |
| 迭代器失效 | 只有删除的元素失效 | 插入删除可能使所有迭代器失效 |
| 内存开销 | 每个元素两个指针 | 容量可能大于元素数 |
list vs deque
| 特性 | list | deque |
|---|---|---|
| 内存布局 | 完全非连续 | 分段连续 |
| 随机访问 | O(n) | O(1) |
| 头部插入删除 | O(1) | O(1) |
| 尾部插入删除 | O(1) | O(1) |
| 中间插入删除 | O(1) | O(n) |
| 迭代器稳定性 | 较高 | 较低 |
5.模拟实现
节点和链表
选择使用带头双向循环链表，因此我们的节点需要的属性有next， prev，val，而链表则需一个指向哨兵位（不存放实际数据，只为了方便边缘数据的插入删除）的指针即可，也可以加上元素个数size，这个在判空和返回大小的时候比较方便，计算链表大小无需遍历。
template <class T>
struct ListNode
{
T _val = 0;
ListNode *_next = nullptr;
ListNode *_prev = nullptr;
ListNode(const T &val = T()) : _val(val)
{}
};
template <class T>
class ListIterator
{
Node *_head;
size_t size;
};
迭代器设计
在模拟实现的时候，迭代器需要被封装成一个类，从而进行一些运算符重载（++， --， *）来符合stl的规定，因此我们需要定义一个ListIterator的类，其内部的成员属性只需节点的指针即可。
这样就存在2种实现方式：
- 封装成内部类
- 在类外实现，类内使用，重命名使用（typedef）
两个版本：const和非const
但是迭代器有const和非const的版本，我们首先要搞清楚这两个迭代器的区别
std::list<int> ls1 = {1,2,3}; const std::list<int> ls2 = {2,3,4}; list<int>::iterator it1 = ls1.begin(); const list<int>::iterator it2 = ls2.begin();
上示两个迭代器，it1是普通迭代器，可以进行元素的访问，修改，而it2是const迭代器，只可以进行读取数据，不能修改数据，但是本身可以修改，容易与const iterator造成混淆,迭代器模拟的是指针的行为，因此可以有以下类比
iterator it1; // 相当于int* it1， 可以进行元素访问，修改 const_iterator it1; // 相当于 const int* it1, 所指向的内容不可以修改，但是指针本身可以修改（指针++，或者--），迭代器同理 const iterator it1; // 相当于 int* const it1, 是一个常量指针，指针自身不可修改，但是其指向的内容可以修改，迭代器同理
我们要实现的是第二种const_iterator, 因此需要2个类分别实现两个版本
class ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T> self;
public:
Node *_node;
ListIterator(Node *node = nullptr) : _node(node)
{
}
T& operator*()
{
return _node->_val;
}
T* operator->()
{
return &(_node->_val);
}
// ……
};
class ConstListIterator
{
typedef ListNode<T> Node;
typedef ConstListIterator<T> self;
public:
Node *_node;
ListIterator(Node *node = nullptr) : _node(node)
{
}
const T& operator*()
{
return _node->_val;
}
const T* operator->()
{
return &(_node->_val);
}
// ……
};
我们会发现，除了一些返回值的类型不同之外，其他部分完全相同，因此我们可以再次借助模板，让编译器替我们生成如上所示的两个类, 类型的传递在list类中传入，具体请看后文
template <class T, class Ref, class Ptr>
class ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> self;
public:
Node *_node;
ListIterator(Node *node = nullptr) : _node(node)
{
}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &(_node->_val);
}
//……
};
成员访问操作符：
如果我们链表中所存放的是个内置类型，那么我们可能会希望迭代器具有以下功能：
struct A
{
int a;
int b;
A(int x = 0, int y = 0):a(x), b(y)
{}
};
int main()
{
list<A> lt;
lt.push_back({1, 1});
lt.push_back({2, 2});
lt.push_back({3, 3});
list<A>::iterator it = lt.begin();
while(it != lt.end())
{
cout<< (*it).a <<" " << (*it).b <<endl; //迭代器正常使用，但是看起来不美观，下一行的方式更加直观
cout<< it->a <<" " << it->b <<endl; //我们在使用自定义元素链表的时候
}
}
我们可以返回元素存储的地址实现成员访问操作符的功能
class ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T> self;
Node *_node;
public:
T* operator->()
{
return &(_node->_val); //返回存储val的地址，我们就可以使用成员发访问操作符->
}
}
但是我们显示调用就会发现一个问题
list<A>::iterator it = lt.begin();
it.operator->()->a; //it.operator->()显示调用，会返回val的地址，正常的省略调用应该是 it->得到地址，
it.operator->()->b; //然后解引用it->->,会出现两个操作符！
it->a = 1;
it->b = 2;
这样的调用是可以正常使用的
it->->a = 1;
it->->b = 2;
这样则会报错，因为编译器为我们做了优化，省略了一个操作符，更符合我们的使用习惯，也增加了代码的可读性
代码封装
解决完上述问题，封装代码基本没有了障碍，我们就可以封装一个具有基本功能的list，代码如下：
#pragma once
#include <iostream>
#include <cassert>
namespace mylist
{
template <class T>
struct ListNode
{
T _val = 0;
ListNode *_next = nullptr;
ListNode *_prev = nullptr;
ListNode(const T &val = T()) : _val(val)
{
}
};
template <class T, class Ref, class Ptr>
class ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> self;
public:
Node *_node;
ListIterator(Node *node = nullptr) : _node(node)
{
}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &(_node->_val);
}
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 &it)
{
return it._node == _node;
}
bool operator!=(const self &it)
{
return it._node != _node;
}
};
template <class T>
class list
{
typedef ListNode<T> Node;
Node *_head = nullptr;
size_t _size = 0;
public:
friend class ListIterator<T, T&, T*>;
typedef ListIterator<T, T&, T*> iterator; //这里进行一个重命名，在类内使用的时候就会自动传出相应类型
typedef ListIterator<T, const T&, const T*> const_iterator;
list()
{
Init();
}
list(size_t n, const T &val = T())
{
Init();
while (n--)
{
push_back(val);
}
}
list(iterator first, iterator last)
{
Init();
while (first != last)
{
push_back(*first);
first++;
}
}
list(const list<T> <)
{
Init();
iterator it = lt.begin();
while (it != lt.end())
{
push_back(*it);
it++;
}
}
void Init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
iterator begin() const
{
return _head->_next;
}
iterator end() const
{
return _head;
}
const_iterator cbegin() const
{
return _head->_next;
}
const_iterator cend() const
{
return _head;
}
void push_back(const T &val)
{
// Node *newnode = new Node(val);
// if (newnode != nullptr)
// {
// _head->_prev->_next = newnode;
// newnode->_prev = _head->_prev;
// _head->_prev = newnode;
// newnode->_next = _head;
// }
insert(end(), val);
}
void push_front(const T &val)
{
insert(begin(), val);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T &val)
{
Node *newnode = new Node(val);
Node *next = pos._node;
Node *prev = next->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = next;
next->_prev = newnode;
_size++;
return newnode;
}
iterator erase(iterator pos)
{
assert(!empty());
Node *next = pos._node->_next;
Node *prev = pos._node->_prev;
prev->_next = next;
next->_prev = prev;
delete pos._node;
_size--;
return next;
}
bool empty()
{
return _size == 0;
}
size_t size()
{
return _size;
}
void print()
{
for (auto &e : *this)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
};
}
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
21
0- 0
已为社区贡献15条内容
所有评论(0)