我记得自古以来最流行的实现方法 std::list<>::sort()是在 bottom-up fashion 中实现的经典归并排序算法(另见 What makes the gcc std::list sort implementation so fast? )。
我记得看到有人恰本地将这种策略称为“洋葱链”方法。
至少在 GCC 的 C++ 标准库实现中是这样的(例如，参见 here)。这就是 MSVC 标准库版本中旧 Dimkumware 的 STL 中的情况，以及在所有版本的 MSVC 中一直到 VS2013。
然而，VS2015 提供的标准库突然不再遵循这种排序策略。 VS2015 附带的库使用了自顶向下合并排序的相当简单的递归实现。这让我觉得很奇怪，因为自上而下的方法需要访问列表的中点才能将其分成两半。自 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<>基本上需要存储它的元素计数，这使得上面的效率稍微提高一些，因为我们总是提前知道元素计数。但这似乎仍然不足以证明在每个递归级别上进行顺序扫描是合理的。(诚然，我并没有试图让实现相互竞争。也许那里有一些惊喜。)
最佳答案
请注意，此答案已更新以解决以下评论中和问题之后提到的所有问题，方法是从列表数组到迭代器数组进行相同的更改，同时保留更快的自底向上合并排序算法，并消除由于使用自上而下的归并排序算法进行递归而导致堆栈溢出的可能性很小。
我最初没有考虑迭代器的原因是由于 VS2015 更改为自顶向下，让我相信尝试更改现有自底向上算法以使用迭代器存在一些问题，需要切换到较慢的自顶向下算法。只有当我尝试自己分析切换到迭代器时，我才意识到存在自下而上算法的解决方案。
在@sbi 的评论中，他询问了自上而下方法的作者 Stephan T. Lavavej，为什么要进行更改。 Stephan 的回应是“避免内存分配和默认构造分配器”。 VS2015 引入了不可默认构造和有状态的分配器，这在使用先前版本的列表数组时会出现问题，因为列表的每个实例分配一个虚拟节点，并且需要进行更改以处理无默认分配器。
Lavavej 的解决方案是改用迭代器来跟踪原始列表中的运行边界，而不是内部列表数组。合并逻辑改为使用 3 个迭代器参数，第一个参数是左运行开始的迭代器，第二个参数是左运行结束的迭代器 == 右运行开始的迭代器，第三个参数是右运行结束的迭代器。合并过程使用 std::list::splice 在合并操作期间移动原始列表中的节点。这具有异常安全的额外好处。如果调用者的比较函数抛出异常，列表将被重新排序，但不会发生数据丢失(假设拼接不会失败)。使用先前的方案，如果发生异常，一些(或大部分)数据将在列表的内部数组中，并且数据将从原始列表中丢失。
然而，不需要切换到自上而下的归并排序。最初，我认为 VS2015 切换到自上而下有一些未知的原因，我专注于以与 std::list::splice 相同的方式使用内部接口(interface)。后来我决定研究自下而上的切换以使用迭代器数组。我意识到存储在内部数组中的运行顺序是最新的(数组 [0] = 最右边)到最旧的(数组 [最后] = 最左边)，并且它可以使用与 VS2015 自上而下的方法相同的基于迭代器的合并逻辑。
对于自下而上的归并排序，array[i] 是具有 2^i 个节点的已排序子列表开头的迭代器，或者它为空(使用 std::list::end 表示为空)。每个排序子列表的结尾将是数组中下一个先前非空条目中排序子列表的开头，或者如果在数组的开头，则在本地迭代器中(它指向最新的结尾)跑)。与自顶向下方法类似，迭代器数组仅用于跟踪原始链表内已排序的运行边界，而合并过程使用 std::list::splice 移动原始链表内的节点。
如果链表很大且节点分散，则会出现大量缓存未命中。自下而上将比自上而下快约 30%(相当于自上而下比自下而上慢约 42%)。再说一次，如果有足够的内存，将列表移动到数组或 vector 通常会更快，对数组或 vector 进行排序，然后从排序后的数组或 vector 创建一个新列表。
示例 C++ 代码:
#define ASZ 32
template <typename T>
void SortList(std::list<T> &ll)
{
if (ll.size() < 2) // return if nothing to do
return;
std::list<T>::iterator ai[ASZ]; // array of iterators
std::list<T>::iterator mi; // middle iterator (end lft, bgn rgt)
std::list<T>::iterator ei; // end iterator
size_t i;
for (i = 0; i < ASZ; i++) // "clear" array
ai[i] = ll.end();
// merge nodes into array
for (ei = ll.begin(); ei != ll.end();) {
mi = ei++;
for (i = 0; (i < ASZ) && ai[i] != ll.end(); i++) {
mi = Merge(ll, ai[i], mi, ei);
ai[i] = ll.end();
}
if(i == ASZ)
i--;
ai[i] = mi;
}
// merge array into single list
ei = ll.end();
for(i = 0; (i < ASZ) && ai[i] == ei; i++);
mi = ai[i++];
while(1){
for( ; (i < ASZ) && ai[i] == ei; i++);
if (i == ASZ)
break;
mi = Merge(ll, ai[i++], mi, ei);
}
}
template <typename T>
typename std::list<T>::iterator Merge(std::list<T> &ll,
typename std::list<T>::iterator li,
typename std::list<T>::iterator mi,
typename std::list<T>::iterator ei)
{
std::list<T>::iterator ni;
(*mi < *li) ? ni = mi : ni = li;
while(1){
if(*mi < *li){
ll.splice(li, ll, mi++);
if(mi == ei)
return ni;
} else {
if(++li == mi)
return ni;
}
}
}
VS2019 的 std::list::sort() 示例替换代码(合并逻辑被制作成一个单独的内部函数，因为它现在在两个地方使用)。
private:
template <class _Pr2>
iterator _Merge(_Pr2 _Pred, iterator _First, iterator _Mid, iterator _Last){
iterator _Newfirst = _First;
for (bool _Initial_loop = true;;
_Initial_loop = false) { // [_First, _Mid) and [_Mid, _Last) are sorted and non-empty
if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First)) { // consume _Mid
if (_Initial_loop) {
_Newfirst = _Mid; // update return value
}
splice(_First, *this, _Mid++);
if (_Mid == _Last) {
return _Newfirst; // exhausted [_Mid, _Last); done
}
}
else { // consume _First
++_First;
if (_First == _Mid) {
return _Newfirst; // exhausted [_First, _Mid); done
}
}
}
}
template <class _Pr2>
void _Sort(iterator _First, iterator _Last, _Pr2 _Pred,
size_type _Size) { // order [_First, _Last), using _Pred, return new first
// _Size must be distance from _First to _Last
if (_Size < 2) {
return; // nothing to do
}
const size_t _ASZ = 32; // array size
iterator _Ai[_ASZ]; // array of iterators to runs
iterator _Mi; // middle iterator
iterator _Li; // last (end) iterator
size_t _I; // index to _Ai
for (_I = 0; _I < _ASZ; _I++) // "empty" array
_Ai[_I] = _Last; // _Ai[] == _Last => empty entry
// merge nodes into array
for (_Li = _First; _Li != _Last;) {
_Mi = _Li++;
for (_I = 0; (_I < _ASZ) && _Ai[_I] != _Last; _I++) {
_Mi = _Merge(_Pass_fn(_Pred), _Ai[_I], _Mi, _Li);
_Ai[_I] = _Last;
}
if (_I == _ASZ)
_I--;
_Ai[_I] = _Mi;
}
// merge array runs into single run
for (_I = 0; _I < _ASZ && _Ai[_I] == _Last; _I++);
_Mi = _Ai[_I++];
while (1) {
for (; _I < _ASZ && _Ai[_I] == _Last; _I++);
if (_I == _ASZ)
break;
_Mi = _Merge(_Pass_fn(_Pred), _Ai[_I++], _Mi, _Last);
}
}
这个答案的其余部分是历史性的。
我能够根据@IgorTandetnik 的演示重现该问题(旧版本无法编译，新版本有效):
#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 日通过电子邮件向 P.J. Plauger 发送了有关此变化的电子邮件。他的回复摘要:
Interestingly enough, our change log doesn't reflect this change. That probably means it was "suggested" by one of our larger customers and got by me on the code review. All I know now is that the change came in around the autumn of 2015. When I reviewed the code, the first thing that struck me was the line:
iterator _Mid = _STD next(_First, _Size / 2);which, of course, can take a very long time for a large list.
The code looks a bit more elegant than what I wrote in early 1995(!), but definitely has worse time complexity. That version was modeled after the approach by Stepanov, Lee, and Musser in the original STL. They are seldom found to be wrong in their choice of algorithms.
I'm now reverting to our latest known good version of the original code.
我不知道 P.J. Plauger 对原始代码的恢复是否处理了新的分配器问题，或者 Microsoft 是否或如何与 Dinkumware 进行交互。
为了比较自顶向下和自底向上方法，我创建了一个包含 400 万个元素的链表，每个元素由一个 64 位无符号整数组成，假设我最终会得到一个几乎按顺序排列的节点的双向链表(即使它们将被动态分配)，用随机数填充它们，然后对它们进行排序。节点不会移动，只是链接发生了变化，但现在遍历列表以随机顺序访问节点。然后我用另一组随机数填充这些随机排序的节点并再次对它们进行排序。我将 2015 年自上而下的方法与之前为匹配 2015 年所做的其他更改而修改的自下而上的方法进行了比较(sort() 现在使用谓词比较函数调用 sort()，而不是具有两个单独的函数)。这些是结果。更新 - 我添加了一个基于节点指针的版本，并注意到了从列表中简单地创建一个 vector 、排序 vector 、复制回来的时间。
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
下面是 std::list::sort() 的第一个替换代码，我用来比较先前的自底向上和小数组 (_BinList[]) 方法与 VS2015 的自顶向下方法我希望比较公平，所以我修改了一个<列表>的拷贝。
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);
}
下面是我用于另一个比较的 std::list::sort() 的基于节点指针的替换。这消除了与分配相关的问题。如果比较异常是可能的并且发生了，则必须将数组和临时列表 (pNode) 中的所有节点附加回原始列表，或者比较异常可能被视为小于比较。
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;
}
关于c++ - `std::list<>::sort()` - 为什么突然切换到自上而下的策略？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40622430/