STL源码学习（4）- list

文章首发于：My Blog 欢迎大佬们前来逛逛

1. list的节点

众所周知list是链表，因此它一定需要一个节点类型，以下是SGI STL list的节点类型：

//list的节点类型
template <typename T>
struct listNode
{
	listNode<T>* next;
	listNode<T>* prev;
	T	data;
};

2. list的迭代器

由于list不像vector一样所有的节点都存储在一块连续的空间中，相反list的节点存储是不连续的。

因此list的迭代器应该具有正确的递增，递减，取值，成员取用的操作。

1. 递增：正确的找到其next的地址
2. 递减：正确的找到其prev的地址
3. 取值：当前节点的取值
4. 成员取用：当前节点的成员

因此list的迭代器必须具有双向移动的功能，他必须是一个 Bidirectional Iterator，即双向迭代器。

list在插入与删除的时候，原迭代器仍然有效，只有被删除或者执行操作的迭代器才有可能失效；而vector由于需要重新配置空间，因此原迭代器全部无效

实现过程：

1. 定义迭代器基本数据类型：value_type，differece_type，pointer，reference，iterator_category等，同时定义节点类型，并且创建一个根节点。

2. list的构造函数，其中注意const iterator&参数的构造函数，我们可能需要执行这样的操作：

   list<int> ls;
   list<int>::iterator it(ls.begin());

   其中it的调用的就是list_iterator的此构造函数。

3. list的迭代器的基本操作：

   1. == 与 != 的操作
   2. * 运算获取的是某个迭代器的data值
   3. -> 运算获取的是某个迭代器的data值的地址，这个不怎么常用。

   ls.begin().operator->()

   1. ++操作：前置++，直接相加，返回引用；后置++，返回的是一个临时的，因此不能是引用
   2. —操作：前置—，直接相减，返回引用；后置—，返回的是一个临时的，因此不能是引用

//list的迭代器类型
template <typename T,typename Ref,typename Ptr>
class list_iterator{
public:
	using iterator = list_iterator<T, T&, T*>;//iterator作为对外接口
	using self = list_iterator<T, Ref, Ptr>;//用于返回值

	using value_type = T;
	using difference_type = ptrdiff_t;
	using pointer = Ptr;
	using reference = Ref;
	using iterator_category = Bibirectional_Iterator_tag;//双向
	using size_type = size_t;
	using link_type = listNode<T>*;	
private:
	link_type node; //list节点
public://构造函数
	list_iterator() {}
	list_iterator(link_type x) :node(x) {}
	list_iterator(const iterator& x) :node(x.node) {}
	~list_iterator() {}
public:
	bool operator==(const self& lhs) {
		return lhs.node == node;
	}
	bool operator!=(const self& lhs) {
		return lhs.node != node;
	}
	//*运算，获取节点的值
	reference operator*() {
		return node->data;
	}
	//->运算，获取节点的值的地址
	pointer operator->()const {
		return &(node->data);
	}
	//前置++
	self& operator++() {
		node = node->next;//前进到下一个
		return *this;
	}
	//后置++
	self operator++(int) {
		auto temp = *this;
		++* this;
		//返回一个临时temp，因此不能使用引用
		return temp;
	}
	//前置--
	self& operator--() {
		node = node->prev;
		return *this;
	}
	//后置--
	self operator--(int) {
		auto temp = *this;
		--* this;
		return temp;
	}
};

3. list的数据结构

list是一个双向循环链表，所以它只需要一个指针，便可以遍历整个链表并且回到原来的位置。

为此我们可以设计一个头节点为list的起始节点，这个头节点不含任何数据，它只是作为一个空的节点而已，方便我们进行遍历与基本判断操作：

1. 当我们进行begin()的时候：直接返回 head->next即可；同理我们的 end()表示的才是 head

2. 调用size() 统计节点的数量，其实就是两个迭代器之间的 距离，这个函数可以自己遍历，也可以调用我们之前完成的distance函数，这个函数的作用就是 计算两个迭代器之间的距离，然后根据迭代器的 category会做一些优化

3. front表示返回头元素节点数据，因此对 begin()进行解引用操作即可。在begin操作结束后，返回的list的迭代器类型（使用 iterator做别名），然后我们已经在list的迭代器的内部定义了解引用的操作，因此会返回该节点（就是头节点的值）；end同理，不过要注意end表示一个空节点，end的上一个才是真正的尾元素

