✨个人主页: 北 海
🎉所属专栏: C++修行之路
🎊每篇一句: 图片来源
- A year from now you may wish you had started today.
- 明年今日,你会希望此时此刻的自己已经开始行动了。
🌇前言
STL
中的 list
是一个双向带头循环链表,作为链表的终极形态,各项操作性能都很优秀,尤其是 list
中迭代器的设计更是让人拍案叫绝,如此优秀的容器究竟是如何实现的?本文将带你共同揭晓
出自书籍《STL源码剖析》 侯捷著
本文重点:迭代器类的设计
🏙️正文
注意:本文实现的只是部分基础函数,更多函数将会在后续进行更新
1、基本框架
list
由三个类构建而成:
- 节点类:每个节点必须的三部分(指向前一个节点的指针、指向后一个节点的指针、当前节点存储的数据)
- 迭代器类:此时的迭代器为双向迭代器,比较特殊,需要对其进行封装,如
it++
并非使迭代器单纯向后移动,而是让其指向下一个节点 - 链表类:实现链表各项功能的类,为主要部分
1.1、节点类
节点类在设计时,需要确定三个成员和构造函数,用来生成类
//节点类
template<class T>
struct __list_node
{
__list_node(const T& data = T())
:_prev(nullptr)
,_next(nullptr)
,_data(data)
{}
__list_node<T>* _prev; //指向前一个节点
__list_node<T>* _next; //指向后一个节点
T _data; //存储相应数据
};
注意:节点的创建与销毁,不在 节点类
中进行,因此不需要写析构函数
1.2、迭代器类
迭代器类中的成员为节点类指针,指向单个节点,同样的,迭代器类也需要提供构造函数
//迭代器类
template<class T>
struct __list_iterator
{
typedef __list_node<T>* link_type; //对节点类的指针,进行重命名
__list_iterator(link_type node)
:_node(node)
{}
link_type _node;
};
注意:迭代器只是一个辅助工具,指向的是节点,同样不需要提供析构函数,析构相关事宜交给链表类处理就好
1.3、链表类
链表类中也只用有一个成员变量:哨兵位节点(头节点)
//list本类
template<class T>
class list
{
typedef __list_node<T> node; //节点
typedef T value_type; //模板参数值
typedef T& refence; //引用
typedef const T& const_refence; //const 引用
private:
node* _head; //哨兵位节点(头节点)
};
为了避免变量名过长,这里用到了很多的 typedef
2、默认成员函数
默认成员函数中包含了 默认构造、带参构造、拷贝构造、赋值重载和析构函数
析构函数负责 释放链表中的节点,而其他默认成员函数负责 构造/构建出其他对象
因为有很多构造函数中都需要对创建出头节点,所以此时 需要先构建出一个空初始化函数 empty_init()
,这个函数只能在类中使用,因此设为 private
private:
//初始化出头节点
void empty_init()
{
_head = new node;
_head->_prev = _head->_tail = _head;
}
其他构造函数在构造对象前,可以先调用此函数
比如 默认构造函数, 构成出一个空对象
//默认构造函数
list() { empty_init(); }
对于带参构造函数,在构造对象前,仍需要调用 empty_init()
构建头节点
参数:
size_t n
对象中包含n
个数据const_reference val
数据值
为了避免与后续的迭代器区间构造起冲突,这里需要再额外提供一个 int n
版本
//带参构造函数(size_t)
list(size_t n, const_refence val = value_type())
{
empty_init();
while (n--) push_back(val);
}
//为了避免与迭代器区间构造函数冲突,提供额外版本(int)
list(int n, const_refence val = value_type())
{
empty_init();
while (n--) push_back(val);
}
在实际创建 list
对象时,多使用迭代器区间进行构造,因为是创建新对象,所以可以直接调用尾插进行创建
//迭代器区间构造
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last) push_back(*first++);
}
关于拷贝构造和赋值重载,可以使用现代写法【交换】
//拷贝构造---现代写法
list(const list<T>& x)
{
empty_init();
list<T> tmp(x.begin(), x.end());
swap(tmp);
}
//赋值重载---现代写法
list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}
注意:
- 以上几种构造函数都是在创建新对象,因此在构建前,需要先调用
empty_init()
初始化出头节点 - 为了避免
list(int, int)
匹配上迭代器区间构造,可以再额外提供一个int
版的带参构造函数 - 拷贝构造的参数必须使用引用,否则会造成 无穷递归 问题
至于 析构函数 的实现就很简单了,直接使用函数 clear()
释放节点,最后再释放头节点即可
//析构函数
~list()
{
clear(); //后续会对这个函数的实现进行讲解
delete _head;
_head = nullptr;
}
对上述函数进行使用
3、迭代器设计
迭代器设计是本文的重难点
它是一个单独存在的类
//迭代器类
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef __list_node<T>* link_type;
typedef __list_iterator<T, Ref, Ptr> self;
__list_iterator(link_type node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(operator*());
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator++(int)
{
self tmp(_node);
//++_node; //谨防错误写法
//_node = _node->_next; //正确写法1
++(*this); //正确写法2
return tmp;
}
self operator--(int)
{
self tmp(_node);
//--_node; //谨防错误写法
//_node = _node->_prev; //正确写法1
--(*this); //正确写法2
return tmp;
}
bool operator==(const self& tar)
{
return tar._node == _node;
}
bool operator!=(const self& tar)
{
return tar._node != _node;
}
link_type _node;
};
注意:节点类及迭代器类都是使用 struct
定义的,目的是为了开放其中的成员
list
类中的迭代器相关函数也有两种:普通版本与 const
版本
规定:
begin()
为list
的头节点的下一个节点end()
是list
的头节点- 返回类型都为迭代器对象,因此可以使用匿名对象进行构造
//=====迭代器设计=====
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
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); }
3.1、双向迭代器
list
中的迭代器只支持双向操作,在进行随机移动时会报错
以下是 std::list
中对迭代器进行随机移动的情况
void TestStdList()
{
std::list<int> slt = { 1, 2, 3 };
std::list<int>::iterator it = slt.begin();
it++; //单向移动,支持
it--; //双向移动,支持
it + 10; //随机移动,不支持
}
虽然我们可以通过某些手段实现随机移动(比如 operator+(int n)
),但为了更好的符合链表及标准库规定,这里设计为双向移动的迭代器即可
迭代器分类:
- 单向迭代器:支持
++
或--
其中一种移动方式 - 双向迭代器:支持
++
及--
两种移动方式 - 随机迭代器:不仅支持
++
和--
,还支持迭代器+n
、-n
,只有随机迭代器才能使用std::sort
进行快速排序
目标:实现前置 ++/--
及后置 ++/--
self& operator++(); //前置++
self& operator--(); //前置--
self operator++(int); //后置++
self operator--(int); //后置--
注:具体代码实现在上面
3.2、特殊移动策略
list
中的双向迭代器在进行移动时也比较特殊,不像之前的 string
和 vector
是连续空间(移动直接调用内置 ++/--
), list
为非连续空间,迭代器在移动时为前后节点间的移动,使用内置 ++/--
会引发严重的迭代器越界问题
因此才需要将迭代器单独封装为一个类,实现我们想要的效果
如何实现不同区域间节点的移动?
- 首先需要先构建出迭代器对象
- 当使用前置
++
时,会去调用迭代器类中的operator++()
重载函数,将迭代器指向当前节点的下一个节点(_node = _node->_next
) - 使用后置
--
时也是如此,调用operator--()
即可(_node = _node->_prev
) - 至于后置
++/--
,可以先构造出当前节点的迭代器对象,再复用前置++/--
即可
self& operator++()
{
_node = _node->_next;
return *this;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator++(int)
{
self tmp(_node);
//++_node; //谨防错误写法
//_node = _node->_next; //正确写法1
++(*this); //正确写法2
return tmp;
}
self operator--(int)
{
self tmp(_node);
//--_node; //谨防错误写法
//_node = _node->_prev; //正确写法1
--(*this); //正确写法2
return tmp;
}
注意:_node
是迭代器中的节点指针,包含在迭代器对象中
在这里分享一个我在模拟迭代器类时遇到的小问题:根据一个 list
对象构造出另一个 list
对象,调用后置 ++/--
并解引用后,出现内存问题(越界访问)
原因分析:调用后置 ++
后,因 operator++(int)
编写不当,导致当前节点指针没有正确指向下一个节点,而是指向当前位置的下一块空间(非法空间),导致迭代器失联,引发后续的越界访问
//以下是后置++的错误写法
self operator++(int)
{
self tmp(_node);
++_node; //错误写法
return tmp;
}
根本原因:_node
是一个节点指针,非迭代器对象,++_node
不是在调用 operator++()
,而是在调用内置的前置 ++
(节点指针没有像迭代器一样进行重载),直接 ++
就指向了非法空间
解决方案:
- 手动实现节点的移动:
_node = _node->_next
- 调用迭代器类的前置
++
:++(*this)
两种解决方法都可以,推荐使用第二种(库中的解决方案)
self operator++(int)
{
self tmp(_node);
//++_node; //谨防错误写法
//_node = _node->_next; //正确写法1
++(*this); //正确写法2
return tmp;
}
补充:假设构造对象为内置的数组或其他库中的容器,++_node
不会出错,因为此时会调用正确的移动方法;而当构造对象为自己模拟实现的 list
时,会出现上述的报错问题
3.3、多参数模板
list
的模拟实现精华在于迭代器类的设计,而迭代器类中的精华在于多参数模板,这种传多模板参数的方法,巧妙的解决了 正常对象 与 const
对象的冗余设计问题
迭代器分为 iterator
和 const_iterator
,不同的对象调用不同的迭代器类型,假设不使用多参数模板,就需要实现两份相差不大的迭代器类(完全没有必要)
优雅、巧妙的解决方案 多参数模板
T
:节点中值的普通类型Ref
:节点中值的引用类型(可为const
)Ptr
:节点中值的指针类型(可为const
)
//迭代器类
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef __list_node<T>* link_type;
typedef __list_iterator<T, Ref, Ptr> self;
//……
link_type _node;
};
//=====迭代器设计=====(list 类中)
typedef __list_iterator<T, T&, T*> iterator; //声明两种不同的迭代器
typedef __list_iterator<T, const T&, const T*> const_iterator;
迭代器类中的模板参数是一对二的
多参数模板的使用,使得 list
的迭代器设计更加优雅,下面是实际使用演示(在 operator*()
中添加信息区分)
Ref operator*()
{
cout << "当前的模板参数为: " << typeid(*this).name() << endl;
return _node->_data;
}
void TestList()
{
int arr[] = { 1,2,3,4,5 };
list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0])); //普通对象
const list<int> rlt(arr, arr + sizeof(arr) / sizeof(arr[0])); //const 对象
auto it = lt.begin();
auto rit = rlt.begin();
cout << *it << endl;
cout << *++rit << endl;
}
使用不同的迭代器类型,可以使迭代器类中的模板参数变为对应类型
这正是 泛型编程 思想之一
3.4、其他功能
关于迭代器类中的其他功能:
- 解引用
operator*()
- 取当前节点指针
operator->()
- 迭代器比较
operator==()
和operator!=()
详细实现代码可以查看本文的 章节3 开头
这里简单说一下 operator->()
适用场景:当 list
中的对象为自定义类型时,想直接通过 it->
访问其中的成员
struct A
{
A(int a = int(), double b = double(), char c = char())
:_a(a)
,_b(b)
,_c(c)
{}
int _a;
double _b;
char _c;
};
void TestList()
{
list<A> lt;
lt.push_back(A(1, 2.2, 'A'));
auto it = lt.begin();
cout << (*it)._a << endl; //不使用 operator->() 比较别扭
cout << it.operator->()->_b << endl; //这种写法是真实调用情况
cout << it->_c << endl; //编译器直接优化为 it->
}
operator->()
存在的意义:使得 迭代器
访问自定义类型中的成员时更加方便
如果没有这个函数,只能通过 (*迭代器).成员
的方式进行成员访问,很不方便
注意:编译器将 迭代器.operator->()->成员
直接优化为 迭代器->成员
4、容量相关
list
中的容量访问有:判空和大小
实现判空:判断当前的 begin()
与 end()
是否相同
统计大小:利用迭代器将整个 list
遍历一遍,计数统计即可
//=====容量相关=====
bool empty() const { return begin() == end(); }
size_t size() const
{
int cnt = 0;
auto it = begin(); //使用 auto 自动推导迭代器类型
while (it != end())
++it, ++cnt;
return cnt;
}
5、数据访问
STL
库中给 list
提供了两种数据访问方式:访问首个数据和访问最后一个数据
//=====数据访问=====
refence front() { return *begin(); }
const_refence front() const { return *begin(); }
refence back() { return *(--end()); }
const_refence back() const { return *(--end()); }
6、数据修改相关
数据修改是 list
的拿手好戏(双向循环链表),只需要找到对应节点的位置,插入/删除 本质上就是在进行前后节点的链接关系修改
出自《STL源码剖析》
6.1、头尾插删
头尾插删是在对 begin()
和 --end()
所指向的节点进行操作,尾部插入/头部删除 逻辑一致,尾部删除/头部删除 逻辑一致,学会其中一个就够用了
尾部插入步骤:
- 根据传入的数值,构建出新尾节点
new_back
- 找到原链表中的尾节点
old_back
- 在
old_back
、new_back
、_head
间建立链接关系即可 - 头部插入逻辑与尾部插入基本一致,不过找的是
old_front
头节点
//尾插
void push_back(const_refence val)
{
node* new_back = new node(val);
node* old_back = _head->_prev;
old_back->_next = new_back; //原尾节点的 _next 指向新尾节点
new_back->_prev = old_back; //新尾节点的 _prev 指向原尾节点
new_back->_next = _head; //新尾节点的 _next 指向头节点
_head->_prev = new_back; //头节点的 _prev 指向新尾节点
}
尾部删除步骤:
- 断言当前
list
不为空,如果为空,就报错 - 选择原来的尾节点
old_back
->_head->_prev
- 确定新的尾节点
new_back
->old_back->prev
- 在
new_back
与_head
之间建立链接关系 - 最后在释放原来的尾节点
old_back
- 头删时,逻辑基本一致,不过选择的是
old_front
与new_front
//尾删
void pop_back()
{
assert(!empty());
node* old_back = _head->_prev; //选择原尾节点
node* new_back = old_back->_prev; //确定新尾节点
new_back->_next = _head; //新尾节点的 _next 指向头节点
_head->_prev = new_back; //头节点的 _prev 指向新尾节点
delete old_back;
}
类似于 push_back()
还有一个函数 assign()
分配,相当于构造函数构造出对象,不过此时是赋值的方式
//=====数据修改=====
//赋值
void assign(size_t n, const_refence val)
{
clear();
while (n--) push_back(val);
}
void assign(int n, const_refence val)
{
assign((size_t)n, val);
}
template<class InputIterator>
void assign(InputIterator first, InputIterator last)
{
list<T> tmp(first, last);
swap(tmp);
}
注意:
- 为了避免
assign(int, int)
与assign(first, last)
起冲突,需要再额外提供一个assign(int n, const_refence val)
版本 assign
行为类似于创建出一个新的对象,因此在赋值(分配)前需要先清空clear()
assign
本质上是在调用push_back
6.2、任意位置插删
任意位置插入就是在插入操作的基础上添加了迭代器 pos
进行定位
- 约定:在
pos
位置前插入 - 根据传入值,创建出新节点
new_node
- 确定当前
pos
位置的节点pos_cur
- 确定当前
pos
位置的上一个节点pos_prev
- 在
pos_prev
、new_node
、pos_cur
间建立链接关系 - 最后返回当前插入新节点的位置
//任意位置插入
iterator insert(iterator pos, const_refence val)
{
node* new_node = new node(val); //创建新节点
node* pos_cur = pos._node; //当前 pos 位置的节点
node* pos_prev = pos_cur->_prev; //pos 的前一个节点
pos_prev->_next = new_node;
new_node->_prev = pos_prev;
new_node->_next = pos_cur;
pos_cur->_prev = new_node;
return iterator(new_node); //最后返回的是一个迭代器对象
}
任意位置删除逻辑与 尾删/头删 基本一致
- 首先断言
list
是否为空 - 分别确定当前节点
pos_cur
,上一个节点pos_prev
,下一个节点pos_next
- 在上下节点
pos_prev
和pos_next
间建立链接关系 - 删除当前节点
pos_cur
- 返回已删除节点下一个节点,即
pos_next
//任意位置删除
iterator erase(iterator pos)
{
assert(!empty());
node* pos_cur = pos._node;
node* pos_prev = pos_cur->_prev;
node* pos_next = pos_cur->_next;
pos_prev->_next = pos_next;
pos_next->_prev = pos_prev;
delete pos_cur;
return iterator(pos_next);
}
注意:list
的插入操作没有迭代器失效问题,删除操作也仅仅是影响被删除节点的迭代器,返回值是为了更好的进行操作
之前提到的 尾部插入/删除、头部插入/删除 可以复用 任意位置插入/删除
//尾插
void push_back(const_refence val)
{
insert(end(), val);
}
//尾删
void pop_back()
{
erase(--end());
}
//头插
void push_front(const_refence val)
{
insert(begin(), val);
}
//头删
void pop_front()
{
erase(begin());
}
复用后,之前的代码也能正常运行
6.3、交换、调整、清理
接下来是一些比较简单函数实现
- 交换
swap
:不同于std::swap
,list::swap
是直接交换两个链表的头节点,效率是极高的 - 调整
resize
:传入n
及值val
,对list
进行大小调整,只有n > size()
才进行大小调整,具体调整就是push_back()
尾插n - size()
次 - 清理
clear
:通过迭代器对list
进行遍历,erase
除头节点外的所有节点
//交换
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}
//大小调整
void resize(size_t n, const_refence val = value_type())
{
if (n > size())
{
while (size() < n)
push_back(val);
}
}
//清理
void clear()
{
iterator it = begin();
while (it != end())
it = erase(it);
}
简单写一个小 demo
测试一下这些函数
void Print(list<int>& lt1, list<int>& lt2)
{
cout << "lt1:" << "empty():" << lt1.empty() << " size():" << lt1.size() << endl;
for (auto e : lt1)
cout << e << " ";
cout << endl;
cout << "lt2:" << "empty():" << lt2.empty() << " size():" << lt2.size() << endl;
for (auto e : lt2)
cout << e << " ";
cout << endl;
cout << "============================" << endl;
}
void TestList()
{
int arr[] = { 1,2,3,4,5 };
list<int> lt1(arr, arr + sizeof(arr) / sizeof(arr[0]));
list<int> lt2(3, 1);
cout << "original" << endl;
Print(lt1, lt2);
cout << "swap(lt1, lt2)" << endl;
lt1.swap(lt2);
Print(lt1, lt2);
cout << "lt1 resize()" << endl;
lt1.resize(10, 2);
Print(lt1, lt2);
cout << "clear()" << endl;
lt1.clear();
lt2.clear();
Print(lt1, lt2);
}
7、源码
关于本文中涉及到的所有代码都在这个仓库中 《list_4_8》
🌆总结
以上就是本次关于 STL
学习之 list
的模拟实现的全部内容了,对于本文来说,最核心的内容莫过于迭代器类的设计,而其中的精华在于多参数模板的使用,只要把迭代器类设计好了,list
中的其他部分都不成问题
如果你觉得本文写的还不错的话,可以留下一个小小的赞👍,你的支持是我分享的最大动力!
如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正
文章来源:https://www.toymoban.com/news/detail-440128.html
相关文章推荐
STL 之 list 类
C++ STL学习之【list的使用】
===============
STL 之 vector 类
C++ STL学习之【vector的模拟实现】
C++ STL学习之【vector的使用】
===============
STL 之 string 类
C++ STL学习之【string类的模拟实现】
C++ STL 学习之【string】
文章来源地址https://www.toymoban.com/news/detail-440128.html
到了这里,关于C++ STL学习之【list的模拟实现】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!