std::sort函数隐藏着BUG，不知道能安心刷题吗

导读：刷题经常用的std::sort函数的比较器隐藏着一个bug，不小心就容易导致coredump。

今天来聊聊STL中一个隐藏BUG的函数： std::sort。

前言

这个问题呢，实际上是来自于交流群小伙伴@Tgive在刷leetcode-56时发现的（完整的代码见附录），最终定位到是std::sort函数的第三个参数写错了，即比较器Compartor写的不对：

Compartor将==判断为true则无法通过；更改为false，能accept。

std::sort部分的代码如下所示：区别仅仅在于lhs[0] == rhs[0]时返回的是false还是true：

std::vector<std::vector<int>>& intervals;

// 未通过版本
std::sort(intervals.begin(), intervals.end(),
          [](const std::vector<int> &lhs, const std::vector<int> &rhs)
          {
            return lhs.at(0) <= rhs.at(0);    // lhs[0] == rhs[0]，返回 true
          });

// 通过版本
std::sort(intervals.begin(), intervals.end(),
          [](const std::vector<int> &lhs, const std::vector<int> &rhs)
          {
            return lhs.at(0) < rhs.at(0);    // lhs[0] == rhs[0]，返回 false
          });

我把这个同学的代码运行了一次后，发现leetcode的编译器（GCC）报错如下：

terminate called after throwing an instance of 'std::out_of_range'
what():  vector::_M_range_check: __n (which is 0) >= this->size() (which is 0)

一开始我以为是这个同学的代码问题，没考虑到一些边界情况，导致越界。后来自己测试下，发现确实是std::sort问题，但是自己写了几个简单的demo，std::sort函数又表现正常，令人匪夷所思。

『源码面前，了无秘密』 --- 侯捷

于是乎，开启 std::sort函数的源码探索之路。

• 更好阅读体验，点击：踩坑记 (1) | std::sort函数隐藏着BUG，你知道吗
• 更多硬核知识，点击并关注: look_code_art，精彩等你发现
• 欢迎加入 [C++学习交流](https://w.url.cn/s/AEPtI***---

std::sort

STL的std::sort函数是基于Musser在1996年提出的内省排序（Introspective sort）算法实现。这个算法是个缝合怪，它汲取了插入排序、堆排序以及快排的优点：

• 针对大数据量，使用快排，时间复杂度是O(NlogN)；
• 若快排递归深度超过阈值__depth_limit ，改用堆排序，防止快排递归过深，同时保持时间复杂度仍是O(NlogN)；
• 当数据规模小于阈值_S_threshold时，改用插入排序。

下面从源码角度分析 std::sort函数是怎么实现这一过程的。

std::__sort

std::sort函数在内部就是直接调用的std::__sort函数。因此下面，直接从std::__sort函数开始分析。

std::__sort代码如下。

  template <typename _RandomAccessIterator, typename _Compare>
  inline void
  __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
  {
    if (__first != __last)
    {
      // 先是完成局部有序
      std::__introsort_loop(__first, __last,
                            std::__lg(__last - __first) * 2, 
                            __comp);
      // 再完全有序
      std::__final_insertion_sort(__first, __last, __comp);
    }
  }

可以看出，std::__sort主体上分为两个部分：

1. 首先，由__introsort_loop函数使得[__first, __last)区间在多个局部有序；
2. 其次，对第一步的结果，再进行一次插入排序std::__final_insertion_sort，保证整个[__first, __last)区间有序。

下面从以上两点进行详述。

为便于讲解，在下面的描述中，将比较器_Compare当作默认的std::less来处理。

std::__introsort_loop

__introsort_loop函数，其代码实现如下：

  template <typename _RandomAccessIterator, typename _Size, typename _Compare>
  void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,
                        _Size __depth_limit, 
                        _Compare __comp)
  {
    // 限制条件1
    while (__last - __first > int(_S_threshold)) {
       // 限制条件2
      if (__depth_limit == 0) {
        std::__partial_sort(__first, __last, __last, __comp);    // 堆排序
        return;
      }

      //下面是快排
      --__depth_limit; 
      _RandomAccessIterator __cut = std::__unguarded_partition_pivot(__first, __last, __comp);    // 寻找轴点
      std::__introsort_loop(__cut, __last, __depth_limit, __comp);                              // 递归
      __last = __cut;
    }
  }

