• C++打怪升级（十一）- STL之list

    ~~~~

    美图

    前言

    本节将介绍list的使用，之后模拟实现list的基本功能，最后将分析与连续顺序容器（vector）的差异。

    1. list是什么

    list是逻辑上的顺序容器，实际list的储存中是不连续的，相邻节点之间通过指针进行链接。
    list是带头节点的双向循环链表，在所有的链表中结构最复杂，使用也最方便。
    list在头部和尾部的插入和删除操作、中间部分的插入删除操作都是常数时间，效率很高；与连续顺序容器相比的优势是中间位置的插入和删除操作时间复杂度是常数时间 O ( 1 ) O(1) O(1)，而像vector在中间插入或删除元素往往涉及到元素的移动，时间复杂度是 O ( N ) O(N) O(N)。劣势是list作为不连续存储的顺序容器不能实现随机访问元素 O ( 1 ) O(1) O(1)，需要从第一个元素开始依次查找，直到找到或到最后一个元素为止，时间复杂度是 O ( N ) O(N) O(N)。
    image.png

    2. list接口函数的使用

    1. 构造相关

    初始化list对象

    默认构造

    声明

    list ();

    • 1

    eg

    list<int> l1;

    • 1

    n个val构造

    声明

    list (size_type n, const value_type& val = value_type());

    • 1

    eg

    list<int> l1(5, 7); // l1: 7 7 7 7 7

    • 1

    迭代器范围构造

    声明

    template <class InputIterator>
list (InputIterator first, InputIterator last);

    • 1
    • 2

    eg

    vector<int> v{1, 2, 3, 4, 5};
list<int> l1(v.begin() + 1, v.end()); // l1: 2 3 4 5

    • 1
    • 2

    拷贝构造

    声明

    list (const list& x);

    • 1

    eg

    list<int> l1(5, 6); // 6 6 6 6 6
list<int> l2(l1);   // l2: 6 6 6 6 6 

    • 1
    • 2

    2 赋值运算符重载函数

    声明

    list& operator= (const list& x);

    • 1

    eg

    list<int> l1(4, 3); // l1: 3 3 3 3
list<int> l2(3, 6); // l2: 6 6 6
l2 = l1; // l2: 3 3 3 3

    • 1
    • 2
    • 3

    2 析构函数

    释放对象申请的所有资源，为对象销毁做好准备。

    ~list();

    • 1

    3 迭代器相关

    迭代器是像指针一样的类型。

    begin 和 end

    声明

    begin

    返回第一个对象的所在位置的迭代器。

    iterator begin();
const_iterator begin() const;

    • 1
    • 2

    end

    返回最后一个对象所在位置的下一个位置的迭代器。

    iterator end();
const_iterator end() const;

    • 1
    • 2

    eg

    list<int> l1{1,2,3,4,5};
list<int>::iterator it = l1.begin();
while (it != l1.end()) {
    cout << *it << " ";
    it++;
}
cout << endl << endl; // 结果为 1 2 3 4 5

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    rbegin 和rend

    声明

    rbegin

    返回第一个对象的前一个位置的迭代器。

    reverse_iterator rbegin();
const_reverse_iterator rbegin() const;

    • 1
    • 2

    rend

    返回最后一个对象的迭代器。

    reverse_iterator rend();
const_reverse_iterator rend() const;

    • 1
    • 2

    eg

    list<int> l1{1,2,3,4,5};

list<int>::reverse_iterator rit = l1.rbegin();
while (rit != l1.rend()) {
    cout << *rit << " ";
    rit++;
}
cout << endl << endl; // 结果为 5 4 3 2 1

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    4 容量相关

    empty

    声明
    判断list对象是否为空，是返回true；反之返回false。

    bool empty() const;

    • 1

    eg

    list<int> l1;
l1.empty();      // true
l1.push_back(10);
l1.empty();      // false

    • 1
    • 2
    • 3
    • 4

    size

    声明
    返回list对象的元素个数

    size_type size() const;

    • 1

    5 元素访问相关

    front

    声明
    返回第一个有效元素的引用。
    当list为空时调用front函数会产生未定义的行为。

    reference front();
const_reference front() const;

    • 1
    • 2

    eg

    list<int> l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.front(); // 1

    • 1
    • 2

    back

    声明
    返回最后一个元素的引用。
    当list为空时调用back函数会产生未定义的行为。

    reference back();
const_reference back() const;

    • 1
    • 2

    eg

    list<int> l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.back(); // 5

    • 1
    • 2

    6 修改相关

    push_back

    声明
    尾插一个新元素

    void push_back (const value_type& val);

    • 1

    eg

    list<int> l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.push_back(10); // l1: 1 2 3 4 5 10
