c++ - 使用迭代器排序列表不会对最后一个元素 C++ 进行排序

Question

所以我正在尝试对列表列表进行排序。在每个子列表中，元素是包含运行时的类。这是我用来对列表进行排序的整数变量。

但是，如果最小运行时间位于列表末尾，则列表不会 100% 自行排序。我在下面附上了终端输出的图像以供可视化。

代码如下:

void sort( list<list<MetaData> > &omegaList )
{
// variables
list<list<MetaData> >::iterator cursor = omegaList.begin();
list<list<MetaData> >::iterator ptr    = omegaList.begin();
list<list<MetaData> >::iterator end    = omegaList.end();

// start the bubble sort...
for(; cursor != end; cursor++)
{
    // iterate through the list
    for(; ptr != end; ptr++)
    {
        // compare runtimes of different lists
        if( ptr->front().getProcessRunTime() < cursor->front().getProcessRunTime() )
            {
            // swap locations of lists in omegaList
            swap( *ptr, *cursor );
            // reset
            cursor = ptr = omegaList.begin();
            }
        }
    }
}

输出:

如果有人可以向我解释为什么它不会查看最后一个元素，然后告诉我如何修复它，我将不胜感激。

Answer 1

进行排序的正确方法是使用 std::list::sort如下:

omegaList.sort(
    [](const list<MetaData>& lhs, const list<MetaData>& rhs) {
       return lhs.front().getProcessRunTime() <
              rhs.front().getProcessRunTime();
});

你可以看到运行 here .

在你的冒泡排序中，你的第一个元素没有被排序的原因是一旦你发现一个乱序的元素，你就这样做......

cursor = ptr = omegaList.begin();

...然后 ptr++ for 循环操作开始，您的排序因此从 begin() + 1 重新开始。 cursor = ptr = omegaList.begin(); 非常疯狂 - 我见过的第一个 O(n^3) 排序实现。