阅读了很多大厂招聘的面经,发现越是受欢迎的企业,越重视程序员对代码底层实现的考察.所以笔者决定从C++ STL内置容器开始,逐个分析其底层实现逻辑和源码,从而对编程有更为深刻的认识.之前的每次阅读源码的尝试,都因为源码内容多而杂,变量命名怪异而且繁多等等原因而放弃,希望这次我能坚持下来.本次分析的是C++ STL list的源码.

首先要了解list的本质. list是一个双向链表,但也有循环列表的部分性质,这意味着它从任意位置存取元素的速度会比较快,但是随机查询某个位置的元素会比具有一段连续空间的顺序表vector慢.阅读list源码的本质就是弄明白三件事:1.list数据结构 2.迭代器的定义,特别是重载运算符的操作.3.list操作方法的实现.

list数据结构

首先是list节点的定义部分.

1
2
3
4
5
6
7
8
9
10
11
struct _List_node_base            //list节点的基础实现
{
    _List_node_base* _M_next;    //定义前驱节点
    _List_node_base* _M_prev;    //定义后继节点
｝

template<typename _Tp>            //类模板
struct _List_node : public __detail::_List_node_base
{
    _Tp _M_data;                  //节点存储的数据
｝

从这里就可以看出list的双向链表本质了。这一步先是定义了list的基类_List_node_base，实现了前驱和后继指针的定义。然后根据该基类继承实现了_List_node类，在两个指针的基础上，定义了本节点存储的值value。

需要注意其中的一些语法：

1
template<typename _Tp>

这是一个类模板，由于用户定义的list可能存取任何可能性的变量类型，所以使用template定义一个类模板，根据此类模板传入value的值，保证了List定义的一般性.可以看到后面定义了一个_Tp类型的变量_M_data

1
2
3
4
struct _List_node : public __detail::_List_node_base
{
    ...
｝
定义了_List_node类，继承了_List_node_base类并使用了__detail命名空间

然后是list的一些定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
template<typename _Tp, typename _Alloc>
class _List_base
{
    protected:
//使用traits方法，得到_List_node<_Tp>的内存分配器
 typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
        _Node_alloc_type;
      typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
  
struct _List_impl
      : public _Node_alloc_type
      {
      //数据成员只有头节点
        __detail::_List_node_base _M_node;
        _List_impl()
        : _Node_alloc_type(), _M_node()
        { }
        _List_impl(const _Node_alloc_type& __a)
        : _Node_alloc_type(__a), _M_node() { }

      };
      _List_impl _M_impl;
//分配节点的接口
  _List_node<_Tp>* _M_get_node()
      { return _M_impl._Node_alloc_type::allocate(1); }
  _List_base()
      : _M_impl()
      { _M_init(); }
//list初始化,在其为空时,头指针和尾指针都指向自身
 void _M_init()
      {
        this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
        this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
      }
//从第一个节点开始依次删除并释放内存。
  template<typename _Tp, typename _Alloc>
    void  _List_base<_Tp, _Alloc>:: _M_clear()
    {
      typedef _List_node<_Tp>  _Node;
      _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next);
      while (__cur != &_M_impl._M_node)
        {
          _Node* __tmp = __cur;
          __cur = static_cast<_Node*>(__cur->_M_next);
          _M_get_Node_allocator().destroy(__tmp);
          _M_put_node(__tmp);
        }
}

可以看到list除了具有双向链表的性质,也具有循环链表的性质,相当于一个双向循环链表.在其不为空时,头节点不存储数据.

迭代器的定义

由于list是一个链表，并不是一块连续的存储空间顺序存储，所以默认的迭代器是不能实现的，需要重写一个迭代器来满足遍历操作。以下为源码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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_iterator()
      : _M_node() { }

      explicit
      _List_iterator(__detail::_List_node_base* __x)
      : _M_node(__x) { }

      // Must downcast from _List_node_base to _List_node to get to _M_data.
      //重载运算符
      reference
      operator*() const
      { return static_cast<_Node*>(_M_node)->_M_data; }

      pointer
      operator->() const
      { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }

      _Self&
      operator++()
      {
        _M_node = _M_node->_M_next;
        return *this;
      }

      _Self
      operator++(int)
      {
        _Self __tmp = *this;
        _M_node = _M_node->_M_next;
      return __tmp;
      }

      _Self&
      operator--()
      {
        _M_node = _M_node->_M_prev;
        return *this;
      }

      _Self
      operator--(int)
      {
        _Self __tmp = *this;
        _M_node = _M_node->_M_prev;
        return __tmp;
      }
      // 指向list节点指针
      __detail::_List_node_base* _M_node;
};

对*,->,++,–等运算符进行了重载,使其能满足用户的需求.

list操作方法的实现

list的操作方法有很多,这里只摘取部分.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
iterator  begin() _GLIBCXX_NOEXCEPT
{ return iterator(this->_M_impl._M_node._M_next); }
 iterator end() _GLIBCXX_NOEXCEPT
{ return iterator(&this->_M_impl._M_node); }
Bool  empty() const _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
void push_front(const value_type& __x)
{ this->_M_insert(begin(), __x); }
void push_back(const value_type& __x)
{ this->_M_insert(end(), __x); }
template<typename... _Args> void _M_insert(iterator __position, _Args&&... __args)
{
     _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
     __tmp->_M_hook(__position._M_node);
}
template<typename _Tp, typename _Alloc>
 typename list<_Tp, _Alloc>::iterator
 list<_Tp, _Alloc>::
insert(iterator __position, const value_type& __x)
{
    _Node* __tmp = _M_create_node(__x);
    __tmp->_M_hook(__position._M_node);
    return iterator(__tmp);
}

阅读源码可以看到end指向头节点，begin指向第一个数据节点，begin和end组成一个前闭后开区间。所以,如果判断List是否为空,判断end与begin是否指向同一个结点即可.了解这些特性,List的常用方法就可以逐个实现了,这里不再赘述.