STL链表容器：自制list（链表）容器

2022年11月6日
昨天，已经看完了的stl课程。现在回过头来发现，最最核心的还是自制链表容器这一部分的内容。

这里的这个链表容器实现的底层逻辑和STL库中的list完全相同，也是通过这个项目，让我知道了STL容器背后一些共同的逻辑。
比如，为什么这个函数要这么用，为什么要定义CMP类型，为什么初始化迭代器对象以前要加上容器的域运算符。

同时，也明白了，如果我们想要让自己定义的类模板可以使用这些容器，那我所定义的东西要具备那些内容。
比如，要是员工sort就要重载()运算符，要重载<,>运算符，等等…

很多东西，如果不接触到源码，不接触到容器的底层实现逻辑，那肯定学习起来，记忆起来，使用起来都是特别特别费力的。
所以，STL学习还在路上，STL中，很多容器的很多内容还不是很透彻，不理解，源码的学习也还在路上。

今天，将List链表的代码和知识点再做以总结，作为对STL标准模板库课程的回顾和复习。

1 最基本的双向链表容器

丛上面的图中能看到一个链表容器的基本信息，有元素结点，有头指针尾指针。
那么先把我们目前位置所理解到的List容器框架写出来。

后面一点点分析List应该有的功能并在这个框架的基础上实现这些功能。

template<class T>
class List{
//这里List的L用了大写，是为了将自己定义的链表容器和STL中的list区分开来
private:
	node* m_head;
	node* m_tail;
	class node{
		//还没有定义，看下一小节
	};
public:
	//默认构造
	List();
	//拷贝构造
	List(List const& that);
	...
	//析构函数
	virtual ~List();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.1 嵌套类node类模板

这个类是放在链表类模板里面的，表示一个数据元素结点。
因为是放在List类模板里面的，所以是一个嵌套类模板。

![[list_node]]

//结点类：代表链表的每一个结点
        class node{
            //类中嵌套类，结点类
            public:
                node(node*prev, T const& data, node*next):
		            m_prev(prev),m_data(data),m_next(next){}
                node* m_prev;//前指针
                T m_data;//数据,类型为位置类T，这样就可以接受任何类型的数据 了
                node* m_next;//后指针
        };

1
2
3
4
5
6
7
8
9
10
11

将上面node结点的定义代码放在最初的链表框架中：

template<class T>
class List{
private:
	class node{
		public:
			//构造函数,传入的三个参数分别为node的三个成员函数赋值
			node(node* prev, T const& data, node* next):
				m_prev(prev), m_data(data), m_next(next){}
			//node结点的内部成员函数
			node* m_prev;//前指针域，指向该结点的前一个结点
			T m_data;//数据域，具体数据类型，由定义链表容器时候所传入的类决定
			node* m_next;//后指针域，指向该结点的后一个结点
	};
	node* m_head;//链表头指针
	node* m_tail;//链表尾指针

public:
	List();
	List(List const& that);
	//成员函数，这是我们后面重点讨论的内容
	virtual ~List();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.2 List基本成员函数

这一小节，来试下List的基本成员函数，具体函数功能如下。

isEmpty(); //链表判空
pushFront(T const& data); //在链表头部添加结点
popFront(); //删除链表尾部的结点
T& Front(); //获取头结点数据
T const& Front()const; //获取头结点数据
/*注意，这里有两个获取头结点
 *主要看第二个，用于const List头元素的获取
 *前面的const表示函数的返回值是const类型的，不能被修改
 *后面的const用来修饰这个函数Front,说明这个函数不会修改对象的成员变量
 */
 pushBack(T const& data);//在链表尾部添加结点
 popBack();//删除链表尾部的结点
 T& Back();//获取尾部结点元素的数据
 T const& Back()const;//获取尾部结点元素的数据，const List
 clear();//清空链表
 size_t Size();//获取链表的大小，也就是链表中结点个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

具体成员函数实现

//我们所有函数的定义都是在类外定义的
//所以，要加上类模板作用域List，和函数模板标识template
//给链表添加头结点
template<class T>
void List<T>::pushFront(T const& data){
    m_head = new node(NULL, data, m_head);
    //创建新节点的时候已经让新节点的next指针指向了原来的头结点
    //然后再让原来的头指针指向新的结点
    if(m_head->m_next)
        m_head->m_next->m_prev = m_head;
        //再利用头指针，让第二个结点前指针指向头结点
    else
        //如果这个链表头节点的next指向空，那说明，
        //这个链表只有一个结点，那应该让尾指针也指向头结点
        //链表唯一的这个结点即是头结点，也是尾结点
        m_tail = m_head;

}

//删除链表头结点
template<class T>
void List<T>::popFront(){
    if(isEmpty())
        return;//如果列表为空，则pop函数结束
    node* temp = m_head->m_next;//先备份第二个结点
    delete m_head;
    if(temp)
        temp->m_prev = NULL;
    else
        //表示链表就剩下一个头了
        m_tail = NULL;
    m_head = temp;

}

//链表判断是不是空链表
template<class T>
bool List<T>::isEmpty(){
    return m_head==NULL && m_tail==NULL;

}

//获取头结点数据（元素）
template<class T>
T& List<T>::Front(){
    if(isEmpty())
        throw underflow_error("null node");
    return m_head->m_data;
}

template<class T>
T const& List<T>::Front()const{
    //去常转换
    return const_cast<List*>(this)->Front();
}

