【C++ 学习 ⑬】- 详解 list 容器

目录

一、list 容器的基本介绍

二、list 容器的成员函数

2.1 - 迭代器

2.2 - 修改操作

三、list 的模拟实现

3.1 - list.h

3.2 - 详解 list 容器的迭代器

3.2 - test.cpp

---

 

---

一、list 容器的基本介绍

list 容器以类模板 list<T>（T 为存储元素的类型）的形式定义在 <list> 头文件中，并位于 std 命名空间中。

template < class T, class Alloc = allocator<T> > class list;    

list 是序列容器，允许在序列内的任意位置高效地插入和删除元素（时间复杂度是 O(1) 常数阶），其迭代器类型为双向迭代器（bidirectional iterator）。

list 容器的底层是以双向链表的形式实现的。

list 容器与 forward_list 容器非常相似，最主要的区别在于 forward_list 容器的底层是以单链表的形式实现的，其迭代器类型为前向迭代器（forward iterator）。

与其他标准序列容器（array、vector 和 deque）相比，list 容器在序列内已经获得迭代器的任意位置进行插入、删除元素时通常表现得更好。

与其他序列容器相比，list 容器和 forward_list 容器的最大缺点是不支持任意位置的随机访问，例如：要访问 list 中的第 6 个元素，必须从已知位置（比如头部或尾部）迭代到该位置，这需要线性阶的时间复杂度的开销。

---

二、list 容器的成员函数

2.1 - 迭代器

begin：

      iterator begin();
const_iterator begin() const;

end:

      iterator end();
const_iterator end() const;

rbegin：

      reverse_iterator rbegin();
const_reverse_iterator rbegin() const;

rend：

      reverse_iterator rend();
const_reverse_iterator rend() const;

示例：

#include <iostream>
#include <list>
using namespace std;
​
int main()
{list<int> l;l.push_back(0);l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);
​for (list<int>::iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";}// 0 1 2 3 4cout << endl;
​for (list<int>::reverse_iterator rit = l.rbegin(); rit != l.rend(); ++rit){cout << *rit << " ";}// 4 3 2 1 0cout << endl;return 0;
}

 

2.2 - 修改操作

push_front：

void push_front(const value_type& val);

注意：value_type 等价于 T。

pop_front：

void pop_front();

push_back：

void push_back(const value_type& val);

pop_back：

void pop_back();

insert：

// C++ 98
single element (1) iterator insert(iterator position, const value_type& val);fill (2)     void insert(iterator position, size_type n, const value_type& val);range (3) template <class InputIterator>void insert(iterator position, InputIterator first, InputIterator last);

相较于 vector，执行 list 的 insert 操作不会产生迭代器失效的问题。

示例一：

#include <iostream>
#include <list>
using namespace std;
​
int main()
{list<int> l;l.push_back(0);l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);
​// 要求：在第三个元素前面插入元素 100// l.insert(l.begin() + 2, 100);  // error// 因为 list 对应的迭代器类型为双向迭代器，所以不支持加法操作，即没有重载该运算符
​// 解决方案：list<int>::iterator it = l.begin();for (size_t i = 0; i < 2; ++i){++it;}l.insert(it, 100);
​for (auto e : l){cout << e << " ";}// 0 1 100 2 3 4cout << endl;return 0;
}

erase：

iterator erase(iterator position);
iterator erase(iterator first, iterator last);

因为节点被删除后，空间释放了，所以执行完 list 的 erase 操作，迭代器就失效了，而解决方案依然是通过返回值对迭代器进行重新赋值。

示例二：

#include <iostream>
#include <list>
using namespace std;
​
int main()
{list<int> l;l.push_back(0);l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);
​// 删除 list 中所有值为偶数的元素list<int>::iterator it = l.begin();while (it != l.end()){if (*it % 2 == 0)it = l.erase(it);  // 直接写 l.erase(it); 会报错else++it;}
​for (auto e : l){cout << e << " ";}// 1 3cout << endl;return 0;
}

