在没有复制的情况下找到值的中值

Question

为了练习，我一直在玩计算中值的游戏。这一次，我希望在不复制输入值(可能是因为输入值很大，或者是类型不可复制)和重新排序容器的情况下，使其工作得很好。

我的实现分为两部分--找到中心值的迭代器(S)，并将这两个值结合起来。这允许高级用户在需要时以有趣的方式组合中心值(例如，从复合对象中提取字段)。但是简单的median::value()接口很容易使用，并且适用于任何带有midpoint()函数的类型(由ADL找到，或者返回到std::midpoint())。

用户可以重写用于中点的算术类型--当我们想要得到小数值而不是整数中点的四舍五入时，这是很有用的。

原理很简单--在迭代器的并行容器上进行外部部分排序，在需要时使用std::nth_element和std::max_element()。这种并行操作意味着我们可以在接受的类型上非常慷慨--我们只需要一个前向范围，而大多数实现都需要一个随机访问范围。

我将首先展示这些测试(使用GoogleTest框架)，因为它们展示了如何使用这些函数。为了简单起见，他们使用int容器，尽管复制值通常比迭代器更有效。

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

template<std::ranges::forward_range Container = std::vector<int>>
static void test_values(Container const& values, int first, int second)
{
    auto const its = median::iterators(values);
    EXPECT_EQ(*its.first, first);
    EXPECT_EQ(*its.second, second);
}

TEST(Median, Empty)
{
    EXPECT_THROW(median::iterators(std::array<bool,0>{}), std::domain_error);
}

TEST(Median, OneElement)
{
    SCOPED_TRACE("");
    test_values({100}, 100, 100);
}


TEST(Median, TwoElements)
{
    SCOPED_TRACE("");
    test_values({100, 200}, 100, 200);
    SCOPED_TRACE("");
    test_values({200, 100}, 100, 200);
}

TEST(Median, ThreeElements)
{
    SCOPED_TRACE("");
    test_values({1, 3, 2}, 2, 2);
}

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

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

TEST(Median, PlainArray)
{
    SCOPED_TRACE("");
    const int arr[] = { 2, 1, 3};
    test_values(arr, 2, 2);
}

TEST(Median, CustomSort)
{
    auto const values = std::array{20, 91, 92, 63, 54};
    // sort by last digit
    auto const compare = [](int a, int b){ return a % 10 < b % 10; };
    EXPECT_EQ(median::value(values, compare), 92);
}

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

    EXPECT_EQ(median::midval(iters), 1); // integer arithmetic
    EXPECT_EQ(median::midval<double>(iters), 1.5);

    // Same, but using convenience functions
    EXPECT_EQ(median::value(values), 1);
    EXPECT_EQ(median::value<double>(values), 1.5);

    // And with reverse sort (causing integer std::midpoint() to round upwards)
    EXPECT_EQ(median::value(values, std::greater<int>{}), 2);
    EXPECT_EQ(median::value<double>(values, std::greater<int>{}), 1.5);
}

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

    double midpoint(const moveonly_int& a, const moveonly_int& b)
    {
        double av = a.value;
        double bv = b.value;
        return std::midpoint(av, bv);
    }
}

TEST(Median, MoveOnly)
{
    std::array<test::moveonly_int, 4> values{0, 1, 2, 3};
    EXPECT_EQ(median::value(values), 1.5);
}

以下是实现：

#include <algorithm>
#include <concepts>
#include <functional>
#include <iterator>
#include <numeric>
#include <ranges>
#include <utility>
#include <vector>

namespace median {

    // Return a pair of iterators to the two median values
    // If the input is of even length, an identical pair is returned
    template<std::ranges::forward_range Range, typename Compare = std::less<>>
    auto iterators(const Range& values, Compare compare = {})
        -> std::pair<std::ranges::iterator_t<const Range>,
                     std::ranges::iterator_t<const Range>>
    {
        auto const begin = std::ranges::begin(values);
        auto const end = std::ranges::end(values);
        auto const size = std::distance(begin, end);

        switch (size) {
        case 0: throw std::domain_error("Attempting median of empty range");
        case 1: return {begin, begin};
        case 2:
            auto a = begin;
            auto b = a; ++b;
            if (!compare(*a, *b)) { std::swap(a, b); }
            return {a, b};
        }

        auto const it_cmp
            = [compare](auto a, auto b){ return compare(*a, *b); };
        std::vector<std::ranges::iterator_t<const Range>> iters;
        iters.reserve(size);
        for (auto it = begin;  it != end;  ++it) {
            iters.push_back(it);
        }
        auto upper = iters.begin() + size / 2;
        std::ranges::nth_element(iters, upper, it_cmp);
        auto lower = size % 2 ? upper
            : std::max_element(iters.begin(), upper, it_cmp);
        return {*lower, *upper};
    }

    auto midval(auto iter_pair)
        requires requires{ *iter_pair.first; *iter_pair.second; }
    {
        using std::midpoint;
        auto const [a, b] = iter_pair;
        return midpoint(*a, *b);
    }

    template<typename ArithType>
    auto midval(auto iter_pair)
        requires requires(ArithType v){ v = *iter_pair.first;
                                        v = *iter_pair.second; }
    {
        using std::midpoint;
        ArithType const a = *iter_pair.first;
        ArithType const b = *iter_pair.second;
        return midpoint(a, b);
    }

