c++ - 递归排序 vector 的最简单方法？

Question

这将对 vector 内的 vector 进行排序:

std::vector<
    std::vector<int>
> my_vector {
    { 1, 3, 2 },
    { 52, 10, 20 },
    { 30, 2, 3 }
};
std::for_each(my_vector.begin(), my_vector.end(), [] (std::vector<int>& v)
    {
        std::sort(v.begin(), v.end());
    });

它实际上并不对最外层 vector 的元素进行排序，因此它不是“递归”排序。递归排序将对所有 vector 进行排序，包括最外层的 vector 。例如，prettyprint.hpp将递归打印容器。我不需要遍历每个容器的所有元素，就像 prettyprinter 那样，只需要遍历范围。

这是我目前的尝试:

template <typename T>
void my_sort(std::vector<T>& v)
{
    std::sort(v.begin(), v.end());
    std::for_each(v.begin(), v.end(), 
        [] (T& vv)
        {
            my_sort(vv);
        });
}

这不起作用，因为当 T = int 时，它会尝试使用 int 调用 my_sort。有什么建议吗？

输出应该是这样的:

[[1, 2, 3], [2, 3, 30], [10, 20, 52]]^--- outermost vector ^---- inner vector

Answer 1

首先，您应该先递归，然后才对外部范围进行排序。否则你会得到一些随机的结果，因为内部容器没有任何规范的顺序。更糟糕的是，后面的排序会改变元素的顺序，导致外部 vector 明显乱序。似乎您想拥有 my_sort() 的条件版本取决于类型 T定义一个关联的 iterator类型。由于您只使用 std::vector<T>不过，更简单的方法是简单地依赖模板的部分排序:

template <typename T>
void my_sort(T const&) {
    // this function delibarately does nothing
}
template <typename T>
void my_sort(std::vector<T>& v) {
    std::for_each(v.begin(), v.end(), [](T& value) { my_sort(value); });
    std:sort(v.begin(), v.end());
}

顺便说一句，因为这个函数实际上从不调用自身，无论是直接还是间接，它实际上并不是一个真正的递归函数:函数模板的每个实例都是一个不同的函数。