柔性中值评价器

Question

我最近发布了一个外评价中值算法 (即不需要移动或复制元素)，反馈鼓励我进一步开发它。

一个简单的建议是处理NaN值，并使用无穷大进行测试。如果输入中存在NaN，则返回似乎是合理的，因为中位数变得毫无意义。如果用户希望忽略can，他们可以使用过滤器视图(参见测试套件中的示例)。

另一项建议是考虑支持价值预测。我还想避免在没有必要的情况下存储指针的效率低下(更糟糕的是，我一直在存储迭代器)。

我的原始算法已经可以使用自定义比较器和中点函数进行配置；在该算法中添加一个投影将导致参数组合爆炸，使得很难默认其中的一些子集，因此我转向了Builder模式。允许简单使用，例如

//值是满足前向范围auto m=stats：：中值(值)的任何序列；

和更高级的使用，调用工厂，可能是连锁的：

auto m= stats::median.using_compare() .using_arithmetic_midpoint() (值)；

为了尽量减少复制，我想在传递所有权时按原样进行排序：

auto m=stats：：中位数(std：：move(值))；

如果我们想允许所有可写范围发生变异，那么我们可以具体地要求就地策略：

auto calc_median = stats::median.using_inplace_strategy()；auto m=calc_median(值)；

其他原始策略包括：

1. copy_strategy，它总是生成(投影)值的副本，并且
2. external_strategy，它提供指向元素的指针(没有投影，因为这不需要透明)。

请注意，这三种策略在范围上有不同的要求--拷贝接受输入范围；外部需要一个前向范围；内部是最有限制的，需要一个随机访问范围。

由此，我们有两种综合策略：

1. 如果可能的话，默认的策略会在适当的情况下进行排序，否则通过复制，返回到外部策略，作为最后的手段。
2. 如果可能的话，最小空间(frugal)策略也倾向于就地排序，但当指向元素的指针小于预测值时，则更喜欢外部策略而不是复制。

我尝试使用一致的模板参数名称(例如，Comp用于比较器，Proj用于投影)。我查看了标准的指导，但在这方面它是不一致的--有时甚至在一个部分内(例如，对nth_element()及其相关概念的描述)。

#include <algorithm>
#include <cmath>
#include <concepts>
#include <functional>
#include <iterator>
#include <memory>
#include <numeric>
#include <ranges>
#include <utility>

/*
  A flexible but user-friendly way to evaluate the median of almost any collection.

  Easy interface:
  * stats::median(values)               // values is unchanged

  * stats::median(std::move(values))    // may re-order the container

  * values | stats::median              // works like a view

  More advanced:
  * auto small_median = stats::median.using_frugal_strategy();
    small_median(values)                // tries harder not to minimize memory use

  * Other strategies are provided.  The "inplace" strategy is useful to end users, as it treats all
    inputs as rvalues (modifying through references) even without `std::move()`.  The "copy" and
    "external" strategies are mostly useful to the implementation of the default and frugal ones.

  * We can use any comparator or projection function, and any any function to calculate the mean of
    the mid elements (this function will be passed duplicate arguments if the input size is odd).

    An "arithmetic" midpoint function is provided; this can be useful for getting fractional medians
    from integer inputs.  For example:

        stats::median.using_arithmetic_midpoint()(std::array{ 0, 1, 2, 3})  ⟶  1.5
 */

namespace stats
{
    // Type traits
    template<std::ranges::forward_range Range, typename Proj>
    using projected_t =
        std::projected<std::ranges::iterator_t<Range>, Proj>::value_type;

    template<std::ranges::forward_range Range, typename Proj, typename Midpoint>
    using median_result_t =
        std::invoke_result_t<Midpoint, projected_t<Range, Proj>, projected_t<Range, Proj>>;

    // Concepts
    template<typename Range, typename Comp, typename Proj>
    concept sortable_range =
        std::sortable<std::ranges::iterator_t<Range>, Comp, Proj>;

    template<typename C, typename Range, typename Proj>
    concept projected_strict_weak_order =
        std::indirect_strict_weak_order<C, std::projected<std::ranges::iterator_t<Range>, Proj>>;

    template<typename M, typename Range, typename Proj>
    concept midpoint_function =
        std::invocable<M, projected_t<Range, Proj>, projected_t<Range, Proj>>;

