文章目录
- 前言:
- 一.list的介绍及使用
- 1. list的介绍
- 2. list的使用
- 2.1 list的构造
- 2.2 list iterator的使用
- 2.3 list capacity
- 2.4 list element access
- 2.5 list modifiers
- 2.6 list的迭代器失效
- 二.list的模拟实现
- 1. list的节点
- 2. list的成员变量
- 3.list迭代器相关问题
- 3.1 普通迭代器
- 3.2 const迭代器
- 4. list的成员函数
- 4.1 list的空初始化
- 4.2 push_back
- 4.3 构造函数
- 4.4 insert
- 4.4 erase
- 4.5 push_front
- 4.6 pop_front
- 4.7 pop_back
- 4.8 clear
- 4.8 析构函数
- 4.9 swap
- 4.10 赋值运算符重载
- 最后想说:
前言:
C++中的List容器是标准模板库(STL)中的一种序列容器,它实现了双向链表的功能。与数组(如vector)和单向链表相比,List容器提供了更加灵活的元素插入和删除操作,特别是在容器中间位置进行这些操作时。
一.list的介绍及使用
1. list的介绍
- 双向链表结构: list容器使用双向链表来存储元素,每个元素(节点)都包含数据部分和两个指针,分别指向前一个元素和后一个元素。这种结构使得在链表的任何位置进行插入和删除操作都非常高效,时间复杂度为
O(1)
。 - 动态大小: list容器的大小可以在运行时动态改变,即可以在程序运行过程中添加或移除元素。
- 不支持随机访问: 与
vector
和array
等连续内存的容器不同,list
不支持随机访问迭代器,不能直接通过索引获取元素,而需要通过迭代器遍历。 - 迭代器稳定性: 在list中插入或删除元素不会导致其他迭代器失效(除了指向被删除元素的迭代器)。这是因为它通过调整相邻节点的指针来维护链表结构,而不需要移动元素或重新分配内存。
2. list的使用
list的使用参考文档:list的文档介绍
2.1 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 |
代码演示:
#include<list>
int main()
{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// 以数组为迭代器区间构造l5int array[] = { 16,2,77,29 };list<int> l5(array, array + sizeof(array) / sizeof(int));// 列表格式初始化C++11list<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;return 0;
}
2.2 list iterator的使用
此处,大家可暂时将迭代器理解成一个指针,该指针指向list中的某个节点。
函数声明 | 接口说明 |
---|---|
begin | 返回第一个元素的迭代器 |
end | 返回最后一个元素下一个位置的迭代器 |
rbegin | 返回一个指向容器中最后一个元素的反向迭代器(即容器的反向起始) |
rend | 返回一个反向迭代器,该迭代器指向列表容器中第一个元素之前的理论元素(该元素被认为是其反向结束)。 |
注意:
- begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动
代码演示:
int main()
{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;return 0;
}
2.3 list capacity
函数声明 | 接口说明 |
---|---|
front | 检测list是否为空,是返回true,否则返回false |
size | 返回list中有效节点的个数 |
2.4 list element access
函数声明 | 接口说明 |
---|---|
front | 返回list的第一个节点中值的引用 |
back | 返回list的最后一个节点中值的引用 |
2.5 list modifiers
函数声明 | 接口说明 |
---|---|
push_front | 在list首元素前插入值为val的元素 |
pop_front | 删除list中第一个元素 |
push_back | 在list尾部插入值为val的元素 |
pop_back | 删除list中最后一个元素 |
insert | 在list position 位置中插入值为val的元素 |
erase | 删除list position位置的元素 |
swap | 交换两个list中的元素 |
clear | 清空list中的有效元素 |
代码演示:
#include<iostream>
#include<vector>
using namespace std;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 << " ";}cout << endl;
}// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList1()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4,头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}// insert /erase
void TestList2()
{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 TestList3()
{// 用数组来构造listint 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;
}int main()
{TestList1();TestList2();TestList3();return 0;
}
运行结果:
2.6 list的迭代器失效
前面已经说过了,此处可以将迭代器理解为类似于指针的东西,迭代器失效即迭代器指向的节点失效了,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list进行插入操作时不会导致迭代器失效,只有删除时才会失效,并且失效的是被删除节点的迭代器,其他迭代器不会受到影响。
二.list的模拟实现
1. list的节点
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){}
};
2. list的成员变量
template<class T>
class list
{typedef list_node<T> Node;
public://成员函数
private:Node* _head; //哨兵位的头节点
};
没有用访问限定符限制的成员class
默认是私有的,struct
默认是公有的,如果一个类既有公有也有私有就用class
,全部为公有一般用struct
。这不是规定,只是个惯例。
3.list迭代器相关问题
简单分析:
&emsp; 这里不能像以前一样给一个结点的指针作为迭代器,如果it
是typedef的节点的指针,it
解引用得到的是节点,不是里面的数据,但是我们期望it
解引用是里面的数据,++it
我们期望走到下一个节点去,而list
中++走不到下一个数据,因为数组的空间是连续的,++可以走到下一个数据。但是链表达不到这样的目的。所以原身指针已经无法满足这样的行为,怎么办呢?这时候我们的类就登场了
用类封装一下节点的指针,然后重载运算符,模拟指针。
例如:
reference operator*()const
{return (*node).data;
}
self& opertor++()
{node = (link_type)((*node).next);return *this;
}
3.1 普通迭代器
template<class T>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node):_node(node){}T& operator*() //用引用返回可以读数据也可以修改数据{return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}
};
3.2 const迭代器
const迭代器在定义的时候不能直接定义成typedef const list_iterator<T> const_iterator
,const迭代器的本质是限制迭代器指向的内容不能被修改,而前面的这种写法限制了迭代器本身不能被修改,所以迭代器就不能进行++
操作。那该怎能办呢?答案是我们可以实现一个单独的类:
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){}const T& operator*(){return _node->_data; //返回这个数据的别名,但是是const别名,所以不能被修改}const T* operator->(){return &_node->_data; //我是你的指针,const指针}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}
};
普通法迭代器与const迭代器的区别就是:普通迭代器可读可写,const迭代器只能读
上面是我们自己实现的普通迭代器和const迭代器,用两个类,并且这两个类高度相似,下来就让我们一起看一看库里面是怎么实现的吧!
我们可以看到库里面是写了两个模板,让编译器去生成对应的类。其本质上也是写了两个类,只不过是让编译器去生成对应的类。
迭代器不需要我们自己写析构函数、拷贝构造函数、赋值运算符重载函数,因为这里要的是浅拷贝,例如我把一个迭代器赋值给另外一个迭代器,就是期望两个迭代器指向同一个节点,这里用浅拷贝即可,拷贝给你我们两个迭代器就指向同一个节点。
4. list的成员函数
4.1 list的空初始化
void empty_init() //空初始化
{_head = new Node();_head->_next = _head;_head->_prev = _head;
}
4.2 push_back
//普通版本
void push_back(const T& x)
{Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;
}
//复用insert版本insert(end(),x);
4.3 构造函数
list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr)
{}
4.4 insert
iterator insert(iterator position; const T& val)
{Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;//prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);
}
4.4 erase
iterator erase(iterator pos)
{assert(pos != end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;return iterator(next);
}
4.5 push_front
void push_front(const T& x)
{insert(begin(), x);
}
4.6 pop_front
void pop_front()
{erase(begin());
}
4.7 pop_back
void pop_back()
{erase(--end());
}
4.8 clear
void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}
4.8 析构函数
~list()
{clear();delete _head;_head = nullptr;
}
4.9 swap
void swap(list<T>& tmp)
{std::swap(_head, tmp._head);//交换哨兵位的头节点
}
4.10 赋值运算符重载
//现代写法
//lt2=lt3
//list<T>& operator=(list<T> lt)
list& operator=(list lt) //不加模板参数
{swap(lt);//交换就是交换哨兵位的头节点return *this;
}//lt3传给lt去调用拷贝构造,所以lt就和lt3有一样大的空间一样大的值,lt2很想要,也就是/this想要,lt2之前的数据不想要了,交换给lt,此时lt2就和lt3有一样大的空间一样大的值,
//lt出了作用域就被销毁了
构造函数和赋值运算符重载函数的形参和返回值类型可以只写类名 list
,不需要写模板参数,这种写法在类里面可以不加,只能在类里面可以这样写,类外面是不行的,一般情况下加上好一点。
最后想说:
本章我们STL的List
就介绍到这里,下期我将介绍关于stack
和queue
的有关知识,如果这篇文章对你有帮助,记得点赞,评论+收藏 ,最后别忘了关注作者,作者将带领你探索更多关于C++方面的问题。