STL-list模拟实现细节
- 一. 模拟实现的思想细节
- 1.迭代器实现：用类进行封装
- 2.++和--的重载
- 3.奇怪的->重载
- 4.const迭代器
- 二.实现源码
一. 模拟实现的思想细节
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;
};
}