 //给链表添加尾结点
template<class T>
void List<T>::pushBack(T const& data){
    //新创建的尾结点的pre指针指向原来的尾结点
    //新尾结点的尾指针指向NULL
    //然后，再将新尾结点的指针赋值给原来的尾指针
    //也就是说，让原来的尾指针指向新的尾结点
    m_tail = new node(m_tail, data, NULL);
    if(m_tail->m_prev)
        //现在原来的尾结点成了倒数第二个结点，
        //所以，要让倒数第二个结点的尾指针指向指向现在的尾结点
        m_tail->m_prev->m_next = m_tail;
    else
        m_head = m_tail;
}

//删除尾结点
template<class T>
void List<T>::popBack(){
    if(isEmpty())
        return;
    node* temp = m_tail->m_prev;
    delete m_tail;
    if(temp)
        temp->m_next = NULL;
    else
        m_head = m_tail;
    m_tail = temp;
}

//获取尾结点的数据
template<class T>
T& List<T>::Back(){
    if(isEmpty())
        throw underflow_error("null node");
    return m_tail->m_data;
}

template<class T>
T const&List<T>::Back()const{
    return const_cast<List*>(this)->Back();
}

//清空链表
template<class T>
void List<T>::Clear(){
    while(!isEmpty()){
        popFront();
    }
}

//获取链表大小，也就是结点的个数
template<class T>
size_t List<T>::Size(){
    size_t i = 0;
    for(node* temp = m_head; m_tail; temp=temp->m_next){++i;}
    return i;
}

template<class T>
List<T>::~List()
{
    Clear();
}

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

2 迭代器

2.1 迭代器的概念

![[迭代器原理.png]]

是什么？

迭代器就是一个类（迭代类）的对象。

可以干什么？

通过对这个迭代器对象进行操作，就可以对链表容器进行遍历，或者局部遍历，或者全局遍历。

注意，我们在STL容器中，对所有容器进行的遍历操作，都是使用迭代器。

使用迭代器的好处是什么？

普通遍历，需要我们对容器结点的内部构造很熟悉，比如有前指针，后指针等。
但是，使用迭代器，用户就可以不去关心链表容器的内部结构，直接使用迭代器对其进行遍历。

2.2 迭代类的分类（stl库的容器对应的迭代器的分类）

• **正向非常迭代类 iterator
• 正向常迭代类 const_iterator
• 反向非常迭代类 reverse_iterator
• **反向常迭代类 const_reverse_iterator

2.3 迭代器的实现

//迭代类:正向非常迭代类
//这个类还是List的嵌套类，卸载List的public中
class Iterator{
    public:
	    //Iterator的带参构造函数
        Iterator(node*start, node*cur, node*End):
            m_start(start), m_cur(cur), m_end(End){}
            
