C++STL(三) ：list的模拟实现

C++STL(三) ：list的模拟实现

三个类及其成员函数的接口总览

#define _CRT_SECURE_NO_WARNINGS 1 
#include <iostream>

namespace pjy
{
    template<class T>
        struct _list_node
        {
            //构造函数
            _list_node(const T& val=T())
            {}
            //成员变量
            T _val;
            _list_node<T>* _prev;
            _list_node<T>* _next;
        };
    template<class T,class Ptr,class Ref>
        struct _list_iterator
        {
            typedef _list_node<T> node;
            typedef _list_node<T,Ptr,Ref> self;
            //构造函数
            _list_iterator(node* pnode);

            //运算符重载
            self operator--();
            self operator++(int);
            self operator--(int);
            bool operator==(const self& s) const;
            bool operator!=(const self& s) const;
            Ref operator*();
            Ptr operator->();

            node* _pnode;
        };
    template<class T>
        class list
        {
            public:
            typedef _list_node<T> node;
            typedef _list_node<T, T*, T&> iterator;
            typedef _list_node<T, const T*, const T&> const_iterator;
            //默认成员函数
            list();
            list(const list<T>& lt);
            list<T>& operator=(const list<T>& lt);
            ~list();

            //迭代器
            iterator begin();
            iterator end();
            const_iterator begin() const;
            const_iterator end() const;

            //访问
            T& front();
            T& back();
            const T& front() const;
            const T& back() const;

            //修改
            void insert(iterator pos, const T& val);
            iterator erase(iterator pos);
            void push_back(const T& val);
            void pop_back();
            void push_front(const T& val);
            void pop_front();
            void swap(list<T>& lt);

            //“容量”
            const size_t size() const;
            void resize(size_t n, const T& val = T());
            void clear();
            bool empty();
            private:
            node* _head;
        };
}

节点类

list在底层其实是一个带头双向循环列表，结构如下图：

因此一个结点需要存储的信息有：数据、前一个结点的地址、后一个结点的地址,即数据、前驱指针、后继指针

而对于该结点类的成员函数来说，我们只需实现一个构造函数即可。因为该结点类只需要根据数据来构造一个结点即可，而结点的释放则由list的析构函数来完成

template<class T>
    struct _list_node
    {
        //构造函数
        _list_node(const T& val=T())
            :_val(val)
                ,_prev(nullptr)
                ,_next(nullptr)
            {}
        //成员变量
        T _val;
        _list_node<T>* _prev;
        _list_node<T>* _next;
    };

迭代器类

迭代器类存在的意义

之前模拟实现string和vector时都没有说要实现一个迭代器类，为什么实现list的时候就需要实现一个迭代器类了呢

因为string和vector对象都将其数据存储在了一块连续的内存空间，我们通过指针进行自增、自减以及解引用等操作，就可以对相应位置的数据进行一系列操作，因此string和vector当中的迭代器不用进行封装

但是对于list来说，其各个结点在内存当中的位置是随机的，并不是连续的，我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作；而迭代器的意义就是，让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问

既然list的结点指针的行为不满足迭代器定义，那么我们可以对这个结点指针进行封装，对结点指针的各种运算符操作进行重载，使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。例如，当你使用list当中的迭代器进行自增操作时，实际上执行了p = p->next语句

迭代器类的模板参数说明

template<class T,class Ptr,class Ref>

这里的参数模板参数列表当中为什么有三个模板参数?

• 通过模板参数区分普通迭代器和常量迭代器，避免重复编写两套逻辑
• 显式指定引用和指针类型，防止非法的类型转换

typedef _list_node<T, T*, T&> iterator;
typedef _list_node<T, const T*, const T&> const_iterator;

构造函数

直接根据所给结点指针构造一个迭代器对象

_list_iterator(node* pnode)
    :_pnode(node)
    {}

运算符函数重载

self operator++()//前置++
{
    _pnode = _pnode->_next;
    return *this;
}
self operator++(int)//后置++
{
    self tmp(*this);
    _pnode = _pnode->_next;
    return tmp;
}
self operator--()//前置--
{
    _pnode = _pnode->_prev;
    return *this;
}
self operator--(int)//后置--
{
    self tmp(*this);
    _pnode = _pnode->_prev;
    return tmp;
}
bool operator==(const self& s) const
{
    return _pnode == s._pnode;
}
bool operator!=(const self& s) const
{
    return _pnode != s._pnode;
}
Ref operator*()
{
    return _pnode->_val;
}
//it.operator->()->val  --> it->val
Ptr operator->()
{
    return &_pnode->_val; 
}

list

默认成员函数

构造函数

因为list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可

list()
{
    _head = new node();
    _head->_next = _head;
    _head->_prev = _head;
}

拷贝构造

拷贝构造函数就是根据所给list容器，拷贝构造出一个对象。对于拷贝构造函数，我们先申请一个头结点，并让其前驱指针和后继指针都指向自己，然后将所给容器当中的数据，通过遍历的方式一个个尾插到新构造的容器后面即可

