0
0

【STL】容器 - list的模拟实现

一.框架

list: 带头双向循环链表

//节点类
template<class T>
struct __list_node
{
    T _val;
    __list_node* _next;
    __list_node* _prev;

    __list_node(const T& x = T())
        :_val(x), _next(nullptr), _prev(nullptr)
    {}
};

//iterator类
template<class T, class Ref, class Ptr>
struct __list_iterator
{
    typedef __list_node<T> node;
    typedef __list_iterator<T, Ref, Ptr> iterator;

    typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
    typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;    

    //属性
    node* _node;

    __list_iterator(node* x);

    iterator operator++();
    iterator operator++(int);

    iterator operator--();
    iterator operator--(int);

    Ref operator*();

    Ptr operator->();

    bool operator!=(iterator it);    
    bool operator==(iterator it);
};
//list类
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 Reverse_iterator<iterator, T&, T*> reverse_iterator;
    typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
        
    iterator begin();
    iterator end();

    const_iterator begin() const;
    const_iterator end() const;

    /
    //反向迭代器
    reverse_iterator rbegin();
    reverse_iterator rend();

    const_reverse_iterator rbegin() const;
    const_reverse_iterator rend() const

    void InitializeList();
    //构造
    list();
    list(int n, const T& value = T());
    template <class Iterator>
    list(Iterator first, Iterator last);
    list(const list<T>& l);
    list<T>& operator=(const list<T> l);
    
    //其余接口
    void swap(list<T>& l);
    bool empty();

    void push_back(const T& x);
    void pop_back();

    void push_front(const T& val);
    void pop_front();

    T& front();
    const T& front()const;

    T& back();
    const T& back()const;

    size_t size() const;

    iterator insert(iterator pos, const T& val);
    iterator erase(iterator pos);

    void clear();

    ~list();
private:
    node* _head;
};

二.list迭代器

1.list迭代器的特殊之处

在string和vector中, 迭代器是原生指针T*, 具体形式: typedef T* iterator

但在list中, 节点的存储是通过指针链接起来的, 底层内存存储空间并不连续, 无法对于节点的指针进行++或者--一系列的操作, 解决这一问题, 是实现list迭代器的关键

我们可以使用操作符重载将++重载成类似于node* cur, cur = cur->next, 针对于iterator的一整套操作符方法我们全部进行重载, 所以, 我们创建了一个iterator类模板, 每次通过调用list类中begin()/end()的方式构造这个类对象it

2.iterator类的代码实现

template<class T, class Ref, class Ptr>
struct __list_iterator
{
    typedef __list_node<T> node;
    typedef __list_iterator<T, Ref, Ptr> iterator;

    node* _node;

    __list_iterator(node* x)
    {
        _node = x;
    }
    
    //前置++
    iterator& operator++()
    {
        _node = _node->_next;
        return *this;
    }
    //后置++
    iterator operator++(int)
    {
        iterator tmp = *this;
        _node = _node->_next;
        return tmp;
    }
    //前置--
    iterator& operator--()
    {
        _node = _node->_prev;
        return *this;
    }
    //后置--
    iterator operator--(int)
    {
        iterator tmp = *this;
        _node = _node->_prev;
        return tmp;
    }
    //解引用
    Ref operator*()
    {
        return _node->_val;
    }
    //如果T是一个自定义类型可以通过it->的方式访问自定义类型成员
    //但实际是it->->, 编译器做了特殊处理, 自动省略掉一个->, 所以直接写it->即可
    //it->->的意思是: it.operator->()->, it.operator->()拿到一个指针(T*/const T*), 指针->是解引用
    Ptr operator->()
    {
        return &(operator*());
    }

    bool operator!=(iterator it)
    {
        return _node != it._node;
    }        
    bool operator==(iterator it)
    {
        return _node == it._node;
    }
};

//list类
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;

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

    //......
    //......
private:
    node* _head;

3.const迭代器复用普通迭代器

