Use the allocator's pointers for deallocation in `std::list`

[• Quuxplusone]

Summary

pointer_traits<P>::to_pointer(r) is not required to return a deallocatable pointer; indeed generally it *cannot* determine a deallocatable representation without help from the allocator. Therefore, we must not rely on representations derived from to_pointer when deallocating; we must pass to deallocate the exact same pointer (or at least a pointer linearly derived from the pointer) that we originally received from allocate.

I have an example fancy-pointer allocator here which might be convertible into a test case:
https://github.com/Quuxplusone/from-scratch/blob/master/include/scratch/bits/containers/segmented-allocator.h

[EricWF]

First, this patch would need tests before continuing, Could you please them? The list tests live under test/std/containers/sequences/list. Let me know if you have any questions or need any help writing tests.

That being said. I'm not sure this patch is viable (or currently correct). First, LWG 2260 was resolved at the Toronto meeting by requiring ::pointer_to(r) to be valid on allocator pointers, so I'm not sure your point about "not returning a deallocatable pointer" is valid anymore. In fact this seems to suggest that implementations should store raw pointers (since fancy-pointers don't require base <--> derived conversions), and then use pointer_to to generate the fancy-pointer for deallocation.

I understand the above behavior is quite limiting for fancy-pointers, since as you say, fancy-pointers often depend on information stored in the allocator in order to be constructed. However this point would have to be addressed to the committee in order for anything to be done about it.

Even if your point were valid, I'm not sure it's possible to correctly remove our dependency on pointer_to (though you're free to try). Leaving even one call to pointer_to within list seems like the manifestation of a bug.

Another problem to addressing this issue is that the pointer types used in list, map, unordered_map, ect are different in ABI v1 and ABI v2, and correctly converting between them is overly complicated and easy to get wrong.

[• Quuxplusone]

I've updated D35863 to be actually correct AFAICT from my local testing; but I'm not sure what's the most appropriate way to get "fancy allocator" tests into libcxx's test suite. The way I did it locally is here:
https://github.com/Quuxplusone/libcxx/pull/1/files
Basically, I conditionally replace "test_allocator.h" with "test_fancy_allocator.h", and then re-run all the existing tests. "test_fancy_allocator" uses fancy pointers that carry with them a "payload" of the allocated size n, and then in a.deallocate(p,n) we assert that p.payload()==n. A bunch of list tests fail this assertion before this patch, and none fail after this patch.

@EricWF re our Slack conversation yesterday afternoon: Am I correct that changing the fancy pointer to a raw pointer in iterator::operator->() like this would be an ABI-breaking change and therefore a non-starter? https://github.com/Quuxplusone/libcxx/commit/c80f4ffad2ad04e8749b162629255b191c896b4f

Even if *that* change were friendly, would I be correct that changing the fancy pointer to a raw pointer in the data member iterator::__ptr_ would be an ABI-breaking change and therefore a non-starter? (That would also require more drastic surgery in list::erase(p), because we could no longer trust p.__ptr_ to be deallocatable; we'd have to compute q = p.__ptr_->__prev_->__next_ and deallocate *that*. I have not attempted to write that patch, because I assume it'd be ABI-breaking anyway.)

include/list

 template <class _Tp, class _VoidPtr>
 struct __list_node
     : public __list_node_base<_Tp, _VoidPtr>
 {
     _Tp __value_;
 
     typedef __list_node_base<_Tp, _VoidPtr> __base;
     typedef typename __base::__link_pointer __link_pointer;
-
-    _LIBCPP_INLINE_VISIBILITY
-    __link_pointer __as_link() {
-        return static_cast<__link_pointer>(__base::__self());
-    }
 };
 
 template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS list;
 template <class _Tp, class _Alloc> class __list_imp;
 template <class _Tp, class _VoidPtr> class _LIBCPP_TEMPLATE_VIS __list_const_iterator;
 
 template <class _Tp, class _VoidPtr>
 class _LIBCPP_TEMPLATE_VIS __list_iterator
__list_imp<_Tp, _Alloc>::clear() _NOEXCEPT
     {
         __node_allocator& __na = __node_alloc();
         __link_pointer __f = __end_.__next_;
         __link_pointer __l = __end_as_link();
         __unlink_nodes(__f, __l->__prev_);
         __sz() = 0;
         while (__f != __l)
         {
-            __node_pointer __np = __f->__as_node();
+            __node_pointer __np = static_cast<__node_pointer>(__f);
             __f = __f->__next_;
             __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
             __node_alloc_traits::deallocate(__na, __np, 1);
         }
         __invalidate_all_iterators();
     }
 }
 
_LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
         "list::insert(iterator, x) called with an iterator not"
         " referring to this list");
 #endif
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __hold->__prev_ = 0;
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-    __link_nodes(__p.__ptr_, __hold->__as_link(), __hold->__as_link());
+    __link_nodes(__p.__ptr_, static_cast<__link_pointer>(__hold.get()), static_cast<__link_pointer>(__hold.get()));
     ++base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-    return iterator(__hold.release()->__as_link(), this);
+    return iterator(static_cast<__link_pointer>(__hold.release()), this);
 #else