l1.size()         // 6

    • 1
    • 2
    • 3

    pop_back

    声明
    尾删一个元素。
    当list对象为空时调用该函数程序将会出错。

    void pop_back();

    • 1

    eg

    list<int> l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.pop_back(); // l1: 1 2 3 4
l1.size()         // 4

    • 1
    • 2
    • 3

    push_front

    声明
    头插一个新元素

    void push_front (const value_type& val);

    • 1

    eg

    list<int> l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.push_front(9); // l1: 9 1 2 3 4 5
l1.size()         // 6

    • 1
    • 2
    • 3

    pop_front

    声明
    头删一个元素
    当list对象为空时调用该函数程序将会出错。

    void pop_front();

    • 1

    eg

    list<int> l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.pop_front(); // l1: 2 3 4 5
l1.size()         // 4

    • 1
    • 2
    • 3

    insert - 插入新值

    声明
    在迭代器pos指向的元素之前插入一个值为val的元素。

    iterator insert (iterator pos, const value_type& val);

    • 1

    eg

    list<int> l1{1,2,3,4,5}; // l1: 1 2 3 4 5
list<int>::iterator pos = find(l1.begin(), l1.end(), 3);

l1.insert(pos, 9); // l1: 1 2 9 3 4 5

    • 1
    • 2
    • 3
    • 4

    声明
    在迭代器pos指向的元素之前插入n个值为val的元素。

    void insert (iterator pos, size_type n, const value_type& val);

    • 1

    eg

    list<int> l1{1,2,3,4,5}; // l1: 1 2 3 4 5
list<int>::iterator pos = find(l1.begin(), l1.end(), 3);

l1.insert(pos, 3, 6); // l1: 1 2 6 6 6 3 4 5

    • 1
    • 2
    • 3
    • 4

    声明
    在迭代器pos指向的元素之前插入指定迭代器范围内的所有元素。
    指定的迭代器范围是左闭右开区间。

    template <class InputIterator>
void insert (iterator pos, InputIterator first, InputIterator last);

    • 1
    • 2

    eg

    list<int> l1{1,2,3,4,5}; // l1: 1 2 3 4 5
vector<int> v{7, 8, 9, 0};
list<int>::iterator pos = find(l1.begin(), l1.end(), 3);

l1.insert(pos, 3, 6); // l1: 1 2 7 8 3 4 5

    • 1
    • 2
    • 3
    • 4
    • 5

    erase

    声明
    删除迭代器pos指向的元素

    iterator erase (iterator position);

    • 1

    eg

    list<int> l1{1, 2, 3, 4, 5}; // l1: 1 2 3 4 5
list<int>::iterator pos = find(l1.begin(), l1.end(), 3);
if (pos != l1.end()) {
    l1.erase(pos);           // l1: 1 2 4 5a
}

    • 1
    • 2
    • 3
    • 4
    • 5

    声明
    删除迭代器范围内的所有元素。

    iterator erase (iterator first, iterator last);

    • 1

    eg

    list<int> l1{1, 2, 3, 4, 5};    // l1: 1 2 3 4 5
list<int>::iterator pos = find(l1.begin(), l1.end(), 3);
l1.erase(l1.begin(), l1.end()); // l1: 空

    • 1
    • 2
    • 3

    resize

    声明
    设置list对象的大小为n，每个元素都使用val初始化；
    如果 n 大于list对象的大小，就尾插新元素直到list对象大小恰好为n；
    如果 n 小于list对象的大小，就尾删元素直到list对象大小恰好为n；
    如果 n 等于list对象大小，就什么也不做。

    void resize (size_type n, value_type val = value_type());

    • 1

    eg

    list<int> l1{1,2,3,4,5};	// l1: 1 2 3 4 5
l1.size();					// 5

l1.resize(8, 9);			// l1: 1 2 3 4 5 8 8 8
l1.size();					// 8

l1.resize(3, 1);			// l1: 1 2 3
l1.size();					// 3

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    assign

    用新值替换就值

    声明
    使用n个val赋值给list对象。
    list对象的大小可能发生变化。

    void assign (size_type n, const value_type& val);

    • 1

    eg

    list<int> l1{1, 2, 3, 4, 5};	// l1: 1 2 3 4 5
l1.size();						// 5
vector<int> v{2, 2, 3, 3};
l1.assign(4, 6);				// l1: 6 6 6 6
l1.size();						// 4

    • 1
    • 2
    • 3
    • 4
    • 5

    声明
    使用指定迭代器范围内的所有元素赋值给list对象。

    template <class InputIterator>
void assign (InputIterator first, InputIterator last);

    • 1
    • 2

    eg

    list<int> l1{1, 2, 3, 4, 5};	// l1: 1 2 3 4 5