从上面可以看出，__introsort_loop函数是个递归函数，并且存在两个限制条件，或者说是递归基：

1. 每次递归时，[__first, __last)区间的元素个数必须大于_S_threshold：

   当不满足这个条件时，__introsort_loop函数就开始返回，这会导致元素个数小于阈值_S_threshold的小区间仍然是无序的。

   那么这部分小区间怎么实现有序呢？？？

2. 最大递归深度__depth_limit：

   当__depth_limit==0时，快排递归深度达到限制，为避免递归层数过深，STL就对当前的 [__first, __last) 区间进行堆排序。

   从另一个角度看，相当于通过 __depth_limit 限制条件，将__introsort_loop函数划分为快排、堆排两部分，而且不一定每次都会调用堆排，需要满足__depth_limit限制条件。

因此，__introsort_loop函数能正常递归，需要满足以下条件：

 __last - __first > int(_S_threshold) && __depth_limit > 0

下面就从这两个限制点继续讲解。

Sthreshold

下面，开始讲解第【1】个限制条件_S_threshold。

我们把先深度限制条件__depth_limit去掉，只看快排部分。那么 __introsort_loop 函数的while循环可简洁如下：

    while (__last - __first > int(_S_threshold)) {
      // ...

      // 寻找分割区间的轴点
      auto __cut = std::__unguarded_partition_pivot(__first, __last, __comp);
      // 在右分支递归
      std::__introsort_loop(__cut, __last, __depth_limit, __comp);
      // 进入左分支
      __last = __cut;
   }

有没有发现，这个快排的实现异常简洁？

在__introsort_loop函数实现中，第一眼看上去似乎只有右分支递归，而忽略了左侧分支？

这一切都是为了效率。

STL将 __introsort_loop 放在了while循环中，寻找到分割 [__first, __last)区间的分割点__cut后，每次先进入右分支递归，在右侧分支递归回来之后，下一步是：

  __last = __cut;

这样，在下一个循环中进入左分支。

相比较常规快排实现，最直观的感受，就是减少一次函数调用的开销。此外，进入左分支后，可能就不满足__last - __first > int(_S_threshold) 限制条件，那么当前循环就退出了，避免递归。

因此，当 __introsort_loop函数因不满足_S_threshold阈值条件，逐层返回到std::__sort函数中时，完整的[__first, __last)区间中会有许多元素个数小于_S_threshold的无序区间，他们的有序性留给最后的插入排序__final_insertion_sort函数来完成。

std::__unguarded_partition_pivot

快排的最后一点，我们来看看STL是如何寻找分割位置__cut 的。这一部分是由__unguarded_partition_pivot函数实现。

  template <typename _RandomAccessIterator, typename _Compare>
  inline _RandomAccessIterator
  __unguarded_partition_pivot(_RandomAccessIterator __first,
                              _RandomAccessIterator __last,
                              _Compare __comp)
  {
      0 + (5-0)/2 = 2
    // 中间位置
    _RandomAccessIterator __mid = __first + (__last - __first) / 2;
    // 取三点的中值，并置于 __first 处
    std::__move_median_to_first(__first, 
                                __first + 1, __mid, __last - 1,
                                __comp);

    // 对 [__first, __last) 进行分割，并返回分割点 __cut
    return std::__unguarded_partition(__first + 1, __last, __first, __comp);
  }

__unguarded_partition_pivot的实现分为两步：

1. 选择一个轴点pivot，用于后续比较。
2. 基于该轴点 pivot分割[__first, __last)区间，使得 [__first, __cut)区间的元素不大于 pivot，[__cut, __last)区间的元素不小于pivot。

下面从这两点进行讲解。

std::__move_median_to_first

__move_median_to_first函数，用意很明显，就是找出__a、__b、__c的中值，并将这个中值放在__result位置处。因此，根据传入参数，就是找出__first+1、__mid、__last-1三个位置的中值，并将中值和__first位置的值进行交换。

