【C++STL】list的模拟实现

✨ Blog’s 主页: 白乐天_ξ( ✿＞◡❛)
🌈 个人Motto：他强任他强，清风拂山冈！
🔥 所属专栏：C++深入学习笔记
💫 欢迎来到我的学习笔记！

一、三个类与成员函数接口

在list.h文件中实现三个类的框架以及各种成员函数接口。

结点类：

// 模拟实现list当中的结点类（一个个的结点）（结点封装成类）
	// 一个节点存储的信息有：数据、前驱指针、后继指针，这就是该结点类的成员变量
	template<class T>
	struct _list_node
	{
		// 成员函数
		_list_node(const T& val = T());// 构造函数

		// 成员变量：
		T _val;					// 数据域
		_list_node<T>* _next;   // 后继指针
		_list_node<T>* _prev;	// 前驱指针
	};

迭代器类：

// 模拟实现list的迭代器（迭代器封装成类）
template<class T,class Ref,class Ptr>
struct _list_iterator
{
	typedef _list_node<T> node;// node：结点类的类型名称
	typedef _list_iterator<T, Ref, Ptr> self;// self：迭代器类的类型名称

	_list_iterator(node* pnode);// _list_iterator构造函数

	// 各种运算符重载函数
	self operator++();// 返回值是self，返回值是迭代器类型
	self operator++(int);
	self operator--();
	self operator--(int);
	bool operator == (const slef & s) const;
	bool operator!=(const self& s) const;
	Ref operator*();
	Ptr operator->();

	// 成员变量：
	node* _pnode;// 一个指向结点的指针
};

list链表类：

	template<class T>
	class list // 链表封装成类
	{
	public:
		typedef _list_node<T> node;									 // node：结点类的类型名称
		typedef _list_iterator<T, T&, T*> iterator;					 // 普通迭代器的类型名称
		typedef _list_iterator<T, const T&, const T*> const_iterator;// const对象的迭代器

		// 默认成员函数
		list();
		list(const list<T>& lt);// 
		list<T> operator=(const list<T> lt);// 赋值运算符的重载
		~list();// 析构函数：完成结点的释放

		// 迭代器相关函数
		iterator begin();
		iterator end();
		const_iterator begin() const;
		const_iterator end() const;

		// 访问容器相关函数
		T& front();
		T& back();
		const T& front() const;
		const T& back() const;

		// 插入删除函数
		void insert(iterator pos, const T& x);
		iterator erase(iteartor pos);
		void push_back(const T& x);// 插入数据（尾插）
		void clear();
		void empty() const;
		void swap(list<T>& lt);

		// 其他函数
		size_t size() const;
		void resize(size_t n, const T& val = T());
		void clear();
		bool empty() const;
		void swap(list<T>& lt);

	private:
		node* _head;// 指向链表头节点的指针
	};

二、结点类的模拟实现

list的底层是一个带头双向循环链表，因此我们如果想要实现list，首先需要实现一个结点类，完成一个个的结点的创建。结点的信息包括：数据（_val）、前驱指针（_prev）、后继指针（_next）。

对于该结点类的成员函数来说，我们只需要实现一个构造函数即可。因为该结点类只需要根据数据来构造一个结点，而结点的释放则由list的析构函数来实现。

class与struct关键字选择：如果不想用访问限定符来限制成员的访问，所有的成员都会用struct。struct默认是公有protected，class默认是私有private。这里选择使用struct：list中会频繁地访问成员变量，想要成员变量都是公有的，就可以使用struct，但是如果使用class的话，就会用到很多的友元friend。

惯例上，如果不想让访问限定符限制成员的访问，所有的成员都设置为公有时，就使用struct；如果要大量访问成员变量时，就使用struct。

结点类的构造函数：根据所给数据构造出一个结点，该结点的数据域存储的是所给的数据，前驱指针与后继指针初始化为空指针。

