c++ - 仅更改一个元素时如何在排序列表中进行快速排序

Question

我需要一个始终排序的元素列表。涉及的操作很简单，例如，如果列表从高到低排序，我在某个循环任务中只需要三个操作:

while true do {
    list.sort() //sort the list that has hundreds of elements
    val = list[0] //get the first/maximum value in the list
    list.pop_front() //remove the first/maximum element

    ...//do some work here  

    list.push_back(new_elem)//insert a new element
    list.sort()
}

但是，由于我一次只添加一个元素，而且我担心速度，我不希望排序遍历所有元素，例如，使用冒泡排序。所以我就想知道是否有按顺序插入元素的功能？或者 list::sort() 函数是否足够智能以在仅添加/修改一个元素时使用某种快速排序？或者如果以上是所有需要的操作，我应该使用 deque 以获得更好的速度性能？

非常感谢!

Answer 1

如评论中所述，如果您没有被 std::list 所束缚，那么您应该尝试 std::set 或 std::multiset 。

std::list::insert 方法采用一个迭代器来指定添加新项的位置。您可以使用 std::lower_bound 找到正确的插入点；如果没有随机访问迭代器，它就不是最优的，但它仍然只进行 O(log n) 比较。

附言不要使用与 list 等内置类冲突的变量名。

lst.sort(std::greater<T>()); //sort the list that has hundreds of elements
while true do {
    val = lst.front(); //get the first/maximum value in the list
    lst.pop_front(); //remove the first/maximum element

    ...//do some work here  

    std::list<T>::iterator it = std::lower_bound(lst.begin(), lst.end(), std::greater<T>());
    lst.insert(it, new_elem); //insert a new element
    // lst is already sorted
}