STL源码剖析学习-深度探索list

list的部分源码如右图的中间方框所示：

• 一个关键的地方是，list是一个模板类，这个类的数据成员只有一个，那就是 link_type node; 那么link_type是什么呢？ 向上看， typedef list_node* link_type; link_type是一个指针，指向了list_node的对象。既然link_type是一个指针，那么指针的大小在32位操作系统是4个字节，因此一个list的对象大小应该是4字节。

• list_node是一个结构体，如右图第一个方框所示，也是一个模板类，与数据结构中链表的定义无差；除了数据域意外，包含两个指针(void*)，实现双向连接; 那么 void*意味着，运作的时候还需要格式转换 (GNU2.9版本)。

• list的迭代器(iterator)，list是链表，连接的内容是不连续的内存空间，list的iterator是模拟指针的行为(smart_pointer)，但不是一个实际上的指针。因为iterator++意味着指向下一个node，而指针的++不容易确定。因此，iterator类需要对一些操作符进行重载。

• iterator为了模仿指针的行为，重载了一些指针的操作符，例如*取值，->操作对象，++等。
• C++语言对操作符重载时的 i++和++i 这种语句进行了确定，++i的操作符重载没有参数，i变成了调用这个操作符对象的本身，对于i++这种行为，将i作为参数传递到操作符函数中。

• 对于++i，没有参数的操作符重载，self & operator++() {node = (link_type) ((*node).next); return *this); } node上文讲了是一个指针，指向list结点的指针。这里将node的next指针赋给了自己，因此node指向了后续结点。这里对this需要仔细的思考，这是一个iterator类，this指向的应该是iterator对象，因此*this得到的结果应该是一个iterator对象，一个smart_pointer，return *this 也就是 return i (指向下一个结点的node对象);
• 对于i++，有参数的操作符重载，self & operator++(int) { self tmp = *this; ++*this; return tmp; } 因为iterator类重载了操作符，其功能是取node.data；那么这里的self tmp = *this; 有可能会被轻易的认为是取出data值，但其实不是的。正如上一段所讲，this是指向iterator对象的指针，this就只是一个普通的指针，*this得到的结果应该是一个iterator对象。self tmp = this; 所以tmp = this 是iterator对象的拷贝构造过程，这个=操作符的重载即是拷贝构造的过程。因此tmp拷贝构造了一个对象，与this一样；然后this++执行了无参数的++操作符重载，然后返回的值是tmp，因此实现了i++的后置功能。
• C++的int操作中，不允许使用 i++++这种情况，因为后置++的返回值是value，是右值，不是reference，而右值是不允许++运算的。iterator向int看齐，因此iterator++++也是不允许的，为了阻止两次++，带参数的++操作符重载返回的是一个self，也就是一个临时的，而不是引用self&。

GNU4.9版本对list源码的改进

• 关于list的iterator模版类的定义，从之前的3个参数减少到了1个参数，但实际上的功能是没有发生变化的，之前的3个参数是T、T的引用和T的指针，确实只需要传递T的类型就可以了。
• GNU2.9版本中list_node的设计，前后两个指针指向了void*的类型，这似乎不是非常理想的方式，似乎意味着大量的类型转换。4.9版本中，定义了_List_node_base结构体，包含了指向自身的两个首尾结点，List_node继承它。

GNU4.9版本中，list源码被设计的更加复杂，首先list类自身没有任何数据成员，但list继承于List_base类，List_base类有成员_List_impl类对象，_List_impl有数据成员_M_node,它是_List_node_base类型，也就是两个首尾指针，因此一个list类的大小变成了2个首尾指针的大小，8字节。

• 这里想浅谈一下STL容器的前闭后开原则，[…)；可以看到无论是GNU2.9还是4.9版本中，list这个双向循环链表都有一个结点（图中蓝色），用来连接list的首结点和尾结点。list的iterator源码中，begin()的源码是这个空闲结点的next，end()方法得到的就是这个空闲结点的引用。 其实一般的说，end()得到的迭代器指向的是容器最后一个元素的下一个位置，这个位置是一个内存空间无法预估，用来符合STL前闭后开的设计方法。end()这样的设计更好的辅助了使用iterator循环、查找find等方法。