-    return iterator(__hold.release()->__as_link());
+    return iterator(static_cast<__link_pointer>(__hold.release()));
 #endif
 }
 
 template <class _Tp, class _Alloc>
 typename list<_Tp, _Alloc>::iterator
 list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
if (__n > 0)
         size_type __ds = 0;
         __node_allocator& __na = base::__node_alloc();
         typedef __allocator_destructor<__node_allocator> _Dp;
         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
         __hold->__prev_ = 0;
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
         ++__ds;
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        __r = iterator(__hold->__as_link(), this);
+        __r = iterator(static_cast<__link_pointer>(__hold.get()), this);
 #else
-        __r = iterator(__hold->__as_link());
+        __r = iterator(static_cast<__link_pointer>(__hold.get()));
 #endif
         __hold.release();
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif  // _LIBCPP_NO_EXCEPTIONS
             for (--__n; __n != 0; --__n, ++__e, ++__ds)
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-                __e.__ptr_->__next_ = __hold->__as_link();
+                __e.__ptr_->__next_ = static_cast<__link_pointer>(__hold.get());
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
                 __link_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
+                __node_alloc_traits::deallocate(__na, static_cast<__node_pointer>(__e.__ptr_), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
                 __e = iterator(__prev, this);
 #else
                 __e = iterator(__prev);
 #endif
             }
if (__f != __l)
         size_type __ds = 0;
         __node_allocator& __na = base::__node_alloc();
         typedef __allocator_destructor<__node_allocator> _Dp;
         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
         __hold->__prev_ = 0;
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
         ++__ds;
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        __r = iterator(__hold.get()->__as_link(), this);
+        __r = iterator(static_cast<__link_pointer>(__hold.get()), this);
 #else
-        __r = iterator(__hold.get()->__as_link());
+        __r = iterator(static_cast<__link_pointer>(__hold.get()));
 #endif
         __hold.release();
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif  // _LIBCPP_NO_EXCEPTIONS
             for (++__f; __f != __l; ++__f, (void) ++__e, (void) ++__ds)
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
-                __e.__ptr_->__next_ = __hold.get()->__as_link();
+                __e.__ptr_->__next_ = static_cast<__link_pointer>(__hold.get());
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
                 __link_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
+                __node_alloc_traits::deallocate(__na, static_cast<__node_pointer>(__e.__ptr_), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
                 __e = iterator(__prev, this);
 #else
                 __e = iterator(__prev);
 #endif
             }

 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::push_front(const value_type& __x)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-    __link_pointer __nl = __hold->__as_link();
+    __link_pointer __nl = static_cast<__link_pointer>(__hold.get());
     __link_nodes_at_front(__nl, __nl);
     ++base::__sz();
     __hold.release();
 }
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::push_back(const value_type& __x)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-    __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
+    __link_nodes_at_back(static_cast<__link_pointer>(__hold.get()), static_cast<__link_pointer>(__hold.get()));
     ++base::__sz();
     __hold.release();
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::push_front(value_type&& __x)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
-    __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
+    __link_nodes_at_front(static_cast<__link_pointer>(__hold.get()), static_cast<__link_pointer>(__hold.get()));
     ++base::__sz();
     __hold.release();
 }
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::push_back(value_type&& __x)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
-    __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
+    __link_nodes_at_back(static_cast<__link_pointer>(__hold.get()), static_cast<__link_pointer>(__hold.get()));
     ++base::__sz();
     __hold.release();
 }
 
 template <class _Tp, class _Alloc>
 template <class... _Args>
 #if _LIBCPP_STD_VER > 14
 typename list<_Tp, _Alloc>::reference
 #else
 void
 #endif
 list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
-    __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
+    __link_nodes_at_front(static_cast<__link_pointer>(__hold.get()), static_cast<__link_pointer>(__hold.get()));
     ++base::__sz();
 #if _LIBCPP_STD_VER > 14
     return __hold.release()->__value_;
 #else
     __hold.release();
 #endif
 }
 
 template <class _Tp, class _Alloc>
 template <class... _Args>
 #if _LIBCPP_STD_VER > 14
 typename list<_Tp, _Alloc>::reference
 #else
 void
 #endif
 list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
-    __link_pointer __nl = __hold->__as_link();
+    __link_pointer __nl = static_cast<__link_pointer>(__hold.get());
     __link_nodes_at_back(__nl, __nl);
     ++base::__sz();
 #if _LIBCPP_STD_VER > 14
     return __hold.release()->__value_;
 #else
     __hold.release();
 #endif
 }
 
 template <class _Tp, class _Alloc>
 template <class... _Args>
 typename list<_Tp, _Alloc>::iterator
 list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
         "list::emplace(iterator, args...) called with an iterator not"
         " referring to this list");
 #endif
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __hold->__prev_ = 0;
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
-    __link_pointer __nl = __hold.get()->__as_link();
+    __link_pointer __nl = static_cast<__link_pointer>(__hold.get());
     __link_nodes(__p.__ptr_, __nl, __nl);
     ++base::__sz();
     __hold.release();
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return iterator(__nl, this);
 #else
     return iterator(__nl);
 #endif
 }
 
 template <class _Tp, class _Alloc>
 typename list<_Tp, _Alloc>::iterator
 list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
         "list::insert(iterator, x) called with an iterator not"
         " referring to this list");
 #endif
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __hold->__prev_ = 0;
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
-    __link_pointer __nl = __hold->__as_link();
+    __link_pointer __nl = static_cast<__link_pointer>(__hold.get());
     __link_nodes(__p.__ptr_, __nl, __nl);
     ++base::__sz();
     __hold.release();
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return iterator(__nl, this);
 #else
     return iterator(__nl);
 #endif
