一、前言
二、模拟实现的意义何在？
三、list 的模拟实现
- 类模板：
- 1. ListNode
- （关于 list 的正向迭代器）
- 2.正向迭代器
- 反向迭代器（适配器）
- - - - - - - - - - - - - -
- 3. list
- 成员函数：
- 0.迭代器相关函数
- 正向迭代器
- 反向迭代器
- 1.构造函数
- 2.析构函数
- 3.拷贝构造函数
- 4.赋值重载函数
- 5. insert 函数
- 6. erase 函数
- 7. push_front 函数
- 8. push_back 函数
- 9. pop_front 函数
- 10. pop_back 函数
- 11. clear 函数
一、前言
list 是可以在任意位置以常数时间进行插入和删除 *** 作的序列容器，并且该容器可以前后双向迭代。
可以将 list 简单地理解成双向带头循环链表。
list 是一个类模板。
推荐的 C/C++ 参考文档：http://www.cplusplus.com
二、模拟实现的意义何在？
为了更好地理解 list 的底层实现原理，加深对 list 的认知。
三、list 的模拟实现
首先，先定义 list 。
为了防止命名冲突，将它放在一个叫做 MyLib 的命名空间里。
模拟实现 list 时，与 list 类模板相关的框架参考 SGI 的 STL3.0 版本的源码。
namespace MyLib
{
//ListNode
template<class T>
struct ListNode
{
// ...
};
//正向迭代器
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef ListNode<T> Node;
// ...
};
//list
template<class T>
class list
{
typedef ListNode<T> Node;
// ...
};
}
前两个类模板都是给 list 类模板作铺垫的。
上面只是三个类模板的框架，下面是它们的具体实现。
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
//构造函数
ListNode(const T& data = T())
:_next(nullptr)
,_prev(nullptr)
,_data(data)
{}
};
首先，我们应该知道的是，迭代器是读写容器对象内部元素的接口，它的使用形式与指针相同（模仿指针的使用），支持 *、++、-- 等 *** 作，也就是说，迭代器表现得很像指针。
迭代器有两种实现方式（具体应根据容器底层的数据结构来实现）：
1）原生指针。
2）对原生指针进行封装。
2.正向迭代器1）像 vector 这种在物理上拥有连续的地址空间的容器，原生指针就是迭代器。
2）像 list 这种在物理上没有连续的地址空间的容器，由于迭代器的使用形式与指针相同，支持*、++、-- 等 *** 作，因此须将原生指针进行封装。
实际中可能的调用：
//访问修改 list lt
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
*it += 2; // 修改
cout << *it << " "; // 打印
++it;
}
cout << endl;
由于 list 的迭代器靠第一种实现方式是达不到迭代器本身的使用要求的，所以 list 的迭代器是由原生指针封装而成的。
位于 list 类模板中的几个正向迭代器函数：
//普通版本
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
//const版本
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
正向迭代器类模板：
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef ListNode<T> Node;
typedef __list_iterator<T, Ref, Ptr> self;
Node* _node;
//构造函数
__list_iterator(Node* x)
:_node(x)
{}
//以下函数均为运算符重载函数
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
//++it;
self& operator++() // 前置++
{
_node = _node->_next;
return *this;
}
//it++;
self operator++(int) // 后置++
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
//--it;
self& operator--() // 前置--
{
_node = _node->_prev;
return *this;
}
//it--;
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;
}
};
由于迭代器模仿指针的使用并且节点的 _data 也可能是一个类，因此也需要对 -> 运算符进行重载。
调用 operator-> 函数后，返回的是节点中 _data 的指针（地址），本来应该还要加上 -> 才能访问到对象内部的成员（比如：it->->_year），但是这样写的话可读性差（运算符重载的目的本来就是为了增强可读性），所以编译器进行了优化，省略了一个 -> 。
（编译器不只是对迭代器会这样做，对所有的自定义类型都会这样做）
由于正向迭代器是不涉及空间资源管理的自定义类型，因此它不需要实现深拷贝，同时它也不会涉及内存泄漏的问题。
因此不需要显式定义拷贝构造函数、赋值重载函数和析构函数，系统默认生成的即可。
问：为什么正向迭代器是一个类模板？
答：正向迭代器有 iterator 和 const_iterator 两种，iterator 和 const_iterator 的代码大体一致，而且 const_iterator 只是在 iterator 代码的基础上做了小部分的修改，完全没必要写两份十分类似的代码。
于是，在这种情况下，为了避免出现代码冗余，将两份代码的共同部分抽离出来，不同的部分用模板参数来表示，使正向迭代器成为一个类模板。
位于 list 类模板中的这两行代码的含义，就是上面所说的：
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
反向迭代器（适配器）当这个类模板实例化之后，便是具体的 iterator 和 const_iterator 。
实际中可能的调用：
//访问修改 list lt
list<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend())
{
*rit /= 2; // 修改
cout << *rit << " "; // 打印
++rit;
}
cout << endl;
不难发现，从效果上看，反向迭代器的表现和正向迭代器的表现正好相反。
于是，我们就会想，既然如此，就没必要重新再写一份反向迭代器的代码了，直接对正向迭代器进行封装即可。
实际上，反向迭代器就是由正向迭代器封装而成的。
位于 list 类模板中的几个反向迭代器函数：
//普通版本
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
//const版本
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
反向迭代器类模板：
template<class Iterator, class Ref, class Ptr>
class reverse_iterator
{
typedef reverse_iterator<Iterator, Ref, Ptr> self;
public:
//构造函数
reverse_iterator(Iterator it)
:_it(it)
{}
//以下函数均为运算符重载函数
Ref operator*()
{
Iterator prev = _it;
return *--prev;
}
Ptr operator->()
{
return &operator*();
}
//++rit;
self& operator++() //前置++
{
--_it;
return *this;
}
//rit++;
self operator++(int) // 后置++
{
self tmp(*this);
--_it;
return tmp;
}
//--rit;
self& operator--() // 前置--
{
++_it;
return *this;
}
//rit--;
self operator--(int) // 后置--
{
self tmp(*this);
++_it;
return tmp;
}
bool operator== (const self & rit) const
{
return _it == rit._it;
}
bool operator!= (const self & rit) const
{
return _it != rit._it;
}
private:
Iterator _it;
};
不需要显式定义拷贝构造函数、赋值重载函数和析构函数，系统默认生成的即可，原因与正向迭代器相同。
反向迭代器也是一个类模板，原因跟正向迭代器一样。
位于 list 类模板中的两行代码：
typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
typedef reverse_iterator<iterator, T&, T*> reverse_iterator;
当这个类模板实例化之后，便是具体的 const_reverse_iterator 和 reverse_iterator 。
问：为什么在模拟实现的 list 类模板中，rbegin() 复用 end() ，以及 rend() 复用 begin() 呢？
答：这样做不是没有道理的。 虽然这样做会使反向迭代器中的成员函数的实现看起来有点别扭，但是从大局的角度看，这样做能使这个反向迭代器适配任何支持反向迭代器的容器，即反向迭代器是适配器（只要支持反向迭代器的容器实现好自身的正向迭代器，那么反向迭代器的行为总会是正确的），而不是只局限于 list 容器。 自己来写一份更直观的不复用正向迭代器函数的反向迭代器代码也可以，但是这只适配于 list 容器，而不能适配于其他容器，没有考虑到大局。
（这个设计就是参考 SGI 的 STL3.0 版本的源码，设计源码的大佬考虑得很周全，只能说大佬就是大佬）
只要在支持反向迭代器的容器类模板中加上那两行 typedef 的代码，就能使反向迭代器适配于当前容器。
- - - - - - - - - - - - - 3. list为了避免涉及迭代器萃取，在这里模拟实现的反向迭代器，跟实际的源码有些许差别：
实际的源码只用了一个模板参数：Iterator，
而这里的模拟实现用了三个模板参数：Iterator, Ref 和 Ptr 。
但是在效果上跟源码一样，都能适配任何支持反向迭代器的容器。
template<class T>
class list
{
typedef ListNode<T> Node;
public:
//迭代器（正向和反向）
//1.对正向迭代器类模板进行typedef
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
//2.对反向迭代器类模板进行typedef
typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
typedef reverse_iterator<iterator, T&, T*> reverse_iterator;
//成员函数
private:
Node* _head; // 指向list头节点的节点指针
};
}
图解 list：
下面模拟实现的都是一些比较常用的重载函数。
//普通版本
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
//const版本
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
//普通版本
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
//const版本
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
由于 list 是双向带头循环链表，因此在构造 list 的有效节点前必须先构造头节点。
// 无参构造
// list lt1;
list()
{
//构造头节点
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
// 使用迭代器区间构造
// list lt2(lt1.begin(), lt1.end());
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
//先构造头节点
_head = new Node();
_head->_prev = _head;
_head->_next = _head;
while (first != last)
{
push_back(*first); // 复用push_back函数
++first;
}
}
// list lt1(5, string("hello"));
list(size_t n, const T& val = T())
{
//先构造头节点
_head = new Node();
_head->_prev = _head;
_head->_next = _head;
for (size_t i = 0; i < n; ++i)
{
push_back(val); // 复用push_back函数
}
}
// list lt1(5, 1);
list(int n, const T& val = T())
{
//先构造头节点
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
for (int i = 0; i < n; ++i)
{
push_back(val); // 复用push_back函数
}
}
关于构造函数的最后一个重载函数的说明：
如果没有最后一个重载函数，用若干个内置类型去初始化 list 的话（比如：list< int > lt1(5, 1); ，两个实参是 int 类型），虽然第二个和第三个重载函数都能匹配，但是编译器会认为第二个重载函数更匹配，这不符合我们的期望。
因为第二个重载函数的两个参数都是模板参数，可以都被推演为 int 类型，能完全匹配，
而第三个重载函数的参数 size_t 和 int 不匹配，需要 int 隐式类型转换为 size_t 才能匹配得上，
于是编译器会认为第二个重载函数更能满足要求。
于是，为了解决这个问题，我们再提供一个重载函数（就是最后一个重载函数），就是将第三个重载函数的第一个参数由原来的 size_t 改为 int ，这样对于语句 list< int > lt1(5, 1); ，编译器就会调用最后一个重载函数，这就符合期望了。
2.析构函数虽然第二个重载函数仍然比最后一个重载函数更能匹配，但是第二个重载函数是一个函数模板，它并非是现成的，需要被推演，
而最后一个重载函数虽然只是部分匹配，但它是现成的，
编译器会优先匹配现成的。
~list()
{
clear(); // 复用clear函数
delete _head; // 释放头节点
_head = nullptr;
}
// list lt2(lt1);
//现代写法
list(const list<T>& lt)
{
//先构造头节点
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
list<T> tmp(lt.begin(), lt.end()); // 复用使用迭代器区间构造的构造函数
std::swap(_head, tmp._head);
}
//传统写法
list(const list<T>& lt)
{
//先构造头节点
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
for (auto e : lt)
{
push_back(e); // 复用push_back函数
}
}
// lt1 = lt2;
//更简洁的现代写法
list<T>& operator=(list<T> lt)
{
std::swap(_head, lt._head);
return *this;
}
//传统写法
list<T>& operator=(const list<T>& lt)
{
if (this != <)
{
clear(); // 复用clear函数
for (auto e : lt)
{
push_back(e); // 复用push_back函数
}
}
return *this;
}
// lt1.insert(pos, 7);
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
6. erase 函数insert 函数的 pos 迭代器不会失效，因为它的意义并没有改变，而且其内部的指针也没有野指针的问题。
STL 规定，应返回一个指向刚插入的节点的迭代器，这里仿照规定。
// lt1.erase(pos);
iterator erase(iterator pos)
{
//不能删掉头节点
assert(pos != end());
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
delete pos._node;
prev->_next = next;
next->_prev = prev;
return iterator(next);
}
7. push_front 函数erase 函数的 pos 迭代器一定会失效，因为它指向的节点被释放了，其内部的指针会变成野指针。
STL 规定，应返回一个指向被释放节点的后一个节点的迭代器，这里仿照规定。
// lt1.push_front(4);
//或 lt1.push_front(string("hello"));
void push_front(const T& val)
{
insert(begin(), val); // 复用insert函数
}
// lt.push_back(3);
//或 lt.push_back(string("hello"));
void push_back(const T& val)
{
insert(end(), val); // 复用insert函数
//这样写也可以
/*Node* tail = _head->_prev;
Node* newnode = new Node(val);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;*/
}
// lt1.pop.front();
void pop_front()
{
erase(begin()); // 复用erase函数
}
// lt1.pop.back();
void pop_back()
{
erase(--end()); // 复用erase函数
}
删掉所有的有效节点。
// lt1.clear();
void clear()
{
iterator it = begin();
while (it != end())
{
erase(it++); // 复用erase函数
}
//这样写也可以
/*iterator it = begin();
while (it != end())
{
iterator del = it++;
delete del._node;
}
_head->_next = _head;
_head->_prev = _head;*/
}
更多文章：
C++ STL中 vector 的模拟实现
C++ STL中 string类的模拟实现
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）