如何在C++中优雅实现支持多容器的通用原地排序

一、解决pointer to reference is illegal编译错误 #

这个错误的根源是decltype(*std::begin(data))返回的是元素的左值引用类型（比如对std::vector<int>来说，返回int&），而C++不允许声明指向引用的指针，因此inner_type*会触发编译错误。

修正方法很简单，用类型萃取工具去掉引用属性：

• 方法1：用std::remove_reference_t直接剥离引用

  #include <type_traits>
  #include <iterator>
  
  template<typename T>
  void mergesort(T& data)
  {
      // 去掉引用，得到元素的实际类型
      using inner_type = std::remove_reference_t<decltype(*std::begin(data))>;
      // 用std::vector代替手动new，避免内存泄漏
      std::vector<inner_type> scratch(std::size(data));
      // 后续归并分治逻辑...
  }
  

• 方法2：用std::iterator_traits获取迭代器的value_type，这是更标准的容器元素类型获取方式

  template<typename T>
  void mergesort(T& data)
  {
      using iter_type = decltype(std::begin(data));
      using inner_type = typename std::iterator_traits<iter_type>::value_type;
      std::vector<inner_type> scratch(std::size(data));
      // 后续逻辑...
  }
  

二、C++中实现类似C#的模板约束 #

C没有C#那样的where关键字，但可以通过**C20概念(Concepts)** 或SFINAE（C++20之前） 来约束模板参数，确保传入的容器满足可索引、元素可比较的要求：

1. C++20 概念（推荐） #

用概念清晰定义容器需要满足的条件：

#include <concepts>
#include <iterator>

// 定义概念：可索引、可获取大小、元素可全序比较且可交换
template<typename T>
concept IndexableComparableContainer = requires(T& cont, std::size_t idx) {
    // 支持operator[]，返回元素引用
    { cont[idx] } -> std::convertible_to<typename std::iterator_traits<decltype(std::begin(cont))>::value_type&>;
    // 支持std::size获取容器大小
    { std::size(cont) } -> std::convertible_to<std::size_t>;
    // 元素支持全序比较（<, >, ==等）
    requires std::totally_ordered<typename std::iterator_traits<decltype(std::begin(cont))>::value_type>;
    // 元素可交换（排序必备）
    requires std::swappable<typename std::iterator_traits<decltype(std::begin(cont))>::value_type>;
};

// 仅接受符合概念的容器
template<IndexableComparableContainer T>
void mergesort(T& data)
{
    using inner_type = typename std::iterator_traits<decltype(std::begin(data))>::value_type;
    std::vector<inner_type> scratch(std::size(data));
    // 分治与归并逻辑实现...
}

2. C++20之前的SFINAE方式 #

通过std::enable_if和类型特性来过滤不符合要求的模板参数：

#include <type_traits>
#include <iterator>

template<typename T>
auto mergesort(T& data) -> typename std::enable_if_t<
    // 检查是否支持operator[]
    std::is_invocable_r_v<typename std::iterator_traits<decltype(std::begin(data))>::value_type&, decltype(&T::operator[]), T&, std::size_t>,
    void
>
{
    using inner_type = typename std::iterator_traits<decltype(std::begin(data))>::value_type;
    // 静态断言元素必须可比较、可交换
    static_assert(std::totally_ordered<inner_type>, "Elements must support full comparison operations");
    static_assert(std::swappable<inner_type>, "Elements must be swappable");
    
    std::vector<inner_type> scratch(std::size(data));
    // 分治与归并逻辑实现...
}

三、原地归并排序的实现提示 #

虽然你要求“原地排序”，但归并排序的核心归并步骤通常需要临时空间来暂存数据（完全原地的归并排序复杂度高，实际场景很少用），这里用std::vector作为临时空间比手动new[]更安全，无需手动管理内存。

实现时要基于索引操作：

• 分治函数接收容器、左边界索引、右边界索引
• 归并时将左右子数组的元素暂存到临时vector，再按顺序拷贝回原容器的对应位置

内容的提问来源于stack exchange，提问作者Jordi Vermeulen