CODEWITHSUNDEEP
c++performancesortingvectormax
Dr.Kameleon
Dr.Kameleon

Reputation: 22810

Get (next) Max object from a vector

OK, so here's my issue :

Now, given that I tried sorting the array (with sort(MyObjects.begin(),MyObjects.end(),MyClassCompare());) and noticed a considerable drop in performance (and also that some of the elements of the vector may not be needed at all in the end), I'm trying to :

Is there any way to achieve that using built-in functions/libraries, in C++? Any ideas?

HINT : Speed and performance are crucial.

Upvotes: 0

Views: 211

Answers (2)

user7116
user7116

Reputation: 64068

If you require access to the maximum valued element of a collection, you will have to incur some performance hit either (a) upfront at insertion time, or (b) during searching time. You've noted that (b) is expensive, probably due to the method you chose, and are asking how you can make this quicker.

Out of the box you have priority_queue which provides probably exactly what you are looking for. I would imagine the performance would be better than your current code.

Upvotes: 1

Mats Petersson
Mats Petersson

Reputation: 129344

If you are "collecting" data that you are later going to select things in some order (biggest, smallest, etc), you will have a few choices:

  1. sorting as you go.
  2. sorting when you have collected all the data.
  3. have poor performance when searching for your data.
  4. create TWO sets of data, where one is sorted, with some sort of index to your unsorted data items.

In your case, you are talking of removing some data as from the collection as well. Is it required that you actually remove the data, or that you simply keep track of what you "no longer need"? If the latter, perhaps option four above is a good choice - you simply remove it from the sorted table. Since this is much smaller than the list of items itself [presumably "MyClass" is bigger than two integers].

Upvotes: 0

Related Questions