l1.size();						// 5
vector<int> v{2, 2, 3, 3};
					// 4
l1.assign(v.begin(), v.end());	// l1: 2 2 3 3
l1.size();						// 4

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    swap

    声明
    交换两个list对象的内容。

    void swap (list& x);

    • 1

    eg

    list<int> l1{1, 2, 3, 4, 5};
l1.size();
list<int> l2{2, 2, 3 ,3};
l2.size();

l1.swap(l2);
// l1: 2 2 3 3		size: 4
// l2: 1 2 3 4 5	size: 5

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    clear

    声明
    删除list对象的所有元素，并使list对象的大小为0。

    void clear();

    • 1

    eg

    list<int> l1{1, 2, 3, 4, 5};// l1: 1 2 3 4 5
l1.size();					// 5

l1.clear();					// 清空l1
l1.size();					// 0

    • 1
    • 2
    • 3
    • 4
    • 5

    7 其他操作相关

    reverse - 逆置

    声明
    逆置list对象的所有元素。

    void reverse();

    • 1

    eg

    list<int> l1{1, 2, 3, 4, 5};	// l1: 1 2 3 4 5
l1.reverse();					// l1: 5 4 3 2 1
reverse(l1.begin(), l1.end());	// l1: 1 2 3 4 5

    • 1
    • 2
    • 3

    sort - 排序

    声明
    对list对象的所有元素进行排序，无参时采用默认排序规则；有参时传入函数指针或仿函数，使用函数或仿函数定义的规则。
    排序方法是归并排序。

    void sort();

template <class Compare>
void sort (Compare comp);

    • 1
    • 2
    • 3
    • 4

    eg

    list<int> l1{1, 3, 5, 2, 4, 6};		// l1: 1 3 5 2 4 6
l1.sort();							// l1: 1 2 3 4 5 6
                                	// 传入函数指针
list<int> l2{ 1, 3, 5, 2, 4, 6 };	// l2: 1 3 5 2 4 6
l2.sort(compare<int>);				// l2: 6 5 4 3 2 1
                                	// 传入函数对象
list<int> l3{ 1, 3, 5, 2, 4, 6 };	// l3: 1 3 5 2 4 6
l3.sort(com<int>());				// l3: 6 5 4 3 2 1

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    从大到小排序

    template<class T>
bool compare(const T& t1, const T& t2) {
	return t1 > t2;
}

    • 1
    • 2
    • 3
    • 4

    从大到小排序

    template<class T>
struct com {
	bool operator()(const T& t1, const T& t2) {
		return t1 > t2;
	}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    unique - 去重

    声明
    无参数时，删除相邻的重复元素；
    有参数时，参数是一个函数指针或函数对象，删除的不再是重复的相邻元素，而是满足传入参数所设置的条件的元素；
    unique函数不对list对象所有参数进行排序，所以在使用该函数之前需要额外调用排序函数进行排序，以保证重复的元素是相邻的。

    void unique();

template <class BinaryPredicate>
void unique (BinaryPredicate binary_pred);

    • 1
    • 2
    • 3
    • 4

    eg

    list<int> l1{3, 2, 3, 1, 1, 2, 2}; // l1: 3, 2, 3, 1, 1, 2, 2
                                   // 不排序直接去重
l1.unique();					   // l1: 3, 2, 3, 1, 2

list<int> l2{3, 2, 3, 1, 1, 2, 2};	// l2: 3, 2, 3, 1, 1, 2, 2
                                	// 先排序在去重
l2.sort();							// l2: 1, 1, 2, 2, 2, 3, 3
l2.unique();						// l2: 1, 2, 3

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    merge - 合并

    声明
    合并两个已经排好序的list对象；
    无参时，按默认规则把x中的所有元素依次转移到本list对象中，转移的操作为把x的元素的值依次与本list对象元素的值进行比较，如果x的元素的值大于比较的值则把x的元素插入到比较的元素之后；反之就继续比较直到最后一个元素。转移完成后，x对象就为空了。
    有参时，区别是传入的函数指针或函数对象定义了比较的规则，转移时不在根据默认默认的规则进行。

    void merge (list& x);

template <class Compare>
void merge (list& x, Compare comp);

    • 1
    • 2
    • 3
    • 4

    eg

    list<int> l1{1, 9, 7, 6, 4};	// l1: 1 9 7 6 4 size: 5
list<int> l2{3, 2, 8};			// l2: 3 2 8     size: 3

l1.sort();						// l1: 1 4 6 7 9
l2.sort();						// l2: 2 3 8

l1.merge(l2);					// l1: 1 2 3 4 6 7 8 9	size: 8
                                // l2: 					size: 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    remove - 删除值为val的元素

    声明

    void remove (const value_type& val);

    • 1

    eg

