一 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 内部的 T
reference 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 位置前面插入 T
void 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 的 node
link_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)
{
// 这里删除的是后一个 T
if(*first == *next) erase(next);
// 不相等让前一个 T first 等于 后一个不相等的 T next
else first = next;
// 删完了，让后一个 T 也就是 next，等于前一个 T 也就是 first
next = 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 的上一个 node
link_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个有序的 list
template<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)
{
// 标记 first2
iterator next = first2;
// 把单个 first2 放到 first1 的前面
transfer(first1,first2,++next);
// 更新 first2
first2 = 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 1
while(!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：