    template<typename S>
    concept median_strategy =
        std::is_same_v<std::invoke_result_t<S, std::vector<int>&&, std::less<>, std::identity, std::less<>>, bool>;

    // Midpoint policies
    struct default_midpoint
    {
        template<typename T>
        constexpr auto operator()(T const& a, T const& b) const
        {
            using std::midpoint;
            return midpoint(a, b);
        }
    };

    template<typename T>
    struct arithmetic_midpoint
    {
        constexpr auto operator()(T const& a, T const& b) const
        {
            return default_midpoint{}.operator()<T>(a, b);
        }
    };

    // Median policies
    struct inplace_strategy
    {
        template<std::ranges::random_access_range Range,
                 std::invocable<std::ranges::range_value_t<Range>> Proj,
                 projected_strict_weak_order<Range, Proj> Comp,
                 midpoint_function<Range, Proj> Midpoint>
        auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
            -> median_result_t<Range, Proj, Midpoint>
            requires sortable_range<Range, Comp, Proj>
        {
            auto const size = std::ranges::distance(values);

            auto upper = std::ranges::begin(values) + size / 2;
            std::ranges::nth_element(values, upper, compare, proj);
            auto lower = size % 2 ? upper
                : std::ranges::max_element(std::ranges::begin(values), upper, compare, proj);
            return midpoint(std::invoke(proj, *lower), std::invoke(proj, *upper));
        }
    };

    struct inplace_strategy_rvalues_only
    {
        // Exists mainly to implement the default and frugal strategies
        // But could be useful if you need to disallow copy and external.
        template<std::ranges::random_access_range Range,
                 std::invocable<std::ranges::range_value_t<Range>> Proj,
                 projected_strict_weak_order<Range, Proj> Comp,
                 midpoint_function<Range, Proj> Midpoint>
        auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
            -> median_result_t<Range, Proj, Midpoint>
            requires sortable_range<Range, Comp, Proj> && (!std::is_lvalue_reference_v<Range>)
        {
            return inplace_strategy{}(std::forward<Range>(values), compare, proj, midpoint);
        }
    };

    struct copy_strategy
    {
        template<std::ranges::input_range Range,
                 std::invocable<std::ranges::range_value_t<Range>> Proj,
                 projected_strict_weak_order<Range, Proj> Comp,
                 midpoint_function<Range, Proj> Midpoint>
        auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
            -> median_result_t<Range, Proj, Midpoint>
            requires std::copyable<std::remove_reference_t<projected_t<Range, Proj>>>
        {
            auto projected = values | std::views::transform(proj);
            auto v = std::vector(std::ranges::begin(projected), std::ranges::end(projected));
            return inplace_strategy{}(v, compare, std::identity{}, midpoint);
         }
    };

    struct external_strategy
    {
        template<std::ranges::forward_range Range,
                 std::invocable<std::ranges::range_value_t<Range>> Proj,
                 projected_strict_weak_order<Range, Proj> Comp,
                 midpoint_function<Range, Proj> Midpoint>
        auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
            -> median_result_t<Range, Proj, Midpoint>
        {
            using pointer_type = std::add_pointer_t<const std::ranges::range_value_t<Range>>;
            using pointer_traits = std::pointer_traits<pointer_type>;
            auto indirect_project = [proj](auto *a)->decltype(auto) { return std::invoke(proj, *a); };

            auto pointers = values | std::views::transform(pointer_traits::pointer_to);
            auto v = std::vector(std::ranges::begin(pointers), std::ranges::end(pointers));
            return inplace_strategy{}(v, compare, indirect_project, midpoint);
         }
    };

