[libc++] Fix common_iterator for output_iterators

[ldionne]

Summary

We were missing a constraint in common_iterator's iterator_traits and
we were eagerly instantiating iter_value_t even when invalid.

Thanks to Casey Carter for finding this bug.

[• Quuxplusone]

Nice catch! That test is a mess, though. I don't object to landing this as-is, just to fix the bug; I would also be happy to merge it into D117400. Your call.

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

67

Well this is weird. non_const_deref_iterator<int*>::iterator_category appears to be input_iterator_tag, but std::common_iterator<Iter, sentinel_type<int*>> is an output iterator instead?

Also, I'm seeing now that non_const_deref_iterator is a template, but it's used in only one place (with int*), so it can be massively simplified. Would you like me to just take this over and merge it into my existing D117400?

[ldionne]

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

67

Yeah, I'd like to understand this part as well.

[CaseyCarter]

I don't object to landing this as-is, just to fix the bug; I would also be happy to merge it into D117400. Your call.

I have a mild preference to merge this small fix as-is.

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

67

input_iterator requires that const iterators are dereferenceable. Hopefully it's obvious that is not the case for non_const_deref_iterator, so it does not trigger the iterator_traits<common_iterator<I, S>> partial specialization once that partial specialization is properly constrained to require input_iterator.

[• Quuxplusone]

@ldionne rubberstamp here as-is, and revisit in D117400? :)

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

67

I get everything you said, but I still don't get why "Iter doesn't satisfy input_iterator" should lead us to "iterator_traits<CommonIter>::iterator_category is defined and is equal to output_iterator_tag." Like, Iter isn't an output iterator either... is it? So the most logical outcomes (in increasing order of wild-west-ness) would have been for CommonIter to be ill-formed, or for CommonIter to be well-formed but not an iterator, or for iterator_traits<CommonIter>::iterator_category to be defined as equal to iterator_traits<Iter>::iterator_category. Having it just randomly equal to output_iterator_tag seems bizarre!

