前言
这篇文章对于理解封装是非常有帮助的，list的底层是双向链表结构，我们在学习数据结构是就已经学过了双向链表，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。因为list独特的结构，在模拟实现的时候就会发现为了list接口更好为用户使用更多是通过封装。
这篇文章会开始从list的使用开始，看完list的使用之后你会发现跟string和vector的接口使用几乎是一样的，虽然他们的使用是一样的，他的接口都是一样的，但是后面我们通过对接口的模拟实现，你就会发现是不一样，到底哪里不一样就需要你的深入观看--卖个关子。总的来说这篇文章就是来展示迭代器的魅力和模板的魅力。
目录
一、list的介绍及使用
1.1list的介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。因为list的底层是双向链表结构。
list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。
带头循环双向链表
1.2.list的使用
对于list的使用来说，list中的接口比较多，实则是与vector差不多的，接下来我们就来简单的演示，掌握list正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。
1.2.1 list的构造
| 构造函数（ (constructor)） | 接口说明 |
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
例：
-
void TestList1()
-
{
-
list<
int> l1;
// 构造空的l1
-
list<int> l2(4, 100);
// l2中放4个值为100的元素
-
list<int> l3(l2.begin(), l2.end());
// 用l2的[begin(), end()）左闭右开的区间构造l3
-
list<int> l4(l3);
// 用l3拷贝构造l4
-
-
// 以数组为迭代器区间构造l5
-
int array[] = {
16,
2,
77,
29 };
-
list<int> l5(array, array + sizeof(array) / sizeof(int));
-
-
// 列表格式初始化C++11
-
list<
int> l6{
1,
2,
3,
4,
5 };
-
-
// 用迭代器方式打印l5中的元素
-
list<
int>::iterator it = l5.
begin();
-
while (it != l5.
end())
-
{
-
cout << *it <<
" ";
-
++it;
-
}
-
cout << endl;
-
-
// C++11范围for的方式遍历
-
for (
auto& e : l5)
-
cout << e <<
" ";
-
-
cout << endl;
-
}
1.2.2 list iterator的使用
在list使用中，我们通过迭代器的方式打印链表元素，在vector中我们用的是[],因为vector是顺序表结构，我们可以通过下标进行随机访问。而list却不能，只能用迭代器的方式进行，它的行为像指针一样。这个后面会通过源码剖析的角度来看待，这里就简单的认为迭代就类似于指针。
list是链表结构，在链表中因为内存地址不是连续开辟的，比如：通过下标2去找地址，顺序表中，地址是连续对应的，而链表的地址是随机开辟的，通过下标是不能找到相应的地址的。
以上就是证明为什么list不能用[]访问，而选择用迭代器。
| 函数声明 | 接口说明 |
| begin+end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
例：
-
// list迭代器的使用
-
// 注意：遍历链表只能用迭代器和范围for
-
void PrintList(const list<int>& l)
-
{
-
// 注意这里调用的是list的 begin() const，返回list的const_iterator对象
-
for (list<
int>::const_iterator it = l.
begin(); it != l.
end(); ++it)
-
{
-
cout << *it <<
" ";
-
// *it = 10; 编译不通过
-
}
-
-
cout << endl;
-
}
-
-
int main()
-
{
-
list<
int> l;
-
l.
push_back(
1);
-
l.
push_back(
2);
-
l.
push_back(
3);
-
l.
push_back(
4);
-
-
-
PrintList(l);
-
-
return
0;
-
}
这里需要说明一下就是begin和end既能使用iterator又能使用const_iterator。
begin iterator begin();const_iterator begin() const; end iterator end();const_iterator end() const;
使用const_iterator it =l.begin()；这里是通过拷贝构造，即使我们没有写拷贝构造，但是系统会默认生成拷贝构造将指针进行拷贝。
const_iterator it = l.begin();
1.2.3list capacity
在链表中就不需要提前把空间开好，这里是按需申请，就不需要reserve和resize了。
| 函数声明 | 接口说明 |
| empty | 检测list是否为空，是返回true，否则返回false |
| size | 返回list中有效节点的个数 |
例：
-
int
main()
-
{
-
list<int> l;
-
l
.push_back(
1);
-
l
.push_back(
2);
-
l
.push_back(
3);
-
l
.push_back(
4);
-
-
cout << l
.size() << endl;
-
if (!l.empty())
-
{
-
cout << "no empty!" << endl;
-
}
-
-
return
0;
-
}
1.2.4 list element access
| 函数声明 | 接口说明 |
| front | 返回list的第一个节点中值的引用 |
| back | 返回list的最后一个节点中值的引用 |
例：
-
void
tets_element(list<int>& l)
-
{
-
-
cout << l
.front() << endl;
-
cout << l
.back() << endl;
-
}
1.2.5 list modifiers
| 函数声明 | 接口说明 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| insert | 在list position 位置中插入值为val的元素 |
| erase | 删除list position位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
例：
-
// list插入和删除
-
void test_modifi
ers()
-
{
-
list <
int> l;
-
//尾插
-
l.
push_back(
1);
-
l.
push_back(
2);
-
l.
push_back(
3);
-
l.
push_back(
4);
-
-
//尾删
-
l.
pop_back();
-
PrintList(l);
-
-
cout << endl;
-
//头插
-
l.
push_front(
6);
-
l.
push_front(
7);
-
l.
push_front(
8);
-
-
//头删
-
l.
pop_front();
-
PrintList(l);
-
-
cout << endl;
-
-
//第一个位置插入10
-
auto pos = l.
begin();
-
l.
insert(pos,
10);
-
PrintList(l);
-
-
cout << endl;
-
-
// 删除pos位置上的元素
-
l.
erase(++pos);
-
PrintList(l);
-
-
}
-
-
// resize/swap/clear
-
void TestList5()
-
{
-
// 用数组来构造list
-
int array1[] = {
1,
2,
3 };
-
list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
-
PrintList(l1);
-
-
// 交换l1和l2中的元素
-
list<
int> l2;
-
l1.
swap(l2);
-
PrintList(l1);
-
PrintList(l2);
-
-
// 将l2中的元素清空
-
l2.
clear();
-
cout << l2.
size() << endl;
-
}
1.2.6 list的迭代器失效
之前在vector中insert是失效的，但是在list中insert是不失效的。因为insert插入并没有改变pos的地址。erase却会失效，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
例：
-
void
TestListIterator1()
-
{
-
int
array[] = {
1,
2,
3,
4,
5,
6,
7,
8,
9,
0 };
-
list<
int>
l(
array,
array +
sizeof(
array) /
sizeof(
array[
0]));
-
-
auto it = l.
begin();
-
while (it != l.
end())
-
{
-
// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
-
-
l.
erase(it);
-
++it;
-
}
-
}
-
-
void
TestListIterator()
-
{
-
int
array[] = {
1,
2,
3,
4,
5,
6,
7,
8,
9,
0 };
-
list<
int>
l(
array,
array+
sizeof(
array)/
sizeof(
array[
0]));
-
-
auto it = l.
begin();
-
while (it != l.
end())
-
{
-
l.
erase(it++);
// it = l.erase(it);
-
-
}
-
}
1.2.7 sort
在list中单独有sort，在之前是以模板的形式写入算法库<algorithm>。这里就说明因为它是已链表的结构，排序需要重新实现，那么就意味着list中sort的时间复杂度是不一样的。
list::sort void sort(); std::sort template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last);
我们通过一段测试代码来比较，同样的长度但是花费时间是巨大的。
-
void test_op()
-
{
-
srand(
time(
0));
-
const
int N =
100000;
-
vector<
int> v;
-
v.
reserve(N);
-
-
list<
int> lt1;
-
list<
int> lt2;
-
for (
int i =
0; i < N; ++i)
-
{
-
auto e =
rand();
-
//v.push_back(e);
-
lt1.
push_back(e);
-
lt2.
push_back(e);
-
}
-
-
// 拷贝到vector排序，排完以后再拷贝回来
-
int begin1 =
clock();
-
for (
auto e : lt1)
-
{
-
v.
push_back(e);
-
}
-
sort(v.
begin(), v.
end());
-
size_t i =
0;
-
for (
auto& e : lt1)
-
{
-
e = v[i++];
-
}
-
int end1 =
clock();
-
-
int begin2 =
clock();
-
// sort(lt.begin(), lt.end());
-
lt2.
sort();
-
int end2 =
clock();
-
-
printf(
"vector sort:%d\n", end1 - begin1);
-
printf(
"list sort:%d\n", end2 - begin2);
-
}
在运行结果：
1.Debug
vector sort:437
list sort:69372.Release
vector sort:7
list sort:16
在N个数据需要排序，vector+ 算法sort list+ sort通过测试发现list中sort是非常耗时的，vector中sort想对来说更加省时直接用list排序还不如将list的数据拷贝到vector中快。
二、list的模拟实现--非const
我们会通过几个阶段来进行模拟实现，如果一下将全部模拟实现是加大了学习的成本，是对学习很不友好的。
2.1list的节点
因为我们知道list是一个双向链表，所以节点里面有一个前指针，一个后指针，有一个数据data。同时我们也模拟一个构造函数list (const list& x)，用于list节点的初始化。
-
template
<
class
T
>
-
struct list_node
-
{
-
list_node
<
T
>
* _
next;
-
list_node
<
T
>
* _prev;
-
T _data;
-
-
/
/构造函数
-
list_node
(const
T
& x
)
-
:_
next
(nullptr
)
-
, _prev
(nullptr
)
-
, _data
(x
)
-
{
}
-
};
2.2list的迭代器
stl3.0当中的迭代器实现：
-
template<
class
T,
class
Ref,
class
Ptr>
-
struct
__list_iterator {
-
typedef __list_iterator<T, T&, T*> iterator;
-
typedef __list_iterator<T,
const T&,
const T*> const_iterator;
-
typedef __list_iterator<T, Ref, Ptr> self;
-
-
typedef bidirectional_iterator_tag iterator_category;
-
typedef T value_type;
-
typedef Ptr pointer;
-
typedef Ref reference;
-
typedef __list_node<T>* link_type;
-
typedef
size_t size_type;
-
typedef
ptrdiff_t difference_type;
-
-
link_type node;
-
-
__list_iterator(link_type x) :
node(x) {}
-
__list_iterator() {}
-
__list_iterator(
const iterator& x) :
node(x.node) {}
-
-
bool
operator==(
const self& x)
const {
return node == x.node; }
-
bool
operator!=(
const self& x)
const {
return node != x.node; }
-
reference
operator*()
const {
return (*node).data; }
-
-
#ifndef __SGI_STL_NO_ARROW_OPERATOR
-
pointer
operator->()
const {
return &(
operator*()); }
-
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
-
-
self&
operator++() {
-
node = (link_type)((*node).next);
-
return *
this;
-
}
-
self
operator++(
int) {
-
self tmp = *
this;
-
++*
this;
-
return tmp;
-
}
-
self&
operator--() {
-
node = (link_type)((*node).prev);
-
return *
this;
-
}
-
self
operator--(
int) {
-
self tmp = *
this;
-
--*
this;
-
return tmp;
-
}
对于stl3.0当中的迭代器实现，我们首先不去关系为什么是3个模板参数，也不用去深研其他的typedef，我们可以理解在iterator中不单单是一个指针了，当然在iterator也有指针，如下
typedef __list_node<T>* link_type;
link_type node;
在之前我们理解中，我们直接对指针进行操作，进行++，--，*（解引用）等等操作，但是对于迭代器iterator，我们通过观察发现iterator中，因为list是链式结构，我们对其++，--，接引用是不能直接实现，所以就不能简单的通过指针就能完成这些操作，那么它是通过对iterator封装来实现++，--等操作的。使用++，--等操作是通过函数调用
大家感兴趣可以先看看上面的，我们先用一个简述版的来带大家简要实现一下
-
template <
class
T>
-
struct _list_iterator
-
{
-
typedef list_node<T> node;
-
node* _pnode;
-
-
//构造函数
-
_list_iterator(node* p)
-
:_pnode(p)
-
{}
-
-
//接引用就是返回节点的值
-
T&
operator*()
-
{
-
return _pnode->_data;
-
}
-
-
//++操作就是就将当前指向下一个节点
-
_list_iterator<T>&
operator++()
-
{
-
_pnode = _pnode->_next;
-
return *
this;
-
}
-
-
//--操作就是将当前指向前一个节点
-
_list_iterator<T>&
operator--()
-
{
-
_pnode = _pnode->_prev;
-
return *
this;
-
}
-
-
//不等于传参节点的指针不等于this节点的指针
-
bool
operator!=(
const _list_iterator<T>& it)
-
{
-
return _pnode != it._pnode;
-
}
-
-
};
2.2迭代器的价值
这里虽然我们使用vector和list的使用方法是基本类似的，但是我们发现他们的底层已经出现很大的差别。这里*（接引用），在gcc下的vector中我们是直接对原生指针进行操作，但是在list下我们是通过函数调用来实现的。
最后关于迭代器需要强调一点，关于vector中的 iterator其实他可能也不是用原生指针，这个需要看代码的实现，因为我们在gcc和vs中我们发现迭代器失效，他们失效并不一样，意味着他们底层代码实现时不一样的，在gcc它可以是通过原生指针的方式实现，在vs也可以通过封装来实现。
结论：
1.封装底层实现，不暴露底层的实现细节
2.提供统一访问方式，降低使用成本
物理层面比较
对于list类封装中的iteratior与vector中的iteratior的字节大小是一样的，他们都是4字节。
为什么list也是4字节，因为只看成员变量，不看函数。所以说指针在类中封装后并没有变大，在内存中还是实实在在的4byte。
他们不同的是list中存的时候节点位置的指针，而vector中的是数据位置的指针。
所以在物理层面上他们是没有区别的，他们字节的大小是一样的，但是他们的类型不一样，底层实现就是天差地别了--类型的力量。
2.3list的接口
-
template <
class
T>
-
class
list
-
{
-
typedef list_node<T> node;
-
public:
-
typedef _list_iterator<T> iterator;
-
-
-
iterator
begin(
)
-
{
-
//使用了匿名对象--调用拷贝构造
-
return
iterator(_head->_next);
-
}
-
-
iterator
end(
)
-
{
-
return
iterator(_head);
-
}
-
-
//当为null时，next与prev都指向head
-
void
empty_initalize(
)
-
{
-
_head =
new
node(
T());
-
_head->_next = _head;
-
_head->_prev = _head;
-
}
-
-
//为null调用empty_initalize
-
list(
)
-
{
-
empty_initalize();
-
}
-
-
//拷贝构造
-
list(
const list<T> & lt)
-
{
-
empty_initalize();
-
//这里需要特别注意&（引用）
-
//如果是内置类型就不影响，e接受数据后，push_back传入后销毁，下一个传又是从lt引用
-
//如果lt是其他类型，比如是vector类型或者是泛型，数据是一串，
-
//当push_back完后，没有用引用那么push_back会销毁，传一个数据他销毁了再传一个数据它又没了
-
for (
const auto &e : lt)
-
{
-
push_back(e);
//this.push_back
-
}
-
-
return *
this;
//返回链接值 head->1->2->3
-
}
-
-
//析构函数
-
~
list(
)
-
{
-
clear();
//第一步清楚数据
-
-
//第二步将头结点置空
-
delete _head;
-
_head = nullptr;
-
}
-
-
//将数据一一清理
-
void
clear(
)
-
{
-
iterator it =
begin();
-
while (it !=
end())
-
{
-
it =
erase(it);
-
}
-
}
-
-
list<T>& operator=(
const list<T>& lt)
-
{
-
if (
this != <)
//判断链表数据不一样后进行操作
-
{
-
clear();
//先清空
-
for (
const auto&e : lt)
//传值
-
{
-
push_back(e);
-
}
-
}
-
-
}
-
-
//头插
-
void
push_front(
const T& x)
-
{
-
insert(
begin(), x);
//调用insert
-
}
-
-
//头删
-
void
pop_front(
)
-
{
-
erase(
begin());
//调用erase
-
}
-
-
//尾删
-
void
pop_back(
)
-
{
-
erase(--
end());
-
}
-
-
//尾插
-
void
push_back(
const T& x)
-
{
-
node* newnode =
new
node(x);
-
node* tail = _head->_prev;
-
-
tail->_next = newnode;
-
newnode->_prev = tail;
-
newnode->_next = _head;
-
_head->_prev = newnode;
-
-
//insert(end(),x)
-
}
-
-
iterator
insert(
iterator pos, const T& x)
-
{
-
node* newnode =
new
node();
//新建节点
-
node* cur = pos.
_pnode;
//插入节点是在数据后插，保存改数据后的节点
-
node* prev = cur.
_prve;
//保存数据前的节点
-
-
//4步链接头尾
-
prev->_next = newnode;
-
newnode->_prev = prev;
-
newnode->_next = cur;
-
cur->_prev = newnode;
-
-
return
iterator(newnode);
//返回节点
-
}
-
-
iterator
erase(
iterator pos)
-
{
-
assert(pos !=
end());
//不能删除头节点
-
-
node* prev = pos.
_pnode->_prev;
//保存pos前的节点
-
node* next = pos.
_pnode->_next;
//保存pos后的节点
-
-
prev->_next = next;
//将后节点链接前节点
-
next->_prev = prev;
//将前节点链接后节点
-
-
delete pos.
_pnode;
//删除pos节点--会失效
-
-
return
iterator(next);
//返回pos节点后的节点
-
-
}
-
-
private:
-
node* _head;
-
};
list接口的模拟实现主要insert和erase有些难度，但是对于写过数据结构的代码，我相信大家稍花功夫就能够轻松解决。
insert图解如下
erase图解如下
三、list的模拟实现--const
下面内容主要是迭代器被const修饰，普通人的写法和大佬的写法，他们尽显锋芒。
3.1理解const修饰iterator
错误写法
-
void list_test(const list<int>& lt)
-
{
-
const list<
int>::iterator lt1 = lt.
begin();
-
}
首先需要理解const T* p1与T* const p2，const迭代器类似p1的行为，保护指向对象不被修改，但是迭代器本身是可以被修改的。
这里的const是修饰的lt1，不符合const迭代器的行为，因为他保护迭代器本身不能修改，那么我们也就不能++迭代器。
因为iterator是被封装使用的，我们发现在struct _list_iterator中，我们改变其返回值用const修饰，那么我们还是可以对迭代器进行++，--等操作，只是返回值不能被改变。
-
T&
operator*()
-
{
-
return _pnode->_data;
-
}
既然是需要const修饰返回值，那么我们能不能直接通过函数重载来支持呢？
-
T&
operator*()
-
{
-
return _pnode->_data;
-
}
-
-
const T&
operator*()
const
-
{
-
return _pnode->_data;
-
}
答案是不能的。如果clt（被const修饰的参数）++，就调用operator++()，返回值是不被修改，这里的this也被const修改，那么this指向的节点都被修改，该节点就不能实现++操作，这样实现的话只能接引用，但不能++。
-
const T&
operator*()
const
-
{
-
return _pnode->_data;
-
}
-
-
_list_iterator<T>&
operator++()
-
{
-
_pnode = _pnode->_next;
-
return *
this;
-
}
如果我们是实现
const _list_iterator<T>& operator++() const
答案也是不行的，因为这个过程就是对this值进行操作，这里其实就this已经都被const修饰了。有点绕但是我们主要需要知道整个this值，不然很容易就昏了。
3.2实现const修饰iterator
既然上述解释了在一个类中通过函数重载，const修饰的this会影响，因为我们需要函数重载的话，const不仅仅需要修返回值，也要修改this，上面写法就是错误的
const T& operator*() const
那么我们重新建立类，其他不变，只将返回参数改成被const修饰即可。
const T& operator*()
-
template<
class
T>
-
struct _list_const_iterator
-
{
-
typedef list_node<T> node;
-
node* _pnode;
-
-
_list_const_iterator(node* p)
-
:_pnode(p)
-
{}
-
-
const T&
operator*()
-
{
-
return _pnode->_data;
-
}
-
-
_list_const_iterator<T>&
operator++()
-
{
-
_pnode = _pnode->_next;
-
return *
this;
-
}
-
-
_list_const_iterator<T>&
operator--()
-
{
-
_pnode = _pnode->_prev;
-
return *
this;
-
}
-
-
bool
operator!=(
const _list_const_iterator<T>& it)
-
{
-
return _pnode != it._pnode;
-
}
-
};
我们建立了两个类，所以我们在list直接进行用就可以了。添加上begin+end被const修饰的接口就可以了。
-
template <
class
T>
-
class
list
-
{
-
typedef list_node<T> node;
-
public:
-
typedef _list_iterator<T> iterator;
-
typedef _list_const_iterator<T> const_iterator;
-
-
const_iterator begin() const
-
{
-
return
const_iterator(_head->_next);
-
}
-
-
const_iterator end() const
-
{
-
return
const_iterator(_head);
-
}
-
}
四、list的模拟实现--大佬的iterator
上面写的iterator，我们发现大多数代码都是一样的，仅仅是返回值不一样，就建立了两个类，这样的话代码就比较冗余。那么大佬是不可能写出这样的代码，大佬就通过增加模板参数就很好的解决这一问题了。
4.1第三个参数
原来模板参数只有一个类型，现在将模板参数增加为两个，以前我们是通过自己构建两个类，来实现他们不同功能，但是我们直接在模板里多增加一个类型，编译器就默认实例化两个类型。
template<class T, class Ref>
同一个类模板实例化出的2个类型
typedef __list_iterator<T, T&,> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
这里T就是普通参数，Ref就是被const修饰的参数。那么在看源码的时候有三个参数，这里就不得不提到返回数据的指针了。
-
struct
pos
-
{
-
int _row;
-
int _col;
-
-
pos(
int row=
0,
int col=
0)
-
:_row(row)
-
, _col(col)
-
{
-
-
}
-
};
-
-
int main()
-
{
-
list<
pos>
lt;
-
pos p1(
1,
1);
-
lt.push_back(p1);
-
lt.push_back(p1);
-
lt.push_back(p1);
-
lt.push_back(
pos(
2,
2));
-
lt.push_back(
pos(
3,
3));
-
-
list<
pos>::iterator it = lt.begin();
-
-
while (it != lt.end())
-
{
-
cout << (*it)._row <<
":" << (*it)._col << endl;
-
++it;
-
}
-
-
return
0;
-
}
我们在结构体中，是通过接引用（迭代器的位置）的值，该值再通过.去访问结构体中的行的值。这样用起来是非常别扭，以前访问结构体就是直接地址->指向实参，it->_row。
回忆C语言中->的用法
-
struct Data
-
{
-
int a, b, c;
-
};
-
-
int main()
-
{
-
struct Data * p;
-
struct Data A = {
1,
2,
3 };
-
-
int x;
-
p = &A;
-
x = p->a;
-
-
cout << x << endl;
-
-
return
0;
-
-
}
这里it是迭代器，所以我们需要封装->，然后在进行应用。
Ptr operator->()
{
return &_pnode->_data;
}
Ptr返回的是节点数据的地址，拥有->后，我们再看看使用。
while (it != lt.end())
{
cout << it->_row << ":" << it->_col << endl;
++it;}
it->_row是什么意思？it->是调用it.operator->(),返回节点数据的地址，紧接着是返回节点数据的地址->_row，正确的写法应该是it->->_row。但是这是既不好看又不好用，编译器为了可读性，省略了一个->。
while (it != lt.end())
{
cout << it.operator->()->_row << ":" << it->_col << endl;
++it;}
当然这样用也是不错的。
综上所述知道我们所添加的第三个参数就是T*,用于接受返回的地址。
template<class T, class Ref, class Ptr>
typedef __list_iterator<T, T&, T*> iterator;
4.2大佬的iterator
-
#pragma once
-
#include<assert.h>
-
-
namespace bit
-
{
-
template<
class
T>
-
struct
list_node
-
{
-
list_node<T>* _next;
-
list_node<T>* _prev;
-
T _data;
-
-
list_node(
const T& x)
-
:_next(
nullptr)
-
, _prev(
nullptr)
-
, _data(x)
-
{}
-
};
-
-
// 同一个类模板实例化出的2个类型
-
// typedef __list_iterator<T, T&, T*> iterator;
-
// typedef __list_iterator<T, const T&, const T*> const_iterator;
-
template<
class
T,
class
Ref,
class
Ptr>
-
struct
__list_iterator
-
{
-
typedef list_node<T> node;
-
typedef __list_iterator<T, Ref, Ptr> Self;
-
node* _pnode;
-
-
__list_iterator(node* p)
-
:_pnode(p)
-
{}
-
-
//因为很多时候我们需要返回到数据的指针
-
//返回数据的指针
-
Ptr
operator->()
-
{
-
return &_pnode->_data;
-
}
-
-
-
Ref
operator*()
-
{
-
return _pnode->_data;
-
}
-
-
-
Self&
operator++()
-
{
-
_pnode = _pnode->_next;
-
return *
this;
-
}
-
-
// it++
-
Self
operator++(
int)
-
{
-
Self tmp(*this);
-
_pnode = _pnode->_next;
-
return tmp;
-
}
-
-
Self&
operator--()
-
{
-
_pnode = _pnode->_prev;
-
return *
this;
-
}
-
-
Self
operator--(
int)
-
{
-
Self tmp(*this);
-
_pnode = _pnode->_prev;
-
return tmp;
-
}
-
-
bool
operator!=(
const Self& it)
const
-
{
-
return _pnode != it._pnode;
-
}
-
-
bool
operator==(
const Self& it)
const
-
{
-
return _pnode == it._pnode;
-
}
-
};
-
-
-
-
//vector<int>
-
//vector<string>
-
//vector<vector<int>>
-
-
// 类名 类型
-
// 普通类 类名 等价于 类型
-
// 类模板 类名 不等价于 类型
-
// 如：list模板 类名list 类型list<T>
-
// 类模板里面可以用类名代表类型，但是建议不要那么用
-
template<
class
T>
-
class
list
-
{
-
typedef list_node<T> node;
-
public:
-
typedef __list_iterator<T, T&, T*> iterator;
-
//typedef __list_const_iterator<T> const_iterator;
-
typedef __list_iterator<T,
const T&,
const T*> const_iterator;
-
-
const_iterator begin() const
-
{
-
return
const_iterator(_head->_next);
-
}
-
-
const_iterator end() const
-
{
-
return
const_iterator(_head);
-
}
-
-
iterator begin()
-
{
-
return
iterator(_head->_next);
-
}
-
-
iterator end()
-
{
-
//iterator it(_head);
-
//return it;
-
return
iterator(_head);
-
}
-
-
void empty_initialize()
-
{
-
_head =
new
node(
T());
-
_head->_next = _head;
-
_head->_prev = _head;
-
-
_size =
0;
-
}
-
-
list()
-
{
-
empty_initialize();
-
}
-
-
//迭代器区间构造
-
template <
class
InputIterator>
-
list(InputIterator first, InputIterator last)
-
{
-
empty_initialize();
-
while (first != last)
-
{
-
push_back(*first);
-
++first;
-
}
-
}
-
-
void swap(list<T>& lt)
-
{
-
std::
swap(_head, lt._head);
-
std::
swap(_size, lt._size);
-
}
-
-
// 现代写法--复用
-
// lt2(lt1)
-
list(
const list<T>& lt)
//在类内部：类名 等等价于 类型
-
//list(const list& lt) // 这里list<T>&与list&是一样的，但是不建议用
-
{
-
empty_initialize();
-
-
list<T> tmp(lt.begin(), lt.end());
//复用迭代器区间构造
-
swap(tmp);
//交换head和size
-
-
}
-
-
// lt3 = lt1
-
list<T>&
operator=(list<T> lt)
//不能加&，因为就是需要交换的是lt的拷贝
-
//list& operator=(list lt) // 不建议
-
{
-
swap(lt);
-
return *
this;
-
}
-
-
size_t size() const
-
{
-
return _size;
-
}
-
-
bool empty() const
-
{
-
return _size ==
0;
-
}
-
-
~
list()
-
{
-
clear();
-
-
delete _head;
-
_head =
nullptr;
-
}
-
-
void clear()
-
{
-
iterator it =
begin();
-
while (it !=
end())
-
{
-
it =
erase(it);
-
}
-
}
-
-
void push_back(const T& x)
-
{
-
insert(
end(), x);
-
}
-
-
void push_front(const T& x)
-
{
-
insert(
begin(), x);
-
}
-
-
void pop_front()
-
{
-
erase(
begin());
-
}
-
-
void pop_back()
-
{
-
erase(--
end());
-
}
-
-
iterator insert(iterator pos, const T& x)
-
{
-
node* newnode =
new
node(x);
-
node* cur = pos._pnode;
-
node* prev = cur->_prev;
-
-
// prev newnode cur
-
prev->_next = newnode;
-
newnode->_prev = prev;
-
newnode->_next = cur;
-
cur->_prev = newnode;
-
-
++_size;
-
-
return
iterator(newnode);
-
}
-
-
iterator erase(iterator pos)
-
{
-
assert(pos !=
end());
-
-
node* prev = pos._pnode->_prev;
-
node* next = pos._pnode->_next;
-
-
prev->_next = next;
-
next->_prev = prev;
-
-
delete pos._pnode;
-
--_size;
-
-
return
iterator(next);
-
}
-
-
private:
-
node* _head;
-
size_t _size;
//为了减少后续频繁调用循环查找size
-
};
-
}
完结！
转载：https://blog.csdn.net/includeevey/article/details/128554418