`std :: list <> :: sort（）` – 为什么突然切换到自顶向下的策略？

我记得自从时代开始以来，实现std::list<>::sort()的最stream行的方法是以自底向上的方式实现的经典合并sortingalgorithm（另请参阅什么使得gcc std :: listsorting实现如此之快？ ）。

我记得有人把这个策略恰当地称为“洋葱链”的方法。

至less在GCC的C ++标准库实现中就是这样的（例如，请参阅这里 ）。 而这正是MSVC版本标准库中老版本Dimkumware的STL以及MSVC所有版本VS2013的所有版本。

然而，随VS2015提供的标准库突然不再遵循这种分类策略。 VS2015附带的库使用相当简单的recursion实现自顶向下合并sorting。 这让我觉得很奇怪，因为自上而下的方法需要访问列表的中点，以便将其分成两半。 由于std::list<>不支持随机访问，所以find中点的唯一方法是从字面上遍历列表的一半。 另外，最初需要知道列表中元素的总数（在C ++ 11之前不一定是O（1）操作）。

不过，VS2015中的std::list<>::sort()正是这样做的。 下面是该实现的摘录，它定位中点并执行recursion调用

 ... 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迭代器。

我想知道这个开关背后的原因是什么？ 我所看到的是在recursion的每个级别重复调用std::next看似明显的低效率。 天真的逻辑说，这是慢的 。 如果他们愿意支付这种价格，他们可能期望得到回报。 他们到底是什么？ 我不会立即看到这种algorithm具有更好的caching行为（与原始的自底向上方法相比）。 我不会立即看到它在预先sorting的序列上performance得更好。

当然，由于C ++ 11 std::list<>基本上需要存储它的元素数量，这使得上面的效率略高一些，因为我们总是事先知道元素数量。 但是，这似乎还不足以certificaterecursion的每个级别的顺序扫描。

（不可否认，我并没有尝试过相互竞争，也许有些惊喜。）

Answer 1

更新 – VS2015引入了非默认构造的和有状态的分配器，这在使用本地列表时提出了一个问题，就像先前的自底向上方法一样。 我能够通过使用节点指针而不是列表来处理这个问题（参见下文）。

在@ sbi的评论中，他问上面的问题作者Stephan T. Lavavej，为什么要做出改变。 Stephan的回应是“避免内存分配和默认构造分配器”。 新的自顶向下的方法比旧的自下而上的方法慢，但它只使用迭代器（recursion存储在堆栈中），不使用任何本地列表，并避免与非默认构造或有状态分配器有关的问题。 @ TC的答案详细介绍了这一点。

至于性能，如果有足够的内存，将列表移动到数组或向量，sorting，然后将已sorting的数组或向量移回列表通常会更快。

基于@IgorTandetnik的演示，我能够重现这个问题（旧的sorting无法编译，新的工作）

 #include <iostream> #include <list> #include <memory> template <typename T> class MyAlloc : public std::allocator<T> { public: MyAlloc(T) {} // suppress default constructor template <typename U> MyAlloc(const MyAlloc<U>& other) : std::allocator<T>(other) {} template< class U > struct rebind { typedef MyAlloc<U> other; }; }; int main() { std::list<int, MyAlloc<int>> l(MyAlloc<int>(0)); l.push_back(3); l.push_back(0); l.push_back(2); l.push_back(1); l.sort(); return 0; } 

---

2016年7月，我注意到这一变化，并于2016年8月1日通过电子邮件向PJ Plauger发送了这一变更。他的回复中有一小部分内容：

有趣的是，我们的更改日志并不反映这种变化。 这可能意味着它是由我们的一个更大的客户“build议”，并通过我的代码审查。 我现在所知道的是，这个变化是在2015年左右。当我回顾这个代码的时候，让我感到震惊的第一件事是：

  iterator _Mid = _STD next(_First, _Size / 2); 

这当然可能需要很长时间才能列出大量的清单。

代码看起来比我在1995年初（！）写的更优雅，但是时间复杂性肯定更差。 这个版本是在Stepanov，Lee和Musser在原始STL中的方法之后build立的。 很less发现他们在selectalgorithm时是错误的。

我现在正在恢复到我们最新的已知的原始代码版本。

我不知道PJ Plauger是否回复到原来的代码是为了处理新的分配器问题，还是微软与Dinkumware交互的方式。