    template<typename ArithType>
    auto value(const auto& values)
    {
        return midval<ArithType>(iterators(values));
    }
    template<typename ArithType>
    auto value(const auto& values, auto compare)
    {
        return midval<ArithType>(iterators(values, compare));
    }
    auto value(const auto& values)
    {
        return midval(iterators(values));
    }
    auto value(const auto& values, auto compare)
    {
        return midval(iterators(values, compare));
    }
}

我已经编译了大量的警告，并运行了下面的测试，以消除任何愚蠢的悬空迭代器问题。

一些具体关切：

• 我有没有遗漏任何有用的测试？
• 我真的需要四个过载的median::value吗？我承认这两个midval()实现是不同的，因此它们是必要的。
• 抛出std::domain_error是否是对空输入的适当反应？
• 通过值传递compare是否是正确的选择？标准算法就是这样做的，我想我们可以使用std::reference_wrapper来覆盖它(如果我们正在收集执行统计数据)。
• 我是否错过了对模板类型的任何有用的约束？
• 任何值得注意的事情。

我从使用std::multiset (通过相同的测试套件)开始使用不同的实现，它只需要存储一半的迭代器(但我怀疑设置开销，以及在下半年每个元素设置三个O(log )设置操作的可能性，可能会分别抹掉任何空间和时间优势)。不管怎样(我们需要包括<cassert>和<set>，而不是<algorithm>和<vector>)。

        std::multiset<std::ranges::iterator_t<const Range>, decltype(it_cmp)>
            sorted(it_cmp);
        auto const halfway = begin + size/2 + 1u;
        for (auto it = begin;  it != halfway;  ++it) {
            sorted.insert(it);
        }
        for (auto it = halfway; it != end;  ++it) {
            auto last = sorted.end(); --last;
            if (it_cmp(it, *sorted.begin())) {
                // before first
                sorted.erase(last);
            } else if (it_cmp(it, *last)) {
                // before last
                sorted.erase(last);
                sorted.erase(sorted.begin());
                sorted.insert(it);
            } else {
                // after last
                sorted.erase(sorted.begin());
            }
        }
        // sorted contains one element for odd-length input, or two
        // elements for even-length input.
        assert(sorted.size() == 1u + !(size % 2));
        auto m = sorted.begin();
        auto n = sorted.end();
        return {*m, *--n};

虽然我没有使用这个版本，但请随时查看它--我一直在寻找学习的机会！

Answer 1

回答您的问题

• 我有没有遗漏任何有用的测试？

是。在测试空范围的边缘情况时，还需要测试其他边缘情况和极值。例如，{INT_MIN, INT_MAX}的中位数。另外，考虑具有正和/或负无穷大的东西的中值，以及一些随机散落在其中的数组的中值。

• 我真的需要四个过载中位数：：值吗？我承认，这两个midval()实现非常不同，因此它们是必要的。

通过让第一个模板使用比较器的默认值，您可以很容易地去掉一个模板：

template<typename ArithType, typename Compare = std::less<>>
auto value(const auto& values, Compare compare = {})
{
    return midval<ArithType>(iterators(values, compare));
}

如果可以为ArithType提供默认值，则不需要未模板的重载。但是，你不能这样做，除非你使用这样的黑客：

template<typename ArithType = void, typename Compare = std::less<>>
auto value(const auto& values, Compare compare = std::less<>{})
{
    if constexpr (std::is_same_v<ArithType, void>)
        return midval(iterators(values, compare));
     else
        return midval<ArithType>(iterators(values, compare));
}

• 抛出std::domain_error是否是对空输入的适当反应？

我会允许这样做的，尽管也有人可能会认为std::invalid_argument更合适。

• 通过比较值是正确的选择吗？标准算法就是这样做的，我想我们可以使用std::reference_wrapper来覆盖它(如果我们正在收集执行统计数据)。

我会复制STL的语义。

• 我是否错过了对模板类型的任何有用的约束？

是。我需要范围和比较器的值类型满足std::strict_weak_order概念。基本上，这确保了您可以对值进行排序。

您还可以定义一个检查是否可以应用midpoint()的概念，这样尝试获取std::strings数组的中值将产生更好的错误消息，但另一方面，一些人可能会认为这是一个过于具体的概念。理想情况下，std::is_arithmetic是一个很好的选择，但它只允许内置类型。

• 任何值得注意的事情。

见下文。

排序迭代器可能比复制范围

更昂贵

对迭代器的std::vector进行排序可能要比将值本身复制到一个新的std::vector中要昂贵得多，尤其是如果您只想要ints、floats或double can的中值。某些容器的迭代器类型可能相当大，因此您需要支付额外的间接费用。另一方面，即使输入是不可复制和不可移动类型的容器，或者值类型本身非常大(例如，undefined)，您的解决方案也工作得很好。

考虑添加投影参数

如果自定义midpoint()函数有效，则使用ADL函数可以工作。但是考虑一下，我想要得到std::complex<double>数的中位数，并根据它们的绝对值排序。使用代码的唯一方法是将std::midpoint()的过载注入到namespace std中，这不是很好。使用投影参数可以避免此问题。