//list
template <typename T,typename Alloc=alloc>
class list
{
protected:
	using list_node =  listNode<T>;
	using data_allocator = simplae_alloc<list_node, Alloc>;//空间配置器
public:
	using link_type = list_node;

    //list的相应型别
	using value_type = Alloc;
	using reference = value_type&;
	using const_reference = const value_type&;
	using pointer = value_type*;
	using const_pointer = const value_type*;
	using difference_type = ptrdiff_t;
	using size_type = size_t;
public:
    //iterator表示的就是list的迭代器
	using iterator = list_iterator<value_type, reference, pointer>;
    //const 迭代器
	using const_iterator = list_iterator<value_type, const_reference, const_pointer>;
protected:
	list_node head;//私有属性：节点的头节点
public:
	inline iterator begin() {
		return head->next;
	}
	inline const_iterator cbegin()const {
		return head->next;
	}
	inline iterator end() {
		return head;//头节点不存储任何数据，它就是end节点
	}
	inline const_iterator cend()const {
		return head;
	}
	inline bool empty() {
		return head == head->next;//自己和自己连接，则list为空
	}
	inline size_type size() {
		return (size_type)distance(begin(), end());//计算两个迭代器之间的距离
	}
	//引用方式返回
	inline reference front() {
		return *begin();//head->next->data
	}
	inline reference back() {
		return *(--end());//list没有 - + 重载
	}
};

---

4. list的构造元素操作

4.1 list的空间配置操作

using data_allocator = simplae_alloc<list_node, Alloc>;//空间配置器

list使用第二级空间配置器作为其空间配置器。

list是由一个个的节点连接的，因此我们需要有一个函数来创建一个节点的空间：

link_type create_node_space(){
		return (link_type)data_allocator::allocate();
	}

对应的销毁某个节点的空间：

void destroy_node_space(link_type pDel) {
		data_allocator::deallocate(pDel);
	}

然后才是创建一个节点对象的行为（创建空间与构造对象）：

如果中途构造对象的失败了，则rallback，销毁这个节点的空间

link_type create_node(const value_type& val) {
		//commit or rallback规则
		link_type* pNew = create_node_space();//分配空间
		_TRY{
			construct(&pNew->data, val);//构造对象
		}
		_CATCH(...){
			destroy_node_space(pNew);//否则销毁空间
		}
		return pNew;
	}

然后是销毁这个节点对象（析构对象与销毁空间）：

void destroy_node(link_type pDel) {
		::destroy(&pDel->data);
		destroy_node_space(pDel);
	}

4.2 list的空构造函数

list 有很多构造函数，其中一个可以让我们配置一个空的节点对象：

注意是配置而不是创建，理解其不同：

list() {
		empty_initialized();
	}
//头节点的配置：创建一个空的list
	void empty_initialized() {
		head = create_node_space();
		head->next = head;
		head->prev = head;
	}

相当于完成了list的初始化，只有一个空节点，自己指向自己。

4.3 list的push_back

list的尾插其实就是完成了往某个位置插入一个元素的操作，只不过这个位置是 在 end的地方

因此我们首先写一个往某个位置创建节点并且插入的操作即可。

//position位置创建并且插入一个节点，返回插入完成后的新的插入位置
	link_type _insert(iterator position, const value_type& value) {
		link_type pNew = create_node(value);//创建节点
		//中间插入
		pNew->next = position.node;
		pNew->prev = position.node->prev;
		position.node->prev->next = pNew;
		position.node->prev = pNew;
		return pNew;//
	}
void push_back(const value_type& value) {
		//其实就是在end的位置插入
		_insert(end(), value);
	}

• end()不是返回 head头节点吗， 为什么是尾插？

list是循环链表，因此第一个也就是最后一个，只要在 head 的前面就是尾部节点，head节点开始才是头部。

5. list的基本元素操作

5.1 其他插入与删除

头插法：push_front 与 push_back类似，从begin()处插入即可：

//头插法
void push_front(const value_type& value) {
    _insert(begin(), value);
}

erase删除某个位置的节点：

直接找到其前驱节点与后继节点跳过pDel节点就可以。