for (__i_node** __p = __c->end_; __p != __c->beg_; )
         {
             (*__p)->__c_ = nullptr;
             if (--__c->end_ != __p)
                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
         }
     }
     __get_db()->unlock();
 #endif
-    __node_pointer __np = __n->__as_node();
+    __node_pointer __np = static_cast<__node_pointer>(__n);
     __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
     __node_alloc_traits::deallocate(__na, __np, 1);
 }
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::pop_back()
 {
for (__i_node** __p = __c->end_; __p != __c->beg_; )
         {
             (*__p)->__c_ = nullptr;
             if (--__c->end_ != __p)
                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
         }
     }
     __get_db()->unlock();
 #endif
-    __node_pointer __np = __n->__as_node();
+    __node_pointer __np = static_cast<__node_pointer>(__n);
     __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
     __node_alloc_traits::deallocate(__na, __np, 1);
 }
 
 template <class _Tp, class _Alloc>
 typename list<_Tp, _Alloc>::iterator
 list<_Tp, _Alloc>::erase(const_iterator __p)
 {
for (__i_node** __ip = __c->end_; __ip != __c->beg_; )
         {
             (*__ip)->__c_ = nullptr;
             if (--__c->end_ != __ip)
                 memmove(__ip, __ip+1, (__c->end_ - __ip)*sizeof(__i_node*));
         }
     }
     __get_db()->unlock();
 #endif
-    __node_pointer __np = __n->__as_node();
+    __node_pointer __np = static_cast<__node_pointer>(__n);
     __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
     __node_alloc_traits::deallocate(__na, __np, 1);
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return iterator(__r, this);
 #else
     return iterator(__r);
 #endif
 }
#if _LIBCPP_DEBUG_LEVEL >= 2
                 {
                     (*__p)->__c_ = nullptr;
                     if (--__c->end_ != __p)
                         memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
                 }
             }
             __get_db()->unlock();
 #endif
-            __node_pointer __np = __n->__as_node();
+            __node_pointer __np = static_cast<__node_pointer>(__n);
             __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
             __node_alloc_traits::deallocate(__na, __np, 1);
         }
     }
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return iterator(__l.__ptr_, this);
 #else
     return iterator(__l.__ptr_);
else if (__n > base::__sz())
         size_type __ds = 0;
         __node_allocator& __na = base::__node_alloc();
         typedef __allocator_destructor<__node_allocator> _Dp;
         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
         __hold->__prev_ = 0;
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
         ++__ds;
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        iterator __r = iterator(__hold.release()->__as_link(), this);
+        iterator __r = iterator(static_cast<__link_pointer>(__hold.release()), this);
 #else
-        iterator __r = iterator(__hold.release()->__as_link());
+        iterator __r = iterator(static_cast<__link_pointer>(__hold.release()));
 #endif
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif  // _LIBCPP_NO_EXCEPTIONS
             for (--__n; __n != 0; --__n, ++__e, ++__ds)
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
-                __e.__ptr_->__next_ = __hold.get()->__as_link();
+                __e.__ptr_->__next_ = static_cast<__link_pointer>(__hold.get());
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
                 __link_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
+                __node_alloc_traits::deallocate(__na, static_cast<__node_pointer>(__e.__ptr_), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
                 __e = iterator(__prev, this);
 #else
                 __e = iterator(__prev);
 #endif
             }
else if (__n > base::__sz())
         __n -= base::__sz();
         size_type __ds = 0;
         __node_allocator& __na = base::__node_alloc();
         typedef __allocator_destructor<__node_allocator> _Dp;
         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
         __hold->__prev_ = 0;
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
         ++__ds;
-        __link_pointer __nl = __hold.release()->__as_link();
+        __link_pointer __nl = static_cast<__link_pointer>(__hold.release());
 #if _LIBCPP_DEBUG_LEVEL >= 2
         iterator __r = iterator(__nl, this);
 #else
         iterator __r = iterator(__nl);
 #endif
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif  // _LIBCPP_NO_EXCEPTIONS
             for (--__n; __n != 0; --__n, ++__e, ++__ds)
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-                __e.__ptr_->__next_ = __hold.get()->__as_link();
+                __e.__ptr_->__next_ = static_cast<__link_pointer>(__hold.get());
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
                 __link_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
+                __node_alloc_traits::deallocate(__na, static_cast<__node_pointer>(__e.__ptr_), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
                 __e = iterator(__prev, this);
 #else
                 __e = iterator(__prev);
 #endif
             }