C++(STL源码刨析/List)

一 List 核心字段和接口

1. 节点字段

template<class T>
struct __list_node
{typedef void* void_pointer;void_pointer prev;void_pointer next;T data;
}

由于 链表 不是连续的内存块，所以对每一个申请到的内存块要进行统一组织，也就是封装成一个类，添加前后指针来关联申请到的内存块，在由 List 统一管理起来。

2. List本身字段

template<class T.class Alloc=alloc>
class list
{protecred:// node 节点typedef __list_node<T> list_node;public:typedef list_node* link_type;ptotected:link_type node;// 这里没有按 T 来开辟空间，是按节点来开辟空间typedef simple_alloc<list_node,Alloc> list_node_allocator;    // 申请一个节点link_type get_node(){ return list_node_allocator::allocate(); }// 释放一个节点void put_node(link_type p){ list_node_allocator::deallocate(p); }// 申请并构造这个节点link_type create_node(const T& x){link_type p = get_node();construct(&p->data,x);        // 全局函数return p;    }// 析构并销毁这个节点void destroy_node(link_type p){destroy(&p->data);            // 全局函数put_node(p);}public:// 无参构造，初始化哨兵节点list(){ empty_initialize(); }protected:void empty_initialize(){node = get_node();node->next = node;node->prev = node;}
}    

list的无参构造表示没有节点，但要有个哨兵节点，因为list是双向带头循环链表，为了处理边界情况，所以有一个领头羊。

那么怎么访问/遍历/修改 List 中的节点，一个个的访问吗？下面来看看 List 的迭代器。

由于 List 不像vector那样有一段连续的空间，所以不能直接用裸指针作为 List 的迭代器，但可以为这个指针封装一层，让他模拟指针的行为即可。

