C++初阶(十六)--STL--list的模拟实现
目录
结点类的实现
迭代器类的模拟实现
迭代器类的模板参数说明
构造函数
*运算符重载
->运算符的重载
++运算符的重载
--运算符重载
!=运算符重载
==运算符重载
list类的模拟实现
成员变量
默认成员函数
构造函数
拷贝构造函数
赋值运算符重载
迭代器相关函数
begin和end
插入and删除
insert
erase
头插和头删
尾插和尾删
其他函数
size
resize
empty
clear
本篇博客会使用较多的模板编程，模拟实现迭代器，加深对模板编程的理解，这里只实现常用接口的模拟，部分不是很常用的接口用到时在翻阅手册即可，大多接口的使用在上篇博客中均已提到。所以本篇博客的重点在迭代器的模拟，因为链表的实现已经在C语言中的数据结构讲解过了。
本次我们需要实现三个类，我们经常说list在底层实现时就是一个链表，更准确来说，list实际上是一个带头双向循环链表。
因此我们要实现一个list肯定要实现一个结点类，这个结点里面存放着的信息有数据，前一个结点的地址和后一个结点的地址。对于该结点，我们只需要写一个构造函数，它的析构由我们的list的析构函数完成。
结点类的实现
template <class T>
struct list_node
{
T _date;
list_node* _prev;
list_node* _next;
list_node(const T& x = T())
:_date(x)
, _prev(nullptr)
, _next(nullptr)
{}
};这里解释一下构造函数的参数：
- 接受各种类型的参数
- 构造函数
list_node(const T& x = T())中的参数x是一个const T&类型，即一个常量引用。使用引用作为参数可以避免在传递对象时进行不必要的拷贝。当T是一个大型对象时，如包含许多成员变量的结构体或类，传引用可以大大提高效率。例如，如果T是一个Matrix类（用于表示矩阵），它可能有很多数据成员来存储矩阵的元素。如果构造函数不使用引用，每次创建list_node节点来存储Matrix对象时，都需要复制整个Matrix对象，这会消耗大量的时间和空间。- 同时，参数被声明为
const，这保证了在构造函数内部不能修改传入的参数x的值。这对于那些不应该在构造函数中被修改的对象是非常重要的。例如，当T是一个不可变的对象（如std::string_view），const保证了其内容不会被改变。- 提供默认构造的灵活性
x = T()这部分设置了默认值。当用户没有显式传入参数时，构造函数会使用T类型的默认构造值来初始化_date成员变量。这使得list_node的构造更加灵活。例如，当T是一个基本数据类型（如int），默认构造值就是 0；当T是一个类，只要这个类有默认构造函数，就可以自动调用它来初始化_date。这样，既可以使用list_node<int> node1;（此时_date被初始化为 0）这种方式创建节点，也可以使用list_node<int> node2(5);（此时_date被初始化为 5）这种方式，根据具体需求来初始化节点。
迭代器类的模拟实现
除了这两个类，我们还要单独实现一个迭代器的类。
之前模拟实现string和vector时都没有说要实现一个迭代器类，为什么实现list的时候就需要实现一个迭代器类了呢？
因为string和vector对象都将其数据存储在了一块连续的内存空间，我们通过指针进行自增、自减以及解引用等操作，就可以对相应位置的数据进行一系列操作，因此string和vector当中的迭代器就是原生指针。
但是对于list来说，其各个结点在内存当中的位置是随机的，并不是连续的，我们无法仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作。
既然list的结点指针的行为不满足迭代器定义，那么我们可以对这个结点指针进行封装，对结点指针的各种运算符操作进行重载，使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。例如，当你使用list当中的迭代器进行自增操作时，实际上执行了p = p->next语句，只是你不知道而已。
总结： list迭代器类，实际上就是对结点指针进行了封装，对其各种运算符进行了重载，使得结点指针的各种行为看起来和普通指针一样。（例如，对结点指针自增就能指向下一个结点）
迭代器类的模板参数说明
template<class T, class Ref, class Ptr> 这里使用了三个模板参数。T 通常与链表节点存储的数据类型相关，用于确保迭代器操作的数据类型一致性。Ref 和 Ptr 则分别用于定义解引用操作符 * 和箭头操作符 -> 返回的引用类型和指针类型，这样可以根据需要灵活地返回不同类型的引用或指针，比如对于常量对象的迭代可以返回常量引用等。
- 例如，当我们想要遍历一个常量链表时，希望解引用迭代器得到的是常量引用（这样就不会意外修改链表中的数据），此时就可以通过调整
Ref和Ptr的类型来实现。如果只是用一个模板参数，就很难灵活地满足这种不同访问需求的场景。
这样说可能也不是太理解，但我们后续会list类中typedef两个迭代器类型，普通迭代器和const迭代器。
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
这里我们就可以看出，迭代器类的模板参数列表当中的Ref和Ptr分别代表的是引用类型和指针类型。
当我们使用普通迭代器时，编译器就会实例化出一个普通迭代器对象；当我们使用const迭代器时，编译器就会实例化出一个const迭代器对象。
若该迭代器类不设计三个模板参数，那么就不能很好的区分普通迭代器和const迭代器。
构造函数
list_iterator(Node* node)
:_node(node)
{}*运算符重载
当我们使用解引用操作符时，是想得到该位置的数据内容。因此，我们直接返回当前结点指针所指结点的数据即可，但是这里需要使用引用返回，因为解引用后可能需要对数据进行修改。
Ref operator*()//T&
{
return _node->_date;//返回结点中的数据
}->运算符的重载
某些情景下，我们使用迭代器的时候可能会用到->运算符。
想想如下场景：
当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; //输出第一个日期的年份
注意： 使用pos->_year这种访问方式时，需要将日期类的成员变量设置为公有。
对于->运算符的重载，我们直接返回结点当中所存储数据的地址即可。
Ptr operator->()
{
return &_node->_date;//返回结点指针所指向的地址
}实际上这里本来是应该有两个->的，第一个箭头是pos ->去调用重载的operator->返回Date* 的指针，第二个箭头是Date* 的指针去访问对象当中的成员变量_year。
但是一个地方出现两个箭头，程序的可读性太差了，所以编译器做了特殊识别处理，为了增加程序的可读性，省略了一个箭头。
++运算符的重载
首先是前置++，前置++原本的作用是将数据自增，然后返回自增后的数据。我们的目的是让结点指针的行为看起来更像普通指针，那么对于结点指针的前置++，我们就应该先让结点指针指向后一个结点，然后再返回“自增”后的结点指针即可。这里返回引用而不是返回值，可以避免不必要的对象拷贝
Self& operator++()
{
return _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 tmp;
}!=运算符重载
bool operator!=(const Self& s)
{
return _node != s._node;
}==运算符重载
bool operator==(const Self& s)
{
return _node == s._node;
}
list类的模拟实现
成员变量
这个头节点也叫做哨兵位结点，是不可访问的，然后我们给一个_size记录list的长度。
private:
Node* _head = nullptr;
size_t _size;默认成员函数
构造函数
list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可。
void empty_Init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_Init();
}为了后序使用方便，我们将构造头结点封装成了一个函数
拷贝构造函数
拷贝构造函数就是根据所给list容器，拷贝构造出一个对象。对于拷贝构造函数，我们先申请一个头结点，并让其前驱指针和后继指针都指向自己，然后将所给容器当中的数据，通过遍历的方式一个个尾插到新构造的容器后面即可。
list(const list& lt)
{
empty_Init();
for (auto e : lt)
{
push_back(e);
}
}赋值运算符重载
这里依然是这种简单的写法，使用swap。
list<T>& operator = (List<T> lt)
{
swap(lt);
return *this;
}也可传引用，清空之后，然后一个个尾插到原容器里面
list<T>& operator = (const list<T>& lt)
{
if (< != this)
{
clear();
for (auto e : lt)
{
push_back(e);
}
}
return *this;
}析构函数
对对象进行析构时，首先调用clear函数清理容器当中的数据，然后将头结点释放，最后将头指针置空即可。
~list()
{
clear();
delete _head;
_head = nullptr;
}迭代器相关函数
begin和end
首先我们应该明确的是：begin函数返回的是第一个有效数据的迭代器，end函数返回的是最后一个有效数据的下一个位置的迭代器。
对于list这个带头双向循环链表来说，其第一个有效数据的迭代器就是使用头结点后一个结点的地址构造出来的迭代器，而其最后一个有效数据的下一个位置的迭代器就是使用头结点的地址构造出来的迭代器。（最后一个结点的下一个结点就是头结点）
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}插入and删除
insert
插入的逻辑并不难，我们这里跟STL接口容器风格统一，所以我们也返回一个迭代器。这里不会出现迭代器失效问题的。
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_next = cur;
newnode->_prev = prev;
cur->_prev = newnode;
++_size;
return iterator(newnode);
}erase
删除的逻辑也不难，注意不要删空了之后还要继续删除。
iterator erase(iterator pos)
{
assert(pos != end());
Node* del = pos._node;
Node* prev = del->_prev;
Node* next = del->_next;
prev->_next = next;
next->_prev = prev;
delete del;
--_size;
return iterator(next);
}这里我们要返回迭代器是方便一些后续的操作，后面在clear和resize中可以看到，方便我们操作下一个结点，而不需要重新获取迭代器，进行复杂的指针操作。而且在遍历链表时，可能需要删除某些满足特定条件的节点。如果
erase函数不返回迭代器，在删除一个节点后，迭代器就会失效，导致后续的遍历无法继续正常进行。也为了与STL风格统一。
头插和头删
这里都可以直接复用前面的接口
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}尾插和尾删
void push_back()
{
insert(end(), x);
}
void pop_back()
{
erase(--end());
}其他函数
size
我们的成员变量里面是有_size的，并且我们每次的插入和删除都会自增和自减_size，所以这里直接返回_size即可
size_t size()
{
return _size;
}resize
resize函数的规则：
1.若当前容器的size小于所给n，则尾插结点，直到size等于n为止。
2.若当前容器的size大于所给n，则只保留前n个有效数据。
实现resize函数时，不要直接调用size函数获取当前容器的有效数据个数，因为当你调用size函数后就已经遍历了一次容器了，而如果结果是size大于n，那么还需要遍历容器，找到第n个有效结点并释放之后的结点。
这里实现resize的方法是，设置一个变量len，用于记录当前所遍历的数据个数，然后开始遍历容器，在遍历过程中：
当len大于或是等于n时遍历结束，此时说明该结点后的结点都应该被释放，将之后的结点释放即可。
当容器遍历完毕时遍历结束，此时说明容器当中的有效数据个数小于n，则需要尾插结点，直到容器当中的有效数据个数为n时停止尾插即可。
void resize(size_t n,const T& x= T())
{
//int len = _size();
int len = 0;
iterator it = begin();
while (it != end() && len < n)
{
len++;
it++;
}
if (len <n)
{
while (len != n)
{
push_back(x);
len++;
}
}
else//len>n
{
while (it != end())
{
it = erase(it);
}
}
_size = n;
}
小贴士：const T& x = T()和const T& x做参数有什么区别？
基本理解
- 可以这样理解，
const T& x = T()是带有缺省值的参数声明，而const T& x是没有缺省值的参数声明。函数调用灵活性差异
- 带缺省值的参数：
- 当参数是
const T& x = T()形式时，在调用函数时具有更大的灵活性。因为有了缺省值，调用者可以选择不传递这个参数，此时函数会使用默认构造的T类型的值作为参数x的值。这在一些情况下可以简化函数调用，尤其是当参数的默认值在很多情况下都能满足函数的基本操作需求时。- 例如，有一个函数
void printValue(const int& x = int())，可以像printValue()这样调用，函数内部会将x当作0（假设int的默认构造是0）来处理，也可以像printValue(5)这样传入一个具体的值来覆盖默认值。- 不带缺省值的参数：
- 对于
const T& x这种没有缺省值的参数声明，函数调用时必须提供一个符合T类型的参数。这使得函数在调用时更加严格，要求调用者明确地提供参数值。这种方式适用于那些参数对于函数操作是必不可少的，不能使用默认值替代的情况。- 例如，
void processString(const std::string& x)，调用这个函数时必须提供一个std::string对象，如processString("example")，不能省略参数。
empty
bool empty() const
{
return begin == end;
}clear
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}swap
swap函数用于交换两个容器，list容器当中存储的实际上就只有链表的头指针，我们将这两个容器当中的头指针交换即可。
void swap(list<T>& lt)
{
std::swap(_head,lt);
std::swap(_size, lt.size());
}代码：
这是.h文件中的代码，复制到.h文件中即可。然后自己创建一个.cpp文件引入.h文件，写代码调用接口进行调试即可。
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <assert.h>
#include <iostream>
using namespace std;
namespace My_List
{
template <class T>
struct list_node
{
T _date;
list_node* _prev;
list_node* _next;
list_node(const T& x = T())
:_date(x)
, _prev(nullptr)
, _next(nullptr)
{}
};
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ref operator*()//T&
{
return _node->_date;//返回结点中的数据
}
Ptr operator->()
{
return &_node->_date;//返回结点指针所指向的地址
}
//前置++
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 tmp;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
template <class T>
class list
{
public:
typedef list_node<T> Node;
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
void empty_Init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_Init();
}
list(const list& lt)
{
empty_Init();
for (auto e : lt)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
/*list<T>& operator = (const list<T>& lt)
{
if (< != this)
{
clear();
for (auto e : lt)
{
push_back(e);
}
}
return *this;
}*/
list<T>& operator = (list<T> lt)
{
swap(lt);
return *this;
}
//迭代器
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
//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;
//}
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_next = cur;
newnode->_prev = prev;
cur->_prev = newnode;
++_size;
return iterator(newnode);
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* del = pos._node;
Node* prev = del->_prev;
Node* next = del->_next;
prev->_next = next;
next->_prev = prev;
delete del;
--_size;
return iterator(next);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
void push_back(const T& x)
{
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
size_t size()
{
return _size;
}
void resize(size_t n,const T& x= T())
{
//int len = _size();
int len = 0;
iterator it = begin();
len = 0;
while (it != end() && len < n)
{
len++;
it++;
}
if (len <n)
{
while (len != n)
{
push_back(x);
len++;
}
}
else//len>n
{
while (it != end())
{
it = erase(it);
}
}
_size = n;
}
bool empty() const
{
return begin == end;
}
void swap(list<T>& lt)
{
std::swap(_head,lt._head);
std::swap(_size, lt._size);
}
private:
Node* _head = nullptr;
size_t _size;
};
}
本篇博客到此结束，如有问题，欢迎各位评论区留言~