(I'm not disputing that it's probably correct according to C++20; I'm just confused about both the mental model and, literally, I don't see by what codepath we end up with output_iterator_tag. Not that I've looked hard at all.)

[ldionne]

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

67

Thanks for explaining @CaseyCarter , but in that case I fail to see the point of this test at all. Instead, why don't we use common_iterator with an output_iterator, and then simply check that IterTraits::iterator_concept isn't defined (which would effectively be a regression test for your change). In other words:

using Iter = output_iterator<int*>;
using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
using IterTraits = std::iterator_traits<CommonIter>;

static_assert(!HasIteratorConcept<IterTraits>);
static_assert(std::same_as<IterTraits::iterator_category, std::output_iterator_tag>);
// etc...

Do you agree that is what we want? Note that this won't work today because it appears that common_iterator<output_iterator<int*>> doesn't work at all today, but we can and should fix that separately (I have a WIP patch locally).

[ldionne]

Commandeering to fix common_iterator with output_iterator. I would have done it as part of a separate patch, but both are interdependent (I can't write tests for my part of the change without your changes).

[ldionne]

Fix common_iterator for output_iterator. Do you folks agree this is the right direction?

[• Quuxplusone]

I continue to think all of these directions are better than the status quo. Consider me still "accept"ing.

libcxx/include/__iterator/common_iterator.h

34–36

Nit: Did you add line 34 to avoid prematurely instantiating iter_reference_t? Is it possible to regression-test for that? Should we? If removing line 34 would be conforming, I'd just do that.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

86–87

153–154

IIUC this comment is misleading. iter_value_t for an ordinary C++11 output iterator is just ThatType::value_type. It's only if the iterator doesn't define a value_type, or defines it as a non-object type, that iter_value_t might be ill-formed.
https://godbolt.org/z/1Ybjv7o9G
Our test iterator's output_iterator<int*>::value_type is void, so its iter_value_t is indeed ill-formed, but that's a special property of our output_iterator, not all output iterators in general.

I'd like to see test coverage for "output iterator with valid value_type" added to iterator_traits.compile.pass.cpp above, even if this means defining a little helper type a la the OutIt in my godbolt.

173

Consider checking iter != sent on at least one of the previous lines.

[CaseyCarter]

LGTM, with Arthur's comments. (Although I'm fine with the extra typename requirement in __can_use_postfix_proxy.)

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

67

common_iterator assumes that non-input_iterators must be output_iterators. Testing with non_const_deref_iterator is equivalent to testing with output_iterator if we never dereference an iterator. common_iterator doesn't intend to be as general as possible: it exists only to adapt "new" iterator+sentinels into "old" iterator pairs. Consequently it has little patience with types that don't satisfy the concepts.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

153–154

"need not be valid for output iterators" would be fine here.

[ldionne]

Apply review comments.

libcxx/include/__iterator/common_iterator.h

34–36

No, the constraint was redundant with simply using iter_value_t in the expressions themselves. Removed.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

153–154

Agreed, the comment was wrong, I'll fix it. However:

I'd like to see test coverage for "output iterator with valid value_type" added to iterator_traits.compile.pass.cpp above, even if this means defining a little helper type a la the OutIt in my godbolt.

The problem is that even though iter_value_t<OutputIter> *can* be non-void, iter_value_t<common_iterator<OutputIter>> will never be, because we are now properly constraining the iterator_traits<common_iterator<...>> specialization to only work on input_iterators. So I can't add a test that checks that iter_value_t<common_iterator<OutputIter>> is going to be non-void.

Please LMK if you think I'm mistaken here.

[• Quuxplusone]

I assume this is still OK, and still necessary, even after D117400 which I assume must have merge-conflicted with it a lot?

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

153–154

I haven't investigated so I assume you're not mistaken. Then it just sounds like my request shifts from test coverage for common_iterator<OutputIterWithNonVoidValueType>::iterator_category, to test coverage that common_iterator<OutputIterWithNonVoidValueType> is SFINAE-friendly ill-formed. I believe we have some prior art, shaped roughly like

template<class T>
concept HasCommonIterator = requires { typename std::ranges::common_iterator<T>; };
static_assert(!HasCommonIterator<OutputIterWithNonVoidValueType>);

[ldionne]

Add test.

[ldionne]

In D117449#3270076, @Quuxplusone wrote:

I assume this is still OK, and still necessary, even after D117400 which I assume must have merge-conflicted with it a lot?

Yes, still necessary. There were only small merge conflicts.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

153–154

I'm not following. common_iterator<OutputIterWithNonVoidValueType> does work, it's only that you can't query its iterator_traits.

I added a test in iterator_traits.compile.pass.cpp which isn't the most useful (because it ends up basically testing the iterator_traits base template), but should clarify what I mean.

[ldionne]

Will ship once CI passes unless @Quuxplusone has other comments.

[• Quuxplusone]

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

153–154

I'm not following. common_iterator<OutputIterWithNonVoidValueType> does work, it's only that you can't query its iterator_traits.

Well, now I'm confused. How can you have an iterator, that "works," but you can't query its iterator_traits? What does that even mean? I would think that by definition a "working iterator" must have iterator_traits that say it's an iterator. Otherwise it's not an iterator.

I pasted your NonVoidOutputIterator into a Godbolt; what happens after this patch? (Also I assume that spew on GCC indicates a libstdc++ bug @jwakely.) https://godbolt.org/z/KrxY6Wd97
I'm surprised that common_iterator<OI, ...>::value_type is void instead of OI::value_type, but I think that's what the standard literally says, yeah.

[ldionne]

The CI only failed on Windows due to missing space. I'm going to ship this now, and we can make adjustments post-commit if the discussion ends up bringing up additional issues.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

153–154

Sorry, I should have been precise. I don't mean that iterator_traits<common_iterator<OutputIterWithNonVoidValueType>> doesn't work. I mean that iterator_traits<common_iterator<OutputIterWithNonVoidValueType>>::value_type is void, despite OutputIterWithNonVoidValueType::value_type not being void. And yes, I think it's a bit silly, but it's definitely what the Standard says.

The reason is simply that iterator_traits<common_iterator<It>> requires It to be an input_iterator. If it is, then the value_type is properly forwarded through. If it isn't, then we end up falling back on the base template of iterator_traits (https://en.cppreference.com/w/cpp/iterator/iterator_traits):

Otherwise, if Iter satisfies the exposition-only concept __LegacyIterator, the member types are declared as follows:

Member type         Definition
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
difference_type     std::incrementable_traits<Iter>::difference_type if valid, otherwise void
value_type          void
pointer             void
reference           void
iterator_category   std::output_iterator_tag

That's my understanding anyways.

libcxx/include/__iterator/common_iterator.h

 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if !defined(_LIBCPP_HAS_NO_RANGES)
 
+template<class _Iter>
+concept __can_use_postfix_proxy =
+  constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>> &&
+  move_constructible<iter_value_t<_Iter>>;
+
 template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
   requires (!same_as<_Iter, _Sent> && copyable<_Iter>)
 class common_iterator {
   class __proxy {
     friend common_iterator;
 
     iter_value_t<_Iter> __value;
     // We can move __x because the only caller verifies that __x is not a reference.
class common_iterator {
   class __postfix_proxy {
     friend common_iterator;
 
     iter_value_t<_Iter> __value;
     constexpr __postfix_proxy(iter_reference_t<_Iter>&& __x)
       : __value(_VSTD::forward<iter_reference_t<_Iter>>(__x)) {}
 
   public:
-    constexpr static bool __valid_for_iter =
-      constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>> &&
-      move_constructible<iter_value_t<_Iter>>;
-
     constexpr const iter_value_t<_Iter>& operator*() const noexcept {
       return __value;
     }
   };
 
 public:
   variant<_Iter, _Sent> __hold_;
 
public:
 
   decltype(auto) operator++(int) {
     _LIBCPP_ASSERT(holds_alternative<_Iter>(__hold_), "Attempted to increment a non-dereferenceable common_iterator");
     if constexpr (forward_iterator<_Iter>) {
       auto __tmp = *this;
       ++*this;
       return __tmp;
     } else if constexpr (requires (_Iter& __i) { { *__i++ } -> __referenceable; } ||
-                         !__postfix_proxy::__valid_for_iter) {
+                         !__can_use_postfix_proxy<_Iter>) {
       return _VSTD::__unchecked_get<_Iter>(__hold_)++;
     } else {
       __postfix_proxy __p(**this);
       ++*this;
       return __p;
     }
   }
 

 };
 
 template<class _Iter, class _Sent>
   requires __common_iter_has_ptr_op<_Iter, _Sent>
 struct __arrow_type_or_void<_Iter, _Sent> {
     using type = decltype(declval<const common_iterator<_Iter, _Sent>&>().operator->());
 };
 
-template<class _Iter, class _Sent>
+template<input_iterator _Iter, class _Sent>
 struct iterator_traits<common_iterator<_Iter, _Sent>> {
   using iterator_concept = _If<forward_iterator<_Iter>,
                                forward_iterator_tag,
                                input_iterator_tag>;
   using iterator_category = _If<__denotes_forward_iter<_Iter>,
                                 forward_iterator_tag,
                                 input_iterator_tag>;
   using pointer = typename __arrow_type_or_void<_Iter, _Sent>::type;
   using value_type = iter_value_t<_Iter>;
   using difference_type = iter_difference_t<_Iter>;
   using reference = iter_reference_t<_Iter>;
 };
 
-
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_COMMON_ITERATOR_H

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14, c++17
 // UNSUPPORTED: libcpp-no-concepts
 
 // template<input_iterator I, class S>
 //   struct iterator_traits<common_iterator<I, S>>;
 
 #include <iterator>
 
+#include <cstddef>
+#include "test_iterators.h"
 #include "test_macros.h"
 #include "types.h"
 
+template<class T>
+concept HasIteratorConcept = requires { typename T::iterator_concept; };
+
+struct NonVoidOutputIterator {
+    using value_type = int;
+    using difference_type = std::ptrdiff_t;
+    const NonVoidOutputIterator& operator*() const;
+    NonVoidOutputIterator& operator++();
+    NonVoidOutputIterator& operator++(int);
+    void operator=(int) const;
+};
+
 void test() {
   {
     using Iter = simple_iterator<int*>;
     using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
     using IterTraits = std::iterator_traits<CommonIter>;
 
     static_assert(std::same_as<IterTraits::iterator_concept, std::input_iterator_tag>);
     static_assert(std::same_as<IterTraits::iterator_category, std::input_iterator_tag>);
void test() {
     static_assert(std::same_as<IterTraits::iterator_concept, std::input_iterator_tag>);
     static_assert(std::same_as<IterTraits::iterator_category, std::input_iterator_tag>);
     static_assert(std::same_as<IterTraits::value_type, int>);
     static_assert(std::same_as<IterTraits::difference_type, std::ptrdiff_t>);
     // Note: IterTraits::pointer == __proxy.
     static_assert(!std::same_as<IterTraits::pointer, int*>);
     static_assert(std::same_as<IterTraits::reference, int>);
   }
+  // Test with an output_iterator that has a void value_type
   {
-    using Iter = non_const_deref_iterator<int*>;
+    using Iter = output_iterator<int*>;
     using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
     using IterTraits = std::iterator_traits<CommonIter>;
 
-    static_assert(std::same_as<IterTraits::iterator_concept, std::input_iterator_tag>);
-    static_assert(std::same_as<IterTraits::iterator_category, std::input_iterator_tag>);
-    static_assert(std::same_as<IterTraits::value_type, int>);
+    static_assert(!HasIteratorConcept<IterTraits>);
+    static_assert(std::same_as<IterTraits::iterator_category, std::output_iterator_tag>);
+    static_assert(std::same_as<IterTraits::value_type, void>);
     static_assert(std::same_as<IterTraits::difference_type, std::ptrdiff_t>);
     static_assert(std::same_as<IterTraits::pointer, void>);
-    static_assert(std::same_as<IterTraits::reference, int&>);
+    static_assert(std::same_as<IterTraits::reference, void>);
+  }
+  // Test with an output_iterator that has a non-void value_type
+  {
+    using CommonIter = std::common_iterator<NonVoidOutputIterator, sentinel_wrapper<NonVoidOutputIterator>>;
+    using IterTraits = std::iterator_traits<CommonIter>;
+
+    static_assert(!HasIteratorConcept<IterTraits>);
+    static_assert(std::same_as<IterTraits::iterator_category, std::output_iterator_tag>);
+    static_assert(std::same_as<IterTraits::value_type, void>);
+    static_assert(std::same_as<IterTraits::difference_type, std::ptrdiff_t>);
+    static_assert(std::same_as<IterTraits::pointer, void>);
+    static_assert(std::same_as<IterTraits::reference, void>);
   }
   {
     using Iter = cpp17_input_iterator<int*>;
     using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
     using IterTraits = std::iterator_traits<CommonIter>;
 
     static_assert(std::same_as<IterTraits::iterator_concept, std::input_iterator_tag>);
     static_assert(std::same_as<IterTraits::iterator_category, std::input_iterator_tag>);

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

 #include <cassert>
 
 #include "test_macros.h"
 #include "types.h"
 
 struct Incomplete;
 
 void test() {
-  int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
-
   // Reference: http://eel.is/c++draft/iterators.common#common.iter.nav-5
   // Case 2: can-reference
   {
+    int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
     auto iter1 = simple_iterator<int*>(buffer);
     auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
     auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
 
     assert(*(commonIter1++) == 1);
     assert(*commonIter1 == 2);
     assert(*(++commonIter1) == 3);
     assert(*commonIter1 == 3);
 
     for (auto i = 3; commonIter1 != commonSent1; ++i) {
       assert(*(commonIter1++) == i);
     }
     assert(commonIter1 == commonSent1);
   }
 
   // Case 2: can-reference
   {
+    int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
     auto iter1 = value_iterator<int*>(buffer);
     auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
     auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
 
     assert(*(commonIter1++) == 1);
     assert(*commonIter1 == 2);
     assert(*(++commonIter1) == 3);
     assert(*commonIter1 == 3);
 
     for (auto i = 3; commonIter1 != commonSent1; ++i) {
       assert(*(commonIter1++) == i);
     }
     assert(commonIter1 == commonSent1);
   }
 
   // Case 3: postfix-proxy
   {
+    int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
     auto iter1 = void_plus_plus_iterator<int*>(buffer);
     auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
     auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
 
     assert(*(commonIter1++) == 1);
     assert(*commonIter1 == 2);
     assert(*(++commonIter1) == 3);
     assert(*commonIter1 == 3);
 
     for (auto i = 3; commonIter1 != commonSent1; ++i) {
       assert(*(commonIter1++) == i);
     }
     assert(commonIter1 == commonSent1);
   }
 
   // Case 2: where this is not referencable or move constructible
   {
+    int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
     auto iter1 = value_type_not_move_constructible_iterator<int*>(buffer);
     auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
     auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
 
     commonIter1++;
-    // Note: postfix operator++ returns void.
-    // assert(*(commonIter1++) == 1);
+    ASSERT_SAME_TYPE(decltype(commonIter1++), void);
     assert(*commonIter1 == 2);
     assert(*(++commonIter1) == 3);
     assert(*commonIter1 == 3);
 
     for (auto i = 3; commonIter1 != commonSent1; ++i) {
       assert(*commonIter1 == i);
       commonIter1++;
     }
     assert(commonIter1 == commonSent1);
   }
 
   // Case 2: can-reference
   {
+    int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
     auto iter1 = cpp17_input_iterator<int*>(buffer);
     auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
     auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
 
     assert(*(commonIter1++) == 1);
     assert(*commonIter1 == 2);
     assert(*(++commonIter1) == 3);
     assert(*commonIter1 == 3);
 
     for (auto i = 3; commonIter1 != commonSent1; ++i) {
       assert(*(commonIter1++) == i);
     }
     assert(commonIter1 == commonSent1);
   }
 
   // Case 1: forward_iterator
   {
+    int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
     auto iter1 = forward_iterator<int*>(buffer);
     auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
     auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
 
     assert(*(commonIter1++) == 1);
     assert(*commonIter1 == 2);
     assert(*(++commonIter1) == 3);
     assert(*commonIter1 == 3);
 
     for (auto i = 3; commonIter1 != commonSent1; ++i) {
       assert(*(commonIter1++) == i);
     }
     assert(commonIter1 == commonSent1);
   }
 
   // Case 1: forward_iterator
   {
+    int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
     auto iter1 = random_access_iterator<int*>(buffer);
     auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
     auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
 
     assert(*(commonIter1++) == 1);
     assert(*commonIter1 == 2);
     assert(*(++commonIter1) == 3);
     assert(*commonIter1 == 3);
 
     for (auto i = 3; commonIter1 != commonSent1; ++i) {
       assert(*(commonIter1++) == i);
     }
     assert(commonIter1 == commonSent1);
   }
+
+  // Increment a common_iterator<output_iterator>: iter_value_t is not always valid for
+  // output iterators (it isn't for our test output_iterator). This is worth testing
+  // because it gets tricky when we define operator++(int).
+  {
+    int buffer[] = {0, 1, 2, 3, 4};
+    using Common = std::common_iterator<output_iterator<int*>, sentinel_type<int*>>;
+    auto iter = Common(output_iterator<int*>(buffer));
+    auto sent = Common(sentinel_type<int*>{buffer + 5});
+
+    *iter++ = 90;
+    assert(buffer[0] == 90);
+
+    *iter = 91;
+    assert(buffer[1] == 91);
+
+    *++iter = 92;
+    assert(buffer[2] == 92);
+
+    iter++;
+    iter++;
+    assert(iter != sent);
+    iter++;
+    assert(iter == sent);
+  }
 }
 
 int main(int, char**) {
   test();
 
   return 0;
 }

libcxx/test/std/iterators/predef.iterators/iterators.common/types.h

public:
     friend constexpr auto operator-(const comparable_iterator& lhs, const simple_iterator<It>& rhs) {
       return lhs.base() - rhs.base();
     }
     friend constexpr auto operator-(const simple_iterator<It>& lhs, const comparable_iterator& rhs) {
       return lhs.base() - rhs.base();
     }
 };
 
-template <class It>
-class non_const_deref_iterator
-{
-    It it_;
-
-public:
-    typedef          std::input_iterator_tag                   iterator_category;
-    typedef typename std::iterator_traits<It>::value_type      value_type;
-    typedef typename std::iterator_traits<It>::difference_type difference_type;
-    typedef It                                                 pointer;
-    typedef typename std::iterator_traits<It>::reference       reference;
-
-    constexpr It base() const {return it_;}
-
-    non_const_deref_iterator() = default;
-    explicit constexpr non_const_deref_iterator(It it) : it_(it) {}
-
-    constexpr reference operator*() {return *it_;} // Note: non-const.
-
-    constexpr non_const_deref_iterator& operator++() {++it_; return *this;}
-    constexpr non_const_deref_iterator operator++(int)
-        {non_const_deref_iterator tmp(*this); ++(*this); return tmp;}
-};
-
 template<class T>
 struct sentinel_type {
   T base;
 
   template<class U>
   friend constexpr bool operator==(const sentinel_type& lhs, const U& rhs) { return lhs.base == rhs.base(); }
   template<class U>
   friend constexpr bool operator==(const U& lhs, const sentinel_type& rhs) { return lhs.base() == rhs.base; }