C++：STL-list模拟实现：迭代器的封装

🕗 发布于 2024-04-20 12:28 c++ list 开发语言 程序人生交友

STL-list模拟实现细节

一. 模拟实现的思想细节
二.实现源码

一. 模拟实现的思想细节

1.迭代器实现：用类进行封装

为什么不使用原生指针：

相比于vector和string，它们两个的物理存储空间都是连续的，因此它们在实现迭代器时，迭代器会使用++等操作，对于它们都是可以直接使用原始指针来进行模拟的，但是对于我们的list链表，其数据存储在一个一个分散的结点之中，我们在进行迭代器遍历的时候使用++，指针移动到下一个位置，但是那里的空间是否我们已经动态内存申请从而来存储结点是未知的，其次通过*进行解引用打印这个数据时，我们得到的并不是直接存储的数据，而是得到的一个一个的结点，那么通过使用原生指针就无法满足我们迭代器的行为。

为什么使用类来封装：

通过类和对象中运算符的重载的学习，我们了解到通过运算符重载可以改变一个运算符的行为，既然我们原生指针 *解引用时无法得到我们想要的行为，那么我们可以通过类的运算符重载来改变 *，++等操作符的行为，让它不是只能访问到结点而实直接访问到结点内部存储的数据，因此我们需要将结点的指针通过类进行封装，从而达到我们的目的。

2.++和–的重载

注意点：迭代器通过++和–改变时，本质是在改变该迭代器内部结点指针的指向，而不是修改这个迭代器本身（即this指针指向的内容）。

在这里插入图片描述

3.奇怪的->重载

这里肯定会有小伙伴产生疑问，我们->之后得到的应该直接是该结点存储的_val，但是为什么实现的时候返回的是其的地址呢？

这里的主要目的是增加可读性。

首先先观察部分实现源码：

在这里插入图片描述

我们看到在STL库中，->的重载是对operator*()的返回值取地址，而了解到 * 的重载重载之后的行为是返回所存储值本身，即迭代器内部结点内存储的值。，那么我们->之后返回的是operator *()返回值的地址，在逻辑上我们使用->时后应该需要再加一个->才能拿到最终的数据。

下面来看这段测试代码：

在这里插入图片描述

it->调用了operator->()，并且返回了存储值的地址，但是我们我们并没有按照我们所想的增加多写一个->来解引用。

如果我们显示写出->重载函数的调用，我们可以看到是有两个->，其中一个用来调用operator->()，另外一个用来对其返回值解引用，但是我们通过it->_a1隐式调用operator->()却只有一个箭头，因为在隐式调用时省略了一个->，相比于写两个->，一个箭头可以增强可读性。

首先我们要理解迭代器模拟的是T*的行为！

对于T*，我们直接->就可以访问其数据，但是如果该容器存储的不是int，double这样的数据，而是一个自定义类型，比如如上的A，如果直接重载->时是返回确切的值，只能返回一个，比如返回了_a1，但是 _a2怎么办？因此这种行为是不合适的。

迭代器模拟的是T* 的行为，我们期望直接一个->就可以访问到数据，我们此处的迭代器it可以理解为T*。

对于-List中：>重载时，其的重载格式如下：

在这里插入图片描述

4.const迭代器

在我们封装好自己实现的迭代器iterator之后，只能对于普通迭代器来使用，但是const迭代器如果还使用上面的那一个类的迭代器，就会出现问题：

我们的const对象不能修改，但是我们使用的是普通对象的迭代器，其的权限是可读可写，通过*可以修改const对象的值，因此我们需要实现一个const版本的迭代器，而它们最本质的区别就是在 *，->等进行解引用操作时，对于返回值类型是否加const限制的问题，因此我们可以直接CV普通对象的迭代器，对于其 *和->运算符重载时，对其返回值类型加上const限制，但是这样会造成有两个功能等各方面都相似的类，这样会显的我们的List的迭代器比较的臃肿。

然后它们的区别是==个别函数的返回值类型不同，对于只有类型不同的函数我们可以考虑使用模板。==我们通过将这两个运算符重载函数的返回值使用模板参数来确定其内容，这样就可以实现同一个类对于const对象和非const对象都可以使用啦。我们将模板参数传入的是没有使用const修饰的类型typedef成为iterator，将使用const修饰时模板参数传入使用const修饰的类typedef成为const_iterator，这样通过对象调用时调用的是const_iterator还是iterator从而实现分别调用实现不同的功能。

对于区分iterator和const_iterator，我们只需要通过typedef该类对应的不同的模板参数即可实现区分调用。对于模板参数，我们在调用普通迭代器时，传入的就是普通的对象，对于const对象，调用其const迭代器，然后list迭代器中会自动生成对应的const迭代器供我们使用。

在这里插入图片描述

二.实现源码