// 结点类的模拟实现
template<class T>
struct _list_node
{
    _list_node(const T& val = T())// 结点类的构造函数
        :_val(val)
        ,_prev(nullptr)
        ,_next(nullptr)
    {}
    // 若构造结点时未传入数据，则默认以list容器所存储的默认构造函数所构造出来的值为传入数据
};

三 、迭代器类的模拟实现

3.1.迭代器类的由来

之前string、vector实现时都没有实现过迭代器类，为什么这里要实现一个迭代器类呢？

原因：string、vector对象都将他们的数据存储在了一块连续的内存空间，我们通过自增、自减以及解引用操作就可以对相应位置的数据进行一系列操作。因此string和vector当中的迭代器就是原生指针。

template<class T>
class vector
{
public:
    typedef T* iterator;// vector的迭代器就是原生指针
};

但是list容器中的各个结点在内存当中的位置是随机的，并不是连续的，我们不能仅仅通过结点指针的自增自减解引用等操作对相应的结点的数据进行操作。而迭代器的意义就是：让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行操作。

既然list的结点指针的行为不满足迭代器的定义，我们可以对这个结点的指针进行封装，然后对结点指针的各种运算符操作进行重载，让我们可以用和string和vector中的迭代器一样的方式使用list当中的迭代器。比如：使用list当中的迭代器进行++操作，实际上就执行了p = p->next;，这种功能可以利用运算符重载来实现。

总结：list的迭代器类实际上就是对结点指针进行了封装，对各种运算符进行了重载，使得结点指针的各种行为看起来与普通迭代器一样。

3.2.模板参数说明、

这里的迭代器类使用的模板参数有三个。

template<class T, class Ref, class Ptr>

在list的模拟实现里，我们有两种类型的迭代器，const迭代器和普通迭代器。

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

根据typedef操作中，我们可以知道，T、Ref、Ptr分别代表的是类型、引用类型和指针类型。

当我们使用普通迭代器时，编译器就会实例化出一个普通迭代器对象；当我们使用const迭代器时，编译器就会实例化出一个const迭代器对象。若该迭代器不传入这三个模板参数，就不能很好的区分普通迭代器和const迭代器。

3.3.构造函数

迭代器类的构造函数作用：对结点的指针进行封装，成员变量只有一个——结点指针。其构造函数直接根据所给结点指针 构造一个迭代器对象即可。

_list_iterator(node* pnode)// _list_iterator构造函数
    :_pnode(pnode)
{}

3.4.运算符重载

3.4.1.前置++

前置++：先让数据自增，然后返回自增后的数据。在这里的目的是：让结点指针“自增”即让结点指向下一个结点（后一个结点），然后返回自增后的结点指针。

// 前置++运算符：
self operator++() // 返回值是self，返回值是迭代器类型
{
    _pnode = _pnode->_next;// 指针指向下一个结点
    return *this;// 返回++之后的结点指针
}

3.4.2.后置++

后置++：先记录当前结点指针的指向，然后再让结点指针指向下一个结点（“自增”），然后返回“自增”前的结点指针。

// 后置++运算符
self operator++(int)
{
    node* tmp = *this->_pnode;
    _pnode = _pnode->_next;
    return tmp;
}

说明：self是当前迭代器对象的类型。

typedef _list_iterator<T, ref, Ptr> self;

3.4.3.前置–

前置--：先让结点指针指向前一个结点（“自减”），然后返回“自减”后的结点指针。

// 前置--运算符
self operator--()
{
    _pnode = _pnode->_prev;
    return *this;
}

3.4.4.后置–

后置--：先记录当前结点指针的指向，然后再让结点指针指向前一个结点（“自减”），再返回“自减”前的结点指针。

// 后置--运算符
self operator--(int)
{
    node* tmp = *this->_pnode;
    _pnode = _pnode->_prev;
    return tmp;
}

3.4.5. ==

==运算符：使用==运算符比较两个迭代器时，我们实际上是想知道这两个迭代器是否是同一个位置上的迭代器，也就是判断两个迭代器中的指针的指向是否相同。

