【STL源码剖析】总结笔记（5）：认识迭代器的好帮手--list

00 写在前面

说完vector，也了解了分配器（alloctor），接下来我们说说比较具有代表性的容器list。
【STL源码剖析】总结笔记（3）：vector初识
【STL源码剖析】总结笔记（4）：幕后功臣–分配器（allocator）

为什么说具有代表性呢，因为list的空间不再连续，对空间的使用也更加精准。

学习list也是帮助我们打开迭代器大门的第一步。

01 概述

list和vector是我们平时最常使用的容器。list就是链表，而且根据前置知识我们知道list是一个双向链表。

list的节点

假如让我们设计一个双向链表，我们肯定会先设计它的节点结构。在节点结构里包含向前的指针和向后的指针。

是的，在STL里也是这样的。

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

当然，这里的void写为_list_node可能更加合适，更符合我们的设计规范。

list的数据结构

list是一个环状双向链表，先上图：

为了符合“前闭后开”的要求，这里故意在尾端设置了一个虚节点。

而整个环形链表结构只需要一个指针就可以遍历了，也就是node。node就是上图中红色的部分，指向虚节点。

template <class T,class Alloc=alloc>
class list{
protected:
    typedef _list_node<T> list_node;
public:
    typdef list_node * link_type;
    
protected:
    link_type node;
}

同理，begin()和end()就可以通过node实现了。

iterator begin(){
    return (link_type)((*node).next);//注意begin()是存在的，而end()不存在，所以类型不同
}
iterator end(){return node;}

empty()，size()，front()（头节点内容），back()（尾节点内容）都比较好实现。

bool empty() const{
    return node->next==node;
}

size_type size() const {
    size_type result = 0;
    distance(begin(),end(),result);
    return result;
}

reference front(){return *begin();}
reference back(){return *(--end());}

02 list的iterator（迭代器）

list和vector不一样，由于空间不是连续的，所以不能使用简单的普通指针进行加加或者减减的操作。

list的iterator必须有能力找到前后的节点，并且完成各种递增、递减、取值操作。也可以说需要实现一种“智能的指针”。

透过list iterator的设计我们也能看到所有容器的迭代器是如何设计的。

template <class T,class Ref,class Ptr>
struct _list_iterator{
    typedef _list_iterator<T,T&,T*> iterator;
    typedef _list_iterator<T,Ref,Ptr> self;
    
    typedef bidirectional_iterator_tag iterator_category;//1
    typedef T value_type;//2
    typedef Ptr pointer;//3
    typedef Ref reference;//4
    typedef _list_node<T> * link_type;
    typedef size_t size_type;
    typedef ptrdiff_t defference_type;//5
    
    link_type node;
    
    ...
        
    reference operator*() const {return (*node).data;}
    
    pointer operator->() const {return&(operator*());}
    
    self& operator++(){
        node=(link_type)((*node).next);
        return *this;
    }
    
    self operator++(int){
        self tmp=*this;
        ++*this;
        return tmp;
    }
    
    
}

首先，所有容器的iterator都要有至少1-5这五个typedef。下面也要有各种操作符的重载实现。

这里挑几个典型的操作符作说明（比如和–道理是一样的，只以为例）

++操作

我们先来看神奇的操作。学过基础知识的我们都知道分为前置和后置，即先取值再做+1操作和先+1再取值。

在操作符重载里面如何区分这两种操作呢，有一个规定：重载中不带int参数的为前置++，带int参数的为后置++。但是这个int本身没有什么作用。

前置++

先来看前置++：

 self& operator++(){
        node=(link_type)((*node).next);
        return *this;
    }

解引用出node指向的区块中的next的值，再赋值给node。

前置++操作是直接返回计算后的结果，所以返回*this。

后置++

后置++要相对难一些，因为要先记录原值，执行操作再返回原值。

 self operator++(int){
        self tmp=*this;//1
        ++*this;//2
        return tmp;
    }

**这里需要特别注意的是不能按照固定思维来看一些操作，因为这些符号（，++）有可能已经被重载了。

