我记得,从一开始,最流行的实现方法std::list<>::sort()是以自下而上的方式实现的经典Merge Sort算法(另请参阅是什么让gcc std :: list排序实现如此之快？).
我记得有人恰如其分地将这种策略称为"洋葱链"方法.
至少这是GCC实现C++标准库的方式(例如,参见这里).这就是旧版Dimkumware在标准库的MSVC版本中的STL,以及所有版本的MSVC到VS2013的情况.
但是,随VS2015提供的标准库突然不再遵循此排序策略.VS2015附带的库使用自上而下的 Merge Sort 的相当简单的递归实现.这让我感到很奇怪,因为自上而下的方法需要访问列表的中点才能将其分成两半.由于std::list<>不支持随机访问,找到该中间点的唯一方法是逐字遍历列表的一半.此外,在最开始时,有必要知道列表中的元素总数(在C++ 11之前不一定是O(1)操作).
尽管如此,std::list<>::sort()在VS2015确实如此.以下是该实现的摘录,它定位中点并执行递归调用
...
iterator _Mid = _STD next(_First, _Size / 2);
_First = _Sort(_First, _Mid, _Pred, _Size / 2);
_Mid = _Sort(_Mid, _Last, _Pred, _Size - _Size / 2);
...
正如您所看到的,他们只是无意中使用std::next了遍历列表的前半部分并到达_Mid迭代器.
我想知道这种转变背后的原因是什么？我所看到的是std::next在每个递归级别上重复调用看似明显的低效率.天真的逻辑说这是慢的.如果他们愿意支付这种价格,他们可能希望获得回报.那他们得到了什么？我没有立即将此算法视为具有更好的缓存行为(与原始自下而上方法相比).我没有立即看到它在预先排序的序列上表现得更好.
当然,由于C++ 11 std::list<>基本上需要存储其元素数,这使得上面的效率略高,因为我们总是提前知道元素数.但这仍然不足以证明每个递归级别的顺序扫描是正确的.
(不可否认,我没有试图相互竞争实施.也许有一些惊喜.)