    struct default_strategy
    {
        template<std::ranges::forward_range Range,
                 std::invocable<std::ranges::range_value_t<Range>> Proj,
                 projected_strict_weak_order<Range, Proj> Comp,
                 midpoint_function<Range, Proj> Midpoint>
        auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
            -> median_result_t<Range, Proj, Midpoint>
            requires std::invocable<inplace_strategy_rvalues_only, Range, Comp, Proj, Midpoint>
                  || std::invocable<copy_strategy, Range, Comp, Proj, Midpoint>
                  || std::invocable<external_strategy, Range, Comp, Proj, Midpoint>
        {
            if constexpr (std::invocable<inplace_strategy_rvalues_only, Range, Comp, Proj, Midpoint>) {
                return inplace_strategy_rvalues_only{}(std::forward<Range>(values), compare, proj, midpoint);
            }
            if constexpr (std::invocable<copy_strategy, Range, Comp, Proj, Midpoint>) {
                try {
                    return copy_strategy{}(std::forward<Range>(values), compare, proj, midpoint);
                } catch (std::bad_alloc&) {
                    if constexpr (!std::invocable<external_strategy, Range, Comp, Proj, Midpoint>) {
                        throw;
                    }
                    if constexpr (sizeof (projected_t<Range, Proj>*) >= sizeof (projected_t<Range, Proj>)) {
                        // external strategy won't help
                        throw;
                    }
                    // Else, we can try using external strategy more cheaply,
                    // so fallthrough to try that.
                }
            }
            if constexpr (std::invocable<external_strategy, Range, Comp, Proj, Midpoint>) {
                return external_strategy{}(std::forward<Range>(values), compare, proj, midpoint);
            }
        }
    };

    struct frugal_strategy
    {
        template<std::ranges::forward_range Range,
                 std::invocable<std::ranges::range_value_t<Range>> Proj,
                 projected_strict_weak_order<Range, Proj> Comp,
                 midpoint_function<Range, Proj> Midpoint>
        auto operator()(Range&& values, Comp compare, Proj proj, Midpoint midpoint) const
            -> median_result_t<Range, Proj, Midpoint>
            requires std::invocable<inplace_strategy_rvalues_only, Range, Comp, Proj, Midpoint>
                  || std::invocable<copy_strategy, Range, Comp, Proj, Midpoint>
                  || std::invocable<external_strategy, Range, Comp, Proj, Midpoint>
        {
            if constexpr (std::invocable<inplace_strategy_rvalues_only, Range, Comp, Proj, Midpoint>) {
                return inplace_strategy_rvalues_only{}(std::forward<Range>(values), compare, proj, midpoint);
            }
            if constexpr (std::invocable<external_strategy, Range, Comp, Proj, Midpoint>) {
                return external_strategy{}(std::forward<Range>(values), compare, proj, midpoint);
            }
            if constexpr (std::invocable<copy_strategy, Range, Comp, Proj, Midpoint>) {
                return copy_strategy{}(std::forward<Range>(values), compare, proj, midpoint);
            }
        }
    };

    // The median calculator type
    template<typename Proj, typename Comp, typename Midpoint, typename Strategy>
    class median_engine
    {
        const Strategy strategy;
        const Comp compare;
        const Proj projection;
        const Midpoint midpoint;

    public:
        // For simple construction, start with stats::median and use
        // the builder interface to customise it.
        constexpr median_engine(Proj projection, Comp comparer,
                                Midpoint midpoint, Strategy strategy) noexcept
            : strategy{std::move(strategy)},
              compare{std::move(comparer)},
              projection{std::move(projection)},
              midpoint{std::move(midpoint)}
        {}

        // Builder interface
        template<typename P>
        constexpr auto using_projection(P projection) const {
            return median_engine<P, Comp, Midpoint, Strategy>
                (std::move(projection), compare, midpoint, strategy);
        }

        template<typename C>
        constexpr auto using_compare(C compare) const {
            return median_engine<Proj, C, Midpoint, Strategy>
                (projection, std::move(compare), midpoint, strategy);
        }

        template<typename M>
        constexpr auto using_midpoint(M midpoint) const {
            return median_engine<Proj, Comp, M, Strategy>
                (projection, compare, std::move(midpoint), strategy);
        }
        template<typename T = double>
        constexpr auto using_arithmetic_midpoint() const {
            return using_midpoint(arithmetic_midpoint<T>{});
        }

        template<median_strategy S>
        constexpr auto using_strategy(S strategy) const
        {
            return median_engine<Proj, Comp, Midpoint, S>
                (projection, compare, midpoint, std::move(strategy));
        }
        constexpr auto using_external_strategy() const { return using_strategy(external_strategy{}); }
        constexpr auto using_inplace_strategy() const { return using_strategy(inplace_strategy{}); }
        constexpr auto using_copy_strategy() const { return using_strategy(copy_strategy{}); }
        constexpr auto using_frugal_strategy() const { return using_strategy(frugal_strategy{}); }
        constexpr auto using_default_strategy() const { return using_strategy(default_strategy{}); }