---

三、list 的模拟实现

3.1 - list.h

#pragma once
​
#include <iostream>
#include <assert.h>
​
namespace yzz
{template<class T>struct __list_node{__list_node<T>* _prev;__list_node<T>* _next;T _data;
​__list_node(const T& val = T()): _prev(0), _next(0), _data(val){ }};
​
​template<class T, class Ref, class Ptr>struct __list_iterator{typedef __list_iterator<T, Ref, Ptr> self;typedef __list_node<T> list_node;list_node* _pnode;  // 节点指针
​__list_iterator(list_node* p = 0): _pnode(p){ }
​self& operator++(){_pnode = _pnode->_next;return *this;}
​self operator++(int){self tmp(*this);_pnode = _pnode->_next;return tmp;}
​self& operator--(){_pnode = _pnode->_prev;return *this;}
​self operator--(int){self tmp(*this);_pnode = _pnode->_prev;return tmp;}
​Ref operator*() const{return _pnode->_data;}
​Ptr operator->() const{return &_pnode->_data;}
​bool operator!=(const self& it) const{return _pnode != it._pnode;}
​bool operator==(const self& it) const{return _pnode == it._pnode;}};
​
​template<class T>class list{private:typedef __list_node<T> list_node;
​void empty_initialize(){_phead = new list_node;_phead->_prev = _phead;_phead->_next = _phead;}
​public:/*-------- 构造函数和析构函数 --------*/list(){empty_initialize();}
​list(const list<T>& l)  // 实现深拷贝{empty_initialize();for (auto& e : l){push_back(e);}}
​~list(){clear();delete _phead;_phead = 0;}
​/*-------- 赋值运算符重载 --------*/// 利用上面写好的拷贝构造函数实现深拷贝void swap(list<T>& l){std::swap(_phead, l._phead);}
​list<T>& operator=(list<T> tmp){swap(tmp);return *this;}
​/*-------- 迭代器 --------*/typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return _phead->_next;// 等价于：return iterator(_phead);// 返回的过程中发生了隐式类型转换}
​iterator end(){return _phead;}
​const_iterator begin() const{return _phead->_next;// 等价于：return const_iterator(_phead->_next);}
​const_iterator end() const{return _phead;}
​/*-------- 容量操作 --------*/size_t size() const{size_t sz = 0;list_node* cur = _phead->_next;while (cur != _phead){++sz;cur = cur->_next;}return sz;}
​bool empty() const{return _phead->_next == _phead;}
​/*-------- 修改操作 --------*/iterator insert(iterator pos, const T& val){list_node* newnode = new list_node(val);newnode->_prev = pos._pnode->_prev;newnode->_next = pos._pnode;
​pos._pnode->_prev->_next = newnode;pos._pnode->_prev = newnode;return newnode;}
​void push_back(const T& val){// 方法一：/*list_node* newnode = new list_node(val);newnode->_prev = _phead->_prev;newnode->_next = _phead;
​_phead->_prev->_next = newnode;_phead->_prev = newnode;*/
​// 方法二（直接复用）：insert(end(), val);}
​void push_front(const T& val){// 方法一：/*list_node* newnode = new list_node(val);newnode->_prev = _phead;newnode->_next = _phead->_next;
​_phead->_next->_prev = newnode;_phead->_next = newnode;*/
​// 方法二（直接复用）：insert(begin(), val);}
​iterator erase(iterator pos){assert(pos != end());  // 前提是 list 非空list_node* prev_pnode = pos._pnode->_prev;list_node* next_pnode = pos._pnode->_next;prev_pnode->_next = next_pnode;next_pnode->_prev = prev_pnode;delete pos._pnode;return iterator(next_pnode);}
​void pop_back(){erase(--end());}
​void pop_front(){erase(begin());}
​void clear(){list_node* cur = _phead->_next;while (cur != _phead){list_node* tmp = cur;cur = cur->_next;delete tmp;}_phead->_prev = _phead->_next = _phead;}
​private:list_node* _phead;  // 头指针};
}

3.2 - 详解 list 容器的迭代器

我们可以通过循序渐进的方式来了解 list 容器的迭代器：

1. 首先，不能使用原生态指针直接作为 list 容器的正向迭代器，即：

   typedef list_node* iterator;

   否则当正向迭代器进行 ++/-- 操作时，无法让它指向下一个或上一个节点，并且进行解引用 * 操作时，无法直接获得节点的值，所以需要对原生态指针进行封装，然后对这些操作符进行重载，即：

   typedef __list_iterator<T> iterator;

2. 其次，不能按以下方式直接定义 list 容器的常量正向迭代器，即：

   typedef const __list_iterator<T> const_iterator;

   否则常量正向迭代器就无法进行 ++/-- 操作，因为 const 类对象只能去调用 const 成员函数，并且 operator* 的返回值类型为 T&，即仍然可以在外部修改 list 容器。

   可以重新定义一个常量正向迭代器 __list_const_iterator，但需要修改的地方仅仅是 operatr* 的返回值，即将其修改为 const T&，显然这样的解决方案会造成代码的冗余，所以在 __list_iterator 类模板中增加一个类型参数 Ref，将 operator* 的返回值修改为 Ref，即：

   typedef __list_iterator<T, T&> iterator;
   typedef __list_iterator<T, const T&> const_iterator;

3. 最后，在重载 -> 操作符时，对于正向迭代器，返回值类型应该是 T*，对于常量正向迭代器，返回值类型应该是 const T*，所以再增加一个类型参数 Ptr，将 operator-> 的返回值类型修改为 Ptr，即：

   typedef __list_iterator<T, T&, T*> iterator;
   typedef __list_iterator<T, const T&, const T*> const_iterator;

3.2 - test.cpp

#include "list.h"
#include <iostream>
using namespace std;
​
void Print1(const yzz::list<int>& l)
{yzz::list<int>::const_iterator cit = l.begin();while (cit != l.end()){cout << *cit << " ";++cit;}cout << endl;
}
​
void test_list1()
{yzz::list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);cout << l1.size() << endl;  // 4yzz::list<int> l2(l1);for (yzz::list<int>::iterator it = l2.begin(); it != l2.end(); ++it){cout << *it << " ";}// 1 2 3 4cout << endl;
​l1.push_front(10);l1.push_front(20);l1.push_front(30);l1.push_front(40);cout << l1.size() << endl;  // 8yzz::list<int> l3;l3 = l1;for (auto& e : l3){cout << e << " ";}// 40 30 20 10 1 2 3 4cout << endl;
​l1.pop_back();l1.pop_back();l1.pop_front();l1.pop_front();cout << l1.size() << endl;  // 4Print1(l1);// 20 10 1 2
​l1.clear();cout << l1.size() << endl;  // 0cout << l1.empty() << endl;  // 1
}
​
struct Point
{int _x;int _y;
​Point(int x = 0, int y = 0): _x(x), _y(y){ }
};
​
void Print2(const yzz::list<Point>& l)
{yzz::list<Point>::const_iterator cit = l.begin();while (cit != l.end()){// 方法一：// cout << "(" << (*cit)._x << ", " << (*cit)._y << ")" << " ";// 方法二：cout << "(" << cit->_x << ", " << cit->_y << ")" << " ";// 注意：operator-> 是单参数，所以本应该是 cit->->_i 和 cit->->_j，// 但为了可读性，编译器做了优化，即省去一个 ->++cit;}cout << endl;
}
​
void test_list2()
{yzz::list<Point> l;l.push_back(Point(1, 1));l.push_back(Point(2, 2));l.push_back(Point(3, 3));l.push_back(Point(4, 4));Print2(l);// (1, 1) (2, 2) (3, 3) (4, 4)
}
​
int main()
{// test_list1();test_list2();return 0;
}