使用自定义迭代器根据另一个容器对容器进行排序

Question

从 MSVC 19.27 (VS 16.7) 更新到 MSVC 19.28+ (VS 16.8+) 后，由于编译器更改了排序算法，我基于另一个容器排序的自定义迭代器退化了。我在一个面向数据的结构（数组结构）上操作，所以我有必要有两个单独的容器。

我的迭代器基于

测试：

#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";
}

预期结果：

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

当前结果：

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

更新后，我不得不在 struct Value 中添加 operator < 来修复以前不需要的编译。我假设 MSVC 19.28 (VS 16.8) 或更高版本中更改后的排序算法现在使用了一些其他缺失或错误的运算符，因为它在 GCC 和 Clang 中工作。

非常感谢任何帮助。

Answer 1

我标记了至少缺失的必需行。我已经使引用和迭代器可复制并且迭代器 - 完全有序。与比较运算符一起，应声明 operator+=，因为某些实现会使用它。这些迭代器仍然不严格符合迭代器的概念，例如尾后迭代器会做什么？

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

Answer 2

感谢 Swift and others I rewrote the iterator based on https://artificial-mind.net/blog/2020/11/28/std-sort-multiple-ranges 的帮助，它现在似乎可以在 MSVC、GCC 和 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";
}

使用自定义迭代器根据另一个容器对容器进行排序

Sort container based on another using custom iterator

c++

sorting

iterator

visual-c++