1. 这句代码可能会被认为this中的是重载后的operator*（），但实际上因为=是拷贝构造，所以这里的*this被当作了拷贝构造的参数，就是对象本身。
2. 同理，第二句的this因为遇到++，已经被当作了operator++()的参数，不会唤起operator()
3. 
   

返回值类型

注意前置和后置还有一点区别，就是返回值类型。前置是self&，后置是self。

为什么要这么做呢？是因为在c中，不允许整数有后置两次的操作。

比如 i=5，可以i，但是不可以i。

所以在STL的设计中也要遵循这个规则，于是前置返回的是引用，也就是可以修改它的原值，而后置不可以进行两次操作，所以返回的是副本。

*与->

iterator还有一个很重要的操作就是取值（dereference）和成员存取（member access）

 reference operator*() const {return (*node).data;}
    
 pointer operator->() const {return&(operator*());}

取值操作就是取到节点中的data。

成员存取我们可以转换分析一下：

ite->method()
= *ite.method()
= &(*ite)->method()

所以可以得出以上实现。

03 list的元素操作

基础操作

在有了迭代器的基础之后，list的元素操作就简单很多了。

因为不同于vector需要在空间不足时进行配置，list的基本操作都是依靠指针的指向变换来完成的。

我们在学习链表时也学习过基本的增删，无非就是指针的切换。当然要注意这里的list是双向链表且有虚节点，需要处理好边界条件。

盘点一下list提供的常用操作，实现就不细说了。

push_front(x)//插入头节点
push_back(x)//插入尾节点,注意push操作的底层实现都是依靠insert()
earse(position)//移除所指位置的节点
pop_front()//移除头节点
pop_back()//移除尾节点
clear()//清除所有节点
remove(value)//将value之前的所有元素移除
unique()//移除相同的连续元素，只有连续且相同才会被移除，只剩一个

transfer()

这里需要单独说一下list里的一个很重要的操作：transfer()，将某连续范围的元素迁移到某个特定位置。

这个功能是其他复杂操作的基础，在实现上其实就是指针的移动。

先看图：

将[first,last)内的所有元素移动到position之前。

void transfer(iterator position,iterator,first,iterator last){
    if(position!=last){
        (*(link_type((*last.node).prev))).next=position.node;//1
        (*(link_type((*first.node).prev))).next=last.node;//2
        (*(link_type((*position.node).prev))).next=first.node;//3
        link_type tmp=link_type((*position.node).prev);//4
        (*position.node).prev=(*last.node).prev;//5
        (*last.node).prev=(*first.node).prev;//6
        (*first.node).prev=tmp;//7
    }
}

从图中可以体会到双向链表移动指针的精髓。

首先1，2，3步都将next指针修改为想要指向的地方，但是保留了prev指针，这样可以通过prev指针找到原来的值，不会丢失。

这时需要一个tmp指针，因为在后面继续修改prev指针后，position这个指针就会失效，所以需要tmp做暂时的保存。

最后的5，6，7步再将链表的prev补充完整。

对于两个链表和一个链表的两个区域都是可以做这样的操作的。

基于transfer()的其他操作

transfer()不是公开的接口，但list提供的其他接合操作的公开接口都是通过ransfer()实现的。

做个简单的盘点：

splice()//将某连续范围的元素从一个list移动到另一个（或同一个）list的某个定点

merge()//将另一个list合并到此list上，两个list都要递增排序

reverse()//反转list

sort()//排序，但不是STL中的sort()算法，采用快速排序实现

04 总结

从list出发可以很好的理解迭代器的实现，很多时候要在普通指针的基础上加工才可以实现看上去很简单的迭代器移动操作。

iterator的设计技巧会在下一篇中说明。

最后

以上就是虚拟乌龟为你收集整理的【STL源码剖析】总结笔记（5）：认识迭代器的好帮手--list的全部内容，希望文章能够帮你解决【STL源码剖析】总结笔记（5）：认识迭代器的好帮手--list所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。