STL中list的模拟实现

  • 开发
  • 21

目录

list模拟实现

list节点

list的push_back()函数

list的迭代器操作（非const）

list的迭代器操作（const）

list迭代器const 非const优化

list的insert()函数

list的erase()函数

list的pop_back() push_front() pop_front()

list的clear()函数

list的empty()_Init函数与构造函数

list的拷贝构造

list的析构函数

list的赋值运算符重载

list的initializer_list

 项目文件

4.list与vector的对比

list模拟实现

list节点

首先看节点：list底层是一个带头双向循环链表

template <class T>
class list_Node{
public:
    T _data;
    list_Node<T>* _prev;
    list_Node<T>* _next;
    
    list_Node(const T& data)
    :_data(data),
    _prev(nullptr),
    _next(nullptr)
    {
        
    }
};
template <class T>
class list{
public:
    typedef list_Node<T> Node;
    list(){
        _head = new Node(T());//不能使用0初始化，因为类型不确定
        _head->_next = _head;
        _head->_prev = _head;
    }

private:
    Node* _head;
}; 
}

list的push_back()函数

void push_back(const T& x){
    Node* newnode = new Node(x);
    Node* tail = _head->_prev;
    
    tail->_next = newnode;
    newnode->_prev = tail;
    newnode->_next = _head;
    _head->_prev = newnode;
    //insert(end(), x);
}

list的迭代器操作（非const）

list在物理上空间不是连续的，因此不可以像vector一样使用

typedef Node* iterator

Node* 不符合遍历的行为

List_iterator封装Node*

再通过重载运算符控制它的行为

因此这里我们可以使用一个类来封装使用

template <class T>
class List_iterator{
public:
    typedef list_Node<T> Node;
    typedef List_iterator Self;
    
    //不需要写析构函数，这个节点又不是这个类的
    //一个类一般不写析构，也就不需要显示写深拷贝
    List_iterator(Node* node)
    :_node(node)
    {
        
    }
    