这个函数比较简单，其中的iter_swap函数是交换两个迭代器指向的值，具体代码解释如下。

  template <typename _Iterator, typename _Compare>
  void
  __move_median_to_first(_Iterator __result, 
                         _Iterator __a, _Iterator __b, _Iterator __c, 
                         _Compare __comp)
  {
    // __a < __b 
    if (__comp(__a, __b))
    {
      // __a < __b < __c 
      if (__comp(__b, __c))  
        std::iter_swap(__result, __b);    // __b
      // __a < __c  <=  _b 
      else if (__comp(__a, __c))
        std::iter_swap(__result, __c);    // _c
      else
       // __c <= __a < __b 
        std::iter_swap(__result, __a);  // _a
    }
    // __b <= __a < __c
    else if (__comp(__a, __c))
      std::iter_swap(__result, __a);   // __a
    // __b <= c <= a
    else if (__comp(__b, __c))
      std::iter_swap(__result, __c);   // _c
    else
     // __c <= _b <= __a
      std::iter_swap(__result, __b);  // _b
  }

std::__unguarded_partition

上面找到待比较的轴点pivot之后，下面就是分割[__first, __last)区间。

分割的核心思想：寻找分割位置__cut，使得[__first, __cut)区间的元素都不大于 pviot，[__cut, __last)区间的元素都不小于pivot，然后返回分割点__cut的位置。

这部分代码讲解，见下面代码注释。

  template <typename _RandomAccessIterator, typename _Compare>
  _RandomAccessIterator
  __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last,
                        _RandomAccessIterator __pivot, 
                        _Compare __comp)
  {
    while (true)
    { 
      while (__comp(__first, __pivot)) ++__first;    // *__first < *__pivot 
      /*** 跳出循环时，满足：*__first >= *__pivot     ***/
      --__last;
      while (__comp(__pivot, __last))  --__last;    // *__pivot < *__last
      /*** 跳出循环时，满足：*__pivot >= *__last     ***/

      if (!(__first < __last))  // __fist >= __last ，表示左右边界相遇，此轮遍历结束
        return __first;           // 返回分割点位置

      /**  经过上面两个while循环，
       *   此时： *__first >= *__pivot &&  *__pivot >= *__last
       *   不满足分割要求，因此需要交换__first, __last 两点的值
       */
      std::iter_swap(__first, __last);  
      ++__first;
    }
  }

by the way

__unguarded_partition函数，有个__unguarded 前缀，表示这个函数里没有越界检测。

那么问题来了，为什么可以没有越界检测？

以pivot左侧的区间为例：

// 无越界检测版本
while (__comp(__first, __pivot)) ++__first;                     
// 常见实现版本
while (__first < __last && __comp(__first, __pivot)) ++__first;      

首先，明确两点：

• __unguarded_partition中传入参数__first，实际上是__unguarded_partition_pivot函数中的__first+1位置；

• __unguarded_partition中传入参数__pivot，实际上是__unguarded_partition_pivot函数中的__first位置。

__pivot是__unguarded_partition_pivot函数中的三个点（__first+1、__mid、__last-1）的中值，即__pivot值肯定并不是最大的。

因此，在__unguarded_partition函数中：

1. ++__first时，肯定存在一个点__pos，其值不小于 __pivot处的值；
2. 要使得__comp(__first, __pivot)为true，必须是*__first < *__pivot；
3. 又因为至少存在一个点__pos，满足*__pos >= *__pivot，使得__comp(__first, __last)为false，

因此，__first > __last的越界情况就不会发生，最终__first会在某个位置停下。同理右侧区间的判断。

因此，即使不要边界检测，也不会发生越界错误。

隐藏的BUG

但是注意了，__unguarded_partition函数，没有引入边界检测仍能正确运行，是基于正确的比较器算法。可当用户传入错误的比较器算法时，比如本文开篇自定义的比较器算法，就容易产生BUG，还是难以检测的BUG。

打开cppreference，可以看到STL要求std::sort的比较器是符合严格弱序性质的，其中容易导致BUG的是这么一条：

当比较器对象comp传入两个相等对象，返回值必须是false！！！

如果不符合严格弱序性质，则会在某些数据下会导致coredump。

假设某个小区间，数据分布如下：

数据： 1   1   1   2   1 
索引： 0   1   2   3   4
       ^   ^       ^
        p  f       l