        // Main function interface:
        // Compute the median of a range of values
        template<std::ranges::forward_range Range>
        auto operator()(Range&& values) const
            requires std::invocable<Strategy, Range, Comp, Proj, Midpoint>
        {
            return calculate_median(std::forward<Range>(values));
        }

        // Overload for const filter views which are not standard ranges.
        // Some standard views (chunk_by_view, drop_while_view, filter_view, split_view) are not
        // const-iterable, due to time complexity requirements on begin() requiring it to remember
        // its result.  See https://stackoverflow.com/q/67667318
        template<typename View>
        auto operator()(View&& values) const
            requires (!std::ranges::range<View>)
            && std::ranges::range<std::decay_t<View>>
        {
            // Make a copy - which is a range
            auto values_copy = values;
            // but pass it as an lvalue ref so we don't order in-place by default
            return calculate_median(values_copy);
        }

    private:
        template<std::ranges::forward_range Range>
        auto calculate_median(Range&& values) const
            requires std::invocable<Strategy, Range, Comp, Proj, Midpoint>
        {
            auto const begin = std::ranges::begin(values);
            auto const size = std::ranges::distance(values);

            switch (size) {
            case 0:
                throw std::invalid_argument("Attempting median of empty range");
            case 1:
                {
                    auto const& a = project(begin);
                    return midpoint(a, a);
                }
            case 2:
                {
                    auto const& a = project(begin);
                    auto const& b = project(std::next(begin));
                    if (compare(a, b)) {
                        // Yes, the order matters!
                        // e.g. std::midpoint rounds towards its first argument.
                        return midpoint(a, b);
                    } else {
                        return midpoint(b, a);
                    }
                }
            }

            // If the range contains NaN values, there is no meaningful median.
            // We still need to launder through mipoint() for correct return type.
            using value_type = std::ranges::range_value_t<Range>;
            if constexpr (std::is_floating_point_v<std::remove_reference_t<value_type>>) {
                auto isnan = [](value_type d){ return std::isnan(d); };
                if (auto it = std::ranges::find_if(values, isnan, projection); it != std::ranges::end(values)) {
                    return midpoint(project(it), project(it));
                }
            }

            // If already ordered, just access the middle elements
            if (std::ranges::is_sorted(values, compare, projection)) {
                auto const lower = std::next(std::ranges::begin(values), (size - 1) / 2);
                auto const upper = size % 2 ? lower : std::next(lower);
                return midpoint(project(lower), project(upper));
            }

            // else use selected strategy
            return strategy(std::forward<Range>(values), compare, projection, midpoint);
        }

        auto project(std::indirectly_readable auto p) const -> decltype(auto)
        {
            return std::invoke(projection, *p);
        }
    };

    // We can put a median engine at the end of an adaptor chain
    // e.g.   auto midval = view | filter | median;
    template<typename InputRange, typename... MedianArgs>
    auto operator|(InputRange&& range, median_engine<MedianArgs...> engine)
    {
        return std::forward<median_engine<MedianArgs...>>(engine)(std::forward<InputRange>(range));
    }

    // Default engine, from which we can obtain customised ones using the builder interface.
    static constexpr auto median = median_engine
        {
            std::identity{},
            std::less<>{},
            default_midpoint{},
            default_strategy{}
        };
}

#include <gtest/gtest.h>
#include <array>
#include <forward_list>
#include <stdexcept>
#include <vector>

namespace test
{
    struct moveonly_int
    {
        int value;

        moveonly_int(int i) : value{i} {}
        moveonly_int(const moveonly_int&) = delete;
        moveonly_int(moveonly_int&&) = default;
        void operator=(const moveonly_int&) = delete;
        moveonly_int& operator=(moveonly_int&&) = default;

        bool operator<(const moveonly_int& other) const
        { return value < other.value; }
    };

    // specific midpoint for this type, to be found by ADL
    double midpoint(const moveonly_int& a, const moveonly_int& b)
    {
        return b.value - a.value; // the name is a lie
    }

    struct nocopy_int
    {
        int value;

        nocopy_int(int i) : value{i} {}
        nocopy_int(const nocopy_int&) = delete;
        void operator=(const nocopy_int&) = delete;

        bool operator<(const nocopy_int& other) const
        { return value < other.value; }
    };

    // specific midpoint for this type, to be found by ADL
    double midpoint(const nocopy_int& a, const nocopy_int& b)
    {
        return a.value + b.value; // the name is a lie
    }

