自定义 STL list模板类 —— MyList 实现

MyList 实现

STL 中list 将元素按顺序储存在链表中，与 向量 相比，它允许快速的插入和删除，但是随机访问却比较慢。本文将实现简单的 list功能。

---

头文件及其命名空间

#include <iostream>
#include <memory>		// 内存配置器包含的头文件   需要用到

using namespace std;

内存适配器可以点击 C++11 —— allocator类了解，或者点击 C++11 —— STL 存储分配器简单使用

---

定义结点

template <typename T>
struct __list_node
{
    typedef __list_node* list_node_pointer;

    list_node_pointer next;	// 后指针
    list_node_pointer prev;    	// 前指针
    T		      data;	// 存放数据
}

1. 为什么用 typename T ,而不用 class T ? 因为typename更加标准。主要是个人习惯 ^_
2. typedef 取别名，方便记忆。
3. list 模板类是一个双向链表，有两个指针分别指向前一个结点与后一个结点。

---

list 迭代器

迭代器用来操作容器

template <typename T>
struct __list_iterator
{
    // 迭代器本身
    typedef __list_iterator<T>	self;		// 迭代器本身
    typedef __list_node<T>* 	link_type;		// 结点指针  操作list

    // 只要一个结点指针，就可以操作整个 list
    link_type 			ptr; 

    __list_iterator(link_type p = nullptr) : ptr(p) {} 		// 构造数据
    __list_iterator(const self& that) : ptr(that.ptr) {} 	// 拷贝

    // 重载 == 
    bool operator==(const self& that)const
    {
        return this->ptr == that.ptr;
    }

    // 重载 !=
    bool operator!=(const self& that)const
    {
        // return !(operator==(that))
        return this->ptr != that.ptr;  
    }

    T& operator*()const
    {
        return ptr->data;		// 返回数据
    }
    
    // 迭代器前++ 指向下一个结点
    slf& operator++()
    {
        ptr = ptr->next;
        return *this;
    }
  
    // 后++ 先返回 再自增
    self operator++(int)	// 加个int 分开区别   避免报错
    {
        self tmp = *this;
        ++*this;
        return tmp;
    }
	
    // -- 操作   与++操作差不多
    self& operator--()
    {
        ptr = ptr->prev;
        return *this;
    }
  
    self operator--(int)
    {
        self tmp = *this;
        --*this;
        return tmp;
    }
};

 迭代器的定义本身不难，不要把list 与迭代器混为一起。
 此处我们的迭代器基本已经完成了。

---

MyList 类

简单的定义list模板类中的几种方法

template <typename T>
class MyList
{
protected:
    // 取一些别名  方便使用
    typedef __list_node<T>		list_node;	// 结点
    
    typedef T				value_tye;	// 值类型
    typedef value_type* 		pointer;	// T*
    typedef const value_type*		const_pointer	// const T*
    typedef size_t			size_type;
    
    // 空间适配器	分配内存
    /*
    大概实现
    	一级空间配置器	直接封装了 molloc    free
   	 二级空间配置器	内存池   自有链表  （不需要知道具体是如何实现的）
    实现原理	
  	  用户申请内存 > 128 ?   一级 ：二级
    设计模式
  	  适配器模式	单例模式	   享元模式
    */

    // 分配一个 list_node大小的内存
    allocator<list_node>	nodeAllocator;

public:
    typedef list_node*		link_type;	// 指向结点的指针
    typedef __list_iterator<T>	iterator;	// 迭代器

protected:
    // 只需要一结点指针就可以表示整个 list
    link_type			node;
    
    // 空间配置器	内部会选择更合适的方式
    // 分配新节点 (内存)	allocate
    link_type alloc_node()
    {
        return nodeAlloctor.allocate(sizeof(list_node));
    }

    // 释放空间		不会析构结点 
    void dealloc_node(list_node p)
    {
        nodeAllocator.deallocate(p);
    }

    // 分配新节点（内存）用value 构造 新节点里面内容
    link_type alloc_dtor_node(const T& value)
    {
        // 分配结点空间
        link_type p = alloc_node();
        // 构造内存
        nodeAllocator.construct(&p->data, value);

        return p;
    }
    
    // 析构结点	 释放内存
    void dealloc_dtor_node(list_node p)   
    {
        nodeAlloator.detroy(&p->data);
        deallc_node(p);
    }

    // 空的时候初始化
    void empty_ini()
    {
        node = alloc_node();		// 分配一个结点空间 让node 指向它
        // 只有一个结点的时候  指向自己   没有元素值
        node->prev = node;
        node->next = node;
    }

public:
    MyList()
    {
        // list  初始化
        empty_init();
    }

    iterator begin()
    {
        return node->next;		// node
    }
    
    iterator begin()const		// 常迭代器
    {
        return node->next;
    }
    
    iterator end()			// end 在begin前一个 形成环状的
    {
        return node;			// node->prev
    }

    iterator end()const
    {
        return node;
    }

    // 判空
    bool empty()const
    {
        return node == node->next;	// 判断是不是等于本身
    }

    // 插入数据	   结点插入操作  画图可以理解的更快一点
    iterator insert(iterator pos, const T& value)
    {
        // 先创造一个结点
        link_type tmp = alloc_dtor_node(value);
        // 寻找位置 插入
        tmp->next = pos.ptr;
        tmp->prev = pos.ptr->prev;

        // 可以画图理解
        pos.ptr->prev->next = tmp;
        pos.ptr->prev = tmp;
        
        return pos;
    }

    // 屁股插入数据
    void push_back(const T& value)
    {
        insert(end(), value);		// 在尾部插入数据 
    }
};

插入结点：

画的有点丑 ^_

---

写到这里，我们就可以使用MyList 操作了

int main()
{
    MyList<int> mylist;

    // 从屁眼插入数据
    mylist.push_back(10);
    mylist.push_back(30);

    // 在指定位置插入数据
    mylist.insert(++mylist.begin(), 20);

    // 循环遍历数据
    for(auto i = mylist.begin(); i != mylist.end(); i+++
    {
        cout << *i << endl;
    }
}

---

2021