<vector>: vector<bool>::iterator fails to meet Cpp17InputIterator requirements

[frederick-vs-ja]

Describe the bug

The following program doesn't compile.

#include <vector>

int main()
{
    std::vector<bool> vb{true};
    vb.begin()->flip();
    (*vb.begin()).flip();
}

It's probably intended that (*vb.begin()).flip() works and is equivalent to vb[0].flip(). As per [tab:inputiterator], it seems that vb.begin()->flip() also needs to be supported.

Command-line test case

Godbolt link

Expected behavior

vb.begin()->flip() works and is equivalent to vb[0].flip().

STL version

Microsoft Visual Studio Community 2022
Version 17.12.0 Preview 2.1

(Probably in all existing versions.)

Additional context

We may need to correspondingly change member type pointer to conform to [iterator.traits]/1.

Also, it's even not very clear to me that vector<bool>::iterator is required to meet the Cpp17InputIterator named requirements. Given vector<bool> is not a real container, it's unclear which requirements on iterators of containers are applied to iterators of vector<bool>. LWG-1422 is related.

[CaseyCarter]

I agree that the input iterator requirements imply that i->flip() must work since (*i).flip() does. (I also agree that the vector<bool> spec is a mess.) It's not clear to me if we want to fix this or submit an LWG issue to punch a hole through the requirements to make the implementations conforming.

[StephanTLavavej]

We talked about this at the weekly maintainer meeting.

"If none of the major implementations have done this in the last 25 years, it honestly couldn't be that big of a deal." - @CaseyCarter

It would probably be possible to make this work, but in any event we want to send this to LWG and have them decide what to do.

[frederick-vs-ja]

Indeed, the semantic equivalence between a->m and (*a).m is unachievable when *a is an rvalue and m denotes some not-fortunate-enough member (still very common, e.g. a public non-static data member of an object type), which is probably the reason why concepts for C++20 iterators don't require this.

IMO a reasonable resolution would be just requiring this when *a is an lvalue. But I wonder why no one did this when designing ranges.

[CaseyCarter]

Indeed, the semantic equivalence between a->m and (*a).m is unachievable when *a is an rvalue and m denotes some not-fortunate-enough member (still very common, e.g. a public non-static data member of an object type), which is probably the reason why concepts for C++20 iterators don't require this.

That's partially the reason, yes. The other part was "generic code doesn't know the names of your type's members, so it's weird for generic code to require operator-> that it's never going to use". I'm still undecided about whether contiguous_iterator should require operator->. Maybe the Standard Library should guarantee that its lvalue iterators (iter_reference_t is an lvalue reference type) all provide operator-> without requiring user iterators to do the same?

This was also the motivation for deprecating move_iterator::operator->.

IMO a reasonable resolution would be just requiring this when *a is an lvalue. But I wonder why no one did this when designing ranges.

Ha! I should have finished reading this before typing my response.

[CaseyCarter]

For reference, making flip callable seems feasible by moving it from _Vb_reference into _Vb_iter_base (which is a base of both _Vb_reference and the iterator types) and having _Vb_iterator::operator-> return a pointer to its _Vb_iter_base subobject:

Click to expand proof-of-nerdsnipe diff

diff --git a/stl/inc/vector b/stl/inc/vector
index ef19788a..15718f01 100644
--- a/stl/inc/vector
+++ b/stl/inc/vector
@@ -2418,6 +2418,10 @@ public:
         this->_Adopt(_Mypvbool);
     }

+    _CONSTEXPR20 void flip() noexcept {
+        *const_cast<_Vbase*>(_Getptr()) ^= _Mask();
+    }
+
     _CONSTEXPR20 void _Advance(_Size_type _Off) noexcept {
         _Myoff += _Off;
         _Myptr += _Myoff / _VBITS;
@@ -2430,6 +2434,24 @@ public:
     }
 #endif // _ITERATOR_DEBUG_LEVEL != 0

+    _CONSTEXPR20 void _Check_dereferenceable() const noexcept {
+#if _ITERATOR_DEBUG_LEVEL != 0
+        const auto _Cont = static_cast<const _Mycont*>(_Getcont());
+        _STL_VERIFY(_Cont, "cannot dereference value-initialized vector<bool> iterator");
+        _STL_VERIFY(_Total_off(_Cont) <= static_cast<_Difference_type>(_Cont->_Mysize),
+            "vector<bool> iterator not dereferenceable");
+#endif // _ITERATOR_DEBUG_LEVEL != 0
+    }
+
+    _CONSTEXPR20 const _Vbase* _Getptr() const noexcept {
+        _Check_dereferenceable();
+        return _Myptr;
+    }
+
+    _CONSTEXPR20 _Vbase _Mask() const noexcept {
+        return static_cast<_Vbase>(1) << _Myoff;
+    }
+
     const _Vbase* _Myptr = nullptr;
     _Size_type _Myoff    = 0;
 };
@@ -2445,6 +2467,9 @@ private:
     // TRANSITION, ABI: non-trivial constructor
     _CONSTEXPR20 _Vb_reference() = default;

+    using _Mybase::_Getptr;
+    using _Mybase::_Mask;
+
 public:
     _CONSTEXPR20 _Vb_reference(const _Vb_reference&) = default;

@@ -2477,39 +2502,19 @@ public:
     }
 #endif // _HAS_CXX23

-    _CONSTEXPR20 void flip() noexcept {
-        *const_cast<_Vbase*>(_Getptr()) ^= _Mask();
-    }
-
     _CONSTEXPR20 operator bool() const noexcept {
         return (*_Getptr() & _Mask()) != 0;
     }

