This const_cast seems a bit suspicious to me. The following would be better - does it not work?

		const iter_return_type & operator*() const
		{ return elm; }

		const iter_return_type * operator->() const
		{ return &elm; }

Hmm, now that you point it out, I'm quite confused about Steffan from 7 months ago too. Maybe I just did not understand at that point in time the idea of a const in the return type.

We then get from MSVC 14.34.31933

error C2678: binary '=': no operator found which takes a left-hand operand of type 'const tpie::packed_array<bool,1>::iter_return_type' (or there is no acceptable conversion)

Here is the MSVC sorting algorithm that is the source of all our problems

template <class _BidIt, class _Pr>
_CONSTEXPR20 _BidIt _Insertion_sort_unchecked(const _BidIt _First, const _BidIt _Last, _Pr _Pred) {
    // insertion sort [_First, _Last)
    if (_First != _Last) {
        for (_BidIt _Mid = _First; ++_Mid != _Last;) { // order next element
            _BidIt _Hole               = _Mid;
            _Iter_value_t<_BidIt> _Val = _STD move(*_Mid);

            if (_DEBUG_LT_PRED(_Pred, _Val, *_First)) { // found new earliest element, move to front
                _Move_backward_unchecked(_First, _Mid, ++_Hole);
                *_First = _STD move(_Val);
            } else { // look for insertion point after first
                for (_BidIt _Prev = _Hole; _DEBUG_LT_PRED(_Pred, _Val, *--_Prev); _Hole = _Prev) {
                    *_Hole = _STD move(*_Prev); // move hole down
                }

                *_Hole = _STD move(_Val); // insert element in hole
            }
        }
    }

    return _Last;
}

Notice the lines with *_First = _STD move(_Val);, and *_Hole = .... For some reason, the packed array iterator is const at this point. Looking at packed_array the iterator is a const_iterator if the packed array itself is called in a const context, so the packed_array is presumably const when calling the sorting algorithm.

Very interesting.

• Does this compile error arise in an open source project when using MSVC and tpie? In other words, can you point me to the code where the problem occurs?
• Does MSVC provide a template instantiation traceback, which could maybe show us how the packed array iterator becomes const? It seems like a range of const iterators indeed shouldn't be sortable, but maybe the const-ness is induced wrongly higher up in the call stack.

• This error occurs from compiling the TPIE unit tests (see item v. in the trace below). Do you want me to try and set up a Windows CI for Adiar?

• Here is the stack trace from the MSVC compiler as available through the GitHub Action console log. I took the liberty to clean it up/format it, so we actually can understand what is going on.

  1. include\algorithm(7517): error C2678: binary '=': no operator found which takes a left-hand operand of type const tpie::packed_array<bool,1>::iter_return_type

  2. include\algorithm(7639): while trying to match the argument list (const tpie::packed_array<bool,1>::iter_return_type, tpie::packed_array<bool,1>::iter_return_type) for the function template instantiation _BidIt std::_Insertion_sort_unchecked<_RanIt,_Pr>(const _BidIt, const _BidIt,_Pr) being compiled with

         _BidIt=tpie::packed_array<bool,1>::iter_base<true>,
         _RanIt=tpie::packed_array<bool,1>::iter_base<true>,
         _Pr=std::less<void>
     

  3. include\algorithm(7669): see reference to function template instantiation void std::_Sort_unchecked<_RanIt,_Fn>(_RanIt,_RanIt,__int64,_Pr) being compiled with

          _RanIt=tpie::packed_array<bool,1>::iter_base<true>,
          _Fn=std::less<void>,
          _Pr=std::less<void>
     

  4. include\algorithm(7674): see reference to function template instantiation void std::sort<_RanIt,std::less<void>>(const _RanIt, const _RanIt,_Pr) being compiled with

         _RanIt=tpie::packed_array<bool,1>::iter_base<true>,
         _Pr=std::less<void>
     

  5. tpie\test\unit\test_array.cpp(223): see reference to function template instantiation void std::sort<_RanIt>(const _RanIt, const _RanIt) being compiled with

         _RanIt=tpie::packed_array<bool,1>::iter_base<true>
     

  It seems like the const is added directly with the std::sort call in the unit test. The bit_array hat in the unit test in question is not set to const.

  Either this is because the MSVC 14.34 STL provides a const sort . Yet, one should think the same problem also occurs in the base-case for the parallel quick sort algorithm.

  Otherwise, it might be that MSVC resolves the begin() and end() unexpectedly to the more restricted const case? A quick google search seems to show the latter is not unlikely (here and here).

I didn't realize the compile error was from the GitHub Actions API!

I've tried to reproduce the compile error on Godbolt running MSVC 19.14, but unfortunately I can't reproduce it - it compiles without error. I wonder if there's some way I can easily run MSVC 19.34 myself to try out my reproduction case: https://godbolt.org/z/ocMb3Gcdh

I tried to click on your link. By default, it uses the x64 msvc v19.14 (WINE) compiler. When I switch it to x64 msvc v19 latest I reproduce the error.

As far as I can tell, the WINE part means, that it is Microsoft's compiler but run on a linux machine rather than a Windows machine? Is this as much as MSVC is supposed to be supported by TPIE?

Based on "Does this compile error arise in an open source project when using MSVC and tpie?" I've started early on creating similar CI for my research project. Since I am not using the packed_array (or at least definitely not using the std::sort on it) all my 1491 unit tests pass on Windows.

Going through the possible MSVC versions on the provided godbolt link, the issue was introduced with version 19.28 of MSVC x64. There are multiple version numbers to think about. Looking at the Wikipedia page, this change was accompanied with:

On second thought, my hack does actually make some sense. What should the const in const iter_base refer to? Should it mean I cannot change where it points to, the underlying value, or both? In other words, is a const iter_base equivalent to (T*) const, (const T)* or (const T)* const?

Microsoft's std::sort seems to be assuming the (T*) const semantics.