C++【STL】之list模拟实现

2023-06-17 112

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： C++ STL list类模拟实现，常用接口详细讲解，干货满满！

list模拟实现

上一篇讲解了list的使用，这一篇接着介绍list的模拟实现，这里依然是讲解常用接口的模拟实现，话不多说，正文开始！

1. 成员变量和节点

list类中的成员变量就是一个哨兵位的头结点，后续在上进行链接操作，而节点的实现需要一个节点类来进行封装

private:
    node* _head; //哨兵位头结点

template<class T>
struct list_node
{
   
    list_node<T>* _next; //指向前一个节点
    list_node<T>* _prev; //指向后一个节点
    T _data; //节点内数据

    list_node(const T& x = T())
        :_next(nullptr)
        , _prev(nullptr)
        , _data(x)
    {
   }
};

2. 迭代器

迭代器要么就是原生指针，要么就是自定义类型对原生指针的封装，模拟指针的行为

显然list中的迭代器是第二种，list的迭代器也是被封装成了一个类，类中的成员为节点类指针，指向单个节点

template<class T, class Ref, class Ptr>
struct _list_iterator
{
   
    typedef list_node<T> node;
    typedef _list_iterator<T, Ref, Ptr> self;
    node* _node; //成员变量
    _list_iterator(node* n) //begin()和end()中需要构造来返回节点指针
        :_node(n)
    {
   }

    Ref operator*()
    {
   
        return _node->_data;
    }

    Ptr operator->()
    {
   
        return &_node->_data;
    }
    //前置++
    self& operator++() 
    {
   
        _node = _node->_next;
        return *this;
    }
    //后置++
    self operator++(int) //局部变量tmp出了作用域会销毁，不能使用引用返回
    {
   
        self tmp(*this);
        _node = _node->_next;

        return tmp;
    }
    //前置--
    self& operator--()
    {
   
        _node = _node->_prev;
        return *this;
    }
    //后置--
    self operator--(int)
    {
   
        self tmp(*this);
        _node = _node->prev;
        return tmp;
    }

    bool operator!=(const self& s)
    {
   
        return _node != s._node;
    }

    bool operator==(const self& s)
    {
   
        return _node == s._node;
    }
};

==注意==

list双向链表是链式结构，迭代器需要自定义类型对原生指针的封装，模拟指针的行为
begin()和end()中需要构造来拿到节点的指针，所以需要提供构造函数
class Ref和class Ptr模板的提供是为了T* 和 const T*不用复用代码来直接传参
typedef _list_iterator<T, Ref, Ptr> self这里的self是其类型别名，*this指针就是self类型，包含了_node成员变量，_node 是迭代器中的节点指针，包含在迭代器对象中

2.1 移动原理

list的空间不是连续的，使用的是双向迭代器，只支持++、--来实现前后节点间的移动，不支持随机移动

那么是如何实现不连续空间之间的移动的呢？

首先构造迭代器对象，当使用++操作时，会去调用迭代器类中实现的operator++()重载方法，核心操作就是将迭代器指向当前节点的下一个节点，即_node = _node -> next，使用--操作原理也是如此

//前置++
self& operator++() 
{
   
    _node = _node->_next;
    return *this;
}
//后置++
self operator++(int) //局部变量tmp出了作用域会销毁，不能使用引用返回
{
   
    self tmp(*this);
    _node = _node->_next;

    return tmp;
}
//前置--
self& operator--()
{
   
    _node = _node->_prev;
    return *this;
}
//后置--
self operator--(int)
{
   
    self tmp(*this);
    _node = _node->prev;
    return tmp;
}

2.2 多参数模板

迭代器分为普通迭代器和const迭代器，不同的对象需要调用不同的迭代器类型，这里使用多模板参数很好的解决了两种迭代器在实现时的冗余问题

T：普通节点类型
Ref：引用节点类型(可以是const)
Ptr：指针节点类型(可以是const)

template<class T, class Ref, class Ptr>
struct _list_iterator
{
   
    typedef list_node<T> node;
    typedef _list_iterator<T, Ref, Ptr> self;
    node* _node; //成员变量
    //...
};

用不同的迭代器类型时，迭代器类中的模板参数变为对应类型，这就是所谓的泛型思想之一

3. 默认成员函数

3.1 构造和析构