按照__move_median_to_first函数中轴点选择法，最终选出的pivot是索引为1处的值，然后索引0、1值互换。

为便于下文分析叙述：pivot简写为p，first简写为f，last简写为l。

case1：比较器符合严格弱序关系

当std::sort传入的比较器Compare符合严格弱序关系，对该数据执行到__unguarded_partition函数时，迭代流程如下：

第一轮迭代后：

数据： 1   1   1   2   1 
索引： 0   1   2   3   4
      ^      ^      ^      
      p      f      l

第二轮迭代后：

此时last指针，到了first的位置，迭代结束。

数据： 1   1   1   2   1 
索引： 0   1   2   3   4
      ^      ^            
      p      f/l  

此时，分割点__cut就是first，其左侧的元素不比pivot大，其右侧不比pivot小。

case 2： 比较器不符合严格弱序关系

当std::sort传入的比较器Compare符合严格弱序关系，即comp(a,a)==true，再执行到__unguarded_partition_pivot函数时，迭代流程如下：

第一轮迭代：

实际上，在第一轮迭代中，last指针就越界了。

因为last在左移的过程中，其取值依次是2、1、1、1，都会使得comp(pivot, last)返回true，进而导致语句 while (__comp(__pivot, __last)) --__last;一直执行，最终就导致last越界。

数据： 1   1   1   2   1 
索引： 0   1   2   3   4
       ^   ^         
    l  p   f

总结来说，严格弱序关系，能保证 ：

1. while (__comp(__first, __pivot)) ++__first; 在++__first的过程中，不会越界。

   原理还是上面分析的那样，即使__first+1、__mid、__last-1三个值都是相等，取得的轴点pivot在弱序关系中，使得comp(__first, __pivot)一直为false，这样while循环就进行不下去。

   如果没有严格弱序关系保证，则就会越界。

2. while (__comp(__pivot, __last)) --__last;

   原理同上。

为了验证上面这个猜想，我自己写了个demo。

在数组vec里全是一样的数字，数组元素个数必须超过_S_threshold阈值（默认值16）才能触发std::sort的快排行为。

注意，代码必须在MSVC下编译运行，因为GCC对于某些越界行为并不报错，不如MSVC严格（没有测试clang）。

#include <vector>
#include <algorithm>

int main(int argc, char const* argv[]) {

    std::vector<int> vec{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};  // 全是一样的元素，且必须超过16个元素
    std::sort(vec.begin(), vec.end(),
             [](const int& lhs, const int& rhs)
             {
                return lhs <= rhs;    // BUG，修改为: return lhs < rhs; 才行
             });
    return 0;
}

__depth_limit

好嘞，下面开始讲解第【2】个限制条件__depth_limit。

当快排的递归深度，达到阈值 __depth_limit时，STL使用堆完成当前[__first, __last)区间的排序。下面我们把快排部分去掉，只看堆排序部分，那么 __introsort_loop 函数的while循环可简洁如下：

  while (__last - __first > int(_S_threshold)) {
      if (__depth_limit == 0) {
        std::__partial_sort(__first, __last, __last, __comp);
        return;
      }
      //...
  }

显而易见，堆排是由__partial_sort函数完成。

std::__partial_sort

__partial_sort函数，旨在取出 [__first, __last)区间前__middle - _frist个最小元素，并将其按照_Cpmpare比较策略进行排序后，有序存放在 [__first, __middle)区间，其余的节点放在[__middle, __last)区间。

__partial_sort函数实现如下（关于堆的实现，可以参考侯捷老师的《STL源码剖析》书籍）。

  // 上层调用
  std::__partial_sort(__first, __last, __last, __comp);

  // 函数原型
  template <typename _RandomAccessIterator, typename _Compare>
  inline void
  __partial_sort(_RandomAccessIterator __first,
                 _RandomAccessIterator __middle,
                 _RandomAccessIterator __last,
                 _Compare __comp)
  {
    // 先建堆，并使 [first, middle) 区间存放前 middle-first 个最小值
    std::__heap_select(__first, __middle, __last, __comp);

    // 对 [first, middle) 区间元素进行排序
    std::__sort_heap(__first, __middle, __comp);
  }

因此，经过 __partial_sort函数后：

