花心胡萝卜 花心胡萝卜工作室 stl list forward_list

STL之序列容器

list

• 环形双向链表
• 本质上, 存储的都是 _List_node, 它包括 Prev, Next, Val 三个属性
• 默认构造函数执行完成后, 会有一个节点, Prev, Next 都指向了自身
• 当新push_back的时候, 就会通过 buynode 来进行链表元素的空间分配, 并进行元素值的构造
• 然后分别制定元素的 Prev和Next, 形成环形双向链表结构

forward_list

以下过程基于 VS2013 跟踪

测试代码如下:

#include <iostream>
#include <forward_list>
#include <algorithm>

int main()
{
    std::forward_list<int> fl;
    fl.push_front(2);
    fl.push_front(3);
    fl.push_front(4);
    std::forward_list<int>::iterator it = fl.begin();
    std::cout << *it << std::endl;
    std::for_each(fl.begin(), fl.end(), [](int x)
    {
        std::cout << x << std::endl;
    });

    return 0;
}

首先 forward_list<int> fl 进行构造
去执行_Mybase的构造 _Mybase是_Flist_buy类
|--_Flist_buy调用_Mybase(_Al), 
|--|--_Flist_base_types<_Ty, _Alloc> > _Mybase
|--就是_Flist_alloc的构造
|--|--在_Flist_alloc中, 调用基类_Flist_val的构造
|--|--|--基类_Flist_val中存在_Nodeptr类型的_Myhead, 在构造的时候初始化, 调用_Nodeptr的默认构造
|--|--|--_Nodeptr其实就是_Val_types::_Nodeptr _Nodeptr, 也就是|--_Flist_node类型
|--|--|--|--_Flist_node里有2个成员变量
|--|--|--|--|--_Voidptr _Next; // 下一个NODE
|--|--|--|--|--_Value_type _Myval; // 当前NODE的值
|--|--执行_Alloc_proxy
|--|--|--它就是给_Myproxy分配 1 个空间, _Myproxy存在于_Container_base12中, 是_Container_base12* 类型
|--|--|--使用 _Container_proxy 来进行值的赋值,|--给一下两个成员变量赋值 0, 然后将 _Myproxy->_Mycont 指向自己
|--|--|--|--它里边有:
|--|--|--|--|--const _Container_base12 *_Mycont;
|--|--|--|--|--_Iterator_base12 *_Myfirstiter;
|--|--到这里, _Alloc_proxy执行完毕, 
|--到这里, _Flist_buy的构造完成, 成功分配了一个 _Flist_node 元素出来

接下来进行 fl.push_front(2);
|--调用 _Insert_after(before_begin(), _STD forward<_Ty>(_Val));
|--|--首先, 调用 before_begin()
|--|--|--它返回一个迭代器, iterator((_Nodeptr)&this->_Myhead, this)
|--|--|--将自己基类_Flist_val中的_Myhead返回出去
|--|--|--|--此时, _Myhead 的 next 和 val 都是无效值
|--|--进入 _Insert_after
|--|--|--第一步, 取 迭代器 中的元素指针 _Ptr, 通过 _Nodeptr _Pnode = _Where._Mynode();
|--|--|--|--_Where._Mynode() 就是返回迭代器中的 _Ptr 的
|--|--|--|--而 _Ptr 则是 _Flist_node 类型的指针
|--|--|--|--取出来当前的结点, 在这里因为是空list, 所以取出来的是 head 节点
|--|--|--第二步, 取出来之后, 找 _Pnode 的 Next, 执行_Nextnode方法, 返回 _Nodepref
|--|--|--|--取出来之后, 对它进行空间分配, 执行 _Buynode
|--|--|--|--|--在 _Buynode 方法中, 调用 _Nodeptr _Pnode = this->_Buynode0(_Next);
|--|--|--|--|--这个_Next就是传递进来的 _Nodepref
|--|--|--|--|--|--_Buynode0中, 首先 获得分配器分配一个 _Npdeptr, 也就是分配一个 _Flist_node
|--|--|--|--|--|--|--_Nodeptr _Pnode = this->_Getal().allocate(1);
|--|--|--|--|--|--|--然后对分配出来的这个 _Pnode 的 Next 进行元素值构造, 以传入的 Next 作为蓝本
|--|--|--|--|--|--|--|--但是传入的 Next 现在是 NULL 所以 _Pnode 的 Next 也是 NULL
|--|--|--|--|--|--|--|--返回这个 _Pnode
|--|--|--|--|--|--现在 _Pnode 有了, 在将传入的值 Val 赋值给 _Pnode
|--|--|--|--|--|--返回这个 _Pnode
|--|--|--|--|--现在, 通过 _Buynode 出现了一个 _Pnode, 它的Next是NULL, 值是 2
|--|--|--|--第二步完成, 生成一个新的 _Newnode, 也就是上边的|--_Pnode
|--|--|--第三步, 将第一步的 _Pnode 的 Next 指向这个新的 _Newnode
|--|--这三步完成, _Insert_after 就完成了, 现在头结点的Next是一个完整的 _Flist_node, 值为2, Next 为NULL

