Why does end() in stl_tree.h return a reference to the iterator object but begin() returns object?

Question

In GCC stl_tree.h:

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

begin() and end() return iterator objects. However end() returns the address of the object whereas begin() returns the object itself.

1. Why is there this difference?
2. Does begin() returning an object mean another block of memory needs to be accessed, the memory containing the iterator object passed by value?

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

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));
            }

Where:

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

and:

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     };

and:

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

There is no object at .end(); it does not exist. This is a "one-past-the-end" iterator. Consequently, .end() must be implemented using a recognisable "sentinel value", and that's what you're seeing here.

(Also, notice that it's &this->_M_impl._M_header, not &this->_M_impl._M_header._M_left!)

A very loose analogy would be the NULL character found at the end of C-strings, though of course in that case you find the NULL value in place.

Arguably, a tree could be implemented such that it always has at least one node which is hidden from the front interface, and it could use this node as end(); then these functions would look a little more like you expected, but it wouldn't be very efficient and you wouldn't gain anything at all.