Why does theMicrosoft Visual C++ library implementation 'unwrap' iterators?

Question

Throughout microsofts stl implementation, pretty much all of their iterators are unwrapped before they are used.

For instance, for_each looks like this:

template <class _InIt, class _Fn>
_Fn for_each(_InIt _First, _InIt _Last, _Fn _Func) { // perform function for each element [_First, _Last)
    _Adl_verify_range(_First, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);
    for (; _UFirst != _ULast; ++_UFirst) {
        _Func(*_UFirst);
    }
    return _Func; }

_Adl_verify_range checks that first <= last, which I understand, but I dont quite understand the purpose of _Get_unwrapped():

#if _HAS_IF_CONSTEXPR
template <class _Iter>
_NODISCARD constexpr decltype(auto) _Get_unwrapped(_Iter&& _It) {
    // unwrap an iterator previously subjected to _Adl_verify_range or otherwise validated
    if constexpr (is_pointer_v<decay_t<_Iter>>) { // special-case pointers and arrays
        return _It + 0;
    } else if constexpr (_Unwrappable_v<_Iter>) {
        return static_cast<_Iter&&>(_It)._Unwrapped();
    } else {
        return static_cast<_Iter&&>(_It);
    }
}
#else // ^^^ _HAS_IF_CONSTEXPR / !_HAS_IF_CONSTEXPR vvv
template <class _Iter, enable_if_t<_Unwrappable_v<_Iter>, int> = 0>
_NODISCARD constexpr decltype(auto) _Get_unwrapped(_Iter&& _It) {
    // unwrap an iterator previously subjected to _Adl_verify_range or otherwise validated
    return static_cast<_Iter&&>(_It)._Unwrapped();
}

It seems that it wants to decay the iterator, or cast it to an rvalue reference.

So my question is why does Visual++ use this paradigm? GCC does not do this as far as I can tell.

EDIT

As requested, source of iterator._Unwrapped()

_NODISCARD constexpr _Ptr _Unwrapped() const noexcept {
    return _Myptr;
}

_Myptr is defined in the iterator itself, and is just a raw pointer:

template <class _Ptr>
class unchecked_array_iterator {
...
private:
    _Ptr _Myptr; // underlying pointer
}

Answer 1

Why does VC++ wrap iterators?

It's a design choice. Indeed, for array-like types like std::array and std::vector an iterator can be a simple typedef to T*, which satisfies iterator semantics nicely, and indeed this is how GNU stdlibc++ implements it. But from the standard perspective, iterator is a pointer-like object, but isn't necessarily a pointer. So...

1. Assuming that it's a pointer would be a mistake and could lead to non-portable code (case in point).

2. Wrapping iterators allows for iterator debugging (see _ITERATOR_DEBUG_LEVEL). For example here's a debug operator++:

   _CONSTEXPR17 _Array_const_iterator& operator++() {
       _STL_VERIFY(_Ptr, "cannot increment value-initialized array iterator");
       _STL_VERIFY(_Idx < _Size, "cannot increment array iterator past end");
       ++_Idx;
       return *this;
   }
   

Why does VC++ unwrap iterators?

1. It's an optimization of error reporting. In loops like std::for_each, instead of getting a range error in the middle of for_each, the error is signaled upon entry into for_each.

2. It's a performance optimization.

   • In Debug mode, checking the preconditions once leads to faster code (debug mode is 10+ times slower already, so performance still matters even in debug mode).
   • In Release mode the compiler can optimize pointer access better than inferring it via an iterator every time. Yes, it can still infer it in most cases, but an additional level of indirection can lead to different decision-making with regard to inlining elsewhere in the code.

Answer 2

If I understand correctly, this is a debugging feature.

The wrapped iterators contain additional information that allows the implementation to verify various preconditions, such as whether two iterators form a valid range, that an iterator has not been invalidated, that an iterator is used only with a container to whose element it refers. _Adl_verify_range is one such check.

But then, when the iterator is actually used in the algorithm, the implementation does not want to incur the overhead of the verifications (which would happen for each ++ operation). It unwraps the iterator to a version that does not have the safety features. Usually this means, that the unwrapped version is just a pointer (not necessarily a naked one, but wrapped in a class).

In Release builds, the algorithm itself can be optimized well because only very simple types are involved and no checks, but the initial safety checks can remain or can be omitted, as the developer wishes.