    template<typename T>
    struct expect_midpoint {
        const T expected_a;
        const T expected_b;
        void operator()(T const& actual_a, T const& actual_b) const
        {
            EXPECT_EQ(expected_a, actual_a);
            EXPECT_EQ(expected_b, actual_b);
        }
    };

    struct dummy_midpoint
    {
        auto operator()(auto&&, auto&&) const {}
    };

    struct invalid_strategy
    {
        template<std::ranges::forward_range Range,
                 typename Comp,
                 typename Proj,
                 typename Midpoint>
        auto operator()(Range&&, Comp, Proj, Midpoint) const
            -> stats::median_result_t<Range, Proj, Midpoint>
        {
            throw std::logic_error("should not be called");
        }
    };

}

// C++20 version of detection idiom
template<typename Func, typename... Args>
constexpr bool can_call(Func&&, Args&&...)
    requires std::invocable<Func, Args...>
{ return true; }

template<typename... Args>
constexpr bool can_call(Args&&...)
{ return false; }

template<typename Strategy, typename Range>
concept strategy_accepts_type =
    std::invocable<Strategy, Range, std::less<>, std::identity, test::dummy_midpoint>;

enum strategy_mask : unsigned {
    sm_inplace        = 0x01,
    sm_inplace_rvalue = 0x02,
    sm_copy           = 0x04,
    sm_external       = 0x08,
    sm_default        = 0x10,
    sm_frugal         = 0x20,

    sm_none =  0u,
    sm_all  = ~0u,
};

constexpr auto operator+(strategy_mask a, strategy_mask b)
{ return static_cast<strategy_mask>(static_cast<unsigned>(a) | static_cast<unsigned>(b)); }
constexpr auto operator-(strategy_mask a, strategy_mask b)
{ return static_cast<strategy_mask>(static_cast<unsigned>(a) & ~static_cast<unsigned>(b)); }
constexpr bool is_set(strategy_mask a, strategy_mask b)
{ return a & b; }

template<typename Range>
void expect_usable(strategy_mask m = 0)
{
    if (!is_set(m, sm_inplace)) {
        // if we can't inplace, then we certainly can't inplace-rvalue
        m = m - sm_inplace_rvalue;
    }
    EXPECT_EQ(is_set(m, sm_inplace), (strategy_accepts_type<stats::inplace_strategy, Range>));
    EXPECT_EQ(is_set(m, sm_inplace_rvalue), (strategy_accepts_type<stats::inplace_strategy_rvalues_only, Range>));
    EXPECT_EQ(is_set(m, sm_copy), (strategy_accepts_type<stats::copy_strategy, Range>));
    EXPECT_EQ(is_set(m, sm_external), (strategy_accepts_type<stats::external_strategy, Range>));
    EXPECT_EQ(is_set(m, sm_default), (strategy_accepts_type<stats::default_strategy, Range>));
    EXPECT_EQ(is_set(m, sm_frugal), (strategy_accepts_type<stats::frugal_strategy, Range>));
}

// Tests of callability
// (Could be static, but we get better diagnostics this way)

TEST(Strategies, Regular)
{
    using Range = std::vector<int>;
    {
        SCOPED_TRACE("pass by value\n");
        expect_usable<Range>(sm_all);
    }
    {
        SCOPED_TRACE("pass by ref\n");
        expect_usable<Range&>(sm_all - sm_inplace_rvalue);
    }
    {
        SCOPED_TRACE("pass by const ref\n");
        expect_usable<Range const&>(sm_all - sm_inplace);
    }
    {
        SCOPED_TRACE("pass by rvalue\n");
        expect_usable<Range&&>(sm_all);
    }
}

TEST(Strategies, MoveOnly)
{
    using Range = std::vector<test::moveonly_int>;
    // can't be copied
    {
        SCOPED_TRACE("pass by value\n");
        expect_usable<Range>(sm_all - sm_copy);
    }
    {
        SCOPED_TRACE("pass by ref\n");
        expect_usable<Range&>(sm_all - sm_copy - sm_inplace_rvalue);
    }
    {
        SCOPED_TRACE("pass by const ref\n");
        expect_usable<Range const&>(sm_external + sm_default + sm_frugal);
    }
    {
        SCOPED_TRACE("pass by rvalue\n");
        expect_usable<Range&&>(sm_all - sm_copy);
    }
}