-    _CONSTEXPR20 const _Vbase* _Getptr() const noexcept {
-#if _ITERATOR_DEBUG_LEVEL != 0
-        const auto _Cont = static_cast<const _Mycont*>(this->_Getcont());
-        _STL_VERIFY(_Cont, "cannot dereference value-initialized vector<bool> iterator");
-        _STL_VERIFY(this->_Total_off(_Cont) <= static_cast<_Difference_type>(_Cont->_Mysize),
-            "vector<bool> iterator not dereferenceable");
-#endif // _ITERATOR_DEBUG_LEVEL != 0
-
-        return this->_Myptr;
-    }
-
     friend _CONSTEXPR20 void swap(_Vb_reference _Left, _Vb_reference _Right) noexcept {
         bool _Val = _Left; // NOT _STD swap
         _Left     = _Right;
         _Right    = _Val;
     }
-
-protected:
-    _CONSTEXPR20 _Vbase _Mask() const noexcept {
-        return static_cast<_Vbase>(1) << this->_Myoff;
-    }
 };

 template <class _Alvbase_wrapped>
-class _Vb_const_iterator : public _Vb_iter_base<_Alvbase_wrapped> {
+class _Vb_const_iterator : protected _Vb_iter_base<_Alvbase_wrapped> {
 public:
     using _Mybase         = _Vb_iter_base<_Alvbase_wrapped>;
     using _Mycont         = typename _Mybase::_Mycont;
@@ -2520,7 +2525,7 @@ public:
     using iterator_category = random_access_iterator_tag;
     using value_type        = bool;
     using difference_type   = typename _Mybase::_Difference_type;
-    using pointer           = const_reference*;
+    using pointer           = void;
     using reference         = const_reference;

     _CONSTEXPR20 _Vb_const_iterator() = default;
@@ -2529,13 +2534,7 @@ public:
         : _Mybase(_Ptr, 0, _Mypvbool) {}

     _NODISCARD _CONSTEXPR20 const_reference operator*() const noexcept {
-#if _ITERATOR_DEBUG_LEVEL != 0
-        const auto _Cont = static_cast<const _Mycont*>(this->_Getcont());
-        _STL_VERIFY(_Cont, "cannot dereference value-initialized vector<bool> iterator");
-        _STL_VERIFY(this->_Total_off(_Cont) < static_cast<difference_type>(_Cont->_Mysize),
-            "vector<bool> iterator not dereferenceable");
-#endif // _ITERATOR_DEBUG_LEVEL != 0
-
+        this->_Check_dereferenceable();
         return _Reft(*this);
     }

@@ -2718,22 +2717,21 @@ public:
     using iterator_category = random_access_iterator_tag;
     using value_type        = bool;
     using difference_type   = typename _Mybase::difference_type;
-    using pointer           = _Reft*;
+    using pointer           = _Vb_iter_base<_Alvbase_wrapped>*;
     using reference         = _Reft;

     using _Mybase::_Mybase;

     _NODISCARD _CONSTEXPR20 reference operator*() const noexcept {
-#if _ITERATOR_DEBUG_LEVEL != 0
-        const auto _Cont = static_cast<const _Mycont*>(this->_Getcont());
-        _STL_VERIFY(_Cont, "cannot dereference value-initialized vector<bool> iterator");
-        _STL_VERIFY(this->_Total_off(_Cont) < static_cast<difference_type>(_Cont->_Mysize),
-            "vector<bool> iterator not dereferenceable");
-#endif // _ITERATOR_DEBUG_LEVEL != 0
-
+        this->_Check_dereferenceable();
         return _Reft(*this);
     }

+    _NODISCARD _CONSTEXPR20 pointer operator->() const noexcept {
+        this->_Check_dereferenceable();
+        return const_cast<_Vb_iterator*>(this);
+    }
+
     _CONSTEXPR20 _Vb_iterator& operator++() noexcept {
         _Mybase::operator++();
         return *this;

Caveat emptor, I didn't test anything but the repro.

Another question here - which I think should be part of the LWG issue submission - is how literally the input iterator requirements are meant to be taken for iterators with proxy reference types. Should iter->~reference() work since (*iter).~reference() does? Or iter1->operator=(*iter2)? What does the latter even mean? (EDIT: No, these should not work. See below.)

[frederick-vs-ja]

Another question here - which I think should be part of the LWG issue submission - is how literally the input iterator requirements are meant to be taken for iterators with proxy reference types. Should iter->~reference() work since (*iter).~reference() does? Or iter1->operator=(*iter2)? What does the latter even mean?

[iterator.cpp17.general]/1 only says m denotes an identifier, not an arbitrary name. So given ~reference and operator= are not identifiers, IIUC, they're not counted for the requirements.

But some readers seemingly thought more things are required to be supported, see LWG-659 & LLVM-111032. Perhaps it would be better to add a note?

[CaseyCarter]

[iterator.cpp17.general]/1 only says m denotes an identifier, not an arbitrary name. So given ~reference and operator= are not identifiers, IIUC, they're not counted for the requirements.

Aha! Yes, thanks. I missed that subtlety. And thanks for the reminder about LWG-659, which was reverted by LWG-2790.

Swinging back to the original issue, to me the error here isn't the implementations but the iterator requirements being wrong for proxy reference types. My intuition tells me that (*i).meow should be able to access members of the proxy reference *i, but i->meow should only access members of the range's value type since there's no reference involved. Maybe the LWG issue should be dumped on SG9, and we need someone to bring operator-> into the future. It wasn't a part of the C++20 Ranges design because the algorithms don't care about ->.

Honestly, vector<bool>::reference::flip shouldn't even exist. vec[42].flip() is less clear IMO than vec[42] ^= true. The latter won't even require changing if we can ever actually get rid of the partial specialization for vector<bool>. (Yeah, I know: imagine vector<bool> being wrong.)