c++ - std::stable_sort:如何选择内存优化算法而不是时间优化算法？

Question

我希望使用 std::stable_sort。算法的复杂度表示为

O(N·log^2(N)), where N = std::distance(first, last) applications of cmp. If additional memory is available, then the complexity is O(N·log(N)). http://en.cppreference.com/w/cpp/algorithm/stable_sort

在我的应用程序中，内存至关重要，因此，我更喜欢 std::stable_sort 使用内存优化的 O(N·log^2(N))算法，而不是时间优化的 O(N·log(N)) 算法。我了解只有在安全的情况下才会选择时间优化版本这样做(可用内存)。但是，我的目标是对我的应用程序进行基准测试，因此，由于内存至关重要，因此希望在内存消耗最低时对算法进行基准测试。由于我的系统目前有足够的内存来分配缓冲区，它会自动选择 std::stable_sort 的 O(N·log^2(N)) 版本。因此，我想向 std::stable_sort 断言采用内存优化版本。这可能吗？

执行策略出现是可以修改算法的参数，但是，它似乎只改变并行的程度。 http://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t

虽然选择了并行或顺序版本实际上可能选择 O(N·log(N)) 或O(N·log^2(N)) 个版本，网页上没有说明。

我想知道是否有人有任何主张这种选择的经验。如果是这样他们能提供任何建议吗？

Answer 1

您可以查看您的 header ，看看如果额外的缓冲区不可用，则调用哪个函数。对我来说 gcc 是

    std::__inplace_stable_sort(__first, __last, __comp);

这当然不符合标准。 __inplace_stable_sort 是一个辅助函数，不能直接使用。

std::stable_sort 对该函数的调用是以下代码的结果

typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
  _TmpBuf __buf(__first, __last);

  if (__buf.begin() == 0)
std::__inplace_stable_sort(__first, __last, __comp);
  else
std::__stable_sort_adaptive(__first, __last, __buf.begin(),
                _DistanceType(__buf.size()), __comp);