TEST(Strategies, NoCopy)
{
    using Range = std::vector<test::nocopy_int>;
    {
        SCOPED_TRACE("pass by value\n");
        expect_usable<Range>(sm_all - sm_inplace - sm_copy);
    }
    {
        SCOPED_TRACE("pass by ref\n");
        expect_usable<Range&>(sm_all - sm_inplace - sm_copy);
    }
    {
        SCOPED_TRACE("pass by const ref\n");
        expect_usable<Range const&>(sm_all - sm_inplace - sm_copy);
    }
    {
        SCOPED_TRACE("pass by rvalue\n");
        expect_usable<Range&&>(sm_all - sm_inplace - sm_copy);
    }
}

TEST(Strategies, ForwardOnly)
{
    using Range = std::forward_list<int>;
    {
        SCOPED_TRACE("pass by value\n");
        expect_usable<Range>(sm_all - sm_inplace);
    }
    {
        SCOPED_TRACE("pass by ref\n");
        expect_usable<Range&>(sm_all - sm_inplace);
    }
    {
        SCOPED_TRACE("pass by const ref\n");
        expect_usable<Range const&>(sm_all - sm_inplace);
    }
    {
        SCOPED_TRACE("pass by rvalue\n");
        expect_usable<Range&&>(sm_all - sm_inplace);
    }
}

TEST(Strategies, FilteredView)
{
    using View = std::ranges::filter_view<std::ranges::ref_view<int[1]>, std::function<bool(int)>>;
    {
        SCOPED_TRACE("pass by value\n");
        expect_usable<View>(sm_all - sm_inplace);
    }
    {
        SCOPED_TRACE("pass by ref\n");
        expect_usable<View&>(sm_all - sm_inplace);
    }
    {
        SCOPED_TRACE("pass by const ref\n");
        // const view isn't a range - needs median_engine to copy it
        expect_usable<View const&>(sm_none);
    }
    {
        SCOPED_TRACE("pass by rvalue\n");
        expect_usable<View&&>(sm_all - sm_inplace);
    }
}


// Don't even try compiling the rest unless earlier tests succeed!
#ifndef TYPE_TESTS_FAILED

// Use this one for tests where the engine should not call out to strategy.
// I.e. when input is ordered, or there's only 1 or 2 elements.
template<std::ranges::forward_range Container = std::vector<int>,
         typename Midpoint = test::expect_midpoint<std::ranges::range_value_t<Container>>,
         typename Comp = std::less<>, typename Proj = std::identity>
static void test_values_trivial(Container&& values, Midpoint expected,
                                Comp compare = {}, Proj projection = {})
{
    stats::median
        .using_compare(compare)
        .using_projection(projection)
        .using_midpoint(expected)
        .using_strategy(test::invalid_strategy{}) // will fail if called
        (std::forward<Container>(values));
}

template<std::ranges::forward_range Container = std::vector<int>,
         typename Midpoint = test::expect_midpoint<std::ranges::range_value_t<Container>>,
         typename Comp = std::less<>, typename Proj = std::identity>
static void test_values_const_input(const Container& values, Midpoint expected,
                                    Comp compare = {}, Proj projection = {})
{
    auto const m = stats::median
        .using_compare(compare)
        .using_projection(projection)
        .using_midpoint(expected);

    {
        SCOPED_TRACE("default strategy");
        m(values);
    }
    {
        SCOPED_TRACE("copy strategy");
        m.using_copy_strategy()(values);
    }
    {
        SCOPED_TRACE("external strategy");
        m.using_external_strategy()(values);
    }
}

template<std::ranges::forward_range Container = std::vector<int>,
         typename Midpoint = test::expect_midpoint<std::ranges::range_value_t<Container>>,
         typename Comp = std::less<>, typename Proj = std::identity>
static void test_values(Container&& values, Midpoint expected,
                        Comp compare = {}, Proj projection = {})
{
    test_values_const_input(values, expected, compare, projection);

    auto const m = stats::median
        .using_compare(compare)
        .using_projection(projection)
        .using_midpoint(expected);

    SCOPED_TRACE("inplace strategy");
    m.using_inplace_strategy()(std::move(values));
}


TEST(Median, Empty)
{
    EXPECT_THROW(stats::median(std::vector<int>{}), std::invalid_argument);
}