为什么iterator这个类模板的模板参数是template<class T, class Ref, class Ptr>, 直接写一个class T不就可以了吗?Ref, Ptr是用来做什么的?

这块整体是一个复用的思想,** 让const_iterator(const迭代器)复用到iterator(普通迭代器)**

如果我要构造一个普通迭代器, 传入T, T&, T* 分别对应iterator类模板的模板参数T, Ref, Ptr

如果我要构造一个const迭代器, 传入T, const T&, T* 分别对应iterator类模板的模板参数T, Ref, Ptr

这样完美的让一份iterator类模板同时可以支持普通迭代器与const迭代器, 如果只写template<class T>, 还需要再实现一个const_iterator的类模板

三.反向迭代器

1.反向迭代器也称迭代器适配器(复用的思想)

反向迭代器是迭代器适配器

stack&&queue&&priority_queue是容器适配器, 在后面的篇章会详细讲解

反向迭代器的精髓就在于, 只需要实现一份reverse_iterator便可以适配出绝大多数的容器的反向迭代器

注意这里是绝大多数容器! 绝大多数可以定义为, 这些容器的迭代器需要支持++与--操作

换句话说, 只要是能够支持迭代器++与--的容器, 就可以使用反向迭代器reverse_iterator适配出该容器自己的反向迭代器

例如forward_list, unordered_map, unordered_set这三种容器便不支持反向迭代器, 也就是不能适配

2.反向迭代器的使用

list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.push_back(5);
list<int>::reverse_iterator it = l.rbegin();
while (it != l.rend())
{
    cout << *it << ' ';
    ++it;
}
cout << endl;

3.反向迭代器操作原理详解

反向迭代器, 从名字上来理解, 他其实就是一个反着的正向迭代器

list: 1,2,3,4,5

正向迭代器: [begin, end]

begin --> end, it++

结果: 1,2,3,4,5

反向迭代器: [rend, rbegin]

rbegin-> rend, it++

结果: 5,4,3,2,1

反向迭代器的++操作, 在底层上是正向迭代器的--操作

rbegin()的位置是原end()的位置

rend()的位置是原begin()的位置

reverse_iterator rbegin()的实现必须是要 return iterator(begin()) 以这种形式, 才可以适配多种容器让reverse_iteartor复用iterator, rend()同理

所以在解引用时, 如上图, 是一定要先拷贝一份后(*不能改变迭代器的位置), 先--再return的

4.反向迭代器的代码实现

//迭代器适配器, 复用思想
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
    typedef Reverse_iterator<Iterator, Ref, Ptr> rIt;
    Iterator _it;
        
    //构造
    Reverse_iterator(Iterator it)
        :_it(it)//使用初始化列表, 如果不在这里定义的化需要在__list_iterator实现默认构造
    {}

    //其余接口
    //前置++
    rIt& operator++()
    {
        _it--;
        return *this;
    }
    //后置++
    rIt operator++(int)
    {
        rIt tmp(_it);
        _it--;
        return tmp;
    }
    //前置--
    rIt& operator--()
    {
        _it++;
        return *this;
    }
    //后置--
    rIt operator--(int)
    {
        rIt tmp(_it);
        _it++;
        return tmp;
    }
    //解引用
    Ref operator*()
    {
        Iterator tmp(_it);
        return *(--tmp);
    }
    //如果*_node是一个自定义类型可以通过it->的方式访问自定义类型成员
    //但实际是it->->, 编译器做了特殊处理, 自动省略掉一个->, 所以直接写it->即可
    //it->->的意思是: it.operator->()->, it.operator->()拿到一个指针(T*/const T*), 指针->是解引用
    Ptr operator->()
    {    
        //调用上面的operator*(), 底层逻辑又会去调用__list_iterator类中的operator*()
        //最终会拿到_node->_val
        //最后再取地址, 拿到_val的地址
        return &(operator*());
    }

    bool operator!=(rIt s)
    {
        return _it != s._it;
    }
    bool operator==(rIt s)
    {
        return _it == s._it;
    }
};