//删除position处的节点，返回删除后的当前位置的节点
iterator erase(iterator position) {
    link_type pDel = position.node;
    link_type pDelNext = pDel->next;
    link_type pDelPrev = pDel->prev;
    pDelPrev->next = pDelNext;
    pDelNext->prev = pDelPrev;
    destroy_node(pDel);//销毁pDel节点
    return pDelNext;
}

pop_back与pop_front函数，利用erase，非常简单：

//删除头节点
void pop_front() {
    erase(begin());
}
//删除尾节点
void pop_back() {
    erase(--end());
}

清空链表：clear

//清空链表
void clear() {
    link_type cur = begin().node, temp = nullptr;
    link_type end = head;//尾节点
    while (cur != end) {
        temp = cur;
        cur = cur->next;
        destroy_node(temp);
    }
    //恢复空list状态
    cur->next = cur;
    cur->prev = cur;
}

---

5.2 remove

remove的作用是移除所有等于val的值的节点：

//删除所有值为value的元素
void remove(const value_type& value) {
    iterator cur = begin(), temp = nullptr;
    while (cur != end()) {
        temp = cur.node->next;
        if (cur.node->data == value) {
            erase(cur);
        }
        cur = temp;
    }
}

5.3 unique

unique的作用是移除所有连续且相等data的元素节点，只留下一个。

过程：next负责前进，first负责保留每个元素的第一个，last表示尾

1. 每次next移动到下一个位置，first此时在next的上一个位置，则比较这两个位置的值是否一样
2. 如果一样，则需要保留first，erase掉next，所以直接erase(next)，然后还需要检查后面是否还有一样的元素，因此next=first，回来继续往后++，重复上面的操作，每次只删除 next 的位置，而不会删除first

//移除连续且相同元素的节点，只剩下一个
void unique() {
    iterator first = begin(), last = end();
    iterator next = first;
    while (++next != last) {
        //first始终指向某个元素的第一个位置
        //变动删除next达到只剩下一个first
        if (*first == *next) {
            erase(next);
        }
        else {
            first = next;//first往后移动
        }
        next = first;
    }
}

5.4 transfrom*

transfrom是一个内部函数，用于将 [first，last)的全部节点转移到position之前：

其实就是几个指针的连接

//将[first,last) 的全部元素移动到 position之前
void transform(iterator first, iterator last, iterator position) {
    //[first,end]
    if (position != last) {
        iterator end = last.node->prev;//需要移动的最后一个元素
        iterator pos_prev = position.node->prev;
        iterator first_prev = first.node->prev;

        //next连接
        end.node->next = position.node;
        first_prev.node->next = last.node;
        pos_prev.node->next = first.node;

        //prev连接
        position.node->prev = last.node->prev;
        last.node->prev = first.node->prev;
        first.node->prev = pos_prev.node;
    }
}

5.5 splice

基于transfrom我们便可以写出splice，此函数的功能是 将一个范围的迭代器所指的节点连接到position处：

//将ls接在position之前，ls必须不同于*this
void splice(iterator position, list& ls) {
    if (!ls.empty()) {
        transform(ls.begin(), ls.end(), position);
    }
}
//将某一个迭代器接在position之前,position和it属于同一个list
void splice(iterator position,iterator it) {
    iterator it_ = it;
    ++it_;	//last
    if (it == position || it_ == position) {
        return;
    }
    transform(it, it_, position);
}
//将 [first,last)所有元素接在position之前
void splice(iterator position, iterator first,iterator last) {
    if (first != last) {
        transform(first, last, position);
    }
}

注意：由于在transform中来自不同list的迭代器是把他们连接到新的position，而不是 new出一块内存，因此原始的移动的 [first，last)中的节点会消失，我们通常使用 splice来移动节点，而不是拷贝

ls.splice(cur, temp); //将整个temp的list都移动到cur的位置，因此temp 会消失！

5.6 merge

将某个链表合并到 this中，两个链表必须是有序的，*二路归并：

//将ls的list合并到*this中，ls会消失，两个list必须有序！
void merge(list& ls) {
    iterator first1 = begin();
    iterator first2 = ls.begin();
    iterator end1 = end();
    iterator end2 = ls.end();
    //合并到 first
    while (first1 != end1 && first2 != end2) {
        if (*first1 > *first2) {
            iterator temp = first2;
            transform(first2, ++temp, first1);
            first2 = temp;//移动到下一个
        }
        else {
            ++first1;
        }
    }
    //待合并的ls还有，则全部放后面
    if (first2 != end2) {
        transform(first2, end2, end1);
    }
}

