前言

上一节我们简单叙述了一下list的概念,知道其底层是一个带头结点的双向循环链表,并且介绍了其使用方法,**但是!**知其然未必知其所以然,我们不但应该知其怎么使用,还应该尝试怎么简单实现.

因此,此篇文章,博主将要从list的各个方向进行底层简单实现.内容包括: 两种构造函数,数据头尾删插,迭代器的实现等;

---

list的结构搭建

template <class T>     //  结点创建
struct __list_node
{
    __list_node* _next;
    __list_node* _prev;
    T _val;
    __list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}
};

template <class T>   // list 结构搭建
class list
{
public:
    typedef __list_node<T> node; //记得要有<T>

private:
	node* _head;    
};

---

两种构造函数

博主这里说的两种构建函数分别是 默认构建函数 和 迭代器区间构建函数.

---

① 默认构建函数

博主在前面章节讲解c++类和对象时候,想必大家已经知道默认构建怎么回事了,博主这里就不再赘述了.便直接开始实现吧.

list()
{
	_head = new node;  // 给头结点开辟一块空间.
    _head->_next = _head;
    _head->_prev = _head;
}

---

② 迭代器区间构建函数

在前面的string和vector章节,博主已经给大家演示了其使用,但是怎么实现呢?

template <class InputIterator, class OutputIterator>
list(InputIterator input,OutputIterator output)
{
    //注意哦~,不可以写list(),误认为这是函数调用了哦 因为list本身就是个类,这样写是一个匿名对象
    _head = new node;  // 给头结点开辟一块空间.
    _head->_next = _head;
    _head->_prev = _head;
    while(input != output)
    {
    	push_back(*input);     //这个函数是用来实现尾插数据的,博主在下面进行讲解
        input++;
    }
}

---

拷贝构造函数

对于拷贝构造,我们便可以直接复用push_back();

list(const list<T>& lt)
{
    _head = new Node;           //  必须先开个头结点空间哦~~,因为这是拷贝构造,不是赋值
    _head->_next = _head;
    _head->_prev = _head;
    for (const auto& e : lt)
    {
        push_back(e);    //这个函数后面会实现
    }
}

---

赋值重载

list<T>& operator=(const list<T> lt)  //  注意哦,这里的参数故意没有使用 引用.这样lt就是通过拷贝构造获取了值
{
    swap(_head, lt._head);   //然后交换两个链表的头结点
    return *this;
}

---

数据的头尾删插

对于头尾删插来说,主要有四个,分别是push_back(),pop_back(),push_front(),pop_front(),现在博主便大致的实现一下

---

① 尾插push_back()

在学习双链表章节,还记得数据是怎样连接的吗?

• 给数据新建一个结点
• 保存尾结点
• 尾结点和新建节点连接
• 新建节点和头结点连接

void push_back(const T& val)
{
    node* tmp = new node(val);  //给新数据新建结点
    node* tail = _head->_prev;   //保存尾结点
    tail->_next = tmp;
    tmp->_prev = tail;      //尾结点和新结点连接
    _head->_prev = tmp;
    tmp->_next = _head;    //头结点和新数据连接
}

测试结果:

---

② 尾删pop_back()

同理,还记得尾结点的删除的步骤吗?

• 保存尾结点的前一个结点
• 释放尾结点
• 头结点和保存的结点连接

void pop_back()
{
    assert(_head != _head->_next);   //如果数据为空,不可删除
    
    node* oldtail = _head->_prev;      //提取旧尾巴结点
    node* newtail = oldtail->_prev;    //保存旧尾巴结点的前一个结点
    delete oldtail;
    oldtail = nullptr;
    _head->_prev = newtail;
    newtail->_next = _head;
    
}

测试:

---

③ 头插push_front()

是否又还记得头插的步骤呢?

• 给新数据新建一个结点
• 保存头结点下一个结点
• 头结点和新数据结点连接
• 新结点和保存结点连接

void push_front(const T& val)
{
    node* tmp = new node(val);     //给新数据新建一个结点
	node* next = _head->_next;     //保存头结点下一个结点
     
    _head->_next = tmp; 
    tmp->_prev = _head;            //头结点和新数据结点连接
    
    tmp->_next = next;
    next->_prev = tmp;             //新结点和保存结点连接
}

测试结果:

---

④ 头删pop_front()

是否又还记得头删的步骤呢?

• 保存头结点下两个结点
• 释放头结点下一个结点
• 头结点和保存结点连接

void pop_front()
{
    assert(_head != _head->_next);   //如果数据为空,不可删除
    node* dnext = _head->_next->_next;
    delete _head->_next;
    _head->_next = dnext;
    dnext->_prev = _head;
}

测试结果:

---

---

迭代器的实现

不同于前面两节所讲,博主此前一直强调目前阶段可以把迭代器当做指针使用,那是因为指针天然支持*,+,-,++,--,<,>等操作,而迭代器也是这样使用的,和指针达到的效果相同.但是今天博主就会强调了,这里便不可以将迭代器当做指针了,因为我们要实现的是list的迭代器,而list是一个带头的双向循环链表,如果我们对结点指针进行加减,这是毫无意义的,因为达不到使用*访问元素的效果.

