C++标准模板库--list
list
介绍
list 是序列容器，允许在序列内的任何位置进行常量时间的插入和删除操作，以及两个方向的迭代。列表容器被实现为双向带头链表；双链表可以将它们包含的每个元素存储在不同且不相关的存储位置。排序是通过与前面元素的链接和后面元素的链接的每个元素的关联在内部保持的。它们与 forward_list非常相似：主要区别在于forward_list对象是单链表，因此它们只能向前迭代，以换取更小和更高效。与其他基本标准序列容器（array、vector和deque）相比，list 在容器内的任何位置插入、提取和移动元素（迭代器已经获得）方面通常表现更好，因此在大量使用列表的算法（如排序算法）中也表现更好。与其他序列容器相比，list 和 forward_list的主要缺点是它们无法通过位置直接访问元素；例如，要访问列表中的第六个元素，必须从已知位置（如开始或结束）迭代到该位置，这需要在两者之间的距离上花费线性时间。它们还消耗一些额外的内存来保存与每个元素相关联的链接信息（对于包含小元素的大型列表来说，这可能是一个重要因素）。
根据官方对 list 的介绍，我们可以了解到 list 中使用的是双向带头链表，其优点有高效的元素插入和删除、双向遍历、迭代器失效问题较小、适应性强等。
使用
list的构造
| 函数名称 | 接口说明 |
|---|---|
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
代码演示：
// list的构造
void TestList1()
{
list<int> l1; // 构造空的l1
list<int> l2(4, 100); // l2中放4个值为100的元素
list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
list<int> l4(l3); // 用l3拷贝构造l4
// 以数组为迭代器区间构造l5
int array[] = { 16,2,77,29 };
list<int> l5(array, array + sizeof(array) / sizeof(int));
// 列表格式初始化C++11
list<int> l6{ 1,2,3,4,5 };
// 用迭代器方式打印l5中的元素
list<int>::iterator it = l5.begin();
while (it != l5.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// C++11范围for的方式遍历
for (auto& e : l5)
cout << e << " ";
cout << endl;
}
list迭代器的使用
| 函数名称 | 接口说明 |
|---|---|
| begin+end | 返回第一个元素的迭代器+返回最后一个元素的下一个位置的迭代器 |
| rbegin+rend | 返回最后一个元素的迭代器，即end-1，返回最后一个元素下一个位置的迭代器即begin-1位置 |
注意：
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后(右)移动。
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前(左)移动。
代码演示：
// list迭代器的使用
// 注意：遍历链表只能用迭代器和范围for
void PrintList(const list<int>& l)
{
// 注意这里调用的是list的 begin() const，返回list的const_iterator对象
for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
{
cout << *it << " ";
// *it = 10; 编译不通过
}
cout << endl;
}
void TestList2()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
// 使用正向迭代器正向list中的元素
// list<int>::iterator it = l.begin(); // C++98中语法
auto it = l.begin(); // C++11之后推荐写法
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 使用反向迭代器逆向打印list中的元素
// list<int>::reverse_iterator rit = l.rbegin();
auto rit = l.rbegin();
while (rit != l.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
}list的容量与首尾
| 函数名称 | 接口说明 |
|---|---|
| empty | 检测 list 是否为空，是返回 true，否则返回 false。 |
| size | 返回list中的有效节点的个数。 |
| front | 返回list第一个节点中的值的引用 |
| back | 返回list最后一恶搞节点中的值的引用 |
list的增删查改
| 函数名称 | 接口说明 |
|---|---|
| push_front | 在list首元素前插入值val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| insert | 在list中pos的位置中插入置为val的元素 |
| erase | 删除list中在pos位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
代码演示：
// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList3()
{
int array[] = { 1, 2, 3 };
list<int> L(array, array + sizeof(array) / sizeof(array[0]));
// 在list的尾部插入4，头部插入0
L.push_back(4);
L.push_front(0);
PrintList(L);
// 删除list尾部节点和头部节点
L.pop_back();
L.pop_front();
PrintList(L);
}
// insert /erase
void TestList4()
{
int array1[] = { 1, 2, 3 };
list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));
// 获取链表中第二个节点
auto pos = ++L.begin();
cout << *pos << endl;
// 在pos前插入值为4的元素
L.insert(pos, 4);
PrintList(L);
// 在pos前插入5个值为5的元素
L.insert(pos, 5, 5);
PrintList(L);
// 在pos前插入[v.begin(), v.end)区间中的元素
vector<int> v{ 7, 8, 9 };
L.insert(pos, v.begin(), v.end());
PrintList(L);
// 删除pos位置上的元素
L.erase(pos);
PrintList(L);
// 删除list中[begin, end)区间中的元素，即删除list中的所有元素
L.erase(L.begin(), L.end());
PrintList(L);
}
// resize/swap/clear
void TestList5()
{
// 用数组来构造list
int array1[] = { 1, 2, 3 };
list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
PrintList(l1);
// 交换l1和l2中的元素
list<int> l2;
l1.swap(l2);
PrintList(l1);
PrintList(l2);
// 将l2中的元素清空
l2.clear();
cout << l2.size() << endl;
}list的迭代器失效问题
此处大家可以将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头节点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效。并且失效的只是只想被删除节点的迭代器，其他迭代器不会受到影响。
代码演示：
void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
l.erase(it);
++it;
}
}
// 改正
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); // it = l.erase(it);
}
}list底层的模拟实现
框架：
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
};
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
};
template<class T>
class list
{
//typedef后的Node受访问限定符的影响。
typedef list_node<T> Node;
public:
//迭代器
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
private:
Node* _head;
size_t _size;
};解析：
list_node类：是一个模板结构，存储任意类型T的数据。其中_data是存储节点的数据；_next是指向下一个节点的指针；_prev是指向前一个节点的指针。list_iterator类：是一个模板结构，使用三个类型参数T、Ref（引用类型）、Ptr（指针类型）。其中Node：为list_node<T>的重命名，方便在迭代器中使用；Self：为list_iterator<T, Ref, Ptr>的重命名，使得在迭代器中可以使用自身的类型；_node是指向当前迭代器所指向的节点。list类：是一个模板类，存储类型T的元素。其中Node：为list_node<T>的重命名，便于使用；iterator：定义为list_iterator<T, T&, T*>，表示指向T类型元素的可修改迭代器；const_iterator：定义为list_iterator<T, const T&, const T*>，表示指向T类型元素的只读迭代器。_head：是指向链表头部的节点指针；_size：记录链表中节点的数量。
本质上是以 list 类为主体，先封装了一个 list_node 类用于记录链表节点的值、前驱指针和后继指针；后封装了一个 list_iterator 迭代器，迭代器以三参数模板可以根据需要灵活调整类型，这里分别构造了普通迭代器和 const 迭代器，满足了不同的访问需求；并且只需定义一个模板类 list_iterator，就能创建不同类型的迭代器，减少重复代码。
默认成员函数
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
//默认构造
list_node(const T& x = T())
:_data(x)
,_next(nullptr)
,_prev(nullptr)
{}
};
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)
{}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
//初始化空链表
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
//默认构造
list()
{
empty_init();
}
//initializer_list
list(initializer_list<T>& li)
{
empty_init();
for (auto& e : li)
{
push_back(e);
}
}
//拷贝构造
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
//swap
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//赋值重载
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
//clear
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
//析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
private:
Node* _head;
size_t _size;
};list_node 中的默认构造函数：
- 默认参数：构造函数的参数
x有一个默认值T()，意味着如果没有提供值，节点的数据将被初始化为类型T的默认构造值（例如，对于内置类型，通常是 0）。 - 成员初始化：
_data初始化为x，允许用户在创建节点时传入特定值。_next和_prev初始化为nullptr，表示新节点在链表中尚未连接到其他节点。
list_iterator 中的构造函数：
- 带参构造：该构造函数接受一个指向
list_node的指针，并将其赋值给成员变量_node。这允许用户创建一个指向特定节点的迭代器，便于在链表中遍历。
list 中的默认成员函数：
- 默认构造函数：空链表初始化，调用
empty_init()方法，创建一个空的链表头节点，并将头节点的_next和_prev指针指向自身。_size初始化为 0，表示链表当前没有元素。 initializer_list构造函数：允许使用初始化列表创建链表，通过push_back方法逐个插入元素。- 拷贝构造函数：复制另一个链表的内容，同样调用
empty_init()初始化新链表，然后逐个插入元素。 - 赋值运算符重载：通过传值方式接收参数，利用拷贝构造函数创建一个临时对象
lt，然后交换内部数据，确保赋值操作的安全性和高效性。 - 析构函数：资源管理，调用
clear()清除所有节点，释放它们的内存，最后释放链表头节点的内存，避免内存泄漏。
迭代器类中的运算符重载函数
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->_data;
}
Ptr 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& node) const
{
return _node != node;
}
bool operator==(const Self& node) const
{
return _node == node;
}
};
list类中的常用函数：
//迭代器
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
//insert
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
newnode->_next = cur;
newnode->_prev = prev;
prev->_next = newnode;
cur->_prev = newnode;
++_size;
return newnode;
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
//erase
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
return next;
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
//size
size_t size() const
{
return _size;
}
//empty
bool empty()
{
return _size == 0;
}
private:
Node* _head;
size_t _size;这段代码实现了双向链表的迭代器、插入、删除、大小和空链表检查的功能，确保链表能够灵活操作和高效管理节点。
iterator：可修改元素的迭代器，指向链表中的节点。const_iterator：只读迭代器，确保不修改链表中的元素。begin()：返回指向链表第一个有效元素的迭代器（头节点的下一个节点）。end()：返回指向链表头节点的迭代器，表示链表的结束。insert(pos, x)：在指定位置pos插入新节点x。push_back(x)：在链表末尾插入元素x，通过insert(end(), x)实现。push_front(x)：在链表开头插入元素x，通过insert(begin(), x)实现。erase(pos)：删除指定位置的节点。pop_back()：删除链表末尾的元素，通过erase(--end())实现。pop_front()：删除链表开头的元素，通过erase(begin())实现。size()：返回链表中元素的数量。empty()：检查链表是否为空，返回布尔值。
完整代码展示：
#pragma once
#include<iostream>
#include<list>
#include<assert.h>
#include<algorithm>
using namespace std;
namespace zy
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
//默认构造
list_node(const T& data = T())
:_data(data)
,_next(nullptr)
,_prev(nullptr)
{}
};
//template<class T>
//struct list_const_iterator
//{
// typedef list_node<T> Node;
// typedef list_const_iterator<T> Self;
//
// Node* _node;
// list_const_iterator(Node* node)
// :_node(node)
// {}
// // operator*
// const T& operator*()
// {
// return _node->_data;
// }
// // operator->
// const T* operator->()
// {
// return &_node->_data;
// }
// // operator++
// Self& operator++()
// {
// _node = _node->_next;
// return *this;
// }
// Self operator++(int)
// {
// Self tmp(*this);
// _node = _node->_next;
// return tmp;
// }
// // operator--
// Self& operator--()
// {
// _node = _node->_prev;
// return *this;
// }
// Self operator--(int)
// {
// Self tmp(*this);
// _node = _node->_prev;
// return tmp;
// }
// // operator!=
// bool operator!=(const Self& s)
// {
// return _node != s._node;
// }
//};
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)
{}
// operator*
Ref operator*()
{
return _node->_data;
}
// operator->
Ptr operator->()
{
return &_node->_data;
}
// operator++
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
// operator--
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
// operator!=
bool operator!=(const Self& s) const
{
return _node != s._node;
}
// operator==
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
template<class T>
class list
{
//typedef 也受访问限定符的限制
typedef list_node<T> Node;
public:
void empty_init()
{
//设置哨兵位
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
list()
{
empty_init();
}
list(initializer_list<T>& li)
{
empty_init();
for (auto& e : li)
{
push_back(e);
}
}
//拷贝构造
list(const list<T>& lt)
{
empty_init();
auto it = lt.begin();
while (it != lt.end())
{
push_back(it);
++it;
}
}
//swap
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//赋值重载
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
//clear
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
//析构
~list()
{
clear();
delete _head;
_head = nullptr;
}
//iterator
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
//使用迭代器类创建一个头结点的迭代器
/*iterator it(_head->_next);
return it;*/
//返回匿名对象
//return iterator(_head->_next);
//隐式类型转换，返回的节点由iterator类型接收
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
// push_back
void push_back(const T& x)
{
//new新节点
//Node* newnode = new Node(x);
//Node* tail = _head->_prev;
//插入新节点
//newnode->_prev = tail;
//newnode->_next = _head;
//tail->_next = newnode;
//_head->_prev = newnode;
//++_size;
//直接复用insert
insert(end(), x);
}
//push_front
void push_front(const T& x)
{
//直接复用insert
insert(begin(), x);
}
// insert
iterator insert(iterator pos, const T& x)
{
// 找到插入位置
Node* cur = pos._node;
Node* prev = cur->_prev;
//new出新节点
Node* newnode = new Node(x);
//进行连接
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;
//++size
++_size;
return newnode;
}
//pop_front
void pop_front()
{
erase(begin());
}
//pop_back
void pop_back()
{
erase(--end());
}
//erase
iterator erase(iterator pos)
{
//不能释放哨兵位
assert(pos != end());
Node* node = pos._node;
Node* prev = node->_prev;
Node* next = node->_next;
prev->_next = next;
next->_prev = prev;
delete node;
--_size;
//隐式类型转换为iterator
return next;
}
// size
size_t size() const
{
return _size;
}
//empty
bool empty()
{
return _size == 0;
}
private:
Node* _head;
size_t _size = 0;
};
// 打印函数
template<class Container>
void print_container(const Container& con)
{
//auto it = con.begin();
typename Container::const_iterator it = con.begin();
while (it != con.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void list_test1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
print_container(lt);
}
}
list 与 vector 的对比
| vector | list | |
|---|---|---|
| 底层结构 | 动态顺序表，一段连续的空间 | 带头节点的双向循环链表 |
| 随机访问 | 支持，访问单个的效率为O(1) | 不支持，访问单个元素的效率为O(1) |
| 插入和删除 | 在任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间拷贝元素，释放旧空间，导致效率更低。 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)。 |
| 迭代器 | 原生态指针 | 独立封装的节点指针 |
| 迭代器失效 | 插入删除都可能会导致迭代器失效。 | 只有删除会导致迭代器失效，但是不会影响后面的位置的迭代器。 |
| 空间利用率 | 空间利用率高，缓存利用率高 | 空间利用率低，缓存利用率低 |
| 使用场景 | 需要高效储存，支持随机访问，不关心插入和删除效率 | 大量插入删除，不关心随机访问 |