# 一、知識點 ## 1. std::bidirectional_iterator_tag `std::bidirectional_iterator_tag` 是 C++ 標準庫中定義的一個迭代器類型標簽，用於標識支持雙向遍歷的迭代器類型。在 C++ 中，迭代器是一種泛型指針，用於遍歷容器中的元素 ...

一、知識點

1. std::bidirectional_iterator_tag

std::bidirectional_iterator_tag 是 C++ 標準庫中定義的一個迭代器類型標簽，用於標識支持雙向遍歷的迭代器類型。

在 C++ 中，迭代器是一種泛型指針，用於遍歷容器中的元素。迭代器類型標簽用於標識迭代器的特性，從而在演算法中選擇合適的迭代器類型。

std::bidirectional_iterator_tag 是迭代器類型標簽中的一種，用於標識支持雙向遍歷的迭代器類型。雙向迭代器可以向前和向後遍歷容器中的元素，支持 ++ 和 -- 運算符。

標準庫中的許多演算法都要求迭代器支持特定的操作，例如 std::reverse 要求迭代器支持雙向遍歷，因此可以使用 std::bidirectional_iterator_tag 標簽來限定迭代器的類型，從而保證演算法的正確性。

//迭代器類型標簽，用於標識支持雙向遍歷的迭代器類型，支持++和--運算符
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 類型還可以提高代碼的可移植性，因為不同平臺上指針的大小可能不同。

//帶符號整型，表示指針之間的差值（即兩個指針在記憶體中的地址差距）
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指針，以及一些方法。

struct _List_node_base
{
      _List_node_base* _M_next;
      _List_node_base* _M_prev;
      ...
};

_List_node

繼承自_List_node_base，主要提供了一個存放數據的 _M_data

/// An actual node in the %list.
  template<typename _Tp>
    struct _List_node : public __detail::_List_node_base
    {
      ///< User's data.
      _Tp _M_data;
//檢查編譯器是否支持c++11及以上版本
#if __cplusplus >= 201103L
      template<typename... _Args>
        _List_node(_Args&&... __args)     //萬能引用
	: __detail::_List_node_base(), _M_data(std::forward<_Args>(__args)...) //完美轉發
        { }
#endif
    };

_List_iterator

迭代器

1. 必須定義的五個typedef

      //下麵這五個typedef是每個iterator必須有的
      //帶符號整型，表示指針之間的差值（即兩個指針在記憶體中的地址差距）
      typedef ptrdiff_t                          difference_type;
      //迭代器類型標簽，用於標識支持雙向遍歷的迭代器類型，支持++和--運算符
      typedef std::bidirectional_iterator_tag    iterator_category;
      typedef _Tp                                value_type;
      typedef _Tp*                               pointer;
      typedef _Tp&                               reference;

2. 兩個構造器

      _List_iterator() _GLIBCXX_NOEXCEPT
      : _M_node() { }

      explicit //修飾類的構造函數，表示該構造函數是顯式的，不能進行隱式轉換
      _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT
      : _M_node(__x) { }      //_M_node:_List_node_base

3. 運算符重載

個人理解，此處之所以能夠向下造型，應該是傳入參數的時候已經做過一次向上造型

// Must downcast from _List_node_base to _List_node to get to _M_data.
      reference
      operator*() const _GLIBCXX_NOEXCEPT 
      { return static_cast<_Node*>(_M_node)->_M_data; }     //_M_node:_List_node_base, _Node:_List_node<_Tp>

      pointer
      operator->() const _GLIBCXX_NOEXCEPT      //2.9版本中是return &(operator*())
      { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }      //__addressof用於取地址

前++運算符與後++運算符

此處模仿了整數的++i與i++，所以前++運算符需要返回一個引用。

個人理解：與左值和右值有關，如++i是左值，i++是右值。

	  _Self&
      operator++() _GLIBCXX_NOEXCEPT      //++item
      {
	_M_node = _M_node->_M_next;
	return *this;	//由於只有一個成員變數_M_node，因此能返回*this
      }

      _Self
      operator++(int) _GLIBCXX_NOEXCEPT   //item++ 感覺跟左值右值有關
      {
	_Self __tmp = *this;
	_M_node = _M_node->_M_next;
	return __tmp;
      }

_List_base

