当前位置：首页 > news >正文

【c++】STL-容器 list 的实现

news 2025/7/19 13:12:12

hello~ 很高兴见到大家! 这次带来的是C++中关于list容器这部分的一些知识点,如果对你有所帮助的话,可否留下你的三连呢?
个人主页: 默|笙

在这里插入图片描述

文章目录

一、做好实现list前的准备工作
- 1.1 节点
- 1.2 实现iterator迭代器
- - 1.实现基本框架（普通迭代器）
  - 2. 常量迭代器的添加
- 3.->重载函数
二、实现list

接上次的博客<list的使用>

一、做好实现list前的准备工作

由于模板的特殊，声明和定义不分离,即把它们放在一个文件里(.h)。

模板的实例化需要看到完整定义，而分文件编译机制导致无法让编译器在使用模板的地方获取定义，导致无法生成实例代码，链接失败。

1.1 节点

与底层为数组的vector不同，list这个模板的底层是链表，是由一个一个的节点组成的，我们首先要实现的就是节点。
我们可以将节点所需变量打包成一个类，其包含一个存储数据的变量和两个指针。由于我们需要经常访问这个类的成员变量，我们用struct实现。
同时不要忘了用模板实现。

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){}};

关于节点构造函数里的 const T& x = T()：c++规定，T()，若T为自定义类型，则会调用默认构造函数，若为内置类型，则会进行零初始化，将值设置为0 或 nullptr。
为了在任何时候节点都能被初始化（无论是设置头节点还是push_back一个节点），我们用全缺省默认构造函数。

1.2 实现iterator迭代器

1.实现基本框架（普通迭代器）

在之前vector的实现里，我们直接将指针重命名为迭代器iterator（vector博客）。这是因为vector的底层是数组，*解引用能直接拿到数据，++能移动到后一个位置，- -能移动到前一个位置，运用指针就能达到预期目的。
但在list里，我们能够直接接触的只有节点，节点的指针解引用，拿到的不会是我们想要的数据，而是节点本身，++与- -也不会达到预期效果，节点指针不能成为我们的迭代器。
那么我们可以类封装节点指针来实现迭代器，通过重载运算符来控制迭代器的行为（重载++与- -实现跳转到前一个或后一个节点，重载*实现访问数据）。

则有：

template<class T>
struct __list_iterator
{typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}T& operator*(){return _node->_data;}//前置++__list_iterator<T>& operator++(){_node = _node->_next;return *this;}//后置++__list_iterator<T> operator++(int){__list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}//前置--__list_iterator<T>& operator--(){_node = _node->_prev;return *this;}//后置--__list_iterator<T> operator--(int){__list_iterator<T> tmp(*this);_node = _node->_prev;return tmp;}//!=bool operator!=(const __list_iterator<T>& it)const{return _node != it._node;}//==bool operator==(const __list_iterator<T>& it)const{return _node == it._node;}
};

注：这里的 this 是迭代器指针，也就是__list_iterator*，而*this是迭代器。

*重载：我们的预期是解引用直接得到数据，重载*函数让其被调用时返回数据便可，这里返回数据的引用）。
前置++与前置- -重载：改变迭代器的指向然后返回迭代器的引用（避免拷贝）就行。
后置++与后置- -重载：由于需要返回的是改变之前的迭代器，需要先把所指节点改变之前的迭代器拷贝存一份，这里迭代器变量名称设置为tmp，迭代器所指节点改变之后再返回tmp。这里不能返回引用，因为tmp离开这个作用域就会销毁。

迭代器这个类不需要实现析构函数，拷贝构造函数和赋值重载函数。前者是因为它没有资源需要释放，它只是目前指向/管理这个节点，这个节点并不属于它；后面两个是因为我们需要的就是浅拷贝，指向同一块空间，不需要进行深拷贝。

!= 与 ==：分辨两个迭代器所指向的节点是否是不同或相同节点便可。

2. 常量迭代器的添加

在一些场景比如创建Print函数时，仅仅是遍历，我们不能允许改变迭代器所指的节点的值，这需要我们使用到常量迭代器。
常量迭代器如何实现？只需要修改*重载函数的返回值就行，加上const修饰。
常量迭代器不是本身不可修改，而是它指向的数据不能被修改。

const T& operator*()
{return _node->_data;
}

接下来，我们来看一段加上常量迭代器过后的代码：

	template<class T>struct __list_iterator{typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}T& operator*(){return _node->_data;}//2const T& operator*(){return _node->_data;}};template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T> iterator; //1typedef const __list_iterator<T> const_iterator;private:};

这里省略了很多代码，留下了主要的部分。这个代码里存在着两处问题。

1处的错误：将 const __list_iterator类型重定义为 const_iterator，也就是常量迭代器。注意，const这里修饰的是 __list_iterator这个类型本身，意思是这个迭代器它本身不能修改，而不是说迭代器它所指向的数据不能被修改，这不符合我们的预期。
假如没有上面的错误，仅有2处，也存在着问题：这里虽然两个*重载函数构成重载，但是只有被const修饰的迭代器才能够调用上面的const *函数，然后又回到了上面的问题，这也是迭代器本身不可修改，做不到迭代器的基本功能遍历。
正确方法应该是再创建一个常量迭代器的类，与上面普通迭代器的类区别开来。

