1

I need a list of elements that are always sorted. the operation involved is quite simple, for example, if the list is sorted from high to low, i only need three operations in some loop task:

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()
}

however, since I only add one elem at a time, and I have speed concern, I don't want the sorting go through all the elements, e.g., using bubble sorting. So I just wonder if there is a function to insert the element in order? or whether the list::sort() function is smarter enough to use some kind of quick sort when only one element is added/modified? Or maybe should I use deque for better speed performance if above are all the operations needed?

thanks alot!

6
  • 2
    If all you're doing is popping one element at a time, and pushing one element at a time, it sounds like you need a heap; not a sorted list. Have you considered std::priority_queue<>?
    – WhozCraig
    Dec 3, 2013 at 22:51
  • 5
    If you need things to remain in sorted order, consider using a std::set. Inserts of new elements will be O(log n).
    – Yuushi
    Dec 3, 2013 at 22:51
  • Seems the list is no std::list, but more like a std::vector.
    – user2249683
    Dec 3, 2013 at 23:20
  • I suggest std::lower_bound
    – user2249683
    Dec 3, 2013 at 23:21
  • list::sort has no idea of the preconditions of the list so it has no way to optimize for your special case. Dec 3, 2013 at 23:38

1 Answer 1

0

As mentioned in the comments, if you aren't locked into std::list then you should try std::set or std::multiset.

The std::list::insert method takes an iterator which specifies where to add the new item. You can use std::lower_bound to find the correct insertion point; it's not optimal without random access iterators but it still only does O(log n) comparisons.

P.S. don't use variable names that collide with built-in classes like 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
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.