【whale-starry-stl】01天 list学习笔记

一、知识点

1. std::bidirectional_iterator_tag

std::bidirectional_iterator_tag 是 C++ 标准库中定义的一个迭代器类型标签，用于标识支持双向遍历的迭代器类型。
在 C++ 中，迭代器是一种泛型指针，用于遍历容器中的元素。迭代器类型标签用于标识迭代器的特性，从而在算法中选择合适的迭代器类型。
std::bidirectional_iterator_tag 是迭代器类型标签中的一种，用于标识支持双向遍历的迭代器类型。双向迭代器可以向前和向后遍历容器中的元素，支持 ++ 和 -- 运算符。
标准库中的许多算法都要求迭代器支持特定的操作，例如 std::reverse 要求迭代器支持双向遍历，因此可以使用 std::bidirectional_iterator_tag 标签来限定迭代器的类型，从而保证算法的正确性。

1. //迭代器类型标签，用于标识支持双向遍历的迭代器类型，支持++和--运算符
2. typedef std::bidirectional_iterator_tag    iterator_category;

复制代码

2. ptrdiff_t

ptrdiff_t 是 C++ 标准库中定义的一个整型类型，用于表示指针之间的差值（即两个指针在内存中的地址差距）。在 C++ 中，指针的加减运算结果是一个 ptrdiff_t 类型的值。
ptrdiff_t 的实现是平台相关的，通常是一个带符号的整数类型。在 32 位平台上，ptrdiff_t 通常是一个 4 字节的整型，而在 64 位平台上，ptrdiff_t 通常是一个 8 字节的整型。
使用 ptrdiff_t 类型可以保证指针操作的安全性，因为指针之间的差值可能超出普通整型的表示范围。此外，使用 ptrdiff_t 类型还可以提高代码的可移植性，因为不同平台上指针的大小可能不同。

1. //带符号整型，表示指针之间的差值（即两个指针在内存中的地址差距）
2. typedef ptrdiff_t                          difference_type;

复制代码

3. #if __cplusplus >= 201103L

#if __cplusplus >= 201103L这行代码是C++中的条件编译指令，意思是如果当前编译器支持C++11标准或更高版本，则编译下面的代码。其中，__cplusplus是一个C++预定义宏，表示当前编译器所支持的C++标准版本，201103L表示C++11标准的版本号。因此，这行代码的作用是在编译时检查当前编译器是否支持C++11标准或更高版本，如果支持，则编译下面的代码，否则忽略。
4. explicit

explicit 是 C++ 中的一个关键字，用于修饰类的构造函数，表示该构造函数是显式的，不能进行隐式转换。
在 C++ 中，如果一个类的构造函数只有一个参数，那么这个构造函数可以被用于隐式转换。例如，如果有一个类 A 和一个构造函数 A(int)，那么可以使用 A a = 1; 的方式创建一个 A 类型的对象，这里的 1 会被自动转换为 A 类型。
使用 explicit 关键字可以禁止这种隐式转换，从而避免一些潜在的问题。例如，如果一个类 B 有一个构造函数 B(int)，但是我们希望这个构造函数只能显式调用，那么可以将其声明为 explicit，这样就不能再使用 B b = 1; 的方式创建一个 B 类型的对象，而必须显式地调用 B b(1);。
另外，explicit 关键字还可以用于修饰转换函数，表示该函数也是显式的，不能进行隐式转换。
5. stl_list.h结构


6. 迭代器相关

• 运算符重载
  重载++（分为++item与item++）
  
  重载*、&
  
  

7. 迭代器 traits

• 模板偏特化（感觉类似java泛型重载）
  
  
• 完整的iterator_traits
  
  

二、源码

_List_node_base

主要提供了prev和next指针，以及一些方法。

1. struct _List_node_base
2. {
3.       _List_node_base* _M_next;
4.       _List_node_base* _M_prev;
5.       ...
6. };

复制代码

_List_node

继承自_List_node_base，主要提供了一个存放数据的 _M_data

