list

  • list调试的时候比较奇怪，许多关于链表操作的函数无法跟进到源代码，原因暂时未知。

底层为双向链表，节点的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
namespace __detail
{
    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
{
    _Tp _M_data;
}

list的迭代器不再是普通的指针，其为结构体_List_iterator/_List_const_iterator，其中重载了许多符号，如++不再是写一个地址块而是根据_M_next指针得到下一块内存的地址，其他的同理。

Constructors

指定初值。such as:list l = {2,3,1};

初值先被放入底层的array中，之后再将其置入list

1
2
3
4
5
6
7
8
template<typename _InputIterator>
void
_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
            __false_type)
{
    for (; __first != __last; ++__first)
        emplace_back(*__first);
}

跟进，调用list的_M_insert函数

1
2
3
4
template<typename... _Args>
void
emplace_back(_Args&&... __args)
{ this->_M_insert(end(), std::forward<_Args>(__args)...); }

_M_insert实现，创建节点之后调用_M_hook将其链入链表的__position位置

1
2
3
4
5
6
7
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);
}

_M_create_node，先调用_M_get_node分配一块内存，之后尝试将值写入，成功后返回指针__p

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename... _Args>
_Node*
_M_create_node(_Args&&... __args)
{
_Node* __p = this->_M_get_node();
__try
{
    _M_get_Node_allocator().construct(__p,
                std::forward<_Args>(__args)...);
}
__catch(...)
{
    _M_put_node(__p);
    __throw_exception_again;
}
return __p;
}

_M_hook尝试单步跟进但直接跳过
查看定义

1
2
void
_M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;

push_back && pop_back && push_front && pop_front

push_back 与 push_front 均是调用_M_insert函数将元素插入，区别在于第一个参数分别为end()，begin()

pop_back 与 pop_front 则均调用_M_earse函数将迭代器指向的位置的元素移除

1
2
3
4
5
6
7
8
void
pop_back() _GLIBCXX_NOEXCEPT
{ this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }


void
pop_front() _GLIBCXX_NOEXCEPT
{ this->_M_erase(begin()); }

跟入_M_erase函数

1
2
3
4
5
6
7
8
void
_M_erase(iterator __position) _GLIBCXX_NOEXCEPT
{
    __position._M_node->_M_unhook();
    _Node* __n = static_cast<_Node*>(__position._M_node);
    _M_get_Node_allocator().destroy(__n);
    _M_put_node(__n);
}

基本操作就是将其解链，然后获得其指针，destory实际上就是调用了其析构函数，之后调用_M_put_node将指针delete

这里重点的_M_unhook函数也同_M_hook一样无法找到实现。

sort

没有太懂…

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
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
sort()
{
    // Do nothing if the list has length 0 or 1.
    if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
    && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
    {
    list __carry;
    list __tmp[64];
    list * __fill = &__tmp[0];
    list * __counter;

    do
    {
        //splice中主要调用的是transfer函数
        __carry.splice(__carry.begin(), *this, begin());

        for(__counter = &__tmp[0];
        __counter != __fill && !__counter->empty();
        ++__counter)
            {
        __counter->merge(__carry);
        __carry.swap(*__counter);
            }
        __carry.swap(*__counter);
        if (__counter == __fill)
            ++__fill;
    }
    while ( !empty() );

    for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
        __counter->merge(*(__counter - 1));
    swap( *(__fill - 1) );
    }
}