• [__first, __middle)区间，有序存储了[__first, __last)区间的前__middle - _frist个最小元素；
• [__middle, __last)区间，无序存储[__first, __last)区间剩余元素。

在 __introsort_loop 函数中调用 __partial_sort 函数时，__middle参数和__last参数都是__last，因此实现的就是[__first, __last)区间的全排序。

std::__final_insertion_sort

当 __introsort_loop 函数执行完毕，最后一步需要将整个数据变得有序，这由__final_insertion_sort函数完成。

在讨论 __final_insertion_sort之前，先回顾下 __introsort_loop函数，它返回有两种可能：

1. _S_threshold：递归到某个[__first, __last)区间时，其元素个数__last - __first <= _S_threshold时，结束递归。

   __introsort_loop函数返回到std::__sort函数时，整个大的区间中还存在一些元素个数不足_S_threshold的小区间仍然是无序的。

2. __depth_limit：递归层次超过限制__depth_limit。

因此，当执行__final_insertion_sort函数时，当前大区间[__first, __last)只存在局部无序，主体上是有序的。这种情况，非常适用于插入排序，此时时间复杂度是O(N)。

为了进一步优化，加速排序的速度，STL针对两种情况分别求解。

  template <typename _RandomAccessIterator, typename _Compare>
  void
  __final_insertion_sort(_RandomAccessIterator __first,
                         _RandomAccessIterator __last, 
                         _Compare __comp)
  {
    // 大数据量
    if (__last - __first > int(_S_threshold))
    {
      std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, __comp);
    }
    else
     // 小数量量直接使用插入排序，不用经过快排、堆排
      std::__insertion_sort(__first, __last, __comp);
  }

std::__insertion_sort

__insertion_sort函数是按照标准的插入排序实现。

插入排序的核心思想：将整个序列视为两个部分，『有序的前缀』和『无序的后缀』，再通过循环迭代，不断地将后缀的首元素转移插入到前缀中，保持前缀仍然有序。当后缀为空，整个序列有序。

时间复杂度：如果当前序列已经完全有序，则插入排序时间复杂度是O(N)，完全逆序则O(N^2)。

运行到 __insertion_sort时，整个数据规模主体保持有序，局部小区间无序，非常适合使用插入排序，算法步骤如下：

• 初始状态下，前缀序列中只有__first一个元素，后缀序列则是[__first+1, __last)区间的元素；
• 对[__first+1, __last)区间的元素进行遍历，不断将后缀序列的首元素，插入到前缀序列中。

在 __insertion_sort函数中，对于后缀序列[__first+1, __last)区间的每个元素__i：

• 先判断__i位置的元素是否小于__first；

  如果是，则直接将[__first, __i)区间的元素整体后移一位，再将__i位置的元素插入到原先__first位置处。这样就避免了从__i位置一路比较到__first位置，才找到__i在前缀序列中的待插入位置，即节省了比较开销。

• 如果否，则需要在(__first, __i)区间寻找合适的位置__pos，使得 *(__pos-1) <= *__i < *__pos

  这个部分是由__unguarded_linear_insert函数完成，这个函数前面也有 __unguarded 前缀，也是没有边界检测的意思。

__insertion_sort函数，整个代码解释如下。

  template <typename _RandomAccessIterator, typename _Compare>
  void
  __insertion_sort(_RandomAccessIterator __first,
                   _RandomAccessIterator __last, 
                   _Compare __comp)
  {
    if (__first == __last) return;

    /*** 下面要将 (fist, last) 区间的每个元素 __i 都插入到前缀序列中 ***/

    for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
    {
      /* case 1:  *__i < *__first 时，则将 [__first, __i)区间后移，
       *          再将 *__i 插入到原先 __first 位置
       */
      if (__comp(__i, __first))
      {
        auto __val = std::move(*__i);              // 待插入的值
        std::move_backward(__first, __i, __i + 1); // 将 [_first, _i) 区间的元素朝后移动一个位置
        *__first = std::move(__val);               // 将 __i 位置处的值移动到 __first 处
      }
      else
      {
        /* case 2:  *__i >= *__fist 时，
         *             此时需要在有序前缀 (fist，_i)区间中，寻找合适的位置再插入
         */
        std::__unguarded_linear_insert(__i, __gnu_cxx::__ops::__val_comp_iter(__comp));
      }
    } // for-end
  }

