Sort container based on another using custom iterator

Question

After updating from MSVC 19.27 (VS 16.7) to MSVC 19.28+ (VS 16.8+) my custom iterator to sort one container based on another regressed due to the compiler's changed sort algorithm. I operate on a data oriented structure (struct of arrays) so it is necessary for me to have two separate containers.

My iterator is based on https://stackoverflow.com/a/46370189/209649

Test:

#include <iterator>

namespace SortHelper
{
    template <typename OrderT, typename DataT>
    struct ValueReference;

    template <typename OrderT, typename DataT>
    struct Value
    {
        OrderT Order;
        DataT Data;

        Value(OrderT order, DataT data) :
            Order(order),
            Data(data)
        {
        }

        Value(const ValueReference<OrderT, DataT>& rhs);

        bool operator <(const Value<OrderT, DataT>& rhs) const { return Order < rhs.Order; }
    };

    template <typename OrderT, typename DataT>
    struct ValueReference
    {
        OrderT* Order;
        DataT* Data;

        ValueReference(OrderT* orderIterator, DataT* dataIterator) :
            Order(orderIterator),
            Data(dataIterator)
        {
        }

        ValueReference& operator =(const ValueReference& rhs)
        {
            *Order = *rhs.Order;
            *Data = *rhs.Data;
            return *this;
        }

        ValueReference& operator =(const Value<OrderT, DataT>& rhs)
        {
            *Order = rhs.Order;
            *Data = rhs.Data;
            return *this;
        }

        bool operator <(const ValueReference& rhs) const { return *Order < *rhs.Order; }
    };

    template <typename OrderT, typename DataT>
    struct ValueIterator
    {
        typedef Value<OrderT, DataT> value_type;
        typedef Value<OrderT, DataT>* pointer;
        typedef ValueReference<OrderT, DataT> reference;
        typedef std::ptrdiff_t difference_type;
        typedef std::random_access_iterator_tag iterator_category;

        OrderT* OrderIterator;
        DataT* DataIterator;

        ValueIterator(OrderT* orderIterator, DataT* dataIterator) :
            OrderIterator(orderIterator),
            DataIterator(dataIterator)
        {
        }

        std::ptrdiff_t operator -(const ValueIterator& rhs) const { return OrderIterator - rhs.OrderIterator; }
        ValueIterator operator +(std::ptrdiff_t off) const { return ValueIterator(OrderIterator + off, DataIterator + off); }
        ValueIterator operator -(std::ptrdiff_t off) const { return ValueIterator(OrderIterator - off, DataIterator - off); }

        ValueIterator& operator ++()
        {
            ++OrderIterator;
            ++DataIterator;
            return *this;
        }

        ValueIterator& operator --()
        {
            --OrderIterator;
            --DataIterator;
            return *this;
        }

        ValueIterator operator ++(int) { return ValueIterator(OrderIterator++, DataIterator++); }
        ValueIterator operator --(int) { return ValueIterator(OrderIterator--, DataIterator--); }
        Value<OrderT, DataT> operator *() const { return Value<OrderT, DataT>(*OrderIterator, *DataIterator); }
        ValueReference<OrderT, DataT> operator [](difference_type n) const { return ValueReference<OrderT, DataT>(OrderIterator + n, DataIterator + n); }
        ValueReference<OrderT, DataT> operator *() { return ValueReference<OrderT, DataT>(OrderIterator, DataIterator); }
        bool operator <(const ValueIterator& rhs) const { return OrderIterator < rhs.OrderIterator; }
        bool operator ==(const ValueIterator& rhs) const { return OrderIterator == rhs.OrderIterator; }
        bool operator !=(const ValueIterator& rhs) const { return OrderIterator != rhs.OrderIterator; }
    };

    template <typename OrderT, typename DataT>
    Value<OrderT, DataT>::Value(const ValueReference<OrderT, DataT>& rhs) :
        Order(*rhs.Order),
        Data(*rhs.Data)
    {
    }