如下：

	//普通迭代器template<class T>struct __list_iterator{typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}T& operator*(){return _node->_data;}//前置++__list_iterator<T>& operator++(){_node = _node->_next;return *this;}//后置++__list_iterator<T> operator++(int){__list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}//前置--__list_iterator<T>& operator--(){_node = _node->_prev;return *this;}//后置--__list_iterator<T> operator--(int){__list_iterator<T> tmp(*this);_node = _node->_prev;return tmp;}//!=bool operator!=(const __list_iterator<T>& it)const{return _node != it._node;}//==bool operator==(const __list_iterator<T>& it)const{return _node == it._node;}};//常量迭代器template<class T>struct __list_const_iterator{typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}const T& operator*(){return _node->_data;}//前置++__list_iterator<T>& operator++(){_node = _node->_next;return *this;}//后置++__list_iterator<T> operator++(int){__list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}//前置--__list_iterator<T>& operator--(){_node = _node->_prev;return *this;}//后置--__list_iterator<T> operator--(int){__list_iterator<T> tmp(*this);_node = _node->_prev;return tmp;}//!=bool operator!=(const __list_iterator<T>& it)const{return _node != it._node;}//==bool operator==(const __list_iterator<T>& it)const{return _node == it._node;}};template<class T>class list{typedef list_node Node;public:typedef __list_iterator iterator;//重命名常量迭代器typedef __list_const_iterator const_iterator;private:};

但上面的代码稍微有些冗长，且两个迭代器几乎完全一样，这里我们可以增加一个模板参数，将它们整合为同一个模板类，最终使得这两个迭代器变成这个模板类的不同实例。

如下：

template<class T, class Ref>
struct __list_iterator
{typedef list_node<T> Node;typedef __list_iterator<T, Ref> Self;Node* _node;__list_iterator(Node* node):_node(node){}//*重载Ref operator*(){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 tmp;}//!=bool operator!=(const Self& it)const{return _node != it._node;}//==bool operator==(const Self& it)const{return _node == it._node;}
};
template<class T>
class list
{typedef list_node Node;
public:typedef __list_iterator<T, T&> iterator;typedef __list_iterator<T, const T&> const_iterator;private:};

这里通过增加Res模板参数来实现迭代器模板类，除此之外，在模板类里，还将__list_iterator<T, Ref> 重命名为Self，这样可以方便以后代码的维护，比如增加一个模板参数时，只用动这里一个地方就行了。

3.->重载函数

接下来看一段代码：

//这是一个类：
struct Pos{int _row;int _col;Pos(int row = 0, int col = 0):_row(row), _col(col){}};
//我们尝试打印一下存储这个Pos类型的list<Pos>,假设list已经实现
int main()
{mosheng::list<Pos> lt1;lt1.push_back({1,1});//隐式类型转换lt1.push_back({2,2});lt1.push_back({3,3});lt1.push_back({4,4});auto it = lt1.begin();while (it != lt1.end()){//cout << (*it)._row << ":" << (*it)._col << endl;cout << it->_row << ":" << it->_col << endl;++it;}cout << endl;			return 0;
}

会出现（其中mosheng是list实现所在的命名空间）：

在这里插入图片描述

这是因为我们重载了*，但是还没有重载->，所以我们无法成功打印。接下来让我们来进行实现：

//operator->() 的返回类型必须是 T* 或迭代器，无论 T 是否为指针类型
T* operator->()
{return &_node->_data;
}

将其放入迭代器类模板里，代码能够正常运行。

在这里插入图片描述

我们能够发现一个有趣现象：根据重载函数，返回的应该是Pos*，而上面代码的 it->_row，它少了一个->，实际应该是it->->row（写的时候不能写两个）。第一个箭头是迭代器运算符重载得到Pos*，第二个取Pos里的row。省略一个->是编译器的特殊处理，为了增强可读性。
为了实例化常量迭代器，我们再增添一个模板参数。

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*(){return _node->_data;}Ptr operator->(){return &_node->_data;}
}
class list
{typedef list_node<T> Node;
public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;
}
//省略中间一部分

二、实现list

由于链表的实现比较简单没有什么需要单独拿出来讲的内容，这里就跳过了。

		template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;//创造头节点函数void empty_Init(){_head = new Node;_head->_prev = _head;_head->_next = _head;}//默认构造函数list(){empty_Init();}//拷贝构造函数list<T> (const list<T>& lt){empty_Init();for (const auto& e : lt){push_back(e);}}//初始化列表构造函数list(initializer_list<T> il){empty_Init();for (const auto& e : il){push_back(e);}}//清除链表节点，留下头节点void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}//析构函数~list(){clear();//清除所有节点delete _head;//清除头节点_head = nullptr;}//交换void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//赋值重载函数（现代写法）list<T>& operator=(list lt){swap(lt);return *this;}//begin()iterator begin(){return iterator(_head->_next);}const_iterator begin()const{return cosnt_iterator(_head->_next);}//end()iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}//在指定位置插入iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;prev->_next = newnode;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;_size++;return iterator(newnode);}//删除指定位置iterator erase(iterator pos){Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;_size--;return iterator(next);}//尾插void push_back(const T& x){insert(end(), x);}//头插void push_front(const T& x){insert(begin(), x);}//尾删void pop_back(){erase(--end());}//头删void pop_front(){erase(begin());}//节点个数size_t size(){return _size;}private:Node* _head;size_t _size = 0;};
}