bool operator == (const self& s) const
{
    return s._pnode == _pnode;// 判断两个结点指针是否相同
}

3.4.6. !=

!=运算符：和==运算符的作用相反，这里!=是判断两个两个迭代器的指针是否不同。

bool operator!=(const self& s) const
{
    return s._pnode != _pnode;
}

3.4.7. *

*运算符：在list的模拟实现中，*操作符的作用就是返回当前结点指针所指向的结点的数据，这里解引用后可能对数据就进行修改，因此使用引用返回，返回值类型Ref。

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

3.4.8. ->

使用到->运算符的场景：当list容器中的每个结点存储的不是内置类型，而是自定义类型如日期类时，那么我么如果得到某个位置的迭代器，我们可能会使用->运算符访问Date的成员。

    list<Date> lt;
    Date d1(2024, 10, 23);
    Date d2(2000, 1, 1);
    Date d3(1949, 9, 1);
    lt.push_back(d1);
    lt.push_back(d2);
    lt.push_back(d3);
    list<Date>::iterator pos = lt.begin();
    cout << pos->_year << endl; //输出第一个日期的年份

使用pos->_year这样的访问方式时，需要将日期类的成员变量设置为公有。因此->运算符的重载：直接返回结点当中所存储数据的地址。返回值类型Ptr。

Ptr operator->()
{
    return &_pnode->_val;// 返回结点当中所存储数据的地址
}

注意：这里本来应该是两个->的：原本的调用形式是pos->operator->_year，第一个->是指pos调用重载的operator->然后返回Date*的指针，第二个->是Date*的指针去访问对象中的成员变量_year。

一个地方连续两个->，影响程序的可读性，所以编译器做了特殊识别处理，省略一个->来增加程序的可读性。

四、list链表类的模拟实现

4.1.默认成员函数

4.1.1.构造函数

list是一个带头双向循环链表，在构造一个list对象时，直接申请了一个头结点，并让前驱指针和后继指针都指向自己。

代码：

// 无参构造函数
list()
{
    _head = new node;// 申请一个头结点
    _head->_next = _head;
    _head->_prev = _head;
}

4.1.2.拷贝构造函数

根据所给的list容器拷贝构造出一个对象。先申请一个头结点，让其前驱指针和后继指针都指向自己，然后将所给容器当中的数据通过遍历的方式一个个地尾插到新构造的容器里面。

// 拷贝构造函数
list(const list<T>& lt)
{
    _head = new node;
    _head->_next = _head;
    _head->_prev = _head;
    for (auto e : lt)
    {
        push_back(e);// 将容器lt当中的数据一个个尾插到新构造的容器里面
    }
}

4.1.3.赋值运算符的重载

1. 传统写法：先调用clear函数将原容器清空，然后将容器lt当中的数据，通过遍历的方式一个个尾插到清空厚的容器当中。

// 赋值运算符的重载的传统写法：
list<T> operator=(const list<T> lt)
{
    if (this != &lt)// 避免自己给自己赋值
    {
        clear();// 清空容器
        for (const auto& e : lt)
        {
            push_back(e);// 将容器中的数据一个个尾插到链表后面
        }
    }
    return  *this;
}

2. 现代写法：首先利用编译器机制，故意不是用引用接收参数，通过编译器哦自动调用list拷贝构造函数构造出一个list对象，然后调用swap函数将原容器与该list对象进行交换。

list<T> operator=(const list<T> lt)// 不是用引用接收参数//编译器会自动调用拷贝构造函数构造出一个list对象，然后调用swap函数将原容器与该list对象进行交换
{
    swap(lt);// 交换这两个对象
    return *this;
}

4.1.4.析构函数

先调用clear函数来清理容器中的数据，然后将头结点释放，最后将头指针置空。

// 析构函数：完成结点的释放
~list()
{
    clear();
    delete[] _head;
    _head = nullptr;
}

4.2.迭代器相关函数

4.2.1.begin和end