那么既然不能再把成迭代器当成指针,又如何实现呢? 答案是对结点指针进行封装,然后重载操作符.

现在我们看看迭代需要实现哪些操作:

• ++ 代表走向数据的下一个位置,博主这里只实现前置++
• – 代表走向数据的上一个位置,博主这里只实现前置–
• ***** 代表获取该迭代器位置的元素
• != 判断两个迭代器的位置是否不一样
• == 判断两个迭代器的位置是否一样

现在既然知道了需求,就可以开始实现了

template<class T>
    struct __list_iterator
    {
        typedef __list_iterator<T> iterator;  //迭代器
        typedef __list_node<T> node;          //链表结点,上面已经定义过
        node* _node;

        __list_iterator(node* pnode):_node(pnode) {}

        T& operator*()        //迭代器使用*的意思是 获取结点值,所以就直接解引用_node,然后返回
        {
            return _node->_val;
        }

        iterator& operator++()       //++的意思就是迭代器向后移动一个位置,但是移动后还是迭代器,所以返回值仍然是iterator
        {
            _node = _node->_next;
            return *this;
        }

        iterator& operator--()       //--的意思就是迭代器向前移动一个位置,但是移动后还是迭代器,所以返回值仍然是iterator
        {
            _node = _node->_prev;
            return *this;
        }

        bool operator!=(const iterator & target) const   //判断迭代器是否相等,就是判断位置是否相等,即判断_node
        {
            return _node != target._node;
        }

        bool operator==(const iterator & target) const  //判断迭代器是否相等,就是判断位置是否相等,即判断_node
        {
            return _node == target._node;
        }
    };

---

到此,好像差不多都实现了功能,但真的是这样吗?仔细一看,我们还忽略了常迭代器(代表结点值不可以修改),那怎么办呢?按照之前实现string和vector第一想到的思路可能就是再重新定义一个迭代器,那这个思路是否有错呢?答案是无错,但还有一个更加简单的方法,那就是给__list_iterator多加一个参数,如下定义:

template <class T,class Ref>
    class __list_iterator
    {};

因此我们在list中实现其他接口时候,应该首先把迭代器命名:

typedef __list_iterator<T,T&> iterator;              //普通迭代器
typedef __list_iterator<T,const T&> const_iterator;  //常迭代器

既然修改好了参数问题,那第二个参数应用在哪里呢? 答曰: operator*,因为常迭代器影响的只是可否修改数据值;修改后如下:

Ref operator*()        //如果是普通迭代器,Ref就是T&,如果是常迭代器,Ref就是const T&.
{
    return _node->_val;
}

---

因此,到此为止后,是不是仍然觉得我们也完成了简单实现?但是事实是,我们还是忽略了一个细节:如果说我们存储的是一个结构体,即T是结构体,假设结构体定义如下:

struct Date
{
    int _year;
    int _month;
};

然后我们像下面一样存储结构体:

Date date[10];
list<Date> li(date,date+10);

再然后,我们用迭代器如何获取结构体的元素呢?

list<Date>::iterator it_b = li.begin();
list<Date>::iterator it_e = li.end();
while(it_b != it_e)
{
    cout<<(*it_b)._year;  //是不是要用三个操作符?分别是* () .
}

也就是通过上面,我们需要 用* () .三个操作符进行.

那我们能不能直接用->呢?那我们要使用->,就需要**把迭代器看成一个结构体的指针(看下面->重载的返回值)**了,那么我们就需要再设置一个参数了.

template <class T,class Ref,class Ptr>
    class __list_iterator
    {};

其中Ptr就是T的指针.

那么我们在list的内部就可以这样定义迭代器名字了

typedef __list_iterator<T,T&,T*> iterator;              //普通迭代器
typedef __list_iterator<T,const T&,const T*> const_iterator;  //常迭代器

而我们也需要在迭代器里面重载一下->操作符.

Ptr operator->()
{
    return &(_node->_val);   //这里一定是返回结构体的地址!!!,下面进行解释.
}

那么我们现在假设有一个list迭代器it,我们想要访问Date结构体的_year值,应该怎样写?答案是:it->->_year.但是这样看着别扭吗?别扭!!!.所以,编译器就帮我们优化了,我们就只需要写it->year.

到此,一个完整的list迭代器完成!!!

template <class T,class Ref,class Ptr>
    struct __list_iterator
    {
        typedef __list_iterator<T> iterator;  //迭代器
        typedef __list_node<T> node;          //链表结点,上面已经定义过
        node* _node;

        __list_iterator(node* pnode):_node(pnode) {}

        Ref operator*()        //迭代器使用*的意思是 获取结点值,所以就直接解引用_node,然后返回
        {
            return _node->_val;
        }

        Ptr operator->()
        {
            return &(_node->_val);  
        }
        
        iterator& operator++()       //++的意思就是迭代器向后移动一个位置,但是移动后还是迭代器,所以返回值仍然是iterator
        {
            _node = _node->_next;
            return *this;
        }

        iterator& operator--()       //--的意思就是迭代器向前移动一个位置,但是移动后还是迭代器,所以返回值仍然是iterator
        {
            _node = _node->_prev;
            return *this;
        }

        bool operator!=(const iterator & target) const   //判断迭代器是否相等,就是判断位置是否相等,即判断_node
        {
            return _node != target._node;
        }

        bool operator==(const iterator & target) const  //判断迭代器是否相等,就是判断位置是否相等,即判断_node
        {
            return _node == target._node;
        }
    };