    list<int> l1{0, 1, 2, 3, 3, 4, 3}; 	// l1: 0, 1, 2, 3, 3, 4, 3	size: 7
l1.remove(3);						// l1: 0, 1, 2, 4   		size: 4

    • 1
    • 2

    remove_if - 删除满足条件的元素

    声明

    template <class Predicate>
void remove_if (Predicate pred);

    • 1
    • 2

    eg

    list<int> l2{0, 1, 2, 3, 4};	// l1: 0, 1, 2, 4		size: 4
l2.remove_if(isOdd());			// l1: 1, 3    			size: 2

    • 1
    • 2

    是偶数就返回true

    struct isOdd {
bool operator()(const int& t) {
    return t % 2 == 0;
}
};

    • 1
    • 2
    • 3
    • 4
    • 5

    splice - 从list对象转移元素到另一个list对象

    声明
    把list对象x的元素转移到另一个list对象的pos迭代器位置之前；

    // 转移x所有的元素
void splice (iterator pos, list& x);
// 转移x迭代器i指向的元素
void splice (iterator pos, list& x, iterator i);
// 转移x中指定迭代器范围的元素
void splice (iterator pos, list& x, iterator first, iterator last);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    eg

    list<int> l1{1, 2, 3, 4, 5};				// l1: 1, 2, 3, 4, 5
list<int> l2{6, 7, 8};						// l2: 6, 7, 8
auto pos = find(l1.begin(), l1.end(), 3);
l1.splice(pos, l2);							// l1: 1, 2, 6, 7, 8, 3, 4, 5	size: 8
                                            // l2: 							size: 0

    • 1
    • 2
    • 3
    • 4
    • 5

    8 非成员函数

    swap

    声明

    template <class T>
void swap (list<T>& x, list<T>& y);

    • 1
    • 2

    eg

    list<int> l1{1, 2, 3};    		// l1: 1, 2, 3		size: 3
list<int> l2{6, 7, 8, 9};	  	// l2: 6, 7, 8, 9	size: 4
swap(l1, l2);					// 交换                            	
								// l1: 6, 7, 8, 9	size: 4
								// l2: 1, 2, 3		size: 3

    • 1
    • 2
    • 3
    • 4
    • 5

    3. list的模拟实现

    本次list实现是简化版，主要以学习为主，着重关注的是list的基本结构和其迭代器的具体实现。特别是const的迭代器与连续顺序容器的迭代器（以Linux下G++采用的SGI版本为例，VS2019下vector的迭代器被封装为了一个类，不再是原生指针）有着巨大的差异：如vector的迭代器是由原生指针typedef而来的，而list迭代器必须封装为一个类才能达到与vector迭代器类似的行为。

    基本框架

    list是带头双向循环链表，本次实现参考的是Linux中g++中采用的STL的SGI版。

    定义节点结构

    由于list可以存放多种类型的数据，需要采用类模板的方式。
    包含三个成员变量：

    节点指针_prev: 指向前一个节点
    节点指针_next: 指向后一个节点
    _val: 节点储存该类型对应的元素

    image.png
    struct和class作用基本相同，只是默认成员变量和成员函数是public的。
    下文定义的list类模板需要在类内访问节点的成员变量和成员函数，直接使用struct定义节点结构就可以方便实现需求。

    template<class T>
struct __list_node {
    __list_node(const T& val)
        :_val(val)
        ,_prev(nullptr)
        ,_next(nullptr){ }

    __list_node* _prev;
    __list_node* _next;
    T _val;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    定义链表结构

    链表结构list也是一个类模板，因为其节点储存的元素类型不确定；
    list的成员变量有两个：

    节点指针_phead: 指向头结点，头结点是整个链表的开始但不存放有效元素
    _size: 表示当前链表的有效节点个数，不包括头结点

    template<class T>
class list {
	typedef __list_node<T> node; // 对节点类实例化重定义以简化写法
public:
	typedef __list_iterator<T> iterator; // 迭代器类型
	typedef __list_const_iterator<T> const_iterator;
private:
    node* _phead;
    size_t _size;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    定义迭代器结构 - 类的封装

    迭代器分类

    原生指针实现；
    类的封装实现；

    模板类的类型与内部类型的特殊使用方式

    类名与类型的区别：
    普通类：类名就是类型；
    类模板：类名+模板参数才是类型，
    例外是：在类内可以省略模板参数，只写类名表示类型；
    但是并不推荐这种写法，应该写出具体完整的类型，防止以后给自己或他人造成困扰；
    例如标准库中list的构造实现：
    image.png

    版本1：只支持非const对象

    迭代器对于链表来说，是一个行为像指针一样的类型。
    指针支持的操作有：

    解引用*、->、前置++、后置++、前置–、后置–、指针比较操作