begin函数返回第一个有效数据的迭代器，end函数返回最后一个有效数据的笑一个位置的迭代器（即头节点的迭代器）。

对于list这个带头双向循环链表来说，第一个有效数据的迭代器就是使用头结点后一个结点的地址构造出来的迭代器，而其最后一个有效数据的下一个迭代器就是使用头节点的地址构造出来的迭代器（最后一个结点的下一个结点就是头结点）。

// 迭代器相关函数
iterator begin()
{
    return iterator(_head->_next);// 返回使用头结点的下一个结点的地址构造出来的普通迭代器
}
iterator end()
{
    return iterator(_head);// 返回使用头节点构造出来的迭代器
}

const对象的begin函数和end函数。

const_iterator begin() const// 
{
    return iterator(_head->_next);// 返回使用头结点的下一个地址构造出来的const迭代器
}
const_iterator end() const
{
    return iterator(_head);// 返回使用头结点的地址构造出来的const迭代器
}

4.3.容器访问的相关函数

4.3.1.front和back

front函数和back函数分别用于获取第一个有效数据和最后一个有效数据。因此，实现时就返回第一个有效数据的引用和最后一个有效数据的引用。

// front函数：获取第一个有效数据——直接返回第一个有效数据的引用
T& front()
{
    return *begin();// begin迭代器是第一个有效数据的指针
}
// back函数：获取最后一个有效数据——返回最后一个有效数据的引用
T& back()
{
    return *(--end());// end迭代器是头节点的指针
}

前面是对普通对象的访问，下面是const对象的访问。const对象调用front和back函数后所得到的数据不能被修改。

const T& front() const
{
    return *begin();// 返回第一个有效数据的const引用
}
const T& back() const
{
    return *(--end());// 返回最后一个有效数据的const引用
}

4.4.插入删除函数

4.4.1.insert

insert函数：在所给迭代器之前插入一个新的结点。

根据上图所示：先判断所给迭代器pos是否合法，然后创建相关指针——根据pos迭代器创建出结点指针cur、cur指针的前一个位置的结点指针prev，然后根据所给数据x构造一个带插入新结点，最后再建立新结点与cur、prev之间的双向关系。

// 插入：在所给迭代器pos之前插入一个新的结点
void insert(iterator pos, const T& x)
{
    assert(pos._pnode);

    // 创建相关的指针
    node* cur = pos._pnode;// 创建cur指针
    node* prev = cur->_prev;// 创建prev指针
    node* newnode = new node(x);// 用传入的数据x创建新结点

    // 建立newnode与cur之间的双向关系
    newnode->_next = cur;
    cur->_prev = newnode;

    // 建立newnode与prev之间的双向关系
    newnode->_prev = prev;
    prev->_next = newnode;
}

4.4.2.erase

erase函数：删除所给迭代器位置的结点。

先检测pos迭代器的合法性，然后创建相关指针——根据pos迭代器创建出结点指针cur、cur指针的前一个位置的结点指针prev、cur指针后一个位置的结点指针next；释放cur指针、建立prev和next之间当然双向关系。

// 插入：在所给迭代器pos之前插入一个新的结点
void insert(iterator pos, const T& x)
{
    assert(pos._pnode);

    // 创建相关的指针
    node* cur = pos._pnode;// 创建cur指针
    node* prev = cur->_prev;// 创建prev指针
    node* newnode = new node(x);// 用传入的数据x创建新结点

    // 建立newnode与cur之间的双向关系
    newnode->_next = cur;
    cur->_prev = newnode;

    // 建立newnode与prev之间的双向关系
    newnode->_prev = prev;
    prev->_next = newnode;
}

4.4.3.push_back和pop_back

push_back在头结点前插入数据，pop_back删除头结点的前一个结点（即最后一个结点）。

		// push_back：尾插
		void push_back(const T& x)
		{
			insert(end(), x);// 在头结点前面插入数据（头结点的前一个位置就是尾结点）
		}
		// pop_back：尾删
		void pop_back(const T& x)
		{
			erase(--end());
		}

