【C++】list的模拟实现

文章目录

• • 1.list 底层
  • 2. list的模拟实现
  • • 1. list_node 类设计
    • 2. list类如何调用类型
    • 3 .push_back(正常实现)
    • 4. 迭代器的实现
    • • 第一个模板参数T
      • const迭代器
      • 第二个模板参数Ref
      • 第三个模板参数Ptr
      • 对list封装的理解
    • 5. insert
    • 6.push_back与 push_front(复用)
    • 7. erase
    • 8. pop_back与pop_front (复用)
    • 9. clear 清空数据
    • 10. 迭代器区间构造
    • 12. 拷贝构造
    • • 传统写法
      • 现代写法
    • 13. 赋值
  • 3.完整代码

1.list 底层

list为任意位置插入删除的容器，底层为带头双向循环链表

begin() 代表第一个结点，end()代表最后一个结点的下一个

2. list的模拟实现

1. list_node 类设计

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

	};

C++中，Listnode作为类名，而next和prev都是类指针，指针引用成员时使用->，而对象引用成员时使用 .
通过显示实例化，将两个类指针指定类型为T

2. list类如何调用类型

Listnode 代表类型
Listnode 代表类名 + 模板参数 才是类型
而_head 以及创建新节点前都需加上类型

3 .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;
        }

当我们想要创建一个节点时，需要调用node的构造函数
typedef list_node node ，node是由 list_node 类提供的

list_node(const T& x=T())//list类的构造函数
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{
		}

最好在构造函数处提供全缺省，对于内置类型int可以使用0，但对于自定义类型来说就不可以，所以为了满足泛型的要求，使用匿名对象调用默认构造函数

4. 迭代器的实现

若在数组上有一个int类型的指针，解引用是int类型的数据，再++可以加载下一个位置，因为物理空间是连续的

同样若在链表上，解引用类型为 node，再++不能到下一个节点，因为物理空间不连续
所以构造迭代器通过封装节点的指针来进行构造 (后面会讲)

第一个模板参数T

创建一个_list_iterator的类，来实现迭代器功能

template<class T>
    struct _list_iterator
    {
        typedef list_node<T> node;
        typedef _list_iterator<T> self;
        node* _node;
        
        _list_iterator(node* n)
            :_node(n)
        {

        }
        T& operator*()//解引用 
        {
            return _node->_data;
        }
        _list_iterator<T>& operator++()//返回迭代器
        {
            _node = _node->_next;//指向下一个节点
            return *this;
        }
        bool operator!=(const self&s)
        {
            return _node != s._node;
        }
    };

在list类中，调用迭代器实现begin()和end()功能
typedef _list_iterator<T,T&,T*> iterator，
通过typedef 将_list_node类模板定义为iterator

iterator begin()
		{
			return iterator(_head->_next);//通过匿名对象访问第一个数据
		}
		iterator end()
		{
			return iterator(_head);//通过匿名对象访问最后一个数据的下一个
		}

在list类中实现begin()和end()，内部调用_list_node类的构造函数

const迭代器

假设第一个代表的是T * ，而第二个代表的 T * const，保护迭代器本身不可以被修改，而我们想要保护迭代器指向的内容不可被修改即 const T*

复制_list_iterator类中的内容，并将名字修改为const_list_iterator
只需修改*operator类型为cosnt T& ，说明解引用后的数据返回不能被修改

template<class T>
    struct _list_const_iterator
    {
        typedef list_node<T> node;
        typedef _list_const_iterator<T> self;
        node* _node;

        _list_const_iterator(node* n)
            :_node(n)
        {

        }
        const T& operator*()//解引用 
        {
            return _node->_data;
        }
        self& operator++()//前置++
        {
            _node = _node->_next;//指向下一个节点
            return *this;
        }
        self& operator++(int)//后置++
        {
            self ret = *this;
            _node = _node->_next;
            return ret;
        }
        self& operator--()//前置--
        {
            _node = _node->_prev;
            return *this;
        }
        self& operator--(int)//后置--
        {
            self ret = *this;
            _node = _node->_prev;
            return ret;
        }
        bool operator!=(const self& s)//!=
        {
            return _node != s._node;
        }
        bool operator==(const self& s)//==
        {
            return _node == s._node;
        }
    };

第二个模板参数Ref

迭代器和const迭代器只有 *operator 的返回值不同，
只需在模板中添加一个参数即可使用一个迭代器实现迭代器和const 迭代器的功能

第三个模板参数Ptr

对于内置类型int使用解引用找到对应数据，而自定义类型需使用->寻找下一个节点