Which C ++ STL container provides the `extract_max ()`, `find (element_value)` and `modify (element)` functions?
I want to use a C ++ STL container to implement the Prim algorithm . I need functions extract_max
, find(element)
and modify(element_value)
, but std::priority_queue
only provides extract_max
. Is there any other container I can use? Obviously, I want them all to be as fast as possible.
Edit: The container must also provide functionality to change the value of its element.
+3
source to share
1 answer
Push your items into std::set<T, std::greater<T>>
, which is an ordered heap.
- Call
*set::begin()
to go to the maximum element in O (1) or O (log (n)), whichever is howset::begin()
. - Use
set::find
to do O (log (n)) lookups. - To change an item, you must unfortunately remove it from the set and then insert the changed version. (This also applies to
make_heap
friends.) There may be an answer where this is optional, but (A) you have to be paranoid about which terms are used for comparison versus equality, and (B) the difference in speed is very small. So there is no generic container that works this way. - If the ordering of an item is not unique within it, use
std::multiset
instead, which is otherwise identical.
Example:
#include <iostream>
#include <set>
int main()
{
std::set<int, std::greater<int>> v { 3, 1, 4, 1, 5, 9 };
std::cout << "initially, v: ";
for (auto i : v) std::cout << i << ' ';
std::cout << '\n';
auto largest = *v.begin();
v.erase(v.begin());
std::cout << "largest element: " << largest << '\n';
std::cout << "after removing the largest element, v: ";
for (auto i : v) std::cout << i << ' ';
std::cout << '\n';
}
+3
source to share