构造函数需要创建头结点，这里要先提供一个空初始化的方法empty_init()

void empty_init()
{
   
    //初始化头结点
    _head = new node;
    _head->_next = _head;
    _head->_prev = _head;
}

==默认构造==

list()
{
   
    empty_init();
}

==迭代器区间构造==

template<class Iterator>
list(Iterator first, Iterator last)
{
   
    empty_init();
    while (first != last)
    {
   
        push_back(*first);
        ++first;
    }
}

在创建 list 对象时，多使用迭代器区间进行构造，创建新对象可以直接调用尾插进行创建

==析构函数==

调用clear()方法释放节点，然后再释放头结点即可

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

3.2 拷贝和赋值

==拷贝构造==

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

list(const list<T>& lt)
{
   
    empty_init();
    list<T> tmp(lt.begin(), lt.end());
    swap(tmp);
}

拷贝构造必须使用引用传参，否则会导致无穷递归问题

==赋值重载==

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

4. 容量操作

4.1 empty方法

判空只需要判断当前 begin() 与 end() 的位置是否相同即可

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

4.2 size方法

统计大小只需要将list遍历一遍，统计节点个数即可

size_t size() const
{
   
    size_t cnt = 0;
    const_iterator it = begin();
    while (it != end())
    {
   
        ++cnt;
        ++it;
    }
    return cnt;
}

5. 数据访问

访问首尾数据只需要通过对应指针来返回对应值即可

T& front()
{
   
    return begin()._node->_data;
}

const T& front() const
{
   
    return begin()._node->_data;
}

T& back()
{
   
    return end()._node->_data;
}

const T& back() const
{
   
    return end()._node->_data;
}

6. 数据修改

6.1 insert方法

操作步骤：

在pos位置前进行插入
记录当前pos位置的节点和pos位置的上一个节点
建立预插入节点和两位置的链接关系

void insert(iterator pos, const T& x)
{
   
    node* cur = pos._node; //pos位置节点
    node* prev = cur->_prev; //pos位置上一个节点

    node* new_node = new node(x);
    //建立链接关系
    prev->_next = new_node;
    new_node->_prev = prev;
    new_node->_next = cur;
    cur->_prev = new_node;
}

6.2 erase方法

操作步骤：

首先判断list是否为空
记录当前节点的上一个节点和下一个节点的位置
将记录的两个节点建立链接关系，
最后删除当前节点，返回已删除节点下一个节点

iterator erase(iterator pos)
{
   
    assert(pos != end());

    node* prev = pos._node->_prev; //pos位置上一个节点
    node* next = pos._node->_next; //pos位置下一个节点

    prev->_next = next;
    next->_prev = prev;
    delete pos._node;

    return iterator(next); //返回位置防止迭代器失效
}

注意：list的删除操作会存在迭代器失效的问题，这里记录返回节点的位置来解决此问题

6.3 头尾插入删除

这里头尾的插入删除操作可以直接复用insert()和erase()

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());
}

6.4 swap方法

list中的交换方法是直接交换两个对象的哨兵位头结点，效率很高

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

6.5 clear方法

遍历链表删除除了头结点外的所有节点

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

7. 完整代码

#pragma once
#include <iostream>
#include<list>
#include <cassert>
using namespace std;

namespace sakura
{
   
    template<class T>
    struct list_node
    {
   
        list_node<T>* _next;
        list_node<T>* _prev;
        T _data;

        list_node(const T& x = T())
            :_next(nullptr)
            , _prev(nullptr)
            , _data(x)
        {
   }
    };

    //迭代器要么就是原生指针
    //迭代器要么就是自定义类型对原生指针的封装，模拟指针的行为
    template<class T, class Ref, class Ptr>
    struct _list_iterator
    {
   
        typedef list_node<T> node;
        typedef _list_iterator<T, Ref, Ptr> self;
        node* _node; //成员变量
        _list_iterator(node* n) //begin()和end()中需要构造来返回节点指针
            :_node(n)
        {
   }

        Ref operator*()
        {
   
            return _node->_data;
        }

        Ptr operator->()
        {
   
            return &_node->_data;
        }
        //前置++
        self& operator++()
        {
   
            _node = _node->_next;
            return *this;
        }
        //后置++
        self operator++(int) //局部变量tmp出了作用域会销毁，不能使用引用返回
        {
   
            self tmp(*this);
            _node = _node->_next;

            return tmp;
        }
        //前置--
        self& operator--()
        {
   
            _node = _node->_prev;
            return *this;
        }
        //后置--
        self operator--(int)
        {
   
            self tmp(*this);
            _node = _node->prev;
            return tmp;
        }

