C++ 可变参数函数就地对参数进行排序

Question

在实现二进制搜索问题的变体时，我需要重新排序切片点（即开始、中间、结束），以便将它们存储在相应的变量中（例如 (1,5,2) -> (1,2,5)）。这对于一些 if statements 和 swaps 来说相当简单。然而，作为一个思想实验，我现在有兴趣将其推广到 n 许多 T 类型变量。我开始尝试一些直观的解决方案，作为起点，我想到了这个模板函数：

template<typename T>
void 
sortInPlace(
    std::function<bool (const T&, const T&)> compareFunc,
    T& start, 
    T& mid, 
    T& end)
    {
        std::vector<T> packed {start, mid, end};
        std::sort(packed.begin(), packed.end(), compareFunc);
        auto packedAsTuple = make_tuple(packed[0], packed[1], packed[2]);
        std::tie(start, mid, end) = packedAsTuple;
    }

当我运行以下时，使用 typedef std::pair<int,int> Pivot:

//Comparison function to sort by pair.first, ascending:
std::function<bool(const Pivot&, const Pivot&)>
  comp =[](const Pivot & a, const Pivot & b) {
     return std::get < 0 > (a) < std::get < 0 > (b);
  };

int main(){
    Pivot a(8,1);
    Pivot b(2,3);
    Pivot c(4,6);

    sortInPlace(comp,a,b,c);
}

事实证明这是按预期工作的：

a after sort: 2, 3
b after sort: 4, 6
c after sort: 8, 1

理想情况下，接下来的步骤是将此模板转换为可变参数模板，但我在实现这一点时遇到了麻烦。关于当前版本，我还有一些困扰我的事情：

std::vector 的使用是一个武断的决定。我这样做是因为我不清楚什么 structure/container 最适合用于打包这些值。在我看来，结构的选择需要构造、排序和 unpacked/converted 到元组很容易，我不确定是否有这样一个神奇的结构。
为了让事情顺利进行，我不得不手动解决 packing/unpacking 参数。我也不清楚如何使用 std::tie 或任何其他 unpacking/moving 具有可变数量（即编译时未知）元素的操作。
虽然没有特别的理由专门使用 stl functions/structures，但我很惊讶地发现没有直观的方法可以使用 stl 中提供的抽象来实现这一点。因此，我更感兴趣的是在 stl 之外使用最少的帮助来实现我的目标。

我开始了这个思想实验，希望最终得到一个句法正确的 std::move(std::sort({x,y,z}, comp), {x,y,z}) 版本，考虑到我的研究到目前为止把我带到了什么地方，我开始认为我过于复杂了这个问题。非常感谢任何帮助、见解或建议！

Answer 1

一种可能的 C++17 解决方案 std::sort 概括了您的示例：

template<class Comp, class... Ts>
void my_sort(Comp comp, Ts&... values) {
    using T = std::common_type_t<Ts...>;
    T vals[]{std::move(values)...};

    std::sort(std::begin(vals), std::end(vals), comp);

    auto it = std::begin(vals);
    ((values = std::move(*it++)), ...);
}

using Pivot = std::pair<int, int>;

const auto comp = [](Pivot a, Pivot b) {
    return std::get<0>(a) < std::get<0>(b);
};

Pivot a(8, 1);
Pivot b(2, 3);
Pivot c(4, 6);

my_sort(comp, a, b, c);

如果包中的参数数量N 很少，则根本不需要std::sort。只需一系列（硬编码）比较（对于小 N，最小比较次数是确切已知的）就可以完成这项工作 - 请参阅 sec。 5.3 Knuth 的 TAOCP 卷的最佳排序。 3.

C++ 可变参数函数就地对参数进行排序

C++ Variadic Function To Sort Arguments In-place

c++

sorting

variadic

in-place