1. /// An actual node in the %list.
2.   template<typename _Tp>
3.     struct _List_node : public __detail::_List_node_base
4.     {
5.       ///< User's data.
6.       _Tp _M_data;
7. //检查编译器是否支持c++11及以上版本
8. #if __cplusplus >= 201103L
9.       template<typename... _Args>
10.         _List_node(_Args&&... __args)     //万能引用
11.         : __detail::_List_node_base(), _M_data(std::forward<_Args>(__args)...) //完美转发
12.         { }
13. #endif
14.     };

复制代码

_List_iterator

迭代器
1. 必须定义的五个typedef

1.       //下面这五个typedef是每个iterator必须有的
2.       //带符号整型，表示指针之间的差值（即两个指针在内存中的地址差距）
3.       typedef ptrdiff_t                          difference_type;
4.       //迭代器类型标签，用于标识支持双向遍历的迭代器类型，支持++和--运算符
5.       typedef std::bidirectional_iterator_tag    iterator_category;
6.       typedef _Tp                                value_type;
7.       typedef _Tp*                               pointer;
8.       typedef _Tp&                               reference;

复制代码

2. 两个构造器

1.       _List_iterator() _GLIBCXX_NOEXCEPT
2.       : _M_node() { }
4.       explicit //修饰类的构造函数，表示该构造函数是显式的，不能进行隐式转换
5.       _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT
6.       : _M_node(__x) { }      //_M_node:_List_node_base

复制代码

3.  运算符重载

个人理解，此处之所以能够向下造型，应该是传入参数的时候已经做过一次向上造型

1. // Must downcast from _List_node_base to _List_node to get to _M_data.
2.       reference
3.       operator*() const _GLIBCXX_NOEXCEPT
4.       { return static_cast<_Node*>(_M_node)->_M_data; }     //_M_node:_List_node_base, _Node:_List_node<_Tp>
6.       pointer
7.       operator->() const _GLIBCXX_NOEXCEPT      //2.9版本中是return &(operator*())
8.       { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }      //__addressof用于取地址

复制代码

前++运算符与后++运算符
此处模仿了整数的++i与i++，所以前++运算符需要返回一个引用。
个人理解：与左值和右值有关，如++i是左值，i++是右值。

1.           _Self&
2.       operator++() _GLIBCXX_NOEXCEPT      //++item
3.       {
4.         _M_node = _M_node->_M_next;
5.         return *this;        //由于只有一个成员变量_M_node，因此能返回*this
6.       }
8.       _Self
9.       operator++(int) _GLIBCXX_NOEXCEPT   //item++ 感觉跟左值右值有关
10.       {
11.         _Self __tmp = *this;
12.         _M_node = _M_node->_M_next;
13.         return __tmp;
14.       }

复制代码

_List_base

1. typedef

1.           //rebind是一个模板类，它接受一个模板参数T和一个新的类型U，然后定义一个新的类型
2.       //这个新的类型是将T中的模板参数全部替换为U后得到的结果
3.       typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
4.         _Node_alloc_type;
6.       typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;

复制代码

2. _List_impl

这段代码定义了一个结构体 _List_impl，它是 list 类的一个内部实现，用于存储 list 对象中的元素和节点信息。
该结构体中使用了两个模板别名：_Node_alloc_type 和 _Tp_alloc_type，它们分别表示节点和元素的分配器类型。这里使用了 typename 关键字来指示 _Alloc::template rebind::other 和 _Alloc::template rebind::other 是类型别名，而不是静态成员变量或函数。
接下来，_List_impl 结构体中定义了一个 _M_node 成员变量，它是一个 _List_node_base 类型的对象，用于存储 list 对象中的头节点和尾节点信息。
_List_impl 结构体还有三个构造函数，分别用于构造一个空的 _List_impl 对象、使用指定的节点分配器构造 _List_impl 对象，以及使用右值引用的节点分配器构造 _List_impl 对象。
需要注意的是，_List_impl 结构体中的 _Node_alloc_type 和 _Tp_alloc_type 类型别名都是使用 _Alloc 类型的 template rebind 成员模板生成的，这是因为 list 类需要支持自定义分配器，因此需要使用 rebind 将原始分配器重新绑定到节点和元素类型上。