    原生的节点指针：

    • 不支持++、–操作；
    • 解引用操作*得到的是整个节点而不是预期的节点的值；
    • ->操作得到的是整个节点的地址，而不是节点值的地址；
    • 比较操作是符合的，可以满足比较操作；

    如string、vector可以直接借助原生指针实现迭代器类型（当然，不是所有版本的string、vector的迭代器是原生指针，可能是被封装为了一个复杂的类），这依赖于它们天生的物理结构优势-连续存储。

    原生指针的迭代器基本不能满足list对迭代器的需求，所以需要把迭代器定义为一个单独的类，依赖运算符重载功能对**运算符*、->、前置++、后置++、前置–、后置–**进行重载以便于满足我们对迭代器的预期。

    对迭代器的预期：

    • *得到节点内部的值；
    • ->得到节点内部值的地址；
    • 支持++：迭代器由当前节点指向下一个节点；
    • 支持–：迭代器由当前节点指向前一个节点；
    基本结构

    迭代器只包含一个节点指针成员变量

    template<class T>
struct __list_iterator {
    typedef __list_node<T> node;
    typedef __list_iterator<T> iterator;
    node* _pnode;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    构造函数

    实现基本的构造函数，接受节点地址进行初始化；
    由于迭代器类本身不涉及资源的申请和释放，故析构、拷贝构造、赋值运算符重载等函数都不需要显式实现，由编译器生成默认的即可。

    __list_iterator(node* pnode)
    :_pnode(pnode){ }

    • 1
    • 2
    *运算符重载

    得到节点内部的值并传引用返回；
    由于这个迭代器是非const的，所以迭代器指向的节点也是非const的，故返回类型是非const的：T&。

    T& operator*() {
    return _pnode->_val;
}

    • 1
    • 2
    • 3
    ->运算符重载

    返回节点内部值的地址；
    由于这是非const迭代器，所以迭代器指向的节点也是非const的，故·返回类型是非const的：T*

    T* operator->() {
    return &(_pnode->_val);
}

    • 1
    • 2
    • 3
    前置++运算符重载

    迭代器指向下一个位置，返回下一个位置的迭代器；
    即前置++返回++之前的值；

    iterator operator++() {
    _pnode = _pnode->_next;
    return *this;
}

    • 1
    • 2
    • 3
    • 4
    后置++运算符重载

    迭代器指向下一个位置，返回当前位置的迭代器；
    即后置++返回++之后的值