list(const list<T>& lt)
{
    _head = new node;
    _head->_next = _head;
    _head->_prev = _head;
    for (auto& e : lt)
    {
        push_back(e);
    }
}

赋值运算符重载

传统写法

先调用clear函数将原容器清空,再通过遍历的方式一个个尾插到清空后的容器当中

list<T>& operator=(const list<T>& lt)
{
    if (this != &lt)
    {
        clear();
        for (const auto& e : lt)
        {
            push_back(e);
        }
    }
    return *this;
}

现代写法

故意不使用引用接收参数，通过编译器自动调用list的拷贝构造函数构造出来一个list对象，然后调用swap函数将原容器与该list对象进行交换

list<T>& operator=(list<T> lt)
{
    if (this != &lt)
    {
        swap(lt);
    }
    return *this;
}

析构函数

首先调用clear函数清理容器当中的数据，然后将头结点释放，最后将头指针置空

~list()
{
    clear();
    delete _head;
    _head = nullptr;
}

迭代器类函数

begin()和end()

首先我们应该明确的是：

• begin函数返回的是第一个有效数据的迭代器
• end函数返回的是最后一个有效数据的下一个位置的迭代器

对于list这个带头双向循环链表来说，其第一个有效数据的迭代器就是使用头结点后一个结点的地址构造出来的迭代器，而其最后一个有效数据的下一个位置的迭代器就是使用头结点的地址构造出来的迭代器

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

访问相关函数

front()和back()

front和back函数分别用于获取第一个有效数据和最后一个有效数据，因此，实现front和back函数时，直接返回第一个有效数据和最后一个有效数据的引用

T& front()
{
    return *begin();
}
T& back()
{
    return *(--end());
}
const T& front() const
{
    return *begin();
}
const T& back() const
{
    return *(--end());
}

修改相关函数

insert()

void insert(iterator pos, const T& val)
{
    assert(pos._pnode);
    node* cur = pos._pnode;
    node* prev = cur->_prev;
    node* newnode = new node(val);

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

erase()

iterator erase(iterator pos)
{
    assert(pos._pnode);
    node* cur = pos._pnode;
    node* prev = cur->_prev;
    node* next = cur->_next;
    prev->_next = next;
    next->_prev = prev;

    return iterator(next);
}

push_back()和pop_back()

push_back函数就是在头结点前插入结点，而pop_back就是删除头结点的前一个结点

直接复用insert与erase即可

void push_back(const T& val)
{
    insert(end(), val);
}
void pop_back()
{
    erase(--end());
}

push_front()和pop_front()

void push_front(const T& val)
{
    insert(begin(), val);
}
void pop_front()
{
    erase(begin());
}

swap()

list容器当中存储的实际上就只有链表的头指针，我们将这两个容器当中的头指针交换

void swap(list<T>& lt)
{
    ::swap(_head, lt._head);
}

“容量相关函数”

size()

只能通过遍历的方式逐个统计有效数据的个数

const size_t size() const
{
    size_t sz = 0; //统计有效数据个数
    const_iterator it = begin(); //获取第一个有效数据的迭代器
    while (it != end()) //通过遍历统计有效数据个数
    {
        sz++;
        it++;
    }
    return sz; //返回有效数据个数
}

resize()

resize函数的规则：

• 若当前容器的size小于所给n，则尾插结点，直到size等于n为止

• 若当前容器的size大于所给n，则只保留前n个有效数据

实现resize函数时，不要直接调用size函数获取当前容器的有效数据个数，因为当你调用size函数后就已经遍历了一次容器了，而如果结果是size大于n，那么还需要遍历容器，找到第n个有效结点并释放之后的结点。

这里实现resize的方法是，设置一个变量len，用于记录当前所遍历的数据个数，然后开始变量容器，在遍历过程中：

• 当len大于或是等于n时遍历结束，此时说明该结点后的结点都应该被释放，将之后的结点释放即可
• 当容器遍历完毕时遍历结束，此时说明容器当中的有效数据个数小于n，则需要尾插结点，直到容器当中的有效数据个数为n时停止尾插即可

void resize(size_t n, const T& val = T())
{
    iterator it = begin(); //获取第一个有效数据的迭代器
    size_t len = 0; //记录当前所遍历的数据个数
    while (len < n && it != end())
    {
        len++;
        it++;
    }
    if (len == n) //说明容器当中的有效数据个数大于或是等于n
    {
        while (it != end()) //只保留前n个有效数据
        {
            it = erase(it); //每次删除后接收下一个数据的迭代器
        }
    }
    else //说明容器当中的有效数据个数小于n
    {
        while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n
        {
            push_back(val);
            len++;
        }
    }
}

clear()

void clear()
{
    iterator it = begin();
    while (it != end()) //逐个删除结点，只保留头结点
    {
        it = erase(it);
    }
}

empty()

bool empty() const
{
    return begin() == end();
}