std::__unguarded_linear_insert

__unguarded_linear_insert函数，在有序前缀(__first, __last)中寻找合适的位置__pos，将__i位置的值插入到__pos处。

那什么叫合适的位置呢？

从__i-1的位置开始遍历，第一个出现逆序对的位置__pos，即：

• __pos < __i ，且
• *(__pos-1) <= *__i < *__pos。

当找到这么个位置，需要将[__pos, __i)区间的元素，后移一位，然后将__i位置的元素插入到__pos。为了实现这一步，STL在 __unguarded_linear_insert函数中，边遍历、边把当前位置的元素向后移动。

下面是__unguarded_linear_insert函数的源码分析。

  template <typename _RandomAccessIterator, typename _Compare>
  void
  __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
  {
    auto __val = std::move(*__last);      // 当前待插入的值 __val
    _RandomAccessIterator __next = __last; 
    --__next;                         // 需要在有序前缀区间 (first, last)中遍历，因此开始遍历的位置需要 --next

    /* __comp(__val, __next) 为false时，表示出现逆序：
    *     + __next 指向当前遍历位置
    *     + __last 用于指向 __next 的上一个位置
    */
    while (__comp(__val, __next))
    {
      /** 下面是将当前遍历位置 __next 存储到 __last ***/

      *__last = std::move(*__next);  // 将当前位置的值后移动一位

      __last = __next;               //  __last 前移
      --__next;                       //  __next 前移
    } 

    /* 以上while循环，相当于将 [__last, __i) 区间的元素，后移动了一位，
     * 现在找到合适位置，此时：*__next <= val && val < *last
     * 因此，将 val 插入到上一个节点位置
     */
    *__last = std::move(__val);
  }

__unguarded_linear_insert 为啥能不用检测是否越界？

因为，之所以能进入__unguarded_linear_insert函数，是因为在__insertion_sort函数中有了 __i >= __first。因此在此函数中，再不济，while(__comp(__val, __next))也会在__first后一个位置停下来，最终插入在___first+1处。

免去边界检测，可以实现一定程度上的优化（STL对性能真的是锱铢必较）。

在这，你可能在想这个 __unguarded_partition函数，会存在之前在 __unguarded_partition中出现的BUG吗？

理论上是应该要出BUG的，这也是符合CPP标准，但是从上面的GCC的源码实现可以看出，GCC下不会出现BUG。下面的代码在MSVC中运行被中止，而GCC的实现却可以正常运行：

#include <vector>
#include <algorithm>

int main(int argc, char const* argv[]) {
    std::vector<int> vec{1,1};

    std::sort(vec.begin(), vec.end(),
              [](const int& lhs, const int& rhs)
              {
                  return lhs <= rhs;
              });

    return 0;
}

因为，在GCC下，会进入__insertion_sort函数的if (__comp(__i, __first))条件分支中，不断地将[__first, __i]区间元素后移动一位，避免了报错。尽管避免了报错，但实际上却不符合CPP标准。

因此，在书写自定义比较器算法时，要使其符合「严格弱序关系」，代码才具有移植性。

到此，std::sort的整个运行流程大致分析完毕。

附录

题目是leetcode-56。以下是源码：

class Solution {
public:
  std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
    if(intervals.size() ==1) 
      return intervals;

    std::sort(intervals.begin(), intervals.end(),
              [](const std::vector<int> &lhs,const std::vector<int> &rhs)
              {
                return lhs.at(0) <= rhs.at(0);        // BUG
              });

    std::vector<std::vector<int>> ans;
    ans.emplace_back(std::move(intervals[0]));
    for(int i=1; i < intervals.size(); ++i) {
      auto&& interval = std::move(intervals[i]); 

      if(interval[0] > ans.back()[1]) {
        ans.emplace_back(std::move(interval));
      }
      else if(interval[1] <= ans.back()[1]) {
        continue;
      }
      else {
        ans.back()[1] = std::move(interval[1]);
      }
    }

    return ans;
  }
};

写完这篇blog，脑袋距离小卤蛋又进了一步。