代码仓库：yanglianoo/My_STL at timer (github.com)

1.List概述

C++标准模板库（STL）中的list是一个双向链表容器，提供了在链表中高效存储和访问数据的功能。它是一个模板类具有以下特性：

  1. 链表结构：list是由节点组成的链表，每个节点包含数据以及指向前一个节点和后一个节点的指针。这种结构使得在list中插入、删除和移动元素非常高效，因为不需要像动态数组那样进行内存的移动和重分配。
  2. 双向访问：list支持双向访问，可以从链表的开头或末尾快速访问元素。你可以使用迭代器进行正向或反向遍历，也可以使用front()和back()函数访问第一个和最后一个元素。
  3. 动态大小：list的大小可以动态增长或缩小，无需预先分配固定大小的内存。
  4. 插入和删除：在list中插入和删除元素非常高效。通过使用迭代器，可以在常数时间内在任意位置插入或删除元素。
  5. 不支持随机访问：list不支持通过索引进行随机访问，这意味着不能像数组那样使用索引来访问元素。如果需要随机访问，vector可能更适合。
  6. 没有连续存储：由于list是一个链表，它的元素在内存中不是连续存储的，这可能会对缓存性能产生一些影响。
  7. 不支持快速的随机访问、排序和二分查找：由于没有随机访问，对list进行排序和二分查找会比较低效。如果需要这些功能，你可以考虑使用vector或deque容器。

STL库中list的定义如下:

template<
    class T,
    class Allocator = std::allocator<T>
> class list;
T 元素的类型。T 必须满足可复制赋值 (CopyAssignable) 和可复制构造 (CopyConstructible) 的要求。
Allocator 用于获取/释放内存及构造/析构内存中元素的分配器。类型必须满足分配器 (Allocator) 的要求。
成员函数
(构造函数) 构造 list (公开成员函数)
(析构函数) 析构 list (公开成员函数)
operator= 赋值给容器 (公开成员函数)
assign 将值赋给容器 (公开成员函数)
get_allocator 返回相关的分配器 (公开成员函数)
元素访问
front 访问第一个元素 (公开成员函数)
back 访问最后一个元素 (公开成员函数)
迭代器
begincbegin(C++11) 返回指向起始的迭代器 (公开成员函数)
endcend(C++11) 返回指向末尾的迭代器 (公开成员函数)
rbegincrbegin(C++11) 返回指向起始的逆向迭代器 (公开成员函数)
rendcrend(C++11) 返回指向末尾的逆向迭代器 (公开成员函数)
容量
empty 检查容器是否为空 (公开成员函数)
size 返回容纳的元素数 (公开成员函数)
max_size 返回可容纳的最大元素数 (公开成员函数)
修改器
clear 清除内容 (公开成员函数)
insert 插入元素 (公开成员函数)
emplace(C++11) 原位构造元素 (公开成员函数)
erase 擦除元素 (公开成员函数)
push_back 将元素添加到容器末尾 (公开成员函数)
emplace_back(C++11) 在容器末尾就地构造元素 (公开成员函数)
pop_back 移除末元素 (公开成员函数)
push_front 插入元素到容器起始 (公开成员函数)
emplace_front(C++11) 在容器头部原位构造元素 (公开成员函数)
pop_front 移除首元素 (公开成员函数)
resize 改变容器中可存储元素的个数 (公开成员函数)
swap 交换内容 (公开成员函数)

参考链接：std::list - cppreference.com

2. 构造节点

list的数据结构有两种，一种是双向链表，结构如下：

图解几种常见的线性表 - 命中水

在双向链表中，每一个节点为一个node，node包含一个指向上一个节点的prev指针和指向下一个节点的next指针，头节点的prev指针指向nullptr，尾节点的next指针指向nullptr。

一种是双向循环链表，和双向链表不同的就是，双向循环链表头节点的prev指针指向了尾节点，尾节点的next指针指向了头节点，由此组成了一个循环。

图解几种常见的线性表 - 命中水

我们实现的list是基于双向链表的，list是一个C++的类，由很多个节点构成，因此先来定义一下节点的数据结构，node节点由两个指针和存储的数据组成，是一个模板类，定义如下：

template <typename T> struct list_node
{
    T data;
    list_node<T>* prev;
    list_node<T>* next;
    list_node(const T& value)
            :next(nullptr)
            ,prev(nullptr)
            ,data(value)
    {}
};

3.构造迭代器

在list的使用种，用两种类型的迭代器，一种是普通的iterator，还有一种就是不可修改的const_iterator，这里的不可修改是指节点的数据不可修改，迭代器构造如下，和vector的迭代器类似，需要去重载不同的操作符。

template<class T, class Ref, class ptr>
struct list_iterator
{
	typedef list_iterator<T, Ref, ptr> self;
	typedef list_node<T> Node;
	Node* _node;
		 
	list_iterator(Node* node)
		:_node(node)
		{}
 
		//拷贝构造、赋值重载，默认浅拷贝即可
		//析构函数，指针指向的节点不属于迭代器的，无需自己销毁
 
