- Even though the sequence container of a
std::priority_queue
can be specified just like for std::stack
, one must specify a non-associative container which is able to maintian the insertion order, like std::vector
or std::deque
(using random access iterators).
Even if a std::set
could be used here to drop duplicates, std::priority_queue
will not return an indicator whether or not an element has been inserted like std::set
or std::map
does.
- A plain
std::set
with a custom comparator would work well, elements could be inserted and removed using begin()
or rbegin()
with erase()
.
- Another way is to manually maintain a custom heap in a sequence container. This is usually done to avoid memory fragmentation and certain performance penalties caused by linked structures of associative containers or linked lists like
std::set
, std::map
, std::list
, std::forward_list
,...:
- Also note, that
std::heap*
algorithms are allowed to maintain an implementation specific order and thus cannot be expected to yield the same results as std::sort()
.
#include <iostream>
#include <numeric>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstdlib>
///@brief Internal insert function for ordered sequences
template<class SequenceContainer, typename Value, class Comparator>
inline typename std::pair<typename SequenceContainer::iterator, bool> heap_set_insert_(SequenceContainer& heap, const Value& value, Comparator comparator)
{
std::pair<typename SequenceContainer::iterator, bool> result(std::lower_bound(heap.begin(), heap.end(), value, comparator), false);
if (!(result.first != heap.end() && !comparator(value, *result.first)))
{
result.first = heap.insert(result.first, value);
result.second = true;
}
return result;
}
/**
* @brief insert function for an ordered vector, works like std::set::insert(const value_type&)
* @param heap The supplied container must already be sorted using the specified comparator
*/
template<typename T, class Allocator, class Comparator = std::less<T> >
inline typename std::pair<typename std::vector<T, Allocator>::iterator, bool> heap_set_insert(std::vector<T, Allocator>& heap, const T& value, Comparator comparator)
{
return heap_set_insert_<std::vector<T> >(heap, value, comparator);
}
/**
* @brief insert function for an ordered deque, works like std::set::insert(const value_type&)
* @param heap The supplied container must already be sorted using the specified comparator
*/
template<typename T, class Allocator, class Comparator = std::less<T> >
inline typename std::pair<typename std::deque<T, Allocator>::iterator, bool> heap_set_insert(std::deque<T, Allocator>& heap, const T& value, Comparator comparator)
{
return heap_set_insert_<std::deque<T> >(heap, value, comparator);
}
///@brief Prints all elements of any container as an array to a std::ostream: {[,elem]...}.
///@note Special container elements and std::pair<> may need additional ostream overloads
template<class Container>
inline std::ostream& print_container_(std::ostream& o, const Container& s)
{
o << '{';
for (typename Container::const_iterator it = s.begin(); it != s.end(); ++it)
{
if (it != s.begin())
o << ',';
o << *it;
}
o << '}';
return o;
}
///@brief Equality functor, derived from a set comparator (which may evaluate less/greater than).
template<typename SetComparator>
class SetAdjacencyComparator
{
public:
SetAdjacencyComparator(const SetComparator& setCmp = SetComparator()) :
setCmp(setCmp)
{
}
//Elements are equal, if neither is less/greater than the other
bool operator()(int a, int b)
{
return !setCmp(a, b) && !setCmp(b, a);
}
private:
SetComparator setCmp;
};
int main()
{
//May be a function pointer
//For a set (with unique values), use less/greater only!
typedef std::less<int> MyCompare;
MyCompare cmp;
std::cout << std::boolalpha;
{
std::deque<int> s
{ 7, 8, 3, 4, 9, 10, 1, 2, 6, 5 }; //(C++11)
//Initialize the custom heap using the one comparator, which is used for all subsequent operations
std::sort(s.begin(), s.end(), cmp);
print_container_(std::cout, s) << std::endl;
std::cout << "inserted: " << heap_set_insert(s, 3, cmp).second << std::endl;
std::cout << "inserted: " << heap_set_insert(s, 33, cmp).second << std::endl;
std::cout << "inserted: " << heap_set_insert(s, 11, cmp).second << std::endl;
print_container_(std::cout, s) << std::endl;
std::cout << "is_sorted() : " << std::is_sorted(s.begin(), s.end(), cmp) << std::endl;
std::cout << "unique : " << (std::adjacent_find(s.begin(), s.end(), SetAdjacencyComparator<MyCompare>(cmp)) == s.end()) << std::endl;
//^- In order for this check to work, the sequence must be sorted in such a way, that equal elements are adjacent
std::cout << "highest (top) : " << s.back() << std::endl;
std::cout << "lowest : " << s.front() << std::endl;
}
std::cout << std::noboolalpha;
return EXIT_SUCCESS;
}