1. typedef

	  //rebind是一個模板類，它接受一個模板參數T和一個新的類型U，然後定義一個新的類型
      //這個新的類型是將T中的模板參數全部替換為U後得到的結果
      typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
        _Node_alloc_type;

      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<_List_node<_Tp> >::other 和 _Alloc::template rebind<_Tp>::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 將原始分配器重新綁定到節點和元素類型上。

      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) _GLIBCXX_NOEXCEPT   //底層const
	: _Node_alloc_type(__a), _M_node()
	{ }

#if __cplusplus >= 201103L
	_List_impl(_Node_alloc_type&& __a) _GLIBCXX_NOEXCEPT  //右值引用
	: _Node_alloc_type(std::move(__a)), _M_node()   //轉為右值，移動語義
	{ }
#endif
      };

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 及以上版本中被定義。

      _List_base()
      : _M_impl()
      { _M_init(); }

      _List_base(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
      : _M_impl(__a)
      { _M_init(); }

#if __cplusplus >= 201103L
      _List_base(_List_base&& __x) noexcept     //右值引用
      : _M_impl(std::move(__x._M_get_Node_allocator()))     //移動構造函數
      {
	_M_init();
	__detail::_List_node_base::swap(_M_impl._M_node, __x._M_impl._M_node);
      }
#endif

4. _M_init()

	  void
      _M_init() _GLIBCXX_NOEXCEPT
      {
        //頭節點的prev與next指向自身
        this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
        this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
      }

list

1. typedef

      // concept requirements
      typedef typename _Alloc::value_type                _Alloc_value_type;
      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
      __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)

      typedef _List_base<_Tp, _Alloc>                    _Base;
      typedef typename _Base::_Tp_alloc_type		 _Tp_alloc_type;
      typedef typename _Base::_Node_alloc_type		 _Node_alloc_type;

    public:
      typedef _Tp                                        value_type;
      typedef typename _Tp_alloc_type::pointer           pointer;
      typedef typename _Tp_alloc_type::const_pointer     const_pointer;
      typedef typename _Tp_alloc_type::reference         reference;
      typedef typename _Tp_alloc_type::const_reference   const_reference;
      typedef _List_iterator<_Tp>                        iterator;
      typedef _List_const_iterator<_Tp>                  const_iterator;
      typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
      typedef std::reverse_iterator<iterator>            reverse_iterator;
      typedef size_t                                     size_type;
      typedef ptrdiff_t                                  difference_type;
      typedef _Alloc                                     allocator_type;

    protected:
      // Note that pointers-to-_Node's can be ctor-converted to
      // iterator types.
      typedef _List_node<_Tp>				 _Node;

      using _Base::_M_impl;
      using _Base::_M_put_node;
      using _Base::_M_get_node;
      using _Base::_M_get_Tp_allocator;
      using _Base::_M_get_Node_allocator;

2. 一些函數

_M_create_node

      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;	//返回指針
	}

assign

assign 函數是 list 類的成員函數，用於將新的元素賦值給當前的 list 對象。該函數有多個重載版本，其中一個版本接受一個初始化列表作為參數，用於將初始化列表中的元素賦值給當前的 list 對象。

具體地，該函數接受一個初始化列表 __l，它將 __l 中的元素替換當前 list 對象中的元素。為此，它調用另一個 assign 函數，該函數接受兩個迭代器參數，分別指向初始化列表的第一個元素和最後一個元素。assign 函數用這些元素來替換當前 list 對象中的元素。

需要註意的是，該函數只在 C++11 及以上版本中被定義。

#if __cplusplus >= 201103L
      /**
       *  @brief  Assigns an initializer_list to a %list.
       *  @param  __l  An initializer_list of value_type.
       *
       *  Replace the contents of the %list with copies of the elements
       *  in the initializer_list @a __l.  This is linear in __l.size().
       */
      void
      assign(initializer_list<value_type> __l)
      { this->assign(__l.begin(), __l.end()); }
#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<value_type> __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 及以上版本中被定義。

list()
#if __cplusplus >= 201103L
      noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value) //判斷是否支持預設構造函數
#endif
      : _Base() { }

      /**
       *  @brief  Creates a %list with no elements.
       *  @param  __a  An allocator object.
       */
      explicit
      list(const allocator_type& __a) _GLIBCXX_NOEXCEPT
      : _Base(_Node_alloc_type(__a)) { }