	//解引用,*it = it.operator*()
	Ref& operator* ()
	{
		return _node->_data;
	}
	ptr operator-> () //本来调用为it->->_value,编译器通过处理省略了一个->
	{
		return &(_node->_data);
	}
	//前置++
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//后置++
	self operator++(int)
	{
		self tmp = *this;
		_node = _node->_next;
		return tmp;
	}
	//前置--
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	//后置--
	self operator--(int)
	{
		self tmp = *this;
		_node = _node->_prev;
		return *this;
	}
 
	//比较
	bool operator != (const self& it) const
	{
		return _node != it._node;
	}
	bool operator == (const self& it) const
	{
		return _node == it._node;
	}
};

在list_iterator内部维护了一个list_node<T>*类型的指针，用来指向list的每一个节点，这里解释一下为啥list_iterator模板类为啥有三个模板参数，那是为了方便通过typedef来定义iterator和const_iterator，在后面list类中可以如下定义：

typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;

4.构造list类

首先list类中包含了如下的成员变量，除了一个node类型的指针还维护了一个_size，当对list容器进行操作时，需要对_size实现增减操作。由于采用循环链表实现，所以当初始化链表时只需要定义一个头节点，让head节点的prev和next指针都指向自己就可以了.

template <typename T> class list{
    typedef list_node<T> Node;
	typedef list_iterator<T, T&, T*> iterator; //普通迭代器
	typedef list_iterator<T, const T&, const T*> const_iterator; //const迭代器
private:
    Node* _head;
    size_t _size;
	void empty_initialize()
    {
        _head = new Node(T());
        _head->_next = _head;
        _head->_prev = _head;

        _size = 0;
    }
 public:
    //定义默认构造函数
   list(){ empty_initialize(); }
    //定义析构函数
   ~list()
    {
        clear();
        delete[] _head;
        _head = nullptr;
    }
 }

然后我们来定义一些和迭代器有关的函数，首先是begin()和end()，用来返回头节点指针和尾节点指针，这里我们定义_head->next为begin，end为_head，然后有两个重载版本。

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

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

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

2.1 容量

和容量相关的接口比较简单，这里不赘述，代码如下：

public:
    size_t size()
    {
        return _size;
    }

    bool empty()
    {
        return begin() == end();
    }

2.2 修改器

在实现其他修改器之前，可先定义insert和erase函数,代码逻辑并不复杂，实现如下：

 //往pos位置插入元素T
iterator insert(iterator pos, const T& value )
    {
        Node* cur = pos._node;
        Node* prev = cur->_prev;

        Node* new_node = new Node(value);
        new_node->_prev = prev;
        new_node->_next = cur;

        
        prev->_next = new_node;
        cur->_prev = new_node;

        _size++;
        //隐式转换为iterator
        return new_node;
    }
//删除pos位置的节点
    iterator erase(iterator pos)
    {
        assert(pos != end());

        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* next = cur->next;

        prev->_next = next;
        next->_prev = prev;

        _size--;
        delete [] cur;

        return next;

    }

// 移除范围为 [first, last) 的元素
iterator erase( iterator first, iterator last )
    {
        if(first == last) { return last;}

        Node* first_node = first._node;
        Node* last_node = last._node;

        Node* prev = first_node->_prev;
        Node* next = last_node;

        prev->_next = next;
        next->_prev = prev;

        size_t count = 0;
        while (first_node != last_node)
        {
            Node* cur = first_node;
            first_node = first_node->_next;
            delete [] cur;
            count++; 
        }
        _size-=count;
        return next;
    }

其他的修改器就可基于insert和erase函数来实现：

public:
    void clear()
    {
        erase(begin(),end());
    }

    void push_back(const T& value)
    {
        insert(end(),value);
    }

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

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

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

2.3 元素访问

提供了访问头节点和尾节点数据的接口：

public:

    T& front()
    {
        return *begin();
    }

    T& back()
    {
        return *(--end());
    }

2.4 其他构造函数

public:
    list(size_t count, const T& value)
    {
        for (size_t i = 0; i < count; ++i) {
            push_back(value);
            _size++;
        }
    }

    list(size_t count)
    {
        for (size_t i = 0; i < count; ++i) {
            push_back(T());
            _size++;
        }
    }
    template <typename InputIt>
    list(InputIt first, InputIt last) : list() 
    {
		while (first != last)
		{
			push_back(*first);
			++first;
            _size++;
		}
    }

    list(const list& other): list() 
    {
		list<T> tmp(other.begin(), other.end());
		swap(_head, tmp._head);
    }

    list(std::initializer_list<T> init) : list()
    {
        for (const T& value : init) {
            push_back(value);
            _size++;
        }
    }
    list<T>& operator=(const list<T> & other)
    {
        if (this == &other) 
        {
            return *this;
        }
        clear();
        for(const T& value : other)
        {
            push_back(value);
            _size++;
        }
        return *this;
    }
    list<T>& operator=( std::initializer_list<T> ilist )
    {
        clear();
        for (const T& value : ilist) 
        {
            push_back(value);
            _size++;
        }
        return *this;

    }

5. 结语

list已完成，未进行测试，list是比较简单的，当然我们还有一些机制没有实现，比如逆向迭代器，assign函数等，不过核心的接口都已经实现，后续可完善。