    template <typename OrderT, typename DataT>
    bool operator <(const Value<OrderT, DataT>& lhs, const ValueReference<OrderT, DataT>& rhs)
    {
        return lhs.Order < *rhs.Order;
    }

    template <typename OrderT, typename DataT>
    bool operator <(const ValueReference<OrderT, DataT>& lhs, const Value<OrderT, DataT>& rhs)
    {
        return *lhs.Order < rhs.Order;
    }

    template <typename OrderT, typename DataT>
    void swap(ValueReference<OrderT, DataT> lhs, ValueReference<OrderT, DataT> rhs)
    {
        std::swap(*lhs.Order, *rhs.Order);
        std::swap(*lhs.Data, *rhs.Data);
    }
}

#include <algorithm>
#include <iostream>

int main()
{
    int Age[] = { 45, 14, 5, 24 };
    const char* Names[] = { "Karl", "Paul", "Martin", "Jennie" };
    std::sort(SortHelper::ValueIterator<int, const char*>(Age, Names), SortHelper::ValueIterator<int, const char*>(Age + 4, Names + 4));

    for (int i = 0; i < 4; ++i)
        std::cout << Age[i] << ": " << Names[i] << "\n";
}

Expected result:

{ "Martin", "Paul", "Jennie", "Karl" };
{ 5, 14, 24, 45 };

Current result:

{ "Karl", "Karl", "Karl", "Karl" };
{ 45, 45, 45, 45 };

After updating I had to add the operator < inside struct Value to fix compile which was not necessary before. I assume that there is some other missing or wrong operator now used by the changed sort algorithm in MSVC 19.28 (VS 16.8) or higher as it works in GCC and Clang.

Any help would be highly appreciated.

