std :: list - 排序一个项目

Question

是否可以根据一个项目对列表进行排序？

例如,如果我有

1,3,2,4,5,6,7 ... 1000000

我知道,3是第二个元素,是可以有效地排序3到它之间的正确位置2,并4没有重新排序整个列表？

编辑:我还应该注意,在这种情况下,假设列表的其余部分已经排序; 它就是3现在不合适的地方.

Answer 1

您可以简单地找到无序对象(O(n)),取出对象(O(1)),找到正确的位置(O(n)),然后再次插入(O(1)).

假设C++ 11,

#include <list>
#include <algorithm>
#include <iostream>

int main() {
    std::list<int> values {1, 2, 3, 9, 4, 5, 6, 7, 12, 14};

    auto it = std::is_sorted_until(values.begin(), values.end());
    auto val = *--it;
    // ^ find that object.

    auto next = values.erase(it);
    // ^ remove it.

    auto ins = std::lower_bound(next, values.end(), val);
    // ^ find where to put it back.

    values.insert(ins, val);
    // ^ insert it.

    for (auto value : values) {
        std::cout << value << std::endl;
    }
}

在C++ 11之前,你需要自己实现std::is_sorted_until.