TEST(Median, OneElement)
{
    SCOPED_TRACE("from here\n");
    test_values_trivial({100}, {100, 100});
}

TEST(Median, TwoElements)
{
    SCOPED_TRACE("from here\n");
    test_values_trivial({100, 200}, {100, 200});
    SCOPED_TRACE("from here\n");
    test_values_trivial({200, 100}, {100, 200});
}

TEST(Median, ThreeSortedElements)
{
    SCOPED_TRACE("from here\n");
    test_values_trivial({1, 2, 3}, {2, 2});
}

TEST(Median, ThreeElements)
{
    SCOPED_TRACE("from here\n");
    test_values({1, 3, 2}, {2, 2});
}

TEST(Median, FourSortedElements)
{
    SCOPED_TRACE("from here\n");
    test_values_trivial({2, 4, 6, 8}, {4, 6});
    SCOPED_TRACE("from here\n");
    test_values_trivial({4, 4, 4, 6}, {4, 4});
}

TEST(Median, FourElements)
{
    SCOPED_TRACE("from here\n");
    test_values({8, 2, 6, 4}, {4, 6});
    SCOPED_TRACE("from here\n");
    test_values({4, 4, 6, 4}, {4, 4});
}

TEST(Median, FiveElements)
{
    SCOPED_TRACE("from here\n");
    test_values({8, 2, 6, 4, 0}, {4, 4});
}


TEST(Median, PlainArray)
{
    int values[] = { 2, 1, 3};
    test_values(values, {2, 2});
}

TEST(Median, ConstPlainArray)
{
    const int values[] = { 2, 1, 3};
    test_values_const_input(values, {2, 2});
    // Also exercise the range-adaptor style
    EXPECT_EQ(values | stats::median, 2);
}

TEST(Median, Strings)
{
    SCOPED_TRACE("from here\n");
    std::string_view values[] = { "one", "two", "three", "four", "five", "six" };
    // Alphabetical:  five four ONE SIX three two
    test_values(values, test::expect_midpoint<std::string_view>{"one", "six"});
}


TEST(Median, NaNsFirst)
{
    constexpr auto nan = std::numeric_limits<double>::quiet_NaN();
    double values[] = { nan, nan, 1, 1, 100, 100, 10 };
    EXPECT_TRUE(std::isnan(stats::median(values)));
}

TEST(Median, NaNsLast)
{
    constexpr auto nan = std::numeric_limits<double>::quiet_NaN();
    double values[] = { 1, 1, 100, 100, 10, nan, nan };
    EXPECT_TRUE(std::isnan(stats::median(values)));
}

TEST(Median, Infinities)
{
    constexpr auto inf = std::numeric_limits<double>::infinity();
    std::vector<double> values;
    values = { -inf, inf, -inf };
    EXPECT_EQ(stats::median(values), -inf);
    values = { inf, -inf, inf };
    EXPECT_EQ(stats::median(values), inf);
    values = { inf, -inf, inf, -inf };
    EXPECT_TRUE(std::isnan(stats::median(values))); // midpoint of ±∞
}


TEST(Median, CustomOrder)
{
    auto const values = std::array{20, 91, 92, 54, 63};
    // order by last digit:  0, 1, 2, 4, 3
    auto const compare = [](int a, int b){ return a % 10 < b % 10; };
    EXPECT_EQ(stats::median.using_compare(compare)(values), 92);
}

TEST(Median, CustomProjection)
{
    auto const values = std::array{20, 91, 92, 54, 63};
    // project to last digit:  0, 1, 2, 4, 3
    auto const projection = [](int a){ return a % 10; };
    EXPECT_EQ(stats::median.using_projection(projection)(values), 2);
}

TEST(Median, Value)
{
    auto const values = std::forward_list{0, 1, 2, 3};

    EXPECT_EQ(stats::median(values), 1); // rounded down
    EXPECT_EQ(stats::median.using_arithmetic_midpoint()(values), 1.5);

    // And with reverse order (causing integer std::midpoint() to round upwards)
    auto m = stats::median.using_compare(std::greater<int>{});
    EXPECT_EQ(m(values), 2);
    EXPECT_EQ(m.using_arithmetic_midpoint<long double>()(values), 1.5L);
}

