c++ - C++可变参数函数对参数进行原位排序

Question

在实现二进制搜索问题的变体时，我需要重新排列 slice 点(即开始，中间，结束)，以便将它们存储在相应的变量(例如(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的使用是一个任意决定。之所以这样做，是因为我不清楚哪种结构/容器最适合用于打包这些值。在我看来，结构的选择需要轻松地进行构造，分类和解包/转换为元组，而且我不确定是否存在这种神奇的结构。

为了使事情顺利进行，我不得不手动打包/解压缩参数。我还不清楚如何使用std::tie或具有可变数量(即编译时未知)元素的任何其他拆包/移动操作。

尽管没有特别的理由专门使用STL函数/结构，但我惊讶地发现没有一种直观的方法可以使用STL中提供的抽象来实现这一点。结果，我对使用STL之外的最少帮助实现目标更加感兴趣。

我开始了这个思想实验，期望最终得到语法正确的 std::move(std::sort({x,y,z}, comp), {x,y,z})版本，并考虑到到目前为止我的研究将我引向何处，我开始认为我使这个问题变得过于复杂了。任何帮助，见解或建议将不胜感激!

Answer 1

一种使用std::sort的可能的C++ 17解决方案，可以概括您的示例:

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，就可以确切知道最小的比较数)即可完成工作-请参见秒。 5.3 Knuth的TAOCP卷的最佳排序。 3。