接下来进行 fl.push_front(3);
|--调用 _Insert_after(before_begin(), _STD forward<_Ty>(_Val));
|--|--首先, 调用 before_begin()
|--|--|--它返回一个迭代器, iterator((_Nodeptr)&this->_Myhead, this)
|--|--|--将自己基类_Flist_val中的_Myhead返回出去
|--|--|--|--此时, _Myhead 的 next 现在是一个完整的 _Flist_node, 值为2, Next 为NULL
|--|--进入 _Insert_after
|--|--|--第一步, 取 迭代器 中的元素指针 _Ptr, 通过 _Nodeptr _Pnode = _Where._Mynode();
|--|--|--|--_Where._Mynode() 就是返回迭代器中的 _Ptr 的
|--|--|--|--而 _Ptr 则是 _Flist_node 类型的指针
|--|--|--|--取出来当前的结点, 它的NEXT的 "值为2, Next 为 NULL"的完整 _Flist_node
|--|--|--第二步, 取出来之后, 找 _Pnode 的 Next, 执行_Nextnode方法, 返回 _Nodepref
|--|--|--|--取出来之后, 对它进行空间分配, 执行 _Buynode
|--|--|--|--|--在 _Buynode 方法中, 调用 _Nodeptr _Pnode = this->_Buynode0(_Next);
|--|--|--|--|--这个_Next就是传递进来的 _Nodepref
|--|--|--|--|--|--_Buynode0中, 首先 获得分配器分配一个 _Npdeptr, 也就是分配一个 _Flist_node
|--|--|--|--|--|--|--_Nodeptr _Pnode = this->_Getal().allocate(1);
|--|--|--|--|--|--|--然后对分配出来的这个 _Pnode 的 Next 进行元素值构造, 以传入的 Next 作为蓝本
|--|--|--|--|--|--|--|--传入的 Next 现在是 一个完整的_Flist_node, 所以 _Pnode 的 Next 也是 就指向了 "值为2, Next为NULL"的一个节点
|--|--|--|--|--|--|--|--返回这个 _Pnode
|--|--|--|--|--|--现在 _Pnode 有了, 在将传入的值 Val 赋值给 _Pnode
|--|--|--|--|--|--返回这个 _Pnode
|--|--|--|--|--现在, 通过 _Buynode 出现了一个 _Pnode, 它的Next是"值为2, Next为NULL"的 _Flist_hode, 它自己的值是 3
|--|--|--|--第二步完成, 生成一个新的 _Newnode, 也就是上边的 _Pnode
|--|--|--第三步, 将第一步的 _Pnode 的 Next 指向这个新的 _Newnode
|--|--这三步完成, _Insert_after 就完成了, 现在头结点的Next是一个完整的 _Flist_node, 值为3, Next 为 "值为2, Next为NULL"的 _Flist_node
|--这样, 链表变成了如下结构:
|--|--HEAD
|--|--|--VAL: 未知的值
|--|--|--NEXT:
|--|--|--|--VAL: 3
|--|--|--|--NEXT:
|--|--|--|--|--VAL: 2
|--|--|--|--|--NEXT: NULL

forward_list的end()返回一个迭代器: iterator(0, this), 是一个 NULL 
forward_list的begin()返回一个迭代器: iterator(this->_Myhead, this), 是链表的头

如有错误,请提出指正!谢谢.

本文由 花心胡萝卜 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2017-04-20 at 03:09 pm