    //日期类返回一个日期，那么迭代器返回一个迭代器
    //++it
    Self& operator++(){
        _node = _node->_next;
        return *this;
    }
    //--it
    Self& operator--(){
        _node = _node->_prev;
        return *this;
    }
    //it++
    Self operator++(int)//加参数 区分前置后置
    {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    //it--
    Self operator--(int){
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    
    
    T& operator*(){
        return _node->_data;
    }
    
    bool operator!=(const Self& it){
        return _node != it._node;
    }
    
    bool operator==(const Self& it){
        return _node == it._node;
    }
    
    T* operator->(){
        return &(_node->_data);
    }
private:
    Node* _node;
    
};

注意： T* operator->()的意义，比如下面的例子

    struct Pos{
        int _x;
        int _y;
        
        Pos(int x = 0,int y = 0)
        :_x(x),
        _y(y)
        {
            
        }
    };
    
    nanyi::list<Pos> ls2;
    ls2.push_back(Pos(100,200));
    ls2.push_back(Pos(300,400));
    ls2.push_back(Pos(500,600));
    
    nanyi::list<Pos>::iterator it1 = ls2.begin();
    while (it1 != ls2.end()) {
        //cout << (*it1)._x << ":" << (*it1)._y << endl;
        // 为了可读性，省略了一个->
        cout << it1->_x << ":" << it1->_y << endl;
        //cout << it1.operator->()->_row << ":" << it1.operator->()->_col << endl;
        
        ++it1;
    }
    cout << endl;
    return 0;

list类中

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

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

list的迭代器操作（const）

const迭代器不能在普通迭代器前加const修饰，比如这种情况

const迭代器的目标是 迭代器本身可以修改，指定的内容不能修改，类似const T* p

一旦加了不可以使用++it

因此我们重新写一个const类进行封装，我们只需改变解引用即可，使得指向内容不能修改

template <class T>
class const_List_iterator{
public:
    typedef list_Node<T> Node;
    typedef const_List_iterator Self;
    
    //不需要写析构函数，这个节点又不是这个类的
    //一个类一般不写析构，也就不需要显示写深拷贝
    const_List_iterator(Node* node)
    :_node(node)
    {
        
    }
    
    //日期类返回一个日期，那么迭代器返回一个迭代器
    //++it
    Self& operator++(){
        _node = _node->_next;
        return *this;
    }
    //--it
    Self& operator--(){
        _node = _node->_prev;
        return *this;
    }
    //it++
    Self operator++(int)//加参数 区分前置后置
    {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    //it--
    Self operator--(int){
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    
    
    const T& operator*(){
        return _node->_data;
    }
    
    bool operator!=(const Self& it){
        return _node != it._node;
    }
    
    bool operator==(const Self& it){
        return _node == it._node;
    }
    
    const T* operator->(){
        return &(_node->_data);
    }
private:
    Node* _node;
    
};

list类中

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

代码是没有问题的，但是我们也可以发现，这样非常的冗余 有些函数是没有变化的，确多写了一遍，有没有什么办法能解决这种冗余呢？

他们的区别主要是返回参数不同，返回是否有const对象

因此我们可以增加模版参数，让编译器完成任务

list迭代器const 非const优化

template <class T,class Ref,class Ptr>
class List_iterator{
public:
    typedef list_Node<T> Node;
    typedef List_iterator Self;
    
    //不需要写析构函数，这个节点又不是这个类的
    //一个类一般不写析构，也就不需要显示写深拷贝
    List_iterator(Node* node)
    :_node(node)
    {
        
    }
    
    //日期类返回一个日期，那么迭代器返回一个迭代器
    //++it
    Self& operator++(){
        _node = _node->_next;
        return *this;
    }
    //--it
    Self& operator--(){
        _node = _node->_prev;
        return *this;
    }
    //it++
    Self operator++(int)//加参数 区分前置后置
    {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    //it--
    Self operator--(int){
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    
    
    Ref operator*(){
        return _node->_data;
    }
    
    bool operator!=(const Self& it){
        return _node != it._node;
    }
    
    bool operator==(const Self& it){
        return _node == it._node;
    }
    
    Ptr operator->(){
        return &(_node->_data);
    }
private:
    Node* _node;
    
};

list的insert()函数

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

由于不牵涉扩容问题 这里不存在迭代器失效

 

list的erase()函数

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

这里存在迭代器失效，因此我们和库里一样返回下一个节点迭代器

list的pop_back() push_front() pop_front()

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

list的clear()函数

    void clear(){
        auto it = begin();
        while (it != end()) {
            it = erase(it);
            //不能++it,首先会迭代器失效，其次erase会自动返回下一个位置
        }
    }

list的empty()_Init函数与构造函数

由于我们经常使用申请头节点，因此我们把头节点封装成一个函数，便于调用

    void empty_Init(){
        _head = new Node(T());//不能使用0初始化，因为类型不确定
        _head->_next = _head;
        _head->_prev = _head;
    }
    list(){
        empty_Init();
    }

list的拷贝构造

如果我们不显示写拷贝构造 ，那么编译器会默认生成一个浅拷贝

浅拷贝生成的ls2，与ls1的地址相同，对ls1操作也会对ls2有影响

因此我们需要显示的写拷贝构造

    //拷贝构造
    list(const list<T>& ls){
        empty_Init();
        for (const auto& e : ls) {
            //范围for不确定类型，加引用
            push_back(e);
        }
        
    }

 

list的析构函数

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

list的赋值运算符重载

    //ls2 = ls1
    list<T>& operator=(list<T> ls){
        std::swap(_head, ls._head);
        return *this;
    }

list的initializer_list

可以将花括号内容，直接赋值给对象

    list (initializer_list<T> il){
        empty_Init();
        for (const auto& e : il) {
            push_back(e);
        }
    }

 项目文件

//
//  list.hpp
//  List
//
//  Created by 南毅 on 2024/5/28.
//

#include <iostream>
using namespace std;

namespace nanyi {
template <class T>
class list_Node{
public:
    T _data;
    list_Node<T>* _prev;
    list_Node<T>* _next;
    
    list_Node(const T& data)
    :_data(data),
    _prev(nullptr),
    _next(nullptr)
    {
        
    }
};

template <class T,class Ref,class Ptr>
class List_iterator{
public:
    typedef list_Node<T> Node;
    typedef List_iterator Self;
    
    //不需要写析构函数，这个节点又不是这个类的
    //一个类一般不写析构，也就不需要显示写深拷贝
    List_iterator(Node* node)
    :_node(node)
    {
        
    }
    
    //日期类返回一个日期，那么迭代器返回一个迭代器
    //++it
    Self& operator++(){
        _node = _node->_next;
        return *this;
    }
    //--it
    Self& operator--(){
        _node = _node->_prev;
        return *this;
    }
    //it++
    Self operator++(int)//加参数 区分前置后置
    {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    //it--
    Self operator--(int){
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    
    
    Ref operator*(){
        return _node->_data;
    }
    
    bool operator!=(const Self& it){
        return _node != it._node;
    }
    
    bool operator==(const Self& it){
        return _node == it._node;
    }
    
    Ptr operator->(){
        return &(_node->_data);
    }
public:
    Node* _node;
    
};

//template <class T>
//class const_List_iterator{
//public:
//    typedef list_Node<T> Node;
//    typedef const_List_iterator Self;
//    
//    //不需要写析构函数，这个节点又不是这个类的
//    //一个类一般不写析构，也就不需要显示写深拷贝
//    const_List_iterator(Node* node)
//    :_node(node)
//    {
//        
//    }
//    
//    //日期类返回一个日期，那么迭代器返回一个迭代器
//    //++it
//    Self& operator++(){
//        _node = _node->_next;
//        return *this;
//    }
//    //--it
//    Self& operator--(){
//        _node = _node->_prev;
//        return *this;
//    }
//    //it++
//    Self operator++(int)//加参数 区分前置后置
//    {
//        Self tmp(*this);
//        _node = _node->_next;
//        return tmp;
//    }
//    //it--
//    Self operator--(int){
//        Self tmp(*this);
//        _node = _node->_prev;
//        return tmp;
//    }
//    
//    
//    const T& operator*(){
//        return _node->_data;
//    }
//    
//    bool operator!=(const Self& it){
//        return _node != it._node;
//    }
//    
//    bool operator==(const Self& it){
//        return _node == it._node;
//    }
//    
//    const T* operator->(){
//        return &(_node->_data);
//    }
//private:
//    Node* _node;
//    
//};

template <class T>
class list{
public:
    typedef list_Node<T> Node;
    typedef List_iterator<T,T&,T*> iterator;
    typedef List_iterator<T,const T&,const T*> const_iterator;
    //typedef const_List_iterator<T> const_iterator;
    void empty_Init(){
        _head = new Node(T());//不能使用0初始化，因为类型不确定
        _head->_next = _head;
        _head->_prev = _head;
    }
    list(){
        empty_Init();
    }
    

    void clear(){
        auto it = begin();
        while (it != end()) {
            it = erase(it);
            //不能++it,首先会迭代器失效，其次erase会自动返回下一个位置
        }
    }
    //拷贝构造
    list(const list<T>& ls){
        empty_Init();
        for (const auto& e : ls) {
            push_back(e);
        }
        
    }
    
    //析构
    ~list(){
        clear();
        delete _head;
        _head = nullptr;
    }
    
    void push_back(const T& x){
//        Node* newnode = new Node(x);
//        Node* tail = _head->_prev;
//        
//        tail->_next = newnode;
//        newnode->_prev = tail;
//        newnode->_next = _head;
//        _head->_prev = newnode;
        
        insert(end(), x);
    }
    
    void pop_back(){
        erase(--end());
    }
    
    void push_front(const T& x){
        insert(begin(), x);
    }
    
    void pop_front(){
        erase(begin());
    }
    
    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);
    }
    
    iterator insert(iterator pos , const T& x){
        Node* cur = pos._node;
        Node* newnode = new Node(x);
        Node* prev = cur->_prev;
        
        newnode->_next = cur;
        newnode->_prev = prev;
        prev->_next = newnode;
        cur->_prev  = newnode;
        return iterator(newnode);
    }
    
    iterator erase(iterator pos){
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* next = cur->_next;
        // prev cur next
        
        prev->_next = next;
        next->_prev = prev;
        delete cur;
        cur = nullptr;
        return iterator(next);
    }
    
    //ls2 = ls1
    list<T>& operator=(list<T> ls){
        std::swap(_head, ls._head);
        return *this;
    }
    
    list (initializer_list<T> il){
        empty_Init();
        for (const auto& e : il) {
            push_back(e);
        }
    }
public:
    Node* _head;
};
}

4.list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

 

 

阅读全部

相关推荐

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-06-06 23:42:03       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-06-06 23:42:03       100 阅读

  9. 在Django里面运行非项目文件

    2024-06-06 23:42:03       82 阅读

  19. Python语言-面向对象

    2024-06-06 23:42:03       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-06-06 23:42:03       85 阅读

热门阅读

  3. 【机器学习通用流程】

    2024-06-06 23:42:03       25 阅读

  4. ubuntu18.04安装pycharm2024.1.2后，创建快捷方式图标

    2024-06-06 23:42:03       30 阅读

  6. 每日一题34：数据分组之查找每个员工花费的总时间

    2024-06-06 23:42:03       33 阅读

  10. 为什么RPC要比Http高效？

    2024-06-06 23:42:03       34 阅读

  13. ES6面试题

    2024-06-06 23:42:03       29 阅读

  14. 代码随想录算法训练营第五十一天|121. 买卖股票的最佳时机、122.买卖股票的最佳时机II

    2024-06-06 23:42:03       33 阅读

  15. web前端三大主流框架

    2024-06-06 23:42:03       29 阅读

  17. springboot，配置类加载过程

    2024-06-06 23:42:03       31 阅读

  18. 跨境项目的SaaS实现：根据语言区分

    2024-06-06 23:42:03       32 阅读

  20. 卷积池化尺寸计算公式

    2024-06-06 23:42:03       36 阅读

  21. linux中的“-＞“符号

    2024-06-06 23:42:03       28 阅读

  22. vscode远程登录ubuntu linux报错，一直输入密码问题

    2024-06-06 23:42:03       26 阅读

  29. TensorRT教程（1）初探TensorRT

    2024-06-06 23:42:03       31 阅读