Recently while doing a code review I was surprised to notice that the developer rolled out his own method to find the maximal element in a container. With the STL offering several ways to do just that, it’s difficult to imagine why reinventing this particular wheel justify the effort.
in this post, I’ll review 4 ways if finding the maximum and minimal elements in a container. Choosing the algorithm best suited for your situation depends on the constraints and the problem you are trying to solve.
max_element / min_element
this is the most trivial algorithm. It will scan the entire container searching for the min/max element, returning an iterator pointing to it.
If your compiler supports C++ 11 and up, you can use the minmax_element method to find both minimal and maximal elements in the same run.
max val: 93
Cost: O(n) as the entire n elements of the container must be scanned.
A priority queue is an ordered sequence starting with a zero sized container, each new element is inserted into a position that maintains the order of the queue:
Priority queue – max value
max val: 8
removing max value
It worth pointing out that a queue structure is built over another container overriding push and pop operations of the original container ensure the priority structure maintains its order after an element is inserted or removed from the queue.
By default the order of the elements is determined by std::less : suppose there are two elements x,y than – x will be placed before y if x < y (max queue).
Your can create a min queue by using std::greater instead of std::less :
as its suggests – partial sort will only sort part of the container so that the first m elements are sorted. It’s a good strategy to employ if you need a set of the first extreme values.
Sorting first 3 elements
As you can see the first 3 values in the list are sorted in descending order. Values past the 3’d elements has no predictable order.
Accessing the max element can be done by simply iterating over the first m elements of the sorted container or by using partial_sort_copy that will sort the container and copies the result to a different container
Cost: sorting the first m elements out of a – n size container will cost O(n lg (m)) which is nearly linear for small m in the. The cost of Inserting elements is container dependent (e.g. it will cost O(1) for a list).
You can use an existing container is a heap by calling make_heap. The containers elements order will change so that the extreme value will be on top of the heap.
Getting the extreme element and removing it are three distinct operations:
- Getting the max/min element is done with the containers front method.
- calling the heap pop_heap to move the current extreme element to the end of the container.
- Calling the container’s pop_back to remove the value from the container.
Note: I almost included the heap method as an honorable mention, while is possible to use a heap. It’s very easy to mess it up by calling the underlying container methods. Honestly, I find it difficult to imagine a scenario where a bare heap will be useful for this purpose, but If you do need to use this method, you’ll probably want to hide the container in another class, exposing specialized insert/retrieve method that will make sure the heap structure is maintained.
Cost: the initial cost of creating the heap is O(3n), once the heap is created it will cost O(2lg n) to retrieve the minimum/maximum value and O(lg n) to push a new value into the container with push_heap.
When it comes to finding a max element, the STL offers something to everyone. There have to be convincing arguments to justify implementing your own algorithm instead of using the fully field tested and super optimized implementation of the standard library.
I am sure there are more ways to find the min/max values, leave a comment if you have other ways of extracting the min/max using the standard library.