STL c++ list——模拟实现

结点类的模拟实现

list是一个带头双向循环链表

因需要实现一个节点类，其中包含哨兵位（用来标识位置），节点信息（val数据，prev后指针，next后指针）

template<class T>
struct list_node
{T _data;list_node<T>* _next;//指向下一个list_node<T>* _prev;//上一个list_node(const T& x=T()):_data(x),_next(nullptr),_prev(nullptr){}
};

知识点：构造函数

• 在后面要new开空间，需要构造分为要带参和不带的 --》全缺省 T()给个缺省值应对不同类型
• 为什么用struct--》当类中全部都是公有，一般用struct （其实和class没什么区别）

迭代器类的模拟实现

模拟迭代器的意义

之前模拟实现string和vector时都没有说要实现一个迭代器类，为什么实现list的时候就需要实现一个迭代器类了呢？

string和vector

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

list 

list来说，其各个结点在内存当中的位置是随机的，并不是连续的，我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作。

 

总结： list迭代器类，实际上就是对结点指针进行了封装，对其各种运算符进行了重载。 

 普通迭代器

构造函数

// 构造函数，接收一个节点指针，用于初始化迭代器，使其指向传入的节点list_iterator(Node* node) :_node(node) {} 

前置 ++ 运算符重载（operator++() ）

前置 ++ 原本的作用是将数据自增，然后返回自增后的数据。对于链表迭代器的前置 ++，目的是让迭代器指向下一个节点并返回修改后的迭代器自身。

// 前置++
Self& operator++() 
{_node = _node->_next; // 让结点指针指向下一个结点return *this; // 返回自增后的迭代器自身引用
}

此函数先让迭代器指向的节点指针移动到下一个节点，再返回修改后的迭代器自身引用。

前置 -- 运算符重载（operator--() ）

前置 -- 原本的作用是将数据自减，然后返回自减后的数据。对于链表迭代器的前置 --，要让迭代器指向前一个节点并返回修改后的迭代器自身。

// 前置--
Self& operator--() 
{_node = _node->_prev; // 让结点指针指向前一个结点return *this; // 返回自减后的迭代器自身引用
}

该函数让迭代器的节点指针移动到前一个节点，再返回移动后的迭代器自身引用。

后置 ++ 运算符重载（operator++(int) ）

后置 ++ 原本是先返回数据原来的值，然后再将数据自增。对于链表迭代器的后置 ++，需先记录当前迭代器状态，再让迭代器移动到下一个节点，最后返回原始状态的迭代器。

// 后置++
Self operator++(int) 
{Self tmp(*this); // 记录当前结点指针的指向，也就是记录迭代器当前状态_node = _node->_next; // 让结点指针指向下一个结点return tmp; // 返回自增前的迭代器，即记录的原始状态的迭代器
}

函数先保存迭代器原始状态，再使其移动到下一个节点，最后返回原始迭代器。

知识点：C++ 规定后置自减运算符重载函数需要带一个 int 类型的参数，这个参数在函数实现中通常不会被使用，它仅仅是作为一个标记，用于编译器区分前置和后置运算符。  

后置 -- 运算符重载（operator--(int) ）

后置 -- 原本是先返回数据原来的值，然后再将数据自减。对于链表迭代器的后置 --，要先记录当前迭代器状态，再让迭代器移动到前一个节点，最后返回原始状态的迭代器。

// 后置--
Self operator--(int) 
{Self tmp(*this); // 记录当前结点指针的指向，即记录迭代器当前状态_node = _node->_prev; // 让结点指针指向前一个结点return tmp; // 返回自减前的迭代器，即记录的原始状态的迭代器
}

此函数先保存迭代器当前状态，再让其指向前一个节点，最后返回原始迭代器。

解引用运算符重载（operator*() ）

解引用运算符 * 原本用于获取指针所指向的数据。对于链表迭代器的 * 运算符重载，目的是获取当前所指向节点存储的数据的引用，以便读写。

// 解引用运算符重载
T& operator*() 
{return _node->_data; // 返回当前节点存储的数据的引用
}

该函数返回当前节点中存储的数据的引用。

箭头运算符重载（operator->() ）

箭头运算符 -> 通常用于通过指针访问结构体或类的成员。对于链表迭代器的 -> 运算符重载，是为了方便访问当前所指向节点存储数据的成员。

// 箭头运算符重载
T* operator->() 
{return &_node->_data; // 返回当前节点存储数据的指针
}

函数返回当前节点存储数据的指针，可使用 迭代器->成员 访问节点数据成员。

不等于运算符重载（operator!=() ）

不等于运算符 != 用于判断两个对象是否不相等。对于链表迭代器的 != 运算符重载，是为了判断两个迭代器是否指向不同的节点。

// 不等于运算符重载
bool operator!=(const Self& s) 
{return _node != s._node; // 判断当前迭代器和传入迭代器所指向的节点是否不同
}

此函数比较两个迭代器所指向的节点指针是否不同，不同则返回 true。

const迭代器