As mentioned it needs to run on MSVC and not GCC however godbolt does not produce output with MSVC — stfx, Oct 29 '21 at 04:50
Maybe try https://www.boost.org/doc/libs/1_77_0/libs/iterator/doc/zip_iterator.html — n. m. could be an AI, Oct 29 '21 at 05:12
The way it is , it's not guaranteed to work. ValueIterator doesn't have a copy constructor here, because copy assignment declared. It might have an implicit shallow copy implemented on some compilers that aren't strictily ISO. Essentially rule of 5 is broken. It doesn't have += operator defined as well, so along with absence of copy ctor some implementations of sort would be ill-formed. Which is shown by clang, clang doesn't compile this code at all. — Swift - Friday Pie, Oct 29 '21 at 06:08
mac os, clang version 12.0.0 with c++20, miss +=, >=, >. and after they added, result is correct. — che.wang, Oct 29 '21 at 06:19
@dyungwang no version of clang I attempted doesn't accept this code (starting with appearance of C++11 every major version since 5).. COuld it be that on Windows in OP configuration clang took MSVC's implementation of standard components? — Swift - Friday Pie, Oct 29 '21 at 06:39
You cannot execute msvc code on godbolt, but you can `static_assert`, so with some `constexpr` added: [Demo](https://godbolt.org/z/ed83z57or) (and as UB should not be possible in constexpr, you either use implementation specific, or unspecified behavior (or msvc bug)). — Jarod42, Oct 29 '21 at 08:09
@Jarod42 Thanks so it seems like it last worked on MSVC 19.27 (VS 16.7) and stopped working in MSVC 19.28 (VS 16.8) — stfx, Oct 29 '21 at 08:24
Since it's all inline, you should be able to debug `std::sort` code and see what is going wrong. — n. m. could be an AI, Oct 29 '21 at 10:03
@Jarod42 isn't the "latest" standard for that version some early C++20 implementation? From C++20 view this code got a number of issues. because of rule change ALso the task is solvable with standard components in that case. — Swift - Friday Pie, Oct 29 '21 at 10:49
@Swift-FridayPie: I didn't look at code validity, just wanted to solve the issue to show the problem with msvc (with run it, as not possible in godbolt). As `std::sort` is used, it need indeed C++20 which adds missing `constexpr`. — Jarod42, Oct 29 '21 at 10:54
@Jarod42 fair enough. VS is notorious for supporting features from standards which weren't issued yet (like it did with lambdas in 2010 or with `module`-like behaviour of templates in pre-2000) — Swift - Friday Pie, Oct 29 '21 at 11:03

stfx · Accepted Answer · 2021-11-01T07:24:41.003

Thanks to the help of Swift and others I rewrote the iterator based on https://artificial-mind.net/blog/2020/11/28/std-sort-multiple-ranges which now seems to work correctly on MSVC, GCC and Clang:

#include <iterator>

namespace SortHelper
{
    template <typename OrderT, typename DataT>
    struct Value
    {
        OrderT Order;
        DataT Data;
    };

    template <typename OrderT, typename DataT>
    struct ValueReference
    {
        OrderT* Order;
        DataT* Data;

        ValueReference& operator=(ValueReference&& r) noexcept
        {
            *Order = std::move(*r.Order);
            *Data = std::move(*r.Data);
            return *this;
        }

        ValueReference& operator=(Value<OrderT, DataT>&& r)
        {
            *Order = std::move(r.Order);
            *Data = std::move(r.Data);
            return *this;
        }

        friend void swap(ValueReference a, ValueReference b)
        {
            std::swap(*a.Order, *b.Order);
            std::swap(*a.Data, *b.Data);
        }

        operator Value<OrderT, DataT>()&&
        {
            return { std::move(*Order), std::move(*Data) };
        }
    };

    template <typename OrderT, typename DataT>
    bool operator<(const ValueReference<OrderT, DataT>& a, const Value<OrderT, DataT>& b)
    {
        return *a.Order < b.Order;
    }

    template <typename OrderT, typename DataT>
    bool operator<(const Value<OrderT, DataT>& a, const ValueReference<OrderT, DataT>& b)
    {
        return a.Order < *b.Order;
    }

    template <typename OrderT, typename DataT>
    bool operator<(const ValueReference<OrderT, DataT>& a, const ValueReference<OrderT, DataT>& b)
    {
        return *a.Order < *b.Order;
    }

    template <typename OrderT, typename DataT>
    struct ValueIterator
    {
        using iterator_category = std::random_access_iterator_tag;
        using difference_type = size_t;
        using value_type = Value<OrderT, DataT>;
        using pointer = value_type*;
        using reference = ValueReference<OrderT, DataT>;

        OrderT* Order;
        DataT* Data;

        bool operator==(const ValueIterator& r) const
        {
            return Order == r.Order;
        }
        bool operator!=(const ValueIterator& r) const
        {
            return Order != r.Order;
        }
        bool operator<(const ValueIterator& r) const
        {
            return Order < r.Order;
        }

        ValueIterator operator+(difference_type i) const
        {
            return { Order + i, Data + i };
        }
        ValueIterator operator-(difference_type i) const
        {
            return { Order - i, Data - i };
        }

        difference_type operator-(const ValueIterator& r) const
        {
            return Order - r.Order;
        }

        ValueIterator& operator++()
        {
            ++Order;
            ++Data;
            return *this;
        }
        ValueIterator& operator--()
        {
            --Order;
            --Data;
            return *this;
        }

        ValueReference<OrderT, DataT> operator*() const
        {
            return { Order, Data };
        }
    };
}

#include <algorithm>
#include <iostream>

int main()
{
    int Age[] = { 45, 14, 5, 24 };
    const char* Names[] = { "Karl", "Paul", "Martin", "Jennie" };
    std::sort(SortHelper::ValueIterator<int, const char*>{ Age, Names }, SortHelper::ValueIterator<int, const char*>{ Age + 4, Names + 4 });

    for (int i = 0; i < 4; ++i)
        std::cout << Age[i] << ": " << Names[i] << "\n";
}

Breaks in newer gcc because of direct initialization going there in code instead of assignment, but adding `ValueReference(const ValueReference&) = default;` `ValueReference(ValueReference&& ) = default;` solves it — Swift - Friday Pie, Oct 29 '21 at 11:17
To be fully portable, iterator have to implement all of those : https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator — Swift - Friday Pie, Oct 29 '21 at 11:23

Swift - Friday Pie · Answer 2 · 2021-10-29T11:10:53.293

I marked required lines that were at very least missing. I've made reference and iterator copyable and the iterator - fully ordered. Along with comparison operators , an operator+= should be declared as some implementations would use it. Those iterators still do not fit strictly into concept of iterator, e.g. what past-of-end iterator would do?

#include <iterator>
#include <algorithm> //! You should not rely on fact that swap is defined.
#include <utility>   //! even if it was used and didn't produce error

namespace SortHelper
{
    template <typename OrderT, typename DataT>
    struct ValueReference;

    template <typename OrderT, typename DataT>
    struct Value
    {
        OrderT Order;
        DataT Data;

        Value(OrderT order, DataT data) :
            Order(order),
            Data(data)
        {
        }

        Value(const ValueReference<OrderT, DataT>& rhs);

        bool operator <(const Value<OrderT, DataT>& rhs) const { return Order < rhs.Order; }
    };

    template <typename OrderT, typename DataT>
    struct ValueReference
    {
        OrderT* Order;
        DataT* Data;

        ValueReference(const ValueReference& v) = default;   ///!
        
        ValueReference(OrderT* orderIterator, DataT* dataIterator) :
            Order(orderIterator),
            Data(dataIterator)
        {
        }

        ValueReference& operator =(const ValueReference& rhs)
        {
            *Order = *rhs.Order;
            *Data = *rhs.Data;
            return *this;
        }

        ValueReference& operator =(const Value<OrderT, DataT>& rhs)
        {
            *Order = rhs.Order;
            *Data = rhs.Data;
            return *this;
        }

        bool operator <(const ValueReference& rhs) const { return *Order < *rhs.Order; }
    };

    template <typename OrderT, typename DataT>
    struct ValueIterator
    {
        typedef Value<OrderT, DataT> value_type;
        typedef Value<OrderT, DataT>* pointer;
        typedef ValueReference<OrderT, DataT> reference;
        typedef std::ptrdiff_t difference_type;
        typedef std::random_access_iterator_tag iterator_category;

        OrderT* OrderIterator;
        DataT* DataIterator;

        ValueIterator(const ValueIterator& v) = default; ///!
        
        ValueIterator(OrderT* orderIterator, DataT* dataIterator) :
            OrderIterator(orderIterator),
            DataIterator(dataIterator)
        {
        }

        std::ptrdiff_t operator -(const ValueIterator& rhs) const { return OrderIterator - rhs.OrderIterator; }
        ValueIterator operator +(std::ptrdiff_t off) const { return ValueIterator(OrderIterator + off, DataIterator + off); }
        ValueIterator operator -(std::ptrdiff_t off) const { return ValueIterator(OrderIterator - off, DataIterator - off); }

        ValueIterator& operator ++()
        {
            ++OrderIterator;
            ++DataIterator;
            return *this;
        }

        ValueIterator& operator --()
        {
            --OrderIterator;
            --DataIterator;
            return *this;
        }
        // operator +=, -= ? that may be used.
        ValueIterator operator +=(int v) { return ValueIterator(OrderIterator+v, DataIterator+v); }
        
        ValueIterator operator ++(int) { return ValueIterator(OrderIterator++, DataIterator++); }
        ValueIterator operator --(int) { return ValueIterator(OrderIterator--, DataIterator--); }
        // This may cause problems, depending on implementation of components
        // It confuses elements referenced being of non-copyable but movable type, while it's actually their copy.
        //Value<OrderT, DataT> operator *() const { return Value<OrderT, DataT>(*OrderIterator, *DataIterator); }
        ValueReference<OrderT, DataT> operator [](difference_type n) const { return ValueReference<OrderT, DataT>(OrderIterator + n, DataIterator + n); }
        ValueReference<OrderT, DataT> operator *() { return ValueReference<OrderT, DataT>(OrderIterator, DataIterator); }
        
        /// this can be replaced by starship operator <=>
        bool operator >(const ValueIterator& rhs) const { return OrderIterator > rhs.OrderIterator; } ///!
        bool operator <=(const ValueIterator& rhs) const { return OrderIterator <= rhs.OrderIterator; } ///!
        bool operator <(const ValueIterator& rhs) const { return OrderIterator < rhs.OrderIterator; }  
        bool operator >=(const ValueIterator& rhs) const { return OrderIterator >= rhs.OrderIterator; } ///!
        bool operator ==(const ValueIterator& rhs) const { return OrderIterator == rhs.OrderIterator; }
        bool operator !=(const ValueIterator& rhs) const { return OrderIterator != rhs.OrderIterator; }
    };

    template <typename OrderT, typename DataT>
    Value<OrderT, DataT>::Value(const ValueReference<OrderT, DataT>& rhs) :
        Order(*rhs.Order),
        Data(*rhs.Data)
    {
    }

    template <typename OrderT, typename DataT>
    bool operator <(const Value<OrderT, DataT>& lhs, const ValueReference<OrderT, DataT>& rhs)
    {
        return lhs.Order < *rhs.Order;
    }

    template <typename OrderT, typename DataT>
    bool operator <(const ValueReference<OrderT, DataT>& lhs, const Value<OrderT, DataT>& rhs)
    {
        return *lhs.Order < rhs.Order;
    }

    template <typename OrderT, typename DataT>
    void swap(ValueReference<OrderT, DataT> lhs, ValueReference<OrderT, DataT> rhs)
    {
        std::swap(*lhs.Order, *rhs.Order);
        std::swap(*lhs.Data, *rhs.Data);
    }
}

Thanks but it still produces the incorrect result on MSVC 16.11.5 — stfx, Oct 29 '21 at 06:42
@stfx well, either I'm missing another UB there or it's compiler bug (non-zero chance, I saw MSVC fail at much simpler code sometimes). I don't have MSVC that fresh to look atm. did you attempt to change standard support flags? — Swift - Friday Pie, Oct 29 '21 at 06:49
@stfx ah... I see where is the problem I think. your operator* can return a copy of data, not reference or ValueReference which is essentially the core idea of whole thing. But then `std::swap(*It , *OtherIt);` if appeared in `sort` code, does nothing, it would swap temporary values! `SortHelper::swap` doesn't get selected,or it would be ambiguous. A dereference operator returning a temporary is considered non-canonic. Btw, `Value` could be a subclass of `std::pair` if you wished to hide implementation — Swift - Friday Pie, Oct 29 '21 at 07:38
Yea it seems like [this line in MSVC STL](https://github.com/microsoft/STL/blob/d8f03cf399d730780b6ca0e5321a9ff4fc76bb0f/stl/inc/algorithm#L7288) causes the issue. Also SortHelper::swap indeed does not get called during debugging. Any idea how to best fix it? — stfx, Oct 29 '21 at 07:48
@stfx Fix rule of 5 for all classes you had created and sadly `Value operator *()` cannot exist for it to work. Note that with newer standard if _any_ constructor is defined class is considered non-agreggate. Commenting it out should redirect compilation to your function but it would use your reference wrapper. THis could be rewritten using RCTP and reference wrappers but that's a larger undertaking — Swift - Friday Pie, Oct 29 '21 at 10:34

Sort container based on another using custom iterator

2 Answers2

Linked