        bool operator!=(const self& s)
        {
   
            return _node != s._node;
        }

        bool operator==(const self& s)
        {
   
            return _node == s._node;
        }
    };

    template<class T>
    class list
    {
   
        typedef list_node<T> node;
    public:
        typedef _list_iterator<T, T&, T*> iterator;
        typedef _list_iterator<T, const T&, const T*> const_iterator;

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

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

        iterator end()
        {
   
            return iterator(_head);
        }

        const_iterator end() const
        {
   
            return const_iterator(_head);
        }

        void empty_init()
        {
   
            //初始化头结点
            _head = new node;
            _head->_next = _head;
            _head->_prev = _head;
        }

        list()
        {
   
            empty_init();
        }

        template<class Iterator>
        list(Iterator first, Iterator last)
        {
   
            empty_init();
            while (first != last)
            {
   
                push_back(*first);
                ++first;
            }
        }

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

        list(const list<T>& lt)
        {
   
            empty_init();
            list<T> tmp(lt.begin(), lt.end());
            swap(tmp);
        }

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

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

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

        T& front()
        {
   
            return begin()._node->_data;
        }

        const T& front() const
        {
   
            return begin()._node->_data;
        }

        T& back()
        {
   
            return end()._node->_data;
        }

        const T& back() const
        {
   
            return end()._node->_data;
        }

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

        size_t size() const
        {
   
            size_t cnt = 0;
            const_iterator it = begin();
            while (it != end())
            {
   
                ++cnt;
                ++it;
            }
            return cnt;
        }

        void push_back(const T& x)
        {
   
            //node* tail = _head->_prev;
            //node* new_node = new node(x);

            //tail->_next = new_node;
            //new_node->_prev = tail;
            //new_node->_next = _head;
            //_head->_prev = new_node;

            insert(end(), x);
        }

        void push_front(const T& x)
        {
   
            insert(begin(), x);
        }

        void pop_back()
        {
   
            erase(--end());
        }

        void pop_front()
        {
   
            erase(begin());
        }

        void insert(iterator pos, const T& x)
        {
   
            node* cur = pos._node; //pos位置节点
            node* prev = cur->_prev; //pos位置上一个节点

            node* new_node = new node(x);
            //建立链接关系
            prev->_next = new_node;
            new_node->_prev = prev;
            new_node->_next = cur;
            cur->_prev = new_node;
        }

        iterator erase(iterator pos)
        {
   
            assert(pos != end());

            node* prev = pos._node->_prev; //pos位置上一个节点
            node* next = pos._node->_next; //pos位置下一个节点

            prev->_next = next;
            next->_prev = prev;
            delete pos._node;

            return iterator(next); //返回位置防止迭代器失效
        }

    private:
        node* _head;
    };

    void print_list(const list<int>& lt)
    {
   
        list<int>::const_iterator it = lt.begin();
        while (it != lt.end())
        {
   
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }
}

C++【STL】之list模拟实现，到这里就介绍结束了，本篇文章对你由帮助的话，期待大佬们的三连，你们的支持是我最大的动力！

文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正！

C++【STL】之list模拟实现

list模拟实现

1. 成员变量和节点

2. 迭代器

2.1 移动原理

2.2 多参数模板

3. 默认成员函数

3.1 构造和析构

3.2 拷贝和赋值

4. 容量操作

4.1 empty方法

4.2 size方法

5. 数据访问

6. 数据修改

6.1 insert方法

6.2 erase方法

6.3 头尾插入删除

6.4 swap方法

6.5 clear方法

7. 完整代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C++【STL】之list模拟实现

list模拟实现

1. 成员变量和节点

2. 迭代器

2.1 移动原理

2.2 多参数模板

3. 默认成员函数

3.1 构造和析构

3.2 拷贝和赋值

4. 容量操作

4.1 empty方法

4.2 size方法

5. 数据访问

6. 数据修改

6.1 insert方法

6.2 erase方法

6.3 头尾插入删除

6.4 swap方法

6.5 clear方法

7. 完整代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景