namespace List
{
template<class T>
struct ListNode
{

//构造
ListNode(const T& val = T())
:_val(val),
_prev(nullptr),
_next(nullptr)
{

}

ListNode<T>* _prev;
ListNode<T>* _next;
T _val;

};

//这两个迭代器本身只有返回值类型不同--->类型不同时考虑模板
//template<class T>
//class Listiterator
//{
//public:
//typedef ListNode<T> Node;
//typedef Listiterator<T> iterator;
//Listiterator(Node* node)
//:_node(node)
//{
//}
//bool operator!=(const iterator end)
//{
//return _node != end._node;
//}
////it++
//iterator operator++(int)
//{
//iterator tmp(*this);
////错误写法
////*this = this->_node->_next;
//
////迭代器++是其内部的节点指针的变化
//_node = _node->_next;
//return tmp;
//}
////++it
//iterator operator++()
//{
//_node = _node->_next;
//return *this;
//}
////it--
//iterator operator--(int)
//{
//iterator tmp(*this);
//_node = _node->_prev;
//return tmp;
//}
////--it
//iterator operator--()
//{
//_node = _node->_prev;
//return *this;
//}
//
//T& operator*()
//{
//return _node->_val;
//}
//
//T* operator->()
//{
//return &_node->_val;
//}
//public:
//Node* _node = nullptr;
//};
//
//template<class T>
//class ConstListiterator
//{
//public:
//typedef ListNode<T> Node;
//typedef ConstListiterator<T> const_iterator;
//
//ConstListiterator(Node* node)
//:_node(node)
//{
//
//}
//
//bool operator!=(const ConstListiterator end)
//{
//return _node != end._node;
//}
//
////it++
//const_iterator operator++(int)
//{
//iterator tmp(*this);
//
////错误写法
////*this = this->_node->_next;
//
////迭代器++是其内部的节点指针的变化
//_node = _node->_next;
//return tmp;
//}
//
////++it
//const_iterator operator++()
//{
//_node = _node->_next;
//return *this;
//}
//
////it--
//const_iterator operator--(int)
//{
//iterator tmp(*this);
//
//_node = _node->_prev;
//
//return tmp;
//}
//
////--it
//const_iterator operator--()
//{
//_node = _node->_prev;
//return *this;
//}
//
// const T& operator*()
//{
//return _node->_val;
//}
//
//const T* operator->()
//{
//return &_node->_val;
//}
//public:
//Node* _node = nullptr;
//};

template<class T, class Ref, class Ptr>
class Listiterator
{
public:
typedef ListNode<T> Node;
typedef Listiterator<T, Ref, Ptr> iterator;

Listiterator(Node* node)
:_node(node)
{

}

bool operator!=(const iterator end)
{
return _node != end._node;
}

//it++
iterator operator++(int)
{
iterator tmp(*this);

//错误写法
//*this = this->_node->_next;

//迭代器++是其内部的节点指针的变化
_node = _node->_next;
return tmp;
}

//++it
iterator operator++()
{
_node = _node->_next;
return *this;
}

//it--
iterator operator--(int)
{
iterator tmp(*this);

_node = _node->_prev;

return tmp;
}

//--it
iterator operator--()
{
_node = _node->_prev;
return *this;
}

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

Ptr operator->()
{
return &_node->_val;
}
public:
Node* _node = nullptr;
};

//迭代器适配器   支持所有的反向迭代器，只要传入正向迭代器，就可以制造出其的反向迭代器
template<class iterator, class Ref, class Ptr>
class reverse_Listiterator
{
public:
typedef reverse_Listiterator<iterator, Ref, Ptr> Self;

iterator _it;

reverse_Listiterator(iterator it)
:_it(it)
{

}

Ref operator*()
{
//这样会打印出哨兵位
//return *_it;
iterator tmp = _it;

//必须先让tmp--到
return *(--tmp);
}

Ptr operator->()
{
return _it.operator->();
}

bool operator!=(const Self& s)
{
return _it != s._it;
}

Self& operator++()
{
--_it;
return *this;
}

Self& operator--()
{
++_it;
return *this;
}
};

template<class T>
class list
{
public:
typedef ListNode<T> Node;
//typedef Listiterator<T> iterator;
//typedef ConstListiterator<T> const_iterator;
typedef Listiterator<T, T&, T*> iterator;
typedef Listiterator<T, const T&, const T*> const_iterator;
typedef reverse_Listiterator<iterator, T&, T*> reverse_iterator;
typedef reverse_Listiterator<const_iterator, const T&, const T*> const_reverse_iterator;


//constructor and destructor

void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}

list()
{
empty_init();
}

list(int n, const T& val = T())
{
empty_init();

for (int i = 0; i < n; i++)
push_back(val);

}

template<class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
first++;
}
}

list(const list<int>& l)
{
empty_init();
const_iterator it = l.begin();
while (it != l.end())
{
push_back(*it);
it++;
}
}

list<T>& operator=(list<T> l)
{
swap(l);
return *this;
}

~list()
{
empty();
delete _head;
}

//Iterator
reverse_iterator rbegin()
{
return end();
}
reverse_iterator rend()
{
return begin();
}

iterator begin()
{
//单参数构造函数支持隐式类型转换
return _head->_next;
}

//最后一个节点的下一个位置
iterator end()
{
return _head;
}

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

const_iterator end() const
{
return _head;
}


