Can I std::unique a std::priority_queue

Question

Thank you for taking the time to read my post.

I require a unique priority queue, however there is no option to get its iterators :(

Is there an alternative or can it be done?

Friendly Regards GM3

@edit

Since it can't be done I will give more information in case someone can give me good advice.

I want to count the days between a collection of dates, the dates are depart or return dates, I want count the days abroad and the days at home. There can be duplicate and overlapping trips. As such I want to start with a depart and a separate return container ordered and with no duplicate entries. I have overloaded the < > = operators for the date objects.

I have not used the stl container in the past because of run time memory allocations but in this case I have no such restriction and would like to get used to using them. I initially wanted to use a priority_queue but now I am doubting my choice.

Answer 1

• 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;
}