---

迭代器接口

我们主要常用的就是四个(两个普通和两个常迭代)

iterator begin()  { return iterator(_head->_next); }
iterator end()  {return iterator(_head);}

const_iterator begin() const { return iterator(_head->_next); }
const_iterator end() const { return iterator(_head); }

---

clear()清理

注意这个清理哦,只会清楚头结点以后的数据,并不会连头结点也一起释放了.

void clear()
{
    iterator it = begin();
    while (it != end())
    {
        it = erase(it);
    }
}

---

析构函数

~list()
{ 
    clear();    //一定要先释放头结点后面的数据
    delete _head;
    _head = nullptr;
}

---

erase和insert的实现and简化头尾数据删除

erase的实现,参数为迭代器

iterator erase(iterator pos)
{
    assert(pos != end());
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    delete cur;
    prev->_next = next;
    next->_prev = prev;
    return iterator(next);
}

insert的实现,参数为迭代器加数据

iterator insert(iterator pos, const T& x)
{
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* newnode = new Node(x);

    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;

    return iterator(newnode);
}

那么我们的数据头尾删插是否可以简化呢?

void push_back(const T& x) {insert(end(), x);}
void push_front(const T& x) {insert(begin(), x);}
void pop_back() {erase(--end());}
void pop_front() {erase(begin());}

最终list代码

template <class T>     //  结点创建
struct __list_node
{
    __list_node* _next;
    __list_node* _prev;
    T _val;
    __list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}
};
template <class T,class Ref,class Ptr>
    struct __list_iterator
    {
        typedef __list_iterator<T> iterator;  //迭代器
        typedef __list_node<T> node;          //链表结点,上面已经定义过
        node* _node;

        __list_iterator(node* pnode):_node(pnode) {}

        Ref operator*()        //迭代器使用*的意思是 获取结点值,所以就直接解引用_node,然后返回
        {
            return _node->_val;
        }

        Ptr operator->()
        {
            return &(_node->_val);  
        }

        iterator& operator++()       //++的意思就是迭代器向后移动一个位置,但是移动后还是迭代器,所以返回值仍然是iterator
        {
            _node = _node->_next;
            return *this;
        }

        iterator& operator--()       //--的意思就是迭代器向前移动一个位置,但是移动后还是迭代器,所以返回值仍然是iterator
        {
            _node = _node->_prev;
            return *this;
        }

        bool operator!=(const iterator & target) const   //判断迭代器是否相等,就是判断位置是否相等,即判断_node
        {
            return _node != target._node;
        }

        bool operator==(const iterator & target) const  //判断迭代器是否相等,就是判断位置是否相等,即判断_node
        {
            return _node == target._node;
        }
    };



template <class T>   // list 结构搭建
class list
{
public:
    
list()
{
	_head = new node;  // 给头结点开辟一块空间.
    _head->_next = _head;
    _head->_prev = _head;
}
template <class InputIterator, class OutputIterator>
list(InputIterator input,OutputIterator output)
{
    //注意哦~,不可以写list(),误认为这是函数调用了哦 因为list本身就是个类,这样写是一个匿名对象
    _head = new node;  // 给头结点开辟一块空间.
    _head->_next = _head;
    _head->_prev = _head;
    while(input != output)
    {
    	push_back(*input);     //这个函数是用来实现尾插数据的,博主在下面进行讲解
        input++;
    }
}    
iterator begin()  { return iterator(_head->_next); }
iterator end()  {return iterator(_head);}

const_iterator begin() const { return iterator(_head->_next); }
const_iterator end() const { return iterator(_head); }
list(const list<T>& lt)
{
    _head = new Node;           //  必须先开个头结点空间哦~~,因为这是拷贝构造,不是赋值
    _head->_next = _head;
    _head->_prev = _head;
    for (const auto& e : lt)
    {
        push_back(e);    //这个函数后面会实现
    }
}
list<T>& operator=(const list<T> lt)  //  注意哦,这里的参数故意没有使用 引用.这样lt就是通过拷贝构造获取了值
{
    swap(_head, lt._head);   //然后交换两个链表的头结点
    return *this;
}    
~list()
{ 
    clear();    //一定要先释放头结点后面的数据
    delete _head;
    _head = nullptr;
}
    
iterator insert(iterator pos, const T& x)
{
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* newnode = new Node(x);

    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;

    return iterator(newnode);
}
    
iterator erase(iterator pos)
{
    assert(pos != end());
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    delete cur;
    prev->_next = next;
    next->_prev = prev;
    return iterator(next);
}    
    
void push_back(const T& x) {insert(end(), x);}
void push_front(const T& x) {insert(begin(), x);}
void pop_back() {erase(--end());}
void pop_front() {erase(begin());}

private:
	node* _head;    
};