1.       struct _List_impl
2.       : public _Node_alloc_type
3.       {
4.         __detail::_List_node_base _M_node;
6.         _List_impl()
7.         : _Node_alloc_type(), _M_node()
8.         { }
10.         _List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT   //底层const
11.         : _Node_alloc_type(__a), _M_node()
12.         { }
14. #if __cplusplus >= 201103L
15.         _List_impl(_Node_alloc_type&& __a) _GLIBCXX_NOEXCEPT  //右值引用
16.         : _Node_alloc_type(std::move(__a)), _M_node()   //转为右值，移动语义
17.         { }
18. #endif
19.       };

复制代码

3. 构造函数

这是 list 类的一个基类 _List_base，包含了 list 类的一些基本实现。这里的三个构造函数都是 _List_base 类的构造函数。
第一个构造函数  _List_base() 是默认构造函数，它使用默认的节点分配器构造了一个 _List_impl 对象 _M_impl，并调用了 _M_init() 函数来初始化 _List_base 对象。
第二个构造函数 _List_base(const _Node_alloc_type& __a) 则接受一个节点分配器 __a，用于构造一个 _List_impl 对象 _M_impl，并调用了 _M_init() 函数来初始化 _List_base 对象。
第三个构造函数 _List_base(_List_base&& __x) 是移动构造函数，它接受一个右值引用 __x，用于构造一个 _List_impl 对象 _M_impl。在构造过程中，它使用 __x._M_get_Node_allocator() 获取 __x 对象的节点分配器，并将其作为参数传递给 _M_impl 的构造函数，从而实现了节点分配器的移动。接着，它调用了 _M_init() 函数来初始化 _List_base 对象，并使用 __detail::_List_node_base::swap 函数交换了 _M_impl._M_node 和 __x._M_impl._M_node 两个节点的信息，实现了 _List_base 对象的移动构造。需要注意的是，该构造函数只在 C++11 及以上版本中被定义。