//Modify
void push_back(const T& val = T())
{
//Node* newnode = new Node(val);
//Node* prev = _head->_prev;

//prev->_next = newnode;
//newnode->_prev = prev;
//newnode->_next = _head;
//_head->_prev = newnode;
insert(end(), val);
}

void push_front(const T& val = T())
{
//Node* newnode = new Node(val);
//Node* next = _head->_next;

//_head->_next = newnode;
//newnode->_prev = _head;
//newnode->_next = next;
//next->_prev = newnode;

insert(begin(), val);

}

//_head   1   2
void pop_front()
{
//Node* next = _head->_next->_next;
//_head->_next = next;
//next->_prev = _head;

erase(begin());
}

void pop_back()
{
//Node* prev = _head->_prev->_prev;
//prev->_next = _head;
//_head->_prev = prev;
erase(--end());
//这里不能使用end() - 1，因为没有重载
//这里也得用--end()，因为end()指向的是最后一个元素的下一个位置
}

//             newnode   pos
//_head    1              2      3 
void insert(iterator pos, const T& val = T())
{
Node* newnode = new Node(val);
Node* cur = pos._node;
Node* prev = cur->_prev;
//Node* next = cur->_next;

prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;

_size++;
}

//              pos
//_head    1     2      3 
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;

prev->_next = next;
next->_prev = prev;
delete cur;
cur = nullptr;
_size--;

return next;
}

void clear()
{
iterator it = begin();
while (it != end())
{
//错因：迭代器失效
//pop_front();
//it++;
it = erase(it);
}
}

void swap(list<T>& l)
{
std::swap(_head, l._head);
std::swap(_size, l._size);
}

//List capacity
size_t size()
{
return _size;
}

bool empty()
{
return _size == 0;
}


//Element access:
T& front()
{
if (_head->_next == _head)
cout << "当前链表没有节点,以下值无效" << endl;
return _head->_next->_val;
}

T& back()
{
if (_head->_prev == _head)
cout << "当前链表没有节点,以下值无效" << endl;
return _head->_prev->_val;
}

const T& front() const
{
if (_head->_next == _head)
cout << "当前链表没有节点,以下值无效" << endl;
return _head->_next->_val;
}

const T& back() const
{
if (_head->_prev == _head)
cout << "当前链表没有节点,以下值无效" << endl;
return _head->_prev->_val;
}
private:
Node* _head = nullptr;
size_t _size = 0;
};
}

原文地址：https://blog.csdn.net/2303_79175956/article/details/137836783

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：STM32F401RCT6电子元器件芯片LQFP64 32位微控制器MCU单片机
下一篇：ICV:《中美量子产业融资比较分析》

react 中 useCallback Hook 作用
在 React 函数组件中，每次组件重新渲染时，内部的函数都会被重新创建。
阅读更多2024-11-16
如何在项目中用elementui实现分页器功能
5.在需要用到分页器的组件像服务器发请求（实现按钮和页面跳转的绑定）这是 Element UI 库中的一个组件，用于创建分页器。3.在分页器组件接收参数。
阅读更多2024-11-16
命名空间（namespace）详解（一）
经查可知，头文件stdlib.h中包含了名为atof的函数，此时我们再定义atof的变量就会报错，那么如何解决这个问题呢？就有了命名空间的用法。
阅读更多2024-11-16
ssm102“魅力”繁峙宣传网站的设计与实现+vue(论文+源码)_kaic
目录摘要ABSTRACT第1章绪论1.1背景及意义1.2 国内外研究概况1.3 研究的内容第2章相关技术2.1 JSP技术介绍2.2 JAVA简介2.3 MyEclipse开发环境2.4 T
阅读更多2024-11-16
深度学习--卷积神经网络
一般认为，人对外界的认知是从局部到全局的，而图像的空间联系也是局部的像素联系较为紧密，而距离较远的像素相关性则较弱。用一个或者多个卷积核扫描照片，卷积核自带的参数就是权重，在同一个卷积核扫描的图层当中
阅读更多2024-11-16
go反射深入学习
reflect.ValueOf(&x) 将 x 的地址传递给 reflect.Value，这使得我们能够通过反射修改 x 的值。传递给 reflect.ValueOf() 的是 x 的值，而不
阅读更多2024-11-16
Git如何简单使用
GitGitlabGitLab和GitHub有什么区别？Gitlab简单使用Gitlab常用指令
阅读更多2024-11-16
动态规划-背包问题——[模版]完全背包问题
与01背包相同，这里的完全背包也是需要一个二维dp表来表示最大价值，具体如下。返回最后一个位置dp表的值。从上至下，每一行从左到右。
阅读更多2024-11-16
hhdb数据库介绍(9-14)
介绍hhdb的sql语法支持
阅读更多2024-11-16
初识算法 · 位运算(end)
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）还是和前文一样，通过三个部分介绍，题目解析，算法原理，算法编写来介绍。那么话不多说，进入主题吧！题目解析题目的要求十分简单，是让我们在
阅读更多2024-11-16

C++：STL-list模拟实现：迭代器的封装

STL-list模拟实现细节

一. 模拟实现的思想细节

1.迭代器实现：用类进行封装

2.++和–的重载

3.奇怪的->重载

4.const迭代器

二.实现源码

相关文章