使用迭代器排序列表不会对最后一个元素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();
});

你可以看到在这里运行.

在你的冒泡排序中,你的第一个元素没有被排序的原因是,一旦你找到一个无序元素,你就这样做......

cursor = ptr = omegaList.begin();

...然后ptr++ for-loop操作启动,因此您的排序重新开始begin() + 1.这cursor = ptr = omegaList.begin();是非常疯狂的 - 我见过的第一个O(n ^ 3)排序实现.