TEST(Median, MoveOnly)
{
    // finds test::midpoint (which returns the difference!)
    std::array<test::moveonly_int, 4> values{0, 3, 5, 2};
    EXPECT_FALSE(can_call(stats::median.using_copy_strategy(), values));
    EXPECT_EQ(stats::median(values), 1); // 3 - 2
    EXPECT_EQ(stats::median.using_inplace_strategy()(values), 1);
}

TEST(Median, NoCopy)
{
    // finds test::midpoint (which returns the sum!)
    std::array<test::nocopy_int, 4> values{0, 1, 4, 2};
    EXPECT_FALSE(can_call(stats::median.using_inplace_strategy(), values));
    EXPECT_FALSE(can_call(stats::median.using_copy_strategy(), values));
    EXPECT_EQ(stats::median.using_external_strategy()(values), 3); // 1 + 2
    EXPECT_EQ(stats::median(std::move(values)), 3);
}

TEST(Median, ProjectByValue)
{
    auto twice = [](auto x) { return 2 * x; };
    constexpr auto m = stats::median.using_projection(twice);
    int values[] = {0, 1, 3, 4, 2};
    EXPECT_EQ(m.using_copy_strategy()(values), 4);
    EXPECT_EQ(m.using_external_strategy()(values), 4);
    EXPECT_EQ(m.using_inplace_strategy()(values), 4);
}

TEST(Median, FilteredRange)
{
    constexpr auto nan = std::numeric_limits<double>::quiet_NaN();

    double values[] = { nan, nan, 1, 100, 10 };
    auto view = values | std::views::filter([](double d){ return !std::isnan(d); });

    EXPECT_EQ(stats::median.using_copy_strategy()(view), 10);
    EXPECT_EQ(stats::median.using_external_strategy()(view), 10);
    EXPECT_EQ(stats::median(view), 10);
    EXPECT_EQ(values[2], 1);    // shouldn't have modified underlying range
}

TEST(Median, FilteredRangeConst)
{
    constexpr auto nan = std::numeric_limits<double>::quiet_NaN();

    double values[] = { nan, nan, 1, 100, 10 };
    auto const view = values | std::views::filter([](double d){ return !std::isnan(d); });

    EXPECT_EQ(stats::median.using_copy_strategy()(view), 10);
    EXPECT_EQ(stats::median.using_external_strategy()(view), 10);
    EXPECT_EQ(stats::median(view), 10);
    EXPECT_EQ(values[2], 1);    // shouldn't have modified underlying range
}

#endif

更新后的代码现在是论GitHub；此版本对应于提交d6ac335。

Answer 1

这个看起来很防水。我只想说几句话：

可能有太多的限制？

您可以在模板参数列表中约束模板参数，但也可以使用requires-clause。像std::sortable这样的概念，或者您自己的助手sortable_range，已经可以检查Range是一个随机访问范围，并且可以使用Comp来比较Proj受影响的值。因此，这有点多余，您可以删除一些代码，使代码稍微更具可读性。

它还可能对错误消息的质量产生影响。看到“这组参数必须形成我可以排序的东西”而不是“这个比较器函数没有在这个范围内给我一个严格的弱顺序”可能会很好。但是，您必须检查来自不同编译器的输出，以检查实际效果。

Make indirect_project()接受const指针

虽然有点挑剔，但是投影操作不应该修改范围，所以最好让indirect_project采用const指针参数。

frugal_strategy可能不适合用于小值类型

考虑到我可能想要std::int8_ts向量的中值，那么copy_strategy比external_strategy更好，而frugal_strategy总是更喜欢后者。可能让它先检查大小，然后在投影值类型的大小等于或小于指针时更倾向于复制。

移动与复制median_engine

参数

构造median_engine std::move()s的所有参数。而构建器接口std::move()s只对每个构建器函数的单个参数进行复制，而复制相应的其他3个成员变量。您可以使median_engine的成员值非const，因此所有这些值都可以在构建器接口中移动。另一方面，你可以总是复制，假设它不太可能是昂贵的。

的std::is_sorted()

开销

虽然检查输入是否已经排序可能会大大加快事情的速度，如果范围确实是排序的话，但如果没有排序，则会增加开销。另外，考虑到对于本地策略，不检查它可能与检查它一样快，这取决于std::ranges::nth_element()的实现。对于复制和外部策略而言，也许在复制过程中检查排序是足够便宜的，可以始终这样做。