//list类
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 Reverse_iterator<iterator, T&, T*> reverse_iterator;
    typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

    //......
    //......

    /
    //反向迭代器
    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }
    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }
    const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }

    //......
    //......
private:
    node* _head;

这里的const_reverse_iterator复用reverse_iterator与上面const_iterator复用iterator是一个道理滴!!!

5.迭代器的分类

单向迭代器(forward_iterator) 支持++

例如: forward_list, unordered_map, unordered_set

双向迭代器(bidirectional_iterator) 支持 ++ / --

例如: list, map, set

随机迭代器(random_access_iterator) 支持 ++ / -- / + / -

例如: vector, deque, string

随机迭代器是特殊的双向迭代器

可以说, 如果该容器可以适配反向迭代器, 那么该容器的迭代器就是双向迭代器

四.常用接口

以下涉及到的深拷贝与迭代器失效详解, 具体可以参考我之前写的vector模拟实现

详解入口: http://t.csdn.cn/B8cpI

1.构造函数

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

list()
{
    InitializeList();
}

list(int n, const T& value = T())
{
    InitializeList();
    while (n--)
    {
        push_back(value);
    }
}

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

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

2.insert与erase

在list中

insert不会发生迭代器失效

erase必定会发生迭代器失效

注意: stl中实现的insert插入之后, 返回的是插入的节点的迭代器, 返回值更新了原迭代器位置为新插入的

erase返回值是删除节点的下一个节点的迭代器

iterator insert(iterator pos, const T& val)
{
    node* cur = pos._node;
    node* newnode = new node(val);
    node* pprev = cur->_prev;
            
    pprev->_next = newnode;
    cur->_prev = newnode;
    newnode->_next = cur;
    newnode->_prev = pprev;

    return iterator(newnode);
}

iterator erase(iterator pos)
{
    node* cur = pos._node;
    node* pprev = cur->_prev;
    node* pnext = cur->_next;

    delete cur;
    cur = nullptr;

    pprev->_next = pnext;
    pnext->_prev = pprev;

    return iterator(pnext);
}

3.其余接口

list<T>& operator=(const list<T> l)
{
    list<T> tmp(l);
    swap(tmp);
    return *this;
}
        
void swap(list<T>& l)
{
    ::swap(_head, l._head);
}

bool empty()
{
    return _head->_next == _head;
}

void push_back(const T& x)
{
    //new节点
    node* newnode = new node(x);
    //尾插
    node* tail = _head->_prev;
    newnode->_next = _head;
    newnode->_prev = tail;
    tail->_next = newnode;
    _head->_prev = newnode;
}
void pop_back()
{
    node* tail = _head->_prev;
    node* tprev = tail->_prev;
    node* tnext = tail->_next;
    delete tail;
    tail = nullptr;
    tprev->_next = tnext;
    tnext->_prev = tprev;
}

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

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

T& front()
{
    return _head->_next->_val;
}        
const T& front()const
{
    return _head->_next->_val;
}
T& back()
{
    return _head->_prev->_val;
}
const T& back()const
{
    return _head->_prev->_val;
}

size_t size() const
{
    node* cur = _head;
    int count = 0;
    while (cur->_next != _head)
    {
        count++;
        cur = cur->_next;
    }
    return count;
}

//清理, 保留头节点
void clear()
{
    node* cur = _head->_next;
    while (cur != _head)
    {
        node* next = cur->_next;
        delete cur;
        cur = next;
    }
    _head->_next = _head;
    _head->_prev = _head;
}

//析构, 全部清理包括头节点在内
~list() 
{ 
    node* cur = _head->_next;
    while (cur != _head)
    {
        node* next = cur->_next;
        delete cur;
        cur = next;
    }
    delete _head;
    _head = nullptr;
}
标签： c++ list java
本文转载自: https://blog.csdn.net/Hello_World_213/article/details/127151383
版权归原作者 Hello_World_213 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【STL】容器 - list的模拟实现”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航