C++ STL之list的使用及模拟实现

1. 介绍

英文解释：

也就是说：

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比（array，vector，deque），list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息（对于存储类型较小元素的大list来说这可能是一个重要的因素）。

图示：

想要具体了解其底层数据结构可以参照：线性表之双向链表

2. list类的使用

template < class T, class Alloc = allocator<T> > class list;

list 是类模板。使用其定义变量时，首先需要实例化。

例如：

实例化类型	解释
list	整型容器，每个元素的类型为 int。
list<char*>	char* 指针容器，每个元素的类型为 char*。
list<vector>	list 类模板嵌套实例化的容器，元素类型为 vector。

2.1 list类对象的构造函数

实例：

// constructing lists
#include <iostream>
#include <list>

int main()
{
    // 按照上述描述的顺序使用的构造函数
    std::list<int> first;                                // empty list of ints
    std::list<int> second(4, 100);                       // four ints with value 100
    std::list<int> third(second.begin(), second.end());  // iterating through second
    std::list<int> fourth(third);                       // a copy of third

    // the iterator constructor can also be used to construct from arrays:
    int myints[] = { 16,2,77,29 };
    std::list<int> fifth(myints, myints + sizeof(myints) / sizeof(int));

    std::cout << "The contents of fifth are: ";
    for (std::list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)
        std::cout << *it << ' ';

    std::cout << '\n';

    return 0;
}

输出结果：

2.2 list类对象的容量操作

2.3 list类对象的修改操作

2.4 list类对象的访问及遍历操作

遍历操作

#include <iostream>
#include <list>

int main()
{
	std::list<int> lt(10, 100);

	// 1. 迭代器遍历
	for (std::list<int>::iterator it = lt.begin(); it != lt.end(); ++it)
		std::cout << *it << " ";
	std::cout << '\n';

	// 2. 范围for遍历
	for (auto e : lt)
		std::cout << e << " ";
	std::cout << '\n';

	return 0;
}

运行结果：

解释

1. 迭代器遍历：

• 首先，通过lt.begin()获取列表的起始迭代器，lt.end()获取列表的结束迭代器。
• 使用std::list<int>::iterator it定义一个迭代器变量，并将其初始化为列表的起始迭代器。
• 使用迭代器变量it进行循环迭代，从列表的起始位置迭代到结束位置（不包括结束位置）。
• 在循环中，通过*it访问当前迭代器指向的元素，并输出到标准输出流std::cout中。

2. 范围for循环遍历：

• 使用auto关键字和范围for循环语法，遍历列表lt中的每个元素。
• 在每次迭代中，将当前元素赋值给变量e。
• 在循环体内，输出变量e的值到标准输出流std::cout中。

3. list类的模拟实现

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

namespace my_list
{   
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T())
            :_pPre(nullptr)
            ,_pNext(nullptr)
            ,_val(val)
        {}
        ListNode<T>* _pPre;
        ListNode<T>* _pNext;
        T _val;
    };

    //List的迭代器类
    template<class T, class Ref, class Ptr>
    class List_iterator
    {
        typedef ListNode<T>* PNode;
        typedef List_iterator<T, Ref, Ptr> Self;
    public:
        List_iterator(PNode pNode = nullptr)
        {
            _pNode = pNode;
        }

        List_iterator(const Self& l)
        {
            _pNode = l._pNode;
        }

        Ref operator*()
        {
            return _pNode->_val;
        }

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

        Self& operator++()
        {
            _pNode = _pNode->_pNext;
            return *this;
        }

        Self operator++(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pNext;
            return tmp;
        }

        Self& operator--()
        {
            _pNode = _pNode->_pPre;
            return *this;
        }

        Self operator--(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pPre;
            return tmp;
        }

        bool operator!=(const Self& l)
        {
            return _pNode != l._pNode;
        }

        bool operator==(const Self& l)
        {
            return _pNode == l._pNode;
        }
        
        PNode GetNode()
        {
            return _pNode;
        }

    private:
        PNode _pNode;
    };

    // 反向迭代器——对正向迭代器的接口进行包装
    template<class Iterator, class Ref, class Ptr>
    struct Reverse_iterator
    {
        Iterator _it;
        typedef Reverse_iterator<Iterator, Ref, Ptr> Self;

        Reverse_iterator() {}

        Reverse_iterator(Iterator it)
            : _it(it)
        {}

        Ref operator*()
        {
            Iterator tmp(_it);
            --tmp;
            return *tmp;
        }

        Ptr operator->()
        {
            return &(operator*());
        }

        Self& operator++()
        {
            --_it;
            return *this;
        }

        Self operator++(int)
        {
            Self tmp(*this);
            --_it;
            return tmp;
        }

        Self& operator--() {
            ++_it;
            return *this;
        }

        Self operator--(int)
        {
            Self tmp(*this);
            ++_it;
            return tmp;
        }

        bool operator!=(const Self& s)
        {
            return _it != s._it;
        }

        bool operator==(const Self& s)
        {
            return _it == s._it;
        }
    };

    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
        typedef Node* PNode;
    public:
        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;

    public:
        
        ///
        // List Iterator
        iterator begin()
        {
            return _pHead->_pNext;
        }

        iterator end()
        {
            return _pHead;
        }
        
        const_iterator begin() const
        {
            return const_iterator(_pHead->_pNext);
        }

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

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

        ///
        // List 构造/赋值
        list()
        {
            CreateHead();
        }

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

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

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

        list(const list<T>& l)
        {
            CreateHead();
            for (auto it : l)
            {
                push_back(it);
                _size++;
            }
        }

        void swap(list<T>& l)
        {
            std::swap(this->_pHead, l._pHead);
            std::swap(this->_size, l._size);
        }
        
        list<T>& operator=(list<T> l)
        {
            swap(l);
            return *this;
        }

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

        ///
        // List Capacity
        size_t size()const
        {
            return _size;
        }

        bool empty()const
        {
            return _size == 0;
        }


        
        // List Access
        T& front()
        {
            assert(!empty());
            return _pHead->_pNext->_val;
        }
       
        const T& front()const
        {
            assert(!empty());
            return _pHead->_pNext->_val;
        }

        T& back()
        {
            assert(!empty());
            return _pHead->_pPre->_val;
        }

        const T& back()const
        {
            assert(!empty());
            return _pHead->_pPre->_val;
        }


        
        // List Modify
        void push_back(const T& val)
        {
            insert(end(), val);
        }

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

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

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

        // 在pos位置前插入值为val的节点
        iterator insert(iterator pos, const T& val)
        {
            PNode tmp = new Node(val);
            PNode cur = pos.GetNode();
            PNode pre = cur->_pPre;
            tmp->_pNext = cur;
            tmp->_pPre = pre;
            pre->_pNext = tmp;
            cur->_pPre = tmp;
            _size++;
            return tmp;
        }

        // 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos)
        {
            PNode cur = pos.GetNode();
            PNode next = cur->_pNext;
            PNode pre = cur->_pPre;
            delete cur;
            pre->_pNext = next;
            next->_pPre = pre;
            _size--;
            return next;
        }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }
        
    private:
        // 创建头结点
        void CreateHead()
        {
            _pHead = new Node;
            _pHead->_pNext = _pHead->_pPre = _pHead;
        }

        PNode _pHead;
        size_t _size = 0;
    };
};

注意

这里实现的反向迭代器类模板同样也可以适配到vector类和string类中。文章来源地址https://www.toymoban.com/news/detail-821342.html

到了这里，关于C++ STL之list的使用及模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！