STL源码解析--list揭秘
1 list简介
list也是最经常使用的一个容器，尤其是在对容器中的元素进行频繁的插入和删除时，通过指针操作使得list的插入和删除在常数时间内即可完成。
list对于内存空间的使用也是非常节俭，不必像vector那样每次申请内存都需要一个连续的足够大的空间，相反，list的内存可以不连续，它通过指针将离散的内存进行连接，从而达到内存使用的最大化。
1.1 list数据节点
list是通过指针将不同的节点进行串联得到，因此在设计list的时候需要对节点进行单独定义，在新的STL list容器中对节点进行如下定义：
//节点基类
struct _List_node_base
{
_List_node_base* _M_next;
_List_node_base* _M_prev;
}
//节点模板，继承基类
template<typename _Tp>
struct _List_node : public __detail::_List_node_base
{
#if __cplusplus >= 201103L
__gnu_cxx::__aligned_membuf<_Tp> _M_storage;
_Tp* _M_valptr() { return _M_storage._M_ptr(); }
_Tp const* _M_valptr() const { return _M_storage._M_ptr(); }
#else
_Tp _M_data;
_Tp* _M_valptr() { return std::__addressof(_M_data); }
_Tp const* _M_valptr() const { return std::__addressof(_M_data); }
#endif
};
上面定义可以看出，从C++11开始，对list的节点定义进行了优化，对节点内容使用__gnu_cxx::__aligned_membuf<_Tp>对内存进行预留，在插入实际元素后再rebind成list<node>的节点。关于__gnu_cxx::__aligned_membuf后面在专门讨论。
1.2 list的迭代器
list管理的不是连续的内存空间，不能通过下标索引的方式访问，但是通过list提供的迭代器可以对list中的节点进行正确的访问。
STL的迭代器是双向链表，迭代器通过加或者减能够进行正确的访问list中的元素。在对迭代器进行操作时，同样会产生迭代器失效的问题，但是list的迭代器时候只指针对删除操作时指向被删除节点的迭代器失效。在插入新的节点时，list会对迭代器进行重置，因此不会产生迭代器失效的问题。如下图：
迭代器的源码如下：
template<typename _Tp>
struct _List_iterator
{
typedef _List_iterator<_Tp> _Self;
typedef _List_node<_Tp> _Node;
typedef ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Tp* pointer;
typedef _Tp& reference;
}从上面定义的代码可以看出，在list迭代器中提供的是双向绑定的迭代器。在迭代器的定义中同样提供了迭代器常用的运算。
//自增运算
_Self& operator++() _GLIBCXX_NOEXCEPT
{
_M_node = _M_node->_M_next;
return *this;
}
//加运算
_Self operator++(int) _GLIBCXX_NOEXCEPT
{
_Self __tmp = *this;
_M_node = _M_node->_M_next;
return __tmp;
}
//自减运算
_Self& operator--() _GLIBCXX_NOEXCEPT
{
_M_node = _M_node->_M_prev;
return *this;
}
//减运算
_Self operator--(int) _GLIBCXX_NOEXCEPT
{
_Self __tmp = *this;
_M_node = _M_node->_M_prev;
return __tmp;
}1.3 list新增元素操作
C++11后，list新增了emplace,emplace_front,emplace_back操作方法，源码定义如下：
- emplace_front：在开头插入元素，参数为右值引用。
// emplace_front方法
#if __cplusplus > 201402L
reference
#else
void
#endif
emplace_front(_Args&&... __args)
{
this->_M_insert(begin(), std::forward<_Args>(__args)...);
#if __cplusplus > 201402L
return front();
#endif
}
#endif- emplace_back:在結尾插入一元素，类型为右值引用。
//empalce_back
#if __cplusplus > 201402L
reference
#else
void
#endif
emplace_back(_Args&&... __args)
{
this->_M_insert(end(), std::forward<_Args>(__args)...);
#if __cplusplus > 201402L
return back();
#endif
}
#endif- empalce：在指定位置插入一个元素。
//empalce方法
#if __cplusplus >= 201103L
template<typename... _Args>
iterator emplace(const_iterator __position, _Args&&... __args)
{
__glibcxx_check_insert(__position);
return { _Base::emplace(__position.base(),
std::forward<_Args>(__args)...), this };
}
#endif新增的empalce_front和empalce_back方法在C++14之后都已经将返回值由void改成了引用。empalce实现时先使用__glibcxx_check_insert检查位置，然后在进行插入。建议如果开发时使用的C++版本是C++11或者以上的，优先使用上述接口。
代码使用示例如下：
#include <iostream>
#include <list>
int main ()
{
std::list< std::pair<int,char> > mylist;
mylist.emplace_front(10,'a');
mylist.emplace_front(20,'b');
mylist.emplace_front(30,'c');
mylist.emplace_back(40,'z');
mylist.emplace_back(50,'r');
mylist.emplace ( mylist.begin(), 100, 'x' );
mylist.emplace ( mylist.begin(), 200, 'y' );
std::cout << "mylist contains:";
for (auto& x: mylist)
std::cout << " (" << x.first << "," << x.second << ")";
std::cout << std::endl;
return 0;
}代码运行结果如下：
mylist contains: (200,y) (100,x) (30,c) (20,b) (10,a) (40,z) (50,r)- EOF -