    iterator operator++(int) {
    iterator tmp(*this);
    _pnode = _pnode->_next;
    return tmp;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    前置–运算符重载

    迭代器指向前一个位置，返回前一个位置的迭代器；

    iterator operator--() {
    _pnode = _pnode->_prev;
    return *this;
}

    • 1
    • 2
    • 3
    • 4
    后置–运算符重载

    迭代器指向前一个位置，返回当前位置的迭代器；

    iterator operator--(int) {
    iterator tmp(*this);
    _pnode = _pnode->_prev;
    return tmp;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    !=运算符重载

    两个迭代器不相等即两个迭代器指向的节点不相等；

    bool operator!=(iterator it) {
    return _pnode != it._pnode;
}

    • 1
    • 2
    • 3
    ==运算符重载

    两个迭代器相等即两个迭代器指向的节点相等；

    bool operator==(iterator it){
    return !(*this != it);
}

    • 1
    • 2
    • 3
    代码汇总
    template<class T>
struct __list_iterator {
    typedef __list_node<T> node;
    typedef __list_iterator<T> iterator;
    node* _pnode;

    __list_iterator(node* pnode)
        :_pnode(pnode){ }
	T& operator*() {
        return _pnode->_val;
    }
    iterator operator++() {
        _pnode = _pnode->_next;
        return *this;
    }
    iterator operator++(int) {
        iterator tmp(*this);
        _pnode = _pnode->_next;
        return tmp;
    }
    iterator operator--() {
        _pnode = _pnode->_prev;
        return *this;
    }
    iterator operator--(int) {
        iterator tmp(*this);
        _pnode = _pnode->_prev;
        return tmp;
    }
    bool operator!=(iterator it) {
        return _pnode != it._pnode;
    }
	bool operator==(iterator it){
        return !(*this != it);
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    版本2：支持const对象和非const对象

    版本1只实现了非const的迭代器，对于const对象无法使用非const迭代器，需要实现const迭代器；
    也许你有疑问，为什么不是普通迭代器前加上const就是const迭代器呢？

    比如：typedef const __list_iterator const_iterator;

    首先清楚const迭代器的const实际上修饰的谁？
    肯定不是修饰的迭代器本身，因为不管迭代器是const还是非const的都应该能满足++、–操作，而++、–迭代器一定会改变迭代器，故迭代器本身是非const的；而简单的在普通迭代器之前加上const修饰而成的迭代器将会导致迭代器本身是const的而不能进行++、–操作，故其不是const迭代器。
    那const修饰的是谁呢？
    const迭代器的const，修饰的其实是迭代器指向的节点，特别是包括节点内的值；
    const迭代器与普通迭代器的不同在于operator()和->operator返回类型分别是const T&和const T；
    至于++、–、比较大小操作同普通迭代器相同；
    需要一个新的类模板作为const迭代器类，以满足于不同于普通迭代器的*和->操作；

    基本结构
    template<class T>
struct __list_const_iterator {
    typedef __list_node<T> node;
    typedef __list_const_iterator<T> const_iterator;
    node* _pnode;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    *运算符重载

    返回迭代器指向节点内的值的引用；
    由于是const迭代器，所以指向的节点是const的，故返回类型是const T&；

    const T& operator*() {
    return _pnode->_val;
}

    • 1
    • 2
    • 3
    ->运算符重载

    返回迭代器指向节点内的值的地址；
    由于是const迭代器，所以指向的节点是const的，故返回类型是const T*;

    const T* operator->(){
    return &(_pnode->_val);
}

    • 1
    • 2
    • 3
    代码汇总
    template<class T>
struct __list_const_iterator {
    typedef __list_node<T> node;
    typedef __list_const_iterator<T> const_iterator;
    node* _pnode;

    __list_const_iterator(node* pnode)
        :_pnode(pnode) { }
    const T& operator*() {
        return _pnode->_val;
    }
    const_iterator operator++() {
        _pnode = _pnode->_next;
        return *this;
    }
    const_iterator operator++(int) {
        const_iterator tmp(*this);
        _pnode = _pnode->_next;
        return tmp;
    }
    const_iterator operator--() {
        _pnode = _pnode->_prev;
        return *this;
    }
    const_iterator operator--(int) {
        const_iterator tmp(*this);
        _pnode = _pnode->_prev;
        return tmp;
    }
    bool operator!=(const_iterator it) {
        return _pnode != it._pnode;
    }
	bool operator==(const_iterator it){
        return !(*this != it);
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    版本3：支持const对象和非const对象且简化写法

    版本1和版本2分别是普通迭代器的实现和const迭代器的实现，仔细分析发现二者的代码基本上很相似，主要区别是*和->操作返回的类型，普通迭代器返回非const的类型，const迭代器返回const的类型；

    为了简化代码书写，选择合并这两个类模板，把两个不同之处分别多增加参数进行表示：

    即操作的返回类型分为普通类型和const类型，用参数Ref表示；
    ->操作的返回类型分为普通    类型和const*类型，用参数Ptr表示；

    本质仍然是会生成两个迭代器类型，只是不再是由我们自己显式写出，而是由编译器根据类模板及其参数进行推导然后生成两个迭代器类型，所做的工作没有减少，只是交给类编译器承担。

    基本结构
    template<class T, class Ref, class Ptr>
struct __list_iterator {
    typedef __list_node<T> node;
    typedef __list_iterator<T, Ref, Ptr> Self;
    node* _pnode;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    typedef __list_iterator Self;
    在一开始，重定义了迭代器类型本身，简化后续书写；
    如果还需要对迭代器模板参数进行改动只需要在此处进行修改即可，不需要对后续涉及到的代码进行修改，很便利。

    *运算符重载
    Ref operator*() {
    return _pnode->_val;
}

    • 1
    • 2
    • 3
    ->运算符重载
    Ptr operator->() {
    return &(_pnode->Val);
}

    • 1
    • 2
    • 3
    前置++
    Self& operator++() {
    _pnode = _pnode->_next;
    return *this;
}

    • 1
    • 2
    • 3
    • 4
    后置++
    Self operator++(int) {
    Self tmp = *this;
    ++*this;
    return tmp;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    前置–
    Self& operator--() {
    _pnode = _pnode->_prev;
    return *this;
}

    • 1
    • 2
    • 3
    • 4
    后置–
    Self operator--(int) {
    Self tmp(*this);
    _pnode = _pnode->_prev;
    return tmp;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    !=运算符重载
    bool operator!=(const Self& it) const{
    return _pnode != it._pnode;
}

    • 1
    • 2
    • 3
    ==运算符重载
    bool operator==(const Self& it) const {
    return !(*this != it);
}

    • 1
    • 2
    • 3
    代码汇总
    template<class T, class Ref, class Ptr>
struct __list_iterator {
    typedef __list_node<T> node;
    typedef __list_iterator<T, Ref, Ptr> Self;
    node* _pnode;
    __list_iterator(node* pnode)
        :_pnode(pnode) { }
    Ref operator*() {
        return _pnode->_val;
    }
    Ptr operator->() {
        return &(_pnode->Val);
    }
    Self& operator++() {
        _pnode = _pnode->_next;
        return *this;
    }
    Self operator++(int) {
        Self tmp = *this;
        ++*this;
        return tmp;
    }
    Self& operator--() {
        _pnode = _pnode->_prev;
        return *this;
    }
    Self operator--(int) {
        Self tmp(*this);
        _pnode = _pnode->_prev;
        return tmp;
    }
    bool operator!=(const Self& it) const{
        return _pnode != it._pnode;
    }
    bool operator==(const Self& it) const {
        return !(*this != it);
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    构造函数

    初始化链表 - 代码复用

    当定义一个list对象时，将会调用构造函数对该对象进行初始化：申请一个节点作为头结点，并使节点指针均指向自己。
    除了无参的构造函数需要这个功能，迭代器范围做参数的构造函数、拷贝构造函数也需要该功能，为了减少代码冗余，便把申请头结点并处理的功能代码单独抽出来作为一个函数供其他需要的构造函数调用。

    void initialize() {
    _phead = new node(T());
    _phead->_next = _phead;
    _phead->_prev = _phead;
    _size = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    无参构造
    list() {
    initialize();
}

    • 1
    • 2
    • 3
    迭代器范围构造

    范围: [ f i r s t , l a s t ) [first, last) [first,last)

    template<class InputIterator>
list(InputIterator first, InputIterator last) {
    initialize();
    while (first != last) {
        push_back(*first);
        ++first;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    拷贝构造函数

    传统写法 - 自己实现

    申请并初始化头结点
    遍历链表lt，依次取节点中的元素尾插到本链表this中

    list(const list<T>& lt) {
    initialize();
    node* cur = lt._phead->_next;
    while (cur != lt._phead) {
        push_back(cur->_val);
        cur = cur->_next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    现代写法 - 复用

    复用迭代器范围的构造函数先构造一个局部list对象tmp
    交换tmp内指针_phead和this内指针_phead，之后除了构造函数作用域tmp对象将自动销毁

    list(const list<T>& lt) {
    initialize();
    
    list<T> tmp(lt.begin(), lt.end());
    swap(tmp);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    赋值运算符重载函数

    传统写法 - 自己实现

    避免自己给自己赋值，特殊判断一下，比较两个list对象用到了!=的运算符重载
    赋值之前先依次delete本身的所有节点

    list<T>& operator=(const list<T>& lt) {
    if (*this != lt) {
        clear();
        node* cur = lt._phead->_next;
        while (cur != lt._phead) {
            push_back(cur->_val);
            cur = cur->_next;
        }
    }

    return *this;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    现代写法 - 复用

    由传引用传参变为传值传参构造局部list对象lt
    交换本对象this和lt内部的_phead指针

    list<T>& operator=(list<T> lt) {
    swap(lt);
    return *this;
}

    • 1
    • 2
    • 3
    • 4

    析构函数

    delete释放所有申请的节点，包括头节点
    复用了clear函数实现出头节点之外的所有节点的delete释放

    ~list() {
    clear();
    delete _phead;
    _phead = nullptr;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    正向迭代器相关

    begin

    头结点不是储存数据节点，第一个储存数据的有效节点是头结点的下一个节点

    iterator begin() {
    return iterator(_phead->_next);
}
const_iterator begin() const {
    return const_iterator(_phead->_next);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    end

    循环链表，最后一个节点的下一个节点是头结点

    iterator end() {
    return iterator(_phead);
}
const_iterator end() const {
    return const_iterator(_phead);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    增删

    insert

    在pos迭代器指向的节点之前插入一个新节点

    image.png
    image.png

    iterator insert(iterator pos, T val) {
    // prev cur newnode
    node* newnode = new node(val);
    node* cur = pos._pnode;
    node* prev = cur->_prev;

    newnode->_prev = prev;
    prev->_next = newnode;
    newnode->_next = cur;
    cur->_prev = newnode;
    ++_size;
    return iterator(newnode);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    erase
    iterator erase(iterator pos) {
    assert(pos != end());
    // prev cur next
    node* cur = pos._pnode;
    node* prev = cur->_prev;
    node* next = cur->_next;

    prev->_next = next;
    next->_prev = prev;
    delete cur;
    --_size;
    return iterator(prev);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    push_back
    void push_back(const T& val){
    // phead  tail  newnode
    insert(end(), val);
}

    • 1
    • 2
    • 3
    • 4
    pop_back
    void pop_back() {
    erase(--end());
}

    • 1
    • 2
    • 3
    push_front
    void push_front(const T& val) {
    insert(begin(), val);
}

    • 1
    • 2
    • 3
    pop_front
    void pop_front() {
    erase(begin());
}

    • 1
    • 2
    • 3
    clear
    void clear() {
    iterator it = begin();
    while (it != end()) {
        it = erase(it);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    swap
    void swap(list<T>& lt) {
    std::swap(_phead, lt._phead);
}

    • 1
    • 2
    • 3
    resize
    void resize(size_t n, const T& val = T()) {
    size_t sizes = size();
    if (n > sizes) {
        while (sizes < n) {
            push_back(val);
            ++sizes;
        }
    }
    else if (n < sizes) {
        while (n < sizes) {
            pop_back();
            --sizes;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    size
    size_t size() const {
    return _size;
}

    • 1
    • 2
    • 3

    关系运算符重载

    ==
    bool operator==(const list<T>& lt) const {
    return _phead == lt._phead;
}

    • 1
    • 2
    • 3
    !=
    bool operator!=(const list<T>& lt) const {
    return !(*this == lt);
}

    • 1
    • 2
    • 3

    list与vector比较

    list与vector排序效率简要分析

    算法库algorithm中的sort函数底层使用快速排序实现，不支持对list进行排序。
    list内部实现了自己的排序函数sort，该函数底层使用归并排序实现。
    快速排序和归并排序的时间复杂度都是 O ( N ∗ l n N ) O(N*lnN) O(N∗lnN)，但是实际上比较算法库中的sort函数和list内部的sort函数效率时，对同一组数，list内部实现的排序函数运行效率明显低于算法库中的排序函数。
    使用同一组数不同情况下效率的比较：

    1. 对vector进行排序；
    2. list的元素先拷贝vector中，对vector排序再拷贝回list中；
    3. 对list进行排序；
    void testSort() {
	int n = 100000;
	vector<int> v1;
	vector<int> v2;
	list<int> l1;
	list<int>l2;
	srand(time(0));
	for (int i = 0; i < n; ++i) {
		int val = rand();
		l1.push_back(val);
		l2.push_back(val);
	}
	v1.reserve(n);
	v2.reserve(n);
	for (auto& e : l1) {
		v1.push_back(e);
	}

	// vector  对vector进行排序
	int begin1 = clock();
	sort(v1.begin(), v1.end());
	int end1 = clock();

	// list->vector->list  list的元素先拷贝vector中，对vector排序再拷贝回list中
	int begin2 = clock();
	for (auto& e : l1) {
		v2.push_back(e);
	}
	sort(v2.begin(), v2.end());
	int i = 0;
	for (auto& e : l1) {
		e = v2[i++];
	}
	int end2 = clock();

	// list  对list进行排序
	int begin3 = clock();
	l2.sort();
	int end3 = clock();

	cout << "vector:             " << end1 - begin1 << endl;
	cout << "list->vector->list: " << end2 - begin2 << endl;
	cout << "list:               " << end3 - begin3 << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    image.png

    list与vector迭代器差异再次分析 - 调试

    相同点：

    • 迭代器的行为相似，都支持*、->、++、–、比较大小、范围for等操作；
    • 都不支持迭代器相加操作；

    不同点：

    • vector迭代器是一个原生指针实现（不排除不同版本STL的vector迭代器也是类的封装实现），list迭代器是类的封装实现；
    • vector的数据连续存储，支持迭代器+1、-1、迭代器之间的相减操作，++后指向相邻的下一个位置，–后指向相邻的前一个位置；list的节点在堆上随机存储，节点之间在储存上没有先后顺序，通过节点内的指针逻辑上链接相邻的节点，不支持+1、-1、迭代器相减操作，++后指向不相邻的下一个位置，–后指向不相邻的前一个位置。

    image.png

    结语

    本节简要介绍了list的接口函数，重点实现了list的主要接口函数，特别是封装的迭代器。list由于是节点链接，insert之后直接插入了一个新的节点，原迭代器还指向原节点，并不会导致迭代器失效问题，与连续容器不同；erase之后，删除了原有节点，原迭代器指向了被删除的节点，迭代器是失效的，与连续容器相同。

    T h e The The E n d End End

  • 相关阅读:
    Python：dict
    打造一个投资组合管理的金融强化学习环境
    人脸检测几种模型在RK3399上推理速度对比
    DTCloud 第1天
    代码应该怎么写？
    这几种食物不要给1岁内宝宝吃
    Python数据分析案例10——北向资金流入与沪深300涨跌幅分析
    RunnerGo UI自动化测试脚本如何配置
    零念科技完成Pre-A轮融资，推动智能驾驶平台软件国产替代
    日期格式转化成星期几部署到linux显示英文
  • 原文地址：https://blog.csdn.net/weixin_64904163/article/details/134452857