template <class T,class Ref,class Ptr>
struct __list_iterator
{// 非 const 迭代器，list操作时使用typedef __list_iterator<T,T&,T*> iterator;// const/非 const迭代器，迭代器内部使用typedef __list_iterator<T,Ref,Ptr> self;// 表示该迭代器是双向迭代器，前章vector的迭代器是随机访问迭代器typedef bidirectional_iterator_tag iterator_category;// 迭代器管理的节点内部 T 对象typedef T value_type;// 迭代器管理的节点内部 T 指针typedef Ptr pointer;// 迭代器管理的节点内部 T 引用typedef Ref reference;// 迭代器管理的节点指针typedef __list_node<T>* link_type;// 无符号整型typedef size_t size_type;// 有符号整型typedef ptrdiff_t difference_type;// node 指针link_type node;// 指针构造__list_iterator(link_type x):node(x){}// 无参构造__list_iterator(){}// 迭代器的拷贝构造，这里是浅拷贝__list_iterator(const iterator& x):node(x.node){}// 迭代器判相等bool operator==(const self& x)const {return node == x.node;}// 迭代器判不相等bool operator!=(const self& x)const {return node != x.node;}// 迭代器模拟指针访问 node 内部的 Treference operator*()const {return (*node).data;}    // 迭代器模拟指针访问 node 内部的 T 的地址reference operator->()const {return &(operator*());}// 前置++ ，返回下一个迭代器的引用self& operator++(){// 先访问 node 内部的 next，在把 next 强转成 node*，next 是 void* 类型node = (link_type)(*node).next;return *this;}//后置++，返回当前迭代器的拷贝self operator++(int){// 当前迭代器拷贝给临时对象self tmp = *this;// this 是指针，解引用成迭代器对象，然后进行 ++++*this;// 返回临时对象，值返回有拷贝return tmp;}// 下面2个--，和上面2个++一样 Self& operator--(){self tmp = *this;return *this}self operator--(int){self tmp = *this;--*this;return tmp;}};

list 内部对管理的 node 进行操作的函数：

template <class T,class Alloc = alloc>
class list
{public:// 返回第一个节点，并用这个节点构造一个迭代器iterator begin() { return (link_type)((*node).next); }// 返回最后一个节点，原理同上iterator end() { return node; }// 判空，和哨兵节点比较bool empty() const { return node->next == node; }// 这里调用了distance，针对迭代器类型进行计数，比如vector(end() - begin())，List就逐个遍历了size_type size() const{size_type result = 0;distance(begin(),end(),result);return result;}// 返回第一个迭代器内部的 T 对象的引用reference front() { return *begin(); }// 返回最后一个迭代器内部 T 对象的引用reference back() { return *(--end()); }// 头插void push_front(const T& x) { insert(begin(),x); }// 尾插void push_back(const T& x) { insert(end(),x); }// 头删void pop_front() { erase(begin()); }// 尾删，这里 end() 是哨兵节点，所以要--到前一个节点，也就是实际的最后一个节点// tmp 是浅拷贝的 end()void pop_back() {iterator tmp = end();erase(--tmp);}// 在 pos 位置前面插入 Tvoid insert(iterator position,const T& x){// 构造 node 节点link_type tmp = create_node(x);// 让这个新节点 next 指向 pos// 下面2个操作不需要强转，因为只需要改变指针的指向，并不访问指针内容tmp->next = position.node;// 让这个新节点 prev 指向 pos 的上一个节点(prev)tmp->prev = position.node->prev;// 这里需要访问指针的内容，让这样内容的 next 指向 tmp，所以要强转// 让 pos 的 prev 的 next 指向 tmp(link_type(position.node->prev))->next = tmp;// 让 pos 的 prev 指向 tmp，这里也不需要强转，不访问 prev，只是改变指向position.node->prev = tmp;return tmp;}// 删除指定迭代器，并返回迭代器的下一个迭代器iterator erase(iterator position){// 该迭代器的下一个迭代器link_type next_node = link_type(position.node->next);// 该迭代器的上一个迭代器link_type prev_node = link_type(position.node->prev);// 让该迭代器的上一个迭代器指向该迭代器的下一个迭代器prev_node->next = next_node;// 让该迭代器的下一个迭代器指向该迭代器的上一个迭代器next_node->prev = prev_node;// 释放该迭代器destroy_node(position.node);// 返回该迭代器的下一个迭代器return iterator(next_node);}// 清空节点，保留哨兵节点template<class T,class Alloc>void list<T,Alloc>::clear(){// cur = 哨兵节点的下一个link_type cur = (link_type)node->next;while(cur != node){// tmp 指向 cur 的 nodelink_type tmp = cur;// cur 访问 node 的 next，在强转 next 为 node*，这里 next 是 void* 类型cur = (link_type)cur->next;// 析构并释放destroy_node(tmp);}// 这里删除全部节点，没删除一个没有处理相互之间的链接关系，哨兵节点的指针是不可预期的// 所以要重置成初始状态node->next = node;node->prev = node;}// 删除所有的 T 对象template<class T,class Alloc>void list<T,Alloc>::remove(const T& value){// 取 List 的头iterator first = begin();// 取哨兵节点iterator last = end();while(first != last){// 这个地方删除用到了迭代器，不像 clear 直接操作 node iterator next = first;++next;相等就删除，并调整链接前后关系if(*first == value)erase(first);first = next;}}// 删除连续且相同的 T，不连续相同不删除template<class T,class Alloc>void list<T,Alloc>::unique(){// 和 remove 一样iterator first = begin();iterator last = end();// 空链表直接返回if(first == last) return;iterator next = first;while(++next != last){// 这里删除的是后一个 Tif(*first == *next) erase(next);// 不相等让前一个 T first 等于 后一个不相等的 T nextelse first = next;// 删完了，让后一个 T 也就是 next，等于前一个 T 也就是 firstnext = first;}}// 将 first ~ last 这个区间的迭代器移动到 pos 的前面，不包含 last// 该函数只能用于同一个 list 内部的迭代器进行操作，不同的list不行，即使模板参数一样void transfer(iterator position,iterator first,iterator last){// 尾和 pos 先等不需要移动，因为 first ~ last 已经在 pos 的前面了if(position != last){// 让 last 的上一个 node 的 next 指向 pos(*(link_type((*last.node).prev))).next = position.node;// 让 first 的上一个 node 的 next 指向 last(*(link_type((*first.node).prev))).next = last.node;// 让 pos 的上一个的 next 指向 first(*(link_type((*position.node).prev))).next = first.node;// tmp 指向 pos 的上一个 nodelink_type tmp = link_type((*position.node).prev);// 让 pos 的 prev 等于 last 的上一个 node(*position.node).prev = (*last.node).prev;// 让 last 的上prev 等于 first 的上一个 node(*last.node).prev = (*first.node).prev;// 让 first 的 prev 指向 tmp(*first.node).prev = tmp;// 让 5,6,7 插入到4的前面pos = 4,first = 5,last = 8[1,2,3,4,5,6,7,8] -> [1,2,3,5,6,7,4,8]第一步：让 last  的上一个 node      即7,指向4第二步：让 first 的上一个 node      即4，指向8第三步：让 pos   的上一个 node      即3，指向5第四步：让 tmp = pos 的上一个       即3第五步：让 pos   的 prev           即3，指向7第六步：让 last  的 prev           即7，指向3第七步：让 first 的 prev           即3，指向 tmp 4}}// STL源码刨析这本书里的 splice 都只能作用与同一个 list，不能跨 list// 主要是因为都调用了 transfer 接口，这个接口只是针对单个 list// 把一个 list 的所有节点挪到 该迭代器的前面void splice(iterator position,list&,iterator i){// 不为空直接调用if(!x.empty()) transfer(position,x.begin(),x.end());}// 把一个迭代器挪到 pos 前面void splice(iterator position,list&,iterator i){iterator j = i;++j;if(position ==i || position == j) return;transfer(position,i,j);}// 把一个迭代器区间挪到 pos 前面void splice(iterator position,list&,iterator first,iterator last){if(first != last) transfer(position,first,last);}// 合并2个有序的 listtemplate<class T,class Alloc>void merage(list<T,ALloc>& x){// 标记2个list的头和尾iterator first1 = begin();iterator last1 = end();iterator first2 = x.begin();iterator last2 = x.end();// 有一个为空则结束循环while(first1 != last1 && first2 != last2){// 如果第二个list的当前迭代器小于第一个list的当前迭代器if(*first2 < *first1){// 标记 first2iterator next = first2;// 把单个 first2 放到 first1 的前面transfer(first1,first2,++next);// 更新 first2first2 = next;}else ++first1;}// 如果 first2 的迭代器没有到结尾，则把剩余的元素挪到 first1 的前面// list1：1，2，3，4 list2：0，5，6，7，8// 上面的 while 循环把 0 挪到 1 的前面：list1 0，1，2，3，4// 然后 list1 的迭代器到结尾，4的后面// 此时 list2 的迭代器指向 5，在把 5 到 last2，也就是 list2 的结尾，5，6，7，8 挪到// last1(4 的后面),在用 transfer 函数把 5，6，7，8 挪到 last的前面，即 4 的后面if(first2 != last2) transfer(last1,first2,last2);}// 反转 list 所有节点void reverse(){// 如果为空或者只有一个节点，直接返回if(node->next == node || (link_type)(node->next)->next == node) return;// 保存下一个节点iterator first = begin();++first;// 下一个节点不等于 end()while(first != end()){// 保存下一个节点iterator old = frist;// 让 first + 到后面一个节点++first;// 在让 old ~ first 这个区间的节点移到 begin() 的前面// 其实只是移动一个节点,这里 first 是 old 的后面的节点，是开区间，不包括 first// 只是单纯的把 old 移到 begin() 前面transfer(begin(),old,first);}}void sort(){// 如果为空或者只有一个节点，直接返回if(node->next == node || (link_type)(node->next)->next == node) return;// 这个对象为后面交换合并做铺垫list<T,Alloc> carry;// 定义 64 个桶，每个桶是 2^n 次方个元素list<T,Alloc> counter[64];// 桶的最高层数int fill = 0;// 4 3 2 1while(!empty()){// 先取当前要排序对象的 第一个节点carry.splice(carry.begin(),*this,begin());// 该变量表示要合并的层数int i = 0;// 循环和合并while(i < fill && !counter[i].empty()){counter[i].merage(carry);carry.swap(counter[i++]);}// 合并之后的结果放到对应的桶里carry.swap(count[i]);// 如果合并的层数达到最高的层数,则让最高的层数++if(i == fill) ++fill;}// 从 1 开始 合并前面的 桶for(int i = i;i < fill;++i){counter[i].merge(counter[i-1]);}// 最后在交换回去swap(counter[fill - 1]);}
}

transfer：