1.       _List_base()
2.       : _M_impl()
3.       { _M_init(); }
5.       _List_base(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
6.       : _M_impl(__a)
7.       { _M_init(); }
9. #if __cplusplus >= 201103L
10.       _List_base(_List_base&& __x) noexcept     //右值引用
11.       : _M_impl(std::move(__x._M_get_Node_allocator()))     //移动构造函数
12.       {
13.         _M_init();
14.         __detail::_List_node_base::swap(_M_impl._M_node, __x._M_impl._M_node);
15.       }
16. #endif

复制代码

4. _M_init()

1.           void
2.       _M_init() _GLIBCXX_NOEXCEPT
3.       {
4.         //头节点的prev与next指向自身
5.         this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
6.         this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
7.       }

复制代码

list

1. typedef

1.       // concept requirements
2.       typedef typename _Alloc::value_type                _Alloc_value_type;
3.       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
4.       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
6.       typedef _List_base<_Tp, _Alloc>                    _Base;
7.       typedef typename _Base::_Tp_alloc_type                 _Tp_alloc_type;
8.       typedef typename _Base::_Node_alloc_type                 _Node_alloc_type;
10.     public:
11.       typedef _Tp                                        value_type;
12.       typedef typename _Tp_alloc_type::pointer           pointer;
13.       typedef typename _Tp_alloc_type::const_pointer     const_pointer;
14.       typedef typename _Tp_alloc_type::reference         reference;
15.       typedef typename _Tp_alloc_type::const_reference   const_reference;
16.       typedef _List_iterator<_Tp>                        iterator;
17.       typedef _List_const_iterator<_Tp>                  const_iterator;
18.       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
19.       typedef std::reverse_iterator<iterator>            reverse_iterator;
20.       typedef size_t                                     size_type;
21.       typedef ptrdiff_t                                  difference_type;
22.       typedef _Alloc                                     allocator_type;
24.     protected:
25.       // Note that pointers-to-_Node's can be ctor-converted to
26.       // iterator types.
27.       typedef _List_node<_Tp>                                 _Node;
29.       using _Base::_M_impl;
30.       using _Base::_M_put_node;
31.       using _Base::_M_get_node;
32.       using _Base::_M_get_Tp_allocator;
33.       using _Base::_M_get_Node_allocator;

复制代码

2. 一些函数

_M_create_node

1.       template<typename... _Args>
2.         _Node*
3.         _M_create_node(_Args&&... __args)        //万能引用
4.         {
5.           _Node* __p = this->_M_get_node();       //获取新的节点指针
6.           __try
7.             {
8.               _M_get_Node_allocator().construct(__p,
9.                                                 std::forward<_Args>(__args)...); //使用完美转发构造节点中的数据
10.             }
11.           __catch(...)
12.             {
13.               _M_put_node(__p);
14.               __throw_exception_again;
15.             }
16.           return __p;        //返回指针
17.         }

复制代码

assign

assign 函数是 list 类的成员函数，用于将新的元素赋值给当前的 list 对象。该函数有多个重载版本，其中一个版本接受一个初始化列表作为参数，用于将初始化列表中的元素赋值给当前的 list 对象。
具体地，该函数接受一个初始化列表 __l，它将 __l 中的元素替换当前 list 对象中的元素。为此，它调用另一个 assign 函数，该函数接受两个迭代器参数，分别指向初始化列表的第一个元素和最后一个元素。assign 函数用这些元素来替换当前 list 对象中的元素。
需要注意的是，该函数只在 C++11 及以上版本中被定义。

1. #if __cplusplus >= 201103L
2.       /**
3.        *  @brief  Assigns an initializer_list to a %list.
4.        *  @param  __l  An initializer_list of value_type.
5.        *
6.        *  Replace the contents of the %list with copies of the elements
7.        *  in the initializer_list @a __l.  This is linear in __l.size().
8.        */
9.       void
10.       assign(initializer_list<value_type> __l)
11.       { this->assign(__l.begin(), __l.end()); }
12. #endif

复制代码

3. 构造函数

第一个构造函数 list() 是默认构造函数，它创建一个空的 list 对象，使用默认的节点分配器。
第二个构造函数 list(const allocator_type& __a) 接受一个节点分配器 __a，用于创建一个空的 list 对象。
第三个构造函数 list(size_type __n) 接受一个整数参数 __n，用于创建一个包含 __n 个默认构造的元素的 list 对象。
第四个构造函数 list(size_type __n, const value_type& __value, const allocator_type& __a = allocator_type()) 接受一个整数参数 __n 和一个元素值 __value，用于创建一个包含 __n 个值为 __value 的元素的 list 对象。
第五个构造函数 list(const list& __x) 是拷贝构造函数，用于创建一个与 __x 相同的 list 对象。
第六个构造函数 list(list&& __x) noexcept 是移动构造函数，用于创建一个与 __x 相同的 list 对象，并将 __x 中的元素移动到新的 list 对象中。
第七个构造函数 list(initializer_list __l, const allocator_type& __a = allocator_type()) 接受一个初始化列表 __l，用于创建一个包含 __l 中元素的 list 对象。
第八个构造函数 list(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) 接受两个迭代器参数 __first 和 __last，用于创建一个包含从 __first 到 __last 的所有元素的 list 对象。需要注意的是，该构造函数只在 C++11 及以上版本中被定义。

1. list()
2. #if __cplusplus >= 201103L
3.       noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value) //判断是否支持默认构造函数
4. #endif
5.       : _Base() { }
7.       /**
8.        *  @brief  Creates a %list with no elements.
9.        *  @param  __a  An allocator object.
10.        */
11.       explicit
12.       list(const allocator_type& __a) _GLIBCXX_NOEXCEPT
13.       : _Base(_Node_alloc_type(__a)) { }
15. #if __cplusplus >= 201103L
16.       /**
17.        *  @brief  Creates a %list with default constructed elements.
18.        *  @param  __n  The number of elements to initially create.
19.        *
20.        *  This constructor fills the %list with @a __n default
21.        *  constructed elements.
22.        */
23.       explicit
24.       list(size_type __n)
25.       : _Base()
26.       { _M_default_initialize(__n); }
28.       /**
29.        *  @brief  Creates a %list with copies of an exemplar element.
30.        *  @param  __n  The number of elements to initially create.
31.        *  @param  __value  An element to copy.
32.        *  @param  __a  An allocator object.
33.        *
34.        *  This constructor fills the %list with @a __n copies of @a __value.
35.        */
36.       list(size_type __n, const value_type& __value,
37.            const allocator_type& __a = allocator_type())
38.       : _Base(_Node_alloc_type(__a))
39.       { _M_fill_initialize(__n, __value); }
40. #else
41.       /**
42.        *  @brief  Creates a %list with copies of an exemplar element.
43.        *  @param  __n  The number of elements to initially create.
44.        *  @param  __value  An element to copy.
45.        *  @param  __a  An allocator object.
46.        *
47.        *  This constructor fills the %list with @a __n copies of @a __value.
48.        */
49.       explicit
50.       list(size_type __n, const value_type& __value = value_type(),
51.            const allocator_type& __a = allocator_type())
52.       : _Base(_Node_alloc_type(__a))
53.       { _M_fill_initialize(__n, __value); }
54. #endif
56.       /**
57.        *  @brief  %List copy constructor.
58.        *  @param  __x  A %list of identical element and allocator types.
59.        *
60.        *  The newly-created %list uses a copy of the allocation object used
61.        *  by @a __x.
62.        */
63.       list(const list& __x)
64.       : _Base(__x._M_get_Node_allocator())
65.       { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
67. #if __cplusplus >= 201103L
68.       /**
69.        *  @brief  %List move constructor.
70.        *  @param  __x  A %list of identical element and allocator types.
71.        *
72.        *  The newly-created %list contains the exact contents of @a __x.
73.        *  The contents of @a __x are a valid, but unspecified %list.
74.        */
75.       list(list&& __x) noexcept
76.       : _Base(std::move(__x)) { }
78.       /**
79.        *  @brief  Builds a %list from an initializer_list
80.        *  @param  __l  An initializer_list of value_type.
81.        *  @param  __a  An allocator object.
82.        *
83.        *  Create a %list consisting of copies of the elements in the
84.        *  initializer_list @a __l.  This is linear in __l.size().
85.        */
86.       list(initializer_list<value_type> __l,
87.            const allocator_type& __a = allocator_type())
88.       : _Base(_Node_alloc_type(__a))
89.       { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }
90. #endif
92.       /**
93.        *  @brief  Builds a %list from a range.
94.        *  @param  __first  An input iterator.
95.        *  @param  __last  An input iterator.
96.        *  @param  __a  An allocator object.
97.        *
98.        *  Create a %list consisting of copies of the elements from
99.        *  [@a __first,@a __last).  This is linear in N (where N is
100.        *  distance(@a __first,@a __last)).
101.        */
102. #if __cplusplus >= 201103L
103.       template<typename _InputIterator,
104.                typename = std::_RequireInputIter<_InputIterator>>
105.         list(_InputIterator __first, _InputIterator __last,
106.              const allocator_type& __a = allocator_type())
107.         : _Base(_Node_alloc_type(__a))
108.         { _M_initialize_dispatch(__first, __last, __false_type()); }
109. #else

复制代码

4. 运算符重载

移动赋值运算符

1.       list&
2.       operator=(list&& __x)   //移动赋值运算符
3.       {
4.         // NB: DR 1204.
5.         // NB: DR 675.
6.         this->clear();
7.         this->swap(__x);
8.         return *this;
9.       }

复制代码

初始化列表

这是 list 类的赋值运算符重载，它允许使用初始化列表来为 list 对象赋值。
该运算符重载接受一个初始化列表 __l，它将 __l 中的元素赋值给当前的 list 对象。具体地，它调用 assign 函数，该函数接受两个迭代器参数，分别指向初始化列表的第一个元素和最后一个元素。assign 函数用这些元素来替换当前 list 对象中的元素。
该运算符重载返回一个 list 的引用，以支持链式赋值。

1.          list&
2.       operator=(initializer_list<value_type> __l)
3.       {
4.         this->assign(__l.begin(), __l.end());
5.         return *this;
6.       }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！