const迭代器与普通不同点在于要单独实现个类（const 迭代器负责只读遍历）并且在类中的 *， -> 的返回值和其他的不同

• 普通迭代器：可读可写，通过重载的 operator* 和 operator-> 返回值无 const 修饰，能修改指向的 list 元素 。比如 *it = newValue;（it 为普通迭代器）可修改元素值。

• const 迭代器：只读， operator* 返回 const T& ，operator-> 返回 const T* ，禁止通过迭代器修改 list 元素。若 *it = newValue;（it 为 const 迭代器），编译器会报错。

• const 迭代器指向的内容不能改变 所以要模拟前置const

 普通类和const类结合

先看编译器底层

这里我们所实现的迭代器类的模板参数列表当中为什么有三个模板参数？

template<class T, class Ref, class Ptr>

普通迭代器和const迭代器。

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

这里我们就可以看出，迭代器类的模板参数列表当中的Ref和Ptr分别代表的是引用类型和指针类型。

当我们使用普通迭代器时，编译器就会实例化出一个普通迭代器对象；当我们使用const迭代器时，编译器就会实例化出一个const迭代器对象。

// 定义普通迭代器类型
// 这里使用了模板参数T，将list_iterator类模板实例化为普通迭代器，Ref为T&，Ptr为T*，意味着可以对元素进行读写操作
typedef list_iterator<T, T&, T*> iterator;
// 定义常量迭代器类型
// 同样使用模板参数T，但Ref为const T&，Ptr为const T*，表示只能对元素进行只读操作
typedef list_iterator<T, const T&, const T*> const_iterator;// 定义list_iterator类模板，包含三个模板参数
// T 表示链表中存储的数据类型
// Ref 表示引用类型，用于operator*返回值的类型，普通迭代器时为T&，常量迭代器时为const T&
// Ptr 表示指针类型，用于operator->返回值的类型，普通迭代器时为T*，常量迭代器时为const T*
template<class T, class Ref, class Ptr>
struct list_iterator
{// 定义Node类型为list_node<T>，方便后续使用，list_node<T>应该是链表节点的类型typedef list_node<T> Node;// 定义Self类型为list_iterator<T, Ref, Ptr>，方便在类内使用自身类型typedef list_iterator<T, Ref, Ptr> Self;// 指向链表节点的指针，用于存储迭代器当前指向的节点Node* _node;// 构造函数，接收一个节点指针，用于初始化迭代器，使其指向传入的节点list_iterator(Node* node):_node(node){}// 重载*运算符，返回当前节点存储的数据的引用// 返回值类型为Ref，根据模板参数不同，普通迭代器时为T&，常量迭代器时为const T&Ref operator*(){return _node->_data;}// 重载->运算符，返回当前节点存储数据的指针// 返回值类型为Ptr，根据模板参数不同，普通迭代器时为T*，常量迭代器时为const T*Ptr operator->(){return &_node->_data;}// 重载前置++运算符，将迭代器指向下一个节点，并返回修改后的迭代器自身引用Self& operator++(){_node = _node->_next;return *this;}// 重载前置--运算符，将迭代器指向前一个节点，并返回修改后的迭代器自身引用Self& operator--(){_node = _node->_prev;return *this;}// 重载后置++运算符，先保存当前迭代器状态，然后将迭代器指向下一个节点，最后返回保存的原始迭代器Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}// 重载后置--运算符，先保存当前迭代器状态，然后将迭代器指向前一个节点，最后返回保存的原始迭代器Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}// 重载!=运算符，用于比较两个迭代器是否指向不同的节点// 返回true表示两个迭代器指向不同节点，否则返回falsebool operator!=(const Self& s){return _node != s._node;} // 重载==运算符，用于比较两个迭代器是否指向相同的节点// 返回true表示两个迭代器指向相同节点，否则返回falsebool operator==(const Self& s){return _node == s._node;}
};

知识点：对于->

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

	list<Date> lt;Date d1(2021, 8, 10);Date d2(1980, 4, 3);Date d3(1931, 6, 29);lt.push_back(d1);lt.push_back(d2);lt.push_back(d3);list<Date>::iterator pos = lt.begin();cout << pos->_year << endl; //输出第一个日期的年份
//相当于cout << pos.operator->()->_year << endl;

对于->运算符的重载，我们直接返回结点当中所存储数据的地址即可。

从逻辑上，原本应该是先调用重载的 operator-> 得到自定义类型（如 Date ）的指针 pd ，然后再用这个指针 pd 去访问成员变量，即 pd->year ，也就是理论上会出现 pos->->year 这种形式 。但 C++ 语法规定，当重载了 -> 运算符返回一个指针后，编译器会自动处理，使得我们可以直接写 pos->year ，省略掉第二个 -> ，编译器会根据重载规则理解为先用 pos-> 调用重载函数得到指针，再用指针访问成员 。

 

默认成员函数

• 构造函数

list 是一个带头双向循环链表。在构造一个 list 对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己。这样就构建好了一个空链表的初始结构。

// 构造函数
list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}

• 拷贝构造函数

