c++ - 为什么 STL_tree.h 中的 end() 返回对迭代器对象的引用，而 begin() 返回对象？

Question

在 GCC STL_tree.h 中:

https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/stl__tree_8h-source.html

begin() 和 end() 返回迭代器对象。但是 end() 返回对象的地址，而 begin() 返回对象本身。

1. 为什么会有这种差异？
2. begin() 返回一个对象是否意味着需要访问另一 block 内存，即包含按值传递的迭代器对象的内存？

................................

00589       iterator begin()
00590       { 
00591     return iterator(static_cast<_Link_type>
00592             (this->_M_impl._M_header._M_left));
00593       }
00594 
00595       const_iterator
00596       begin() const
00597       { 
00598     return const_iterator(static_cast<_Const_Link_type>
00599                   (this->_M_impl._M_header._M_left));
00600       }
00601 
00602       iterator
00603       end()
00604       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
00605 
00606       const_iterator
00607       end() const
00608       { 
00609     return const_iterator(static_cast<_Const_Link_type>
00610                   (&this->_M_impl._M_header));
            }

地点:

typedef _Rb_tree_iterator<_Tp> iterator;
typedef _Rb_tree_const_iterator<value_type> const_iterator;

和:

template<typename _Tp>
00221     struct _Rb_tree_const_iterator
00222     {
00223       typedef _Tp        value_type;
00224       typedef const _Tp& reference;
00225       typedef const _Tp* pointer;
00226 
00227       typedef _Rb_tree_iterator<_Tp> iterator;
00228 
00229       typedef bidirectional_iterator_tag iterator_category;
00230       typedef ptrdiff_t                  difference_type;
00231 
00232       typedef _Rb_tree_const_iterator<_Tp>        _Self;
00233       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
00234       typedef const _Rb_tree_node<_Tp>*           _Link_type;
00235 
00236       _Rb_tree_const_iterator()
00237       : _M_node() { }
00238 
00239       explicit
00240       _Rb_tree_const_iterator(_Link_type __x)
00241       : _M_node(__x) { }
00242 
00243       _Rb_tree_const_iterator(const iterator& __it)
00244       : _M_node(__it._M_node) { }
00245 
00246       reference
00247       operator*() const
00248       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00249 
00250       pointer
00251       operator->() const
00252       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00253 
00254       _Self&
00255       operator++()
00256       {
00257     _M_node = _Rb_tree_increment(_M_node);
00258     return *this;
00259       }
00260 
00261       _Self
00262       operator++(int)
00263       {
00264     _Self __tmp = *this;
00265     _M_node = _Rb_tree_increment(_M_node);
00266     return __tmp;
00267       }
00268 
00269       _Self&
00270       operator--()
00271       {
00272     _M_node = _Rb_tree_decrement(_M_node);
00273     return *this;
00274       }
00275 
00276       _Self
00277       operator--(int)
00278       {
00279     _Self __tmp = *this;
00280     _M_node = _Rb_tree_decrement(_M_node);
00281     return __tmp;
00282       }
00283 
00284       bool
00285       operator==(const _Self& __x) const
00286       { return _M_node == __x._M_node; }
00287 
00288       bool
00289       operator!=(const _Self& __x) const
00290       { return _M_node != __x._M_node; }
00291 
00292       _Base_ptr _M_node;
00293     };

和:

template<typename _Tp>
00151     struct _Rb_tree_iterator
00152     {
00153       typedef _Tp  value_type;
00154       typedef _Tp& reference;
00155       typedef _Tp* pointer;
00156 
00157       typedef bidirectional_iterator_tag iterator_category;
00158       typedef ptrdiff_t                  difference_type;
00159 
00160       typedef _Rb_tree_iterator<_Tp>        _Self;
00161       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
00162       typedef _Rb_tree_node<_Tp>*           _Link_type;
00163 
00164       _Rb_tree_iterator()
00165       : _M_node() { }
00166 
00167       explicit
00168       _Rb_tree_iterator(_Link_type __x)
00169       : _M_node(__x) { }
00170 
00171       reference
00172       operator*() const
00173       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00174 
00175       pointer
00176       operator->() const
00177       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00178 
00179       _Self&
00180       operator++()
00181       {
00182     _M_node = _Rb_tree_increment(_M_node);
00183     return *this;
00184       }
00185 
00186       _Self
00187       operator++(int)
00188       {
00189     _Self __tmp = *this;
00190     _M_node = _Rb_tree_increment(_M_node);
00191     return __tmp;
00192       }
00193 
00194       _Self&
00195       operator--()
00196       {
00197     _M_node = _Rb_tree_decrement(_M_node);
00198     return *this;
00199       }
00200 
00201       _Self
00202       operator--(int)
00203       {
00204     _Self __tmp = *this;
00205     _M_node = _Rb_tree_decrement(_M_node);
00206     return __tmp;
00207       }
00208 
00209       bool
00210       operator==(const _Self& __x) const
00211       { return _M_node == __x._M_node; }
00212 
00213       bool
00214       operator!=(const _Self& __x) const
00215       { return _M_node != __x._M_node; }
00216 
00217       _Base_ptr _M_node;
00218   };

Answer 1

.end()处没有对象；它不存在。这是一个“最后一次”迭代器。因此，.end() 必须使用可识别的“哨兵值”来实现，这就是您在这里看到的。

(另外，请注意它是&this->_M_impl._M_header，而不是&this->_M_impl._M_header._M_left!)

一个非常松散的类比是在 C 字符串末尾找到的 NULL 字符，当然在那种情况下你会找到 NULL 值到位。

可以说，一棵树可以这样实现，它总是有至少一个从前端界面隐藏的节点，并且它可以将这个节点用作end()；那么这些函数看起来会更像你预期的那样，但它不会非常有效，你根本不会有任何收获。