时间戳

首页 > 解决方案 > 使用自定义迭代器基于另一个容器对容器进行排序

c++ - 使用自定义迭代器基于另一个容器对容器进行排序

问题描述

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

我的迭代器基于https://stackoverflow.com/a/46370189/209649

测试：

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

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

任何帮助将不胜感激。

标签： c++sortingvisual-c++iterator

解决方案

感谢Swift和其他人的帮助，我重写了基于https://artificial-mind.net/blog/2020/11/28/std-sort-multiple-ranges的迭代器，现在它似乎可以在 MSVC、GCC 和铛：

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

推荐阅读