拷贝构造函数的作用是根据所给 list 容器，构造出一个新对象。首先申请一个头结点并完成初始化，然后遍历原容器，将其中的数据逐个尾插到新构造的容器中。

// 拷贝构造函数
list(const list<T>& lt)
{_head = new Node;_head->_next = _head;_head->_prev = _head;for (auto it = lt.begin(); it != lt.end(); ++it){push_back(*it);}
}

1. 赋值运算符重载函数

• 写法一：传统写法
  先调用 clear 函数将原容器清空，避免残留数据干扰。然后遍历传入容器，将其中的数据逐个尾插到清空后的容器中，实现赋值操作。

// 传统写法
list<T>& operator=(const list<T>& lt)
{if (this != &lt){clear();for (auto it = lt.begin(); it != lt.end(); ++it){push_back(*it);}}return *this;
}

• 写法二：现代写法
  利用编译器机制，故意不使用引用接收参数，让编译器自动调用拷贝构造函数构造出一个临时 list 对象。然后调用 swap 函数将原容器与该临时对象进行交换，实现高效赋值。

// 现代写法
list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

析构函数
对象析构时，先调用 clear 函数清理容器中的数据，释放所有有效节点。接着释放头结点，最后将头指针置空，完成资源的彻底释放。

// 析构函数
~list()
{clear();delete _head;_head = nullptr;
}

迭代器相关函数

begin 和 end

• 对于普通 list 对象：
  begin 函数返回第一个有效数据的迭代器，即使用头结点后一个结点的地址构造出来的迭代器；end 函数返回最后一个有效数据的下一个位置的迭代器，也就是头结点地址构造的迭代器。

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

• 对于 const list 对象：
  重载 const 版本的 begin 和 end 函数，返回 const 迭代器，保证在遍历 const 对象时不能修改数据。

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

访问容器相关函数

front 和 back

对于普通 list 对象：
front 函数返回第一个有效数据的引用，通过解引用 begin 函数返回的迭代器实现；back 函数返回最后一个有效数据的引用，通过先将 end 函数返回的迭代器前置递减，再解引用实现。

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

• 对于 const list 对象：
  重载 const 版本的 front 和 back 函数，返回 const 引用，防止通过这些函数修改 const 对象中的数据。

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

插入、删除函数

insert

insert 函数可以在所给迭代器之前插入一个新结点。先根据迭代器得到对应位置的结点指针 cur，再找到 cur 的前驱结点指针 prev，根据给定数据构造待插入结点 newnode，然后建立 newnode 与 cur、prev 之间的双向链接关系。

iterator insert(iterator pos, const T& x)
{assert(pos._node);Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);
}

 

erase

erase 函数用于删除所给迭代器位置的结点。先根据迭代器得到对应位置的结点指针 cur，以及其前驱结点指针 prev 和后继结点指针 next，释放 cur 结点，再建立 prev 和 next 之间的双向链接关系，最后返回删除位置的下一个迭代器。

// erase函数
// 功能：删除所给迭代器pos位置的结点
// 参数：iterator pos，指定要删除结点位置的迭代器
// 返回值：iterator，返回指向删除位置下一个结点的迭代器
iterator erase(iterator pos)
{// 确保迭代器pos有效assert(pos._node);// 确保要删除的不是end迭代器指向的位置（头结点）assert(pos != end());// 获取迭代器pos指向的结点指针Node* cur = pos._node;// 获取cur结点的前驱结点指针Node* prev = cur->_prev;// 获取cur结点的后继结点指针Node* next = cur->_next;// 建立prev和next结点之间的双向链接关系prev->_next = next;next->_prev = prev;// 释放要删除的cur结点delete cur;// 返回指向删除位置下一个结点的迭代器return iterator(next);
}

push_back 和 pop_back

• push_back 函数在链表尾部插入数据，复用 insert 函数，在 end 迭代器位置前插入元素。

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

• pop_back 函数删除链表尾部元素，复用 erase 函数，删除 end 迭代器前置递减位置的元素。

void pop_back()
{assert(!empty());erase(--end());
}

push_front 和 pop_front

• push_front 函数在链表头部插入数据，复用 insert 函数，在 begin 迭代器位置前插入元素。

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

• pop_front 函数删除链表头部元素，复用 erase 函数，删除 begin 迭代器位置的元素。

void pop_front()
{assert(!empty());erase(begin());
}

其他函数

size

size 函数用于获取当前容器中的有效数据个数。由于 list 是链表结构，只能通过遍历的方式逐个统计元素个数。

size_t size() const
{size_t count = 0;for (auto it = begin(); it != end(); ++it){++count;}return count;
}

empty

empty 函数用于判断容器是否为空，通过比较 begin 和 end 迭代器是否相等来判断，相等则表示容器为空。

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

clear

clear 函数用于清空容器中的数据。从第一个有效数据结点开始，逐个删除结点，直到只剩下头结点，完成数据清理。

void clear()
{auto it = begin();while (it != end()){auto next = it;++next;delete it._node;it = next;}_head->_next = _head;_head->_prev = _head;
}