5.7 reverse

翻转整个链表：把每一个元素直接移动到begin()的前面即可。

//翻转链表
void reverse() {
    //如果NULL或者只有1个，则不执行
    if (head->next == head || head->next->next == head) {
        return;
    }
    iterator first = begin(),last=end();
    ++first;//跳过head
    while (first != last) {
        auto temp = first;
        transform(temp,++first, begin());
    }
}

5.8 Sort*

//排序
	void sort() {
		if (head->next == head || head->next->next == head) return;
		list<T, Alloc> carry;//每一归并层之间合并的 “中转站”
		list<T, Alloc> counter[64]; // counter[i]表示第i层《归并层》
		int fill = 0;
		while (!empty()) {//一直输入元素
			carry.splice(carry.begin(), *this, begin());//每次carry首先获取新插入的元素
			int i = 0;
			/*
			每一层从 0->i 归并层进行逐一合并
			*/
			while (i < fill && !counter[i].empty()) {
				counter[i].merge(carry);		//首先把carry 合并到 counter[i]层
				carry.swap(counter[i++]);	//交由carry临时存储此层归并后的结果
			}
			carry.swap(counter[i]); //将当前处理的结果给到 counnter[i] 层
			if (i == fill) {	//归并层扩容
				++fill;
			}
		}
		for (int i = 1; i < fill; ++i) {
			counter[i].merge(counter[i - 1]); //层层归并
		}
		swap(counter[fill - 1]);//最后一层就是答案
	}

原数据：14 13 8 7 6 5 2 1 0

第一次循环	counter[0]	counter[1]	counter[2]	counter[3]
14	14
13		13,14
8	8	13,14
7			7,8,13,14
6	6		7,8,13,14
5		5,6	7,8,13,14
2	2	5,6	7,8,13,14
1				1,2,5,6,7,8,13,14
0	0			1,2,5,6,7,8,13,14

最终再归并起来： 0,1,2,5,6,7,8,13,14

有几个关键函数：

1. splice：把某个迭代器移到position的位置处。
2. merge：合并到*this成为一个有序非递减链表
3. swap：交换两个list容器的所有节点值。

排序过程如下：

1. 首先传入 14：splice把14插入到carry，此时fill为0，不进入内层循环。swap把count和counter[0]容器交换，此时 counter[0]：14；carry是空的，fill 递增为 1
2. 传入13：splice把13插入到carry中，此时fill为1，并且counter[0]不为空，进入内层循环，首先couter[0]与carry合并，合并后结果放到counter[0]中，carry变为空。然后把counter[0]与carry交换，之后counter[0]为空，carry：13，14。跳出循环后counter[1]与carry交换，counter[1]：13，14，carry变为空。
3. ….
4. 一直到传入0：splice把0插入到carry中，此时fill为4，由于counter[0]为空，因此不会进入内层循环。counter[0] 与carry交换，counter[0]：0，carry为空。
5. 然后 this的empty触发，跳出大循环，从 i=1开始一直到fill-1 *闭区间：
   1. counter[1]与 counter[0] 合并，结果存入counter[1]
   2. counter[2]与 counter[1] 合并，结果存入counter[2]
   3. counter[3]与 counter[2] 合并，结果存入counter[3]
6. 最后counter[fill-1] 为counter[3]里面存储的节点的值，因此结果为0，1，2，5，6，7，8，13，14

---

综上：

• 可以看出这基本是一个归并排序，并且这还是个非递归版本的归并排序。

• list的sort排序利用carry存储每次新插入的值或者当作每次counter[i]与counter[i-1]合并的时候的中转站

• counter数组存储每一层归并的排序结果，最后所有的 counter[0] 到counter [fill-1]一起自底向上一路归并过来，最后的 counter[fill-1]存储的就是归并后的整个数组的sort排序结果

• 按层次归并，层层合并，最后一起合并，这就是list的sort排序思想。

• counter的 数组下标表示 counter[0] 这一层只能容纳一个元素；counter[1]可以容纳两个元素；counter[2]可以容纳四个元素；counter[3]可以容纳八个元素；因此counter[i]可以容纳 2^i 个元素。