        //重载*操作运算符
        T& operator*(){
            if(m_cur == NULL)
                //如果当前指针为空，则告诉用户，当前cur没有指向结点
                throw underflow_error("null node");
            return m_cur->m_data;
        }

        //重载++操作运算符
        Iterator operator++(){
            if(m_cur == NULL)
                //实现循环迭代器
                m_cur = m_start;//为空指向开始指向
            else
                m_cur = m_cur->m_next;
            //调用++肯定是一个迭代器对象
            //return *this的意思就是返回这个迭代器对象本身
            //this是一个指向当前对象的指针
            //*this就指的是当前对象（解地址）
            return *this;
        }

        Iterator& operator--(){
            if(m_cur == NULL)
                //实现循环迭代
                m_cur = m_end;
            else
                m_cur = m_cur->m_prev;
            return *this;
        }
        //重载==运算符
        bool operator==(Iterator const& that)const{
            return m_start ==that.m_start & m_cur == that.m_end & m_end = that.m_end;
        }
        //重载!=运算符
        bool operator!=(Iterator const& that)const{
            //调用刚才重载的==运算符
            //在实现后面功能的时候，尽量使用前面已经定义好的功能
            return !(*this==that);
        }
    private:
	    friend class List;//在Iterator中，我们可能要使用List的私有成员变量，所以声明为friend
        node* m_start;//开始指向
        node* m_cur;//当前指向
        node* m_end;//终止指向
};

//Begin函数属于List的成员函数，List调用成员函数就会得到一个Iterator对象
//这个Iterator对象的当前指向为m_head,即链表的头结点
Iterator Begin(){
	return Iterator(m_head, m_head, m_tail);
}

//同样,End函数也属于List成员函数，List调用End会返回一个Iterator对象，
//这个Iterator对象的当前指向为NULL，
//所以，我们一般也把调用End对象返回的迭代器称为终止迭代器，
//因为，List的尾结点的next就指向NULL,
//所以，当迭代器的当前指向为NULL的时候，说明遍历也就结束了，到头了
Iterator End(){
	return Iterator(m_head, NULL, m_tail);
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

2.4 向双向链表中插入结点

向链表中插入结点为什么要放在迭代器这里来说明。
因为，要插入结点的位置就是当前迭代器所指向的位置。

//插入结点的参数有两个，第一个是在那个位置插入结点，第二个是插入结点的数据
void Insert(Iterator const& loc, T const& data){
	if(loc == End()){
		//如果所给定的位置是终止迭代器，即为NULL,
		//说明，要向List尾结点的后面插入结点
		pushBack();
	}else{
		//初始化带插入结点的时候，就完成了两件事
		//1.让待插入结点的m_prev指向loc的前一个结点
		//2.让带插入结点的m_next指向loc
		//所以，现在只需要让loc的前一个指针的next指向待插入结点
		//让loc的prev执行待插入结点
		node* temp = new node(loc.cur->m_prev, data, loc.m_cur);
		//node*temp是一个指向node的指针
		if(temp->m_prev)
		//若要插入结点的前一个结点不是NULL,则，让loc的前一个结点的尾指针指向待插入的结点
			temp->m_prev->m_next = temp;
		else 
			m_head = temp;//若没有，说明我们插入的是头结点
		temp->m_next->m_prev = temp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.5 删除指定的结点

void Erase(Iterator const& loc){
	if(loc == End())
		return;//loc当前指向为NULL,删除结束，这个loc位置没有要删除的结点
	node* temp = loc.m_cur;
	//先让一个指针指向loc的当前指向，当处理好m_cur前后结点的指向以后，就可以直接删除temp指针了,不能删除loc哈，因为loc使用const修饰的参数

	//判断是不是要删除头结点
	if(temp->m_prev)
		temp->m_prev->m_next = temp->next;
	else
		m_head = temp->next;

	//判断是不是要删除尾结点
	if(temp->m_next)
		temp->m_next->m_prev = temp->m_prev;
	else
		m_tail = temp->m_prev;

	delete temp;//最后删除temp指针
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3 查找功能

template<class IT, class T>
IT Find (IT const& a, IT const& b, T const& data) {
//IT参数接受迭代类型，a和b就是两个迭代器，Begin和End
    for (IT it=a; it!=b; ++it) {
        if (*it==data) {
            return it;//返回找到的那个节点的迭代器
        }
    }
    return b;
}
1
2
3
4
5
6
7
8
9
10

4 快速排序

快速排序规则：

• p和谁相同谁不能动
• p和谁交换数据，p就得和谁相同
• 当p,i,j都相同时候，意味着p,i,j对应的这个数据位置就确定了
• 递归进行

//采用<进行比较
//定义排序函数模板，本质上还是用的STL库中容器的迭代器实现
template<class IT>
void Sort(IT const& Begin, IT const& End){
    IT p = Begin;
    IT last = End;
    --last;//End本来指向tail结点的后一个结点NULL
    //现在--last就是让last指向链表的最后一个结点
    for (IT i = Begin, j = last; i !=j;) {
        while(i != p && *i < *p)
            ++i;
        if (i != p) {
            swap(*i, *p);
            p = i;
        }
        while(j!=p && *p<*j)
            --j;
        if (j!=p) {
            swap(*p, *j);
            p = j;
        }
    }

    //现在开始递归循环
    //什么情况下可以进行递归循环呢？
    //p的左边和右边都个子至少有两个结点
    //先检查左边
    IT it = Begin;
    ++it;
    if(p != Begin && p != it)
    //P没有指向第一个结点，也没有指向第二个结点
    //那么p肯定在第三个包括第三个结点以后了
        Sort(Begin, p);

    //再检查右边
    it = p;
    ++it;
    if(it != End && it != last)
    //it至少指向链表的倒数第二个结点
    //p至少指向链表的倒数第三个结点
        Sort(it, End);
}


//进阶版本：用【比较器】排序
//比较类，由用户来实现，而不是写容器的人
//有比较器版本的Sort没有限制用户的使用权限
//用户可以用比较器来自己选择升序还是降序
//告诉用户，你自己弄个比价器类，里面重载个()运算符
//返回<为升序，返回>为降序
template<class IT, class CMP>
void Sort(IT const& Begin, IT const& End, CMP cmp){
    IT p = Begin;
    IT last = End;
    --last;//End本来指向tail结点的后一个结点NULL
    //现在--last就是让last指向链表的最后一个结点
    for (IT i = Begin, j = last; i !=j;) {
        while(i != p && cmp(*i,*p)) //*i < *p)
        //类对象(),这种形式会触发小括号操作符
        //类(),这种形式才是构造函数，注意区分类和类对象
            ++i;
        if (i != p) {
            swap(*i, *p);
            p = i;
        }
        while(j!=p && cmp(*p, *j))
            --j;
        if (j!=p) {
            swap(*p, *j);
            p = j;
        }
    }
    //现在开始递归循环
    //什么情况下可以进行递归循环呢？
    //p的左边和右边都个子至少有两个结点
    //先检查左边
    IT it = Begin;
    ++it;
    if(p != Begin && p != it)
    //P没有指向第一个结点，也没有指向第二个结点
    //那么p肯定在第三个包括第三个结点以后了
        Sort(Begin, p, cmp);

    //再检查右边
    it = p;
    ++it;
    if(it != End && it != last)
    //it至少指向链表的倒数第二个结点
    //p至少指向链表的倒数第三个结点
        Sort(it, End, cmp);
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

但凡听到“XX器”就代表这是一个模板类对象