讨论/技术交流/交流 | std::sort函数隐藏着BUG,你知道吗/
交流 | std::sort函数隐藏着BUG,你知道吗

导读:std::sort函数隐藏的bug,不了解能安心刷题吗。

今天来聊聊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函数的源码探索之路。

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

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

_S_threshold

下面,开始讲解第【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的是这么一条:

2.png

当比较器对象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简写为pfirst简写为flast简写为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在左移的过程中,其取值依次是2111,都会使得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,脑袋距离小卤蛋又进了一步。

47

收藏起来,等我刷够百题回来再看,现在先不追源QWQ

1
展开全部 19 讨论