文章目录
- 一、list的概念
- 二、list的使用
- 三、list的练习
- 四、与vector的对比
- 五、总结
一、list的概念
list 是一种容器,实现了双向链表结构
它具有以下特点:
- 动态大小,可按需增减元素数量。
- 高效的插入和删除操作,在任意位置插入和删除元素时间复杂度为 O (1)。但随机访问元素较慢,时间复杂度为 O (n)。
- 提供双向迭代器,方便遍历、访问和修改元素。
- 不支持随机访问,访问特定位置的元素需要通过迭代器逐步遍历,时间复杂度为线性。
总之,list适用于需要频繁进行插入和删除操作,而对随机访问要求不高的场景。 - 常见操作包括元素访问(如 front ()、back ())、插入(如 push_front ()、push_back ()、insert ())、删除(如 pop_front ()、pop_back ()、erase ())以及获取大小(size ())和判断是否为空(empty ())等。
二、list的使用
list的构造
// list的构造
void TestList1()
{list<int> l1; // 构造空的l1list<int> l2(4, 100); // l2中放4个值为100的元素list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end())左闭右开的区间构造l3list<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;
}
list iterator的使用
- begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
- 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 capacity
list element access
list modifiers
// 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,头部插入0L.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()
{// 用数组来构造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;
}
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的练习
模拟实现list的迭代器
List 的迭代器
迭代器有两种实现方式,具体应根据容器底层数据结构实现:
- 原生态指针,比如:vector
- 将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下方法:
指针可以解引用,迭代器的类中必须重载operator()- 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()
- 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)
至于operator–()/operator–(int)释放需要重载,根据具体的结构来抉择,双向链表可以向前 移动,所以需要重载,如果是forward_list就不需要重载 - 迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()
template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;// Ref 和 Ptr 类型需要重定义下,实现反向迭代器时需要用到public:typedef Ref Ref;typedef Ptr Ptr;public://// 构造ListIterator(Node* node = nullptr): _node(node){}//// 具有指针类似行为Ref operator*() { return _node->_val;}Ptr operator->() { return &(operator*()); }//// 迭代器支持移动Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self temp(*this);_node = _node->_next;return temp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self temp(*this);_node = _node->_prev;return temp;}//// 迭代器支持比较bool operator!=(const Self& l)const{ return _node != l._node;}bool operator==(const Self& l)const{ return _node != l._node;}Node* _node;};
注意:
- 此处typename的作用是明确告诉编译器,Ref是Iterator类中的一个类型,而不是静态成员变量
- 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
- 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
template<class Iterator>class ReverseListIterator{// 注意:此处typename的作用是明确告诉编译器,Ref是Iterator类中的一个类型,而不是静态成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的public:typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIterator<Iterator> Self;public://// 构造ReverseListIterator(Iterator it): _it(it){}//// 具有指针类似行为Ref operator*(){Iterator temp(_it);--temp;return *temp;}Ptr operator->(){return &(operator*());}//// 迭代器支持移动Self& operator++(){--_it;return *this;}Self operator++(int){Self temp(*this);--_it;return temp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self temp(*this);++_it;return temp;}//// 迭代器支持比较bool operator!=(const Self& l)const{return _it != l._it;}bool operator==(const Self& l)const{return _it != l._it;}Iterator _it;};
list的反向迭代器
通过前面知道,反向迭代器的++就是正向迭代器的–,反向迭代器的–就是正向迭代器的++,因此反向迭代器的实现可以借助正向迭代器,即:反向迭代器内部可以包含一个正向迭代器,对正向迭代器的接口进行包装即可。
template<class Iterator>
class ReverseListIterator
{// 注意:此处typename的作用是明确告诉编译器,Ref是Iterator类中的类型,而不是静态成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIterator<Iterator> Self;
public://// 构造ReverseListIterator(Iterator it) : _it(it) {}//// 具有指针类似行为Ref operator*() {Iterator temp(_it);--temp;return *temp;}Ptr operator->() { return &(operator*()); }//// 迭代器支持移动Self& operator++() {--_it;return *this;}Self operator++(int) {Self temp(*this);--_it;return temp;}Self& operator--() {++_it;return *this;}Self operator--(int){Self temp(*this);++_it;return temp;}/// 迭代器支持比较bool operator!=(const Self& l)const{ return _it != l._it;}bool operator==(const Self& l)const{ return _it != l._it;}Iterator _it;
};
四、与vector的对比
vector与list都是STL中非常重要的序列式容器,由于两个容器的底层结构不同,导致其特性以及
应用场景不同,其主要不同如下:
五、总结
- 容器特点
list是一种双向链表容器,具有以下显著特点:- 动态性强:可以根据需要随时添加或删除元素,无需担心预先分配固定大小的内存问题。
插入和删除高效:在链表的任意位置进行插入和删除操作的时间复杂度为常数级别,这使得它在频繁进行此类操作的场景下表现出色。 - 迭代灵活:提供双向迭代器,可方便地进行正向和反向遍历。但不支持随机访问,访问特定位置的元素相对较慢。
- 动态性强:可以根据需要随时添加或删除元素,无需担心预先分配固定大小的内存问题。
- 适用场景
- 频繁插入和删除:当需要在容器中频繁地进行插入和删除操作时,list是一个很好的选择。例如,在实现一些数据结构(如栈、队列)或者处理动态变化的数据集合时。
- 顺序访问:如果主要是按照顺序访问元素,而不是随机访问,list可以满足需求。比如,依次处理一系列数据,而不需要直接跳到特定位置的元素。
- 与其他容器对比
与 C++ 中的其他容器(如vector、array等)相比:- 与vector:vector支持随机访问,但其在插入和删除元素时,可能需要移动大量元素,时间复杂度可能较高。而list在插入和删除方面更高效,但随机访问能力较弱。
- 与array:array大小固定,不具备动态性。list则可以根据需要动态调整大小。
总之,C++ 中的list是一种功能强大的容器,在特定的场景下能够发挥出很大的优势。