On 2015-04-17 08:17, Bo Thorsen wrote: > On 04/17/2015 12:12 PM, Berkay Elbir wrote: >> Hello All, >> >> I want to ask a question to you to be certain. Is void qsort() function >> obsolete? Should we use std::sort instead of this function? Because I >> have a priority list and need to sort it. > > Slightly off-topic: Don't implement a priority queue this way. Unless > you have a system where you get a bunch of those and can sort them once, > and handle all of them. If this isn't the case, you are going to have > inserts and removes mixed. Then you will continually sort something > that's already sorted.
What Bo said. If you need to be able to peek into the queue, the best you are probably going to manage is to do a merge sort of all new items (which themselves you can sort with std::sort). In the single insertion case this degenerates into an insertion sort. You might, if you are clever, turn inserts into a strict append into a scratch array that isn't merged into the main queue until a read access is attempted. This will let you batch insertions even if your public API does not allow doing so, or if the producer needs to make separate insertions for whatever reason, but the consumer is likely to not need items until a number of insertions have happened. If you don't need to peek into the queue (i.e. you use only push and pop operations), and you don't have heavy batching, you're probably better off implementing the queue as a binary heap. The underlying array is not "sorted" as such, but push and pop operations are much faster (guaranteed O(log N) vs. O(N)). -- Matthew _______________________________________________ Interest mailing list Interest@qt-project.org http://lists.qt-project.org/mailman/listinfo/interest
