Sort container based on another using custom iterator-CodePudding

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.

CodePudding user response：

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<(ValueReference<OrderT, DataT> const& a, Value<OrderT, DataT> const& b)
    {
        return *a.Order < b.Order;
    }

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

    template <typename OrderT, typename DataT>
    bool operator<(ValueReference<OrderT, DataT> const& a, ValueReference<OrderT, DataT> const& 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==(ValueIterator const& r) const {
            return Order == r.Order;
        }
        bool operator!=(ValueIterator const& r) const {
            return Order != r.Order;
        }
        bool operator<(ValueIterator const& 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-(ValueIterator const& r) const {
            return static_cast<difference_type>(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";
}

CodePudding user response：

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);
    }
}