为了比较自上而下和自下而上的方法，我创build了一个有400万个元素的链表，每个元素由一个64位无符号整数组成，假设我最终会得到一个几乎是顺序排列的节点的双向链表（尽pipe它们将被dynamic分配），用随机数填充，然后对它们进行sorting。 节点不移动，只改变链接，但是现在遍历列表以随机顺序访问节点。 然后我用另一组随机数填充那些随机排列的节点，并将它们重新sorting。 我将2015年自顶向下的方法与之前的自下而上方法进行了比较，以便与2015年的其他更改（sort（）现在调用sort（）与谓词比较函数相匹配，而不是具有两个单独的函数）。 这是结果。 更新 – 我添加了一个基于节点指针的版本，并注意到从列表中简单地创build一个向量，sorting向量，复制回来的时间。

 sequential nodes: 2015 version 1.6 seconds, prior version 1.5 seconds random nodes: 2015 version 4.0 seconds, prior version 2.8 seconds random nodes: node pointer based version 2.6 seconds random nodes: create vector from list, sort, copy back 1.25 seconds 

对于顺序节点，先前的版本只有一点点快，但对于随机节点，先前的版本快了30％，节点指针版本快了35％，并且从列表创build了一个向量，对向量进行sorting，然后复制快69％。

下面是std :: list :: sort（）的第一个replace代码我用来比较先前自下而上的小数组（_BinList []）方法与VS2015的自顶向下的方法，我想比较公平，所以我修改了<list>的副本。

  void sort() { // order sequence, using operator< sort(less<>()); } template<class _Pr2> void sort(_Pr2 _Pred) { // order sequence, using _Pred if (2 > this->_Mysize()) return; const size_t _MAXBINS = 25; _Myt _Templist, _Binlist[_MAXBINS]; while (!empty()) { // _Templist = next element _Templist._Splice_same(_Templist.begin(), *this, begin(), ++begin(), 1); // merge with array of ever larger bins size_t _Bin; for (_Bin = 0; _Bin < _MAXBINS && !_Binlist[_Bin].empty(); ++_Bin) _Templist.merge(_Binlist[_Bin], _Pred); // don't go past end of array if (_Bin == _MAXBINS) _Bin--; // update bin with merged list, empty _Templist _Binlist[_Bin].swap(_Templist); } // merge bins back into caller's list for (size_t _Bin = 0; _Bin < _MAXBINS; _Bin++) if(!_Binlist[_Bin].empty()) this->merge(_Binlist[_Bin], _Pred); } 

我做了一些小的改变。 原始代码保持跟踪名为_Maxbin的variables中的实际最大二进制文件，但最终合并中的开销足够小，因此我删除了与_Maxbin关联的代码。 在数组构build期间，原始代码的内部循环合并到一个_Binlist []元素中，然后交换到_Templist，这似乎毫无意义。 我改变了内部循环，只是合并到_Templist，只有一次find一个空的_Binlist []元素交换。

下面是一个基于节点指针replacestd :: list :: sort（）我用于另一个比较。 这消除了分配相关的问题。 如果可能发生比较exception，则数组中的所有节点和临时列表（pNode）都必须附加回原始列表，或者可能将比较exception视为比较不足。

  void sort() { // order sequence, using operator< sort(less<>()); } template<class _Pr2> void sort(_Pr2 _Pred) { // order sequence, using _Pred const size_t _NUMBINS = 25; _Nodeptr aList[_NUMBINS]; // array of lists _Nodeptr pNode; _Nodeptr pNext; _Nodeptr pPrev; if (this->size() < 2) // return if nothing to do return; this->_Myhead()->_Prev->_Next = 0; // set last node ->_Next = 0 pNode = this->_Myhead()->_Next; // set ptr to start of list size_t i; for (i = 0; i < _NUMBINS; i++) // zero array aList[i] = 0; while (pNode != 0) // merge nodes into array { pNext = pNode->_Next; pNode->_Next = 0; for (i = 0; (i < _NUMBINS) && (aList[i] != 0); i++) { pNode = _MergeN(_Pred, aList[i], pNode); aList[i] = 0; } if (i == _NUMBINS) i--; aList[i] = pNode; pNode = pNext; } pNode = 0; // merge array into one list for (i = 0; i < _NUMBINS; i++) pNode = _MergeN(_Pred, aList[i], pNode); this->_Myhead()->_Next = pNode; // update sentinel node links pPrev = this->_Myhead(); // and _Prev pointers while (pNode) { pNode->_Prev = pPrev; pPrev = pNode; pNode = pNode->_Next; } pPrev->_Next = this->_Myhead(); this->_Myhead()->_Prev = pPrev; } template<class _Pr2> _Nodeptr _MergeN(_Pr2 &_Pred, _Nodeptr pSrc1, _Nodeptr pSrc2) { _Nodeptr pDst = 0; // destination head ptr _Nodeptr *ppDst = &pDst; // ptr to head or prev->_Next if (pSrc1 == 0) return pSrc2; if (pSrc2 == 0) return pSrc1; while (1) { if (_DEBUG_LT_PRED(_Pred, pSrc2->_Myval, pSrc1->_Myval)) { *ppDst = pSrc2; pSrc2 = *(ppDst = &pSrc2->_Next); if (pSrc2 == 0) { *ppDst = pSrc1; break; } } else { *ppDst = pSrc1; pSrc1 = *(ppDst = &pSrc1->_Next); if (pSrc1 == 0) { *ppDst = pSrc2; break; } } } return pDst; } 

作为新的VS2015 std :: list :: sort（）的替代，你可以使用这个独立的版本。

 template <typename T> void listsort(std::list <T> &dll) { const size_t NUMLISTS = 32; std::list <T> al[NUMLISTS]; // array of lists std::list <T> tl; // temp list while (!dll.empty()){ // t1 = next element from dll tl.splice(tl.begin(), dll, dll.begin(), std::next(dll.begin())); // merge element into array size_t i; for (i = 0; i < NUMLISTS && !al[i].empty(); i++){ tl.merge(al[i], std::less<T>()); } if(i == NUMLISTS) // don't go past end of array i -= 1; al[i].swap(tl); // update array list, empty tl } // merge array back into original list for(size_t i = 0; i < NUMLISTS; i++) dll.merge(al[i], std::less<T>()); } 

或者使用类似的gccalgorithm。

Answer 2

@sbi问 MSVC的标准库维护者Stephan T. Lavavej， 他回答说 ：

我这样做，以避免内存分配和默认构造分配器。

为此，我将添加“免费的基本例外安全”。

详细说明：VS2015之前的实现有几个缺陷：

• _Myt _Templist, _Binlist[_MAXBINS]; 创build一堆中间list （ _Myt只是当前实例化list一个typedef;对于这个list ，这个list不那么容易混淆）来保存sorting过程中的节点，但是这些list是默认构造的，这导致许多问题：
  1. 如果所使用的分配器不是默认的可构造的（并且没有要求分配器是默认的可构造的），那么这将不会被编译，因为list的默认构造器将尝试默认构造其分配器。
  2. 如果使用的分配器是有状态的，那么缺省构造的分配器可能不会与this->get_allocator()相比较，这意味着后面的splice和merge是技术上未定义的行为，并且可能会在debugging构build中崩溃。 （“技术上”，因为节点全部被合并回来，所以如果函数成功完成，实际上不会使用错误的分配器来释放）。
  3. Dinkumware的list使用一个dynamic分配的哨兵节点，这意味着上述将执行_MAXBINS + 1dynamic分配。 我怀疑，很多人希望sort bad_alloc 。 如果分配器是有状态的，那么这些哨兵节点甚至可能不能从正确的位置分配（见＃2）。
• 该代码不是例外安全的。 特别是，允许​​比较抛出，并且如果在中间list s中存在元素的情况下抛出，那么在堆栈展开期间这些元素被list s简单地销毁。 sort用户不希望列表sorting如果sort引发exception，当然，但他们也可能不希望元素丢失。
  • 这与上面＃2的交互性很差，因为现在它不只是技术上未定义的行为：那些中间list的析构函数将释放和销毁与错误的分配器拼接在一起的节点。

这些缺陷是否可以修复？ 大概。 ＃1和＃2可以通过将get_allocator()传递给list s的构造函数来修复：

  _Myt _Templist(get_allocator()); _Myt _Binlist[_MAXBINS] = { _Myt(get_allocator()), _Myt(get_allocator()), _Myt(get_allocator()), /* ... repeat _MAXBINS times */ }; 

exception安全问题可以通过用一个try-catch环绕回路来解决， try-catch将中间list的所有节点拼接回*this而不考虑抛出exception的顺序。

修复＃3更难，因为这意味着根本不使用list作为节点的持有者，这可能需要大量的重构，但这是可行的。

问题是：为了提高容器的性能，通过devise来降低性能是否值得跳过所有这些环节？ 毕竟，真正关心性能的人可能不会首先使用list 。