4.4.4.push_front和pop_front

push_front函数是在第一个有效结点前插入结点（头插），pop_front是删除第一个有效结点（尾插）。

// push_front：头插
void push_front(const T& x)
{
    insert(begin(), x);// 在第一个有效结点前插入一个结点
}

// pop_front：头删
void pop_front()
{
    erase(begin());// 删除第一个有效结点
}

4.5.其他函数

4.5.1.size

size：获取当前容器中的有效数据个数，list链表中只能通过遍历的方式来逐个统计有效数据个数，不能直接通过size()函数获取。

// size：获取当前容器中的有效数据个数，list链表中只能通过遍历的方式逐个统计有效数据个数
size_t size() const
{
    size_t sz = 0;// 统计
    const_iterator it = begin();// 获取第一个有效数据的const_iterator
    while (it != end())// 通过遍历统计有效数据个数
    {
        sz++;
        it++;
    }
    return sz;// 返回有效数据个数
}

4.5.2.clear

clear函数：通过遍历的方式清空容器，逐个删除结点，只保留头结点。

// clear：通过遍历的方式清空容器，逐个删除结点，只保留头结点
void clear()
{
    iterator it = begin();// 从第一个迭代器开始
    while (it != end())// 逐个删除结点，只保留头结点
    {
        it = erase(it);// 不用++操作，因为erase间接++了
    }
}

4.5.3.resize

resize函数：

1. 若当前容器的size晓瑜所给的n，则尾插结点知道size为n。
2. 若当前容器的size大于所给n，则只保留前n个有效数据。

实现resize的方法是：设置一个变量len，用来记录当前所遍历的数据个数，然后开始遍历容器。在遍历的过程中如果：

1. len大于或者等于n时遍历结束，释放掉该结点厚的所有结点。
2. 容器遍历完成同时遍历结束，此时说明容器中的有效数据个数小于n，需要尾插结点，直到容器当中的有效数据个数为n时停止尾插。

// resize
void resize(size_t n, const T& val = T())
{
    iterator i = begin(); //获取第一个有效数据的迭代器
    size_t len = 0; //记录当前所遍历的数据个数
    while (len < n && i != end())
    {
        len++;
        i++;
    }
    if (len == n) //说明容器当中的有效数据个数大于或是等于n
    {
        while (i != end()) //只保留前n个有效数据
        {
            i = erase(i); //每次删除后接收下一个数据的迭代器
        }
    }
    else //说明容器当中的有效数据个数小于n
    {
        while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n
        {
            push_back(val);
            len++;
        }
    }
}

4.5.4.empty

empty函数：判断容器是否为空，可直接判断改容其的begin函数和end函数所返回的迭代器是否为同一个位置上的迭代器。

// 判断容器是否为空
bool empty() const
{
    return begin() == end();
}

4.5.5.swap

swap函数：交换两个容器，list容器中只存储了链表的头指针，所以交换两个容器的头指针即可。

在此处调用库中的swap函数时需要在swap之前加上::域作用限定符，告诉编译器这里优先在全局范围寻找swap函数，否则编译器会认为调用的是正在实现的swap函数（即就近原则）。

// swap：交换两个容器，list容器中只存储了链表的头指针，交换两个容器的头指针即可
void swap(list<T>& lt) 
{
    ::swap(_head, lt._head);
}

push_back：尾插一个节点。找尾：_head->_prev

void push_back(const T& x)// 插入数据x，类型是T，不允许修改，使用传引用传值
{
    // 插入数据
    Node* newnode = new Node(x);// 创建了一个结点
    Node tail = _head->_prev;// tail是最后就一个结点（尾插新节点之前），就是head的prev前驱指针

    // 连接四步骤：
    tail->_next = newnode;// 尾结点与新结点相连
    newnode->_prev = tail;
    newnode->_next = _head;
    _head->_prev = newnode;

    ++_size;
}