#if __cplusplus >= 201103L
      /**
       *  @brief  Creates a %list with default constructed elements.
       *  @param  __n  The number of elements to initially create.
       *
       *  This constructor fills the %list with @a __n default
       *  constructed elements.
       */
      explicit
      list(size_type __n)
      : _Base()
      { _M_default_initialize(__n); }

      /**
       *  @brief  Creates a %list with copies of an exemplar element.
       *  @param  __n  The number of elements to initially create.
       *  @param  __value  An element to copy.
       *  @param  __a  An allocator object.
       *
       *  This constructor fills the %list with @a __n copies of @a __value.
       */
      list(size_type __n, const value_type& __value,
	   const allocator_type& __a = allocator_type())
      : _Base(_Node_alloc_type(__a))
      { _M_fill_initialize(__n, __value); }
#else
      /**
       *  @brief  Creates a %list with copies of an exemplar element.
       *  @param  __n  The number of elements to initially create.
       *  @param  __value  An element to copy.
       *  @param  __a  An allocator object.
       *
       *  This constructor fills the %list with @a __n copies of @a __value.
       */
      explicit
      list(size_type __n, const value_type& __value = value_type(),
	   const allocator_type& __a = allocator_type())
      : _Base(_Node_alloc_type(__a))
      { _M_fill_initialize(__n, __value); }
#endif

      /**
       *  @brief  %List copy constructor.
       *  @param  __x  A %list of identical element and allocator types.
       *
       *  The newly-created %list uses a copy of the allocation object used
       *  by @a __x.
       */
      list(const list& __x)
      : _Base(__x._M_get_Node_allocator())
      { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }

#if __cplusplus >= 201103L
      /**
       *  @brief  %List move constructor.
       *  @param  __x  A %list of identical element and allocator types.
       *
       *  The newly-created %list contains the exact contents of @a __x.
       *  The contents of @a __x are a valid, but unspecified %list.
       */
      list(list&& __x) noexcept
      : _Base(std::move(__x)) { }

      /**
       *  @brief  Builds a %list from an initializer_list
       *  @param  __l  An initializer_list of value_type.
       *  @param  __a  An allocator object.
       *
       *  Create a %list consisting of copies of the elements in the
       *  initializer_list @a __l.  This is linear in __l.size().
       */
      list(initializer_list<value_type> __l,
           const allocator_type& __a = allocator_type())
      : _Base(_Node_alloc_type(__a))
      { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }
#endif

      /**
       *  @brief  Builds a %list from a range.
       *  @param  __first  An input iterator.
       *  @param  __last  An input iterator.
       *  @param  __a  An allocator object.
       *
       *  Create a %list consisting of copies of the elements from
       *  [@a __first,@a __last).  This is linear in N (where N is
       *  distance(@a __first,@a __last)).
       */
#if __cplusplus >= 201103L
      template<typename _InputIterator,
	       typename = std::_RequireInputIter<_InputIterator>>
        list(_InputIterator __first, _InputIterator __last,
	     const allocator_type& __a = allocator_type())
	: _Base(_Node_alloc_type(__a))
        { _M_initialize_dispatch(__first, __last, __false_type()); }
#else

4. 運算符重載

移動賦值運算符

      list&
      operator=(list&& __x)   //移動賦值運算符
      {
        // NB: DR 1204.
        // NB: DR 675.
        this->clear();
        this->swap(__x);
        return *this;
      }

初始化列表

這是 list 類的賦值運算符重載，它允許使用初始化列表來為 list 對象賦值。

該運算符重載接受一個初始化列表 __l，它將 __l 中的元素賦值給當前的 list 對象。具體地，它調用 assign 函數，該函數接受兩個迭代器參數，分別指向初始化列表的第一個元素和最後一個元素。assign 函數用這些元素來替換當前 list 對象中的元素。

該運算符重載返回一個 list 的引用，以支持鏈式賦值。

	 list&
      operator=(initializer_list<value_type> __l)
      {
	this->assign(__l.begin(), __l.end());
	return *this;
      }

【whale-starry-stl】01天 list學習筆記

一、知識點

1. std::bidirectional_iterator_tag

2. ptrdiff_t

3. #if __cplusplus >= 201103L

4. explicit

5. stl_list.h結構

6. 迭代器相關

7. 迭代器 traits

二、源碼

_List_node_base

_List_node

_List_iterator

1. 必須定義的五個typedef

2. 兩個構造器

3. 運算符重載

_List_base

1. typedef

2. _List_impl

3. 構造函數

4. _M_init()

list

1. typedef

2. 一些函數

_M_create_node

assign

3. 構造函數

4. 運算符重載