6
\$\begingroup\$

This is an updatable priority queue. In contains an index (implemented as std::unordered_map) which maps a value to its position in the queue itself. The queue is implemented as a binary heap in a std::vector. This class stores each value twice: once in the queue and once in the index. Internally it uses a self-reporting type: an object which reports all its movements to headquarters:

template<typename V>
class self_reporting
{
public:
    using value_type = V;

    self_reporting(const value_type & v, self_reporting** pp)
        : value(v), registry(pp)
    {
        report();
    }
    self_reporting(value_type && v, self_reporting** pp)
        : value(std::move(v)), registry(pp)
    {
        report();
    }

    ~self_reporting()
    {
        if (registry)
            *registry = nullptr;
    }

    self_reporting(const self_reporting &) = delete;
    self_reporting(self_reporting && other)
        : value(std::move(other.value)), registry(other.registry)
    {
        other.registry = nullptr;
        report();
    }

    self_reporting & operator=(const self_reporting &) = delete;
    self_reporting & operator=(self_reporting && other)
    {
        value = std::move(other.value);
        registry = other.registry;
        other.registry = nullptr;
        report();
        return *this;
    }

    const value_type & get() const
    {
        return value;
    }

    value_type & get()
    {
        return value;
    }

    void swap(self_reporting & other)
    {
        using std::swap;

        swap(value, other.value);
        swap(*registry, *other.registry);
        swap(registry, other.registry);
    }

private:
    void report()
    {
        if (registry)
            *registry = this;
    }

    value_type value;
    self_reporting **registry;
};

template<typename V>
inline void swap(self_reporting<V> & lhs, self_reporting<V> & rhs)
{
    lhs.swap(rhs);
}

Updatable priority queue:

template <typename V, typename P, typename Cmp = std::less<P>>
class updatable_priority_queue
{
public:

    using value_type = V;
    using priority_type = P;
    using priority_compare = Cmp;

    struct value_priority
    {
        value_type value;
        priority_type priority;
    };

    using element_type = value_priority;
    using reference = element_type &;
    using const_reference = element_type const &;

    using queue_element_type = self_reporting<element_type>;
    using queue_type = std::vector<queue_element_type>;
    using index_type = std::unordered_map<value_type, queue_element_type*>;

    updatable_priority_queue() = default;
    updatable_priority_queue(const priority_compare & cmp)
        : cmp_(cmp)
    {}

    struct priority_comparator
    {
        priority_compare & cmp_;
        bool operator()(const queue_element_type & lhs,
                        const queue_element_type & rhs) const
        {
            return cmp_(lhs.get().priority, rhs.get().priority);
        }
    };

    size_t size() const
    {
        assert(queue_.size() == index_.size());
        return queue_.size();
    }

    bool empty() const
    {
        assert(queue_.size() == index_.size());
        return queue_.empty();
    }

    const_reference top() const
    {
        return queue_.front().get();
    }

    bool insert(const value_type & value, const priority_type & priority)
    {
        assert(std::is_heap(queue_.begin(), queue_.end(), priority_comparator{cmp_}));
        auto r = index_.emplace(value, nullptr);

        if (!r.second)
            return false;

        queue_.emplace_back(element_type{value, priority}, &(r.first->second));
        std::push_heap(queue_.begin(), queue_.end(), priority_comparator{cmp_});

        assert(std::is_heap(queue_.begin(), queue_.end(), priority_comparator{cmp_}));
        return true;
    }

    void pop()
    {
        assert(!empty());
        assert(std::is_heap(queue_.begin(), queue_.end(), priority_comparator{cmp_}));

        value_type v = top().value;
        std::pop_heap(queue_.begin(), queue_.end(), priority_comparator{cmp_});
        queue_.pop_back();
        index_.erase(v);

        assert(std::is_heap(queue_.begin(), queue_.end(), priority_comparator{cmp_}));
    }

    bool exists(const value_type & value) const
    {
        return index_.find(value) != index_.end();
    }

    bool update(const value_type & value, const priority_type & new_priority)
    {
        assert(std::is_heap(queue_.begin(), queue_.end(), priority_comparator{cmp_}));
        auto i = index_.find(value);
        if (i == index_.end())
            return false;
        queue_element_type * p = i->second;
        if (cmp_(p->get().priority, new_priority))
        {
            p->get().priority = new_priority;
            sift_up(queue_.begin(), queue_.end(),
                    queue_.begin() + (p - &queue_[0]), priority_comparator{cmp_});
        }
        else
        {
            p->get().priority = new_priority;
            sift_down(queue_.begin(), queue_.end(),
                      queue_.begin() + (p - &queue_[0]), priority_comparator{cmp_});
        }

        assert(std::is_heap(queue_.begin(), queue_.end(), priority_comparator{cmp_}));
        return true;
    }

private:
    index_type index_;
    queue_type queue_;
    priority_compare cmp_;
};

Usage example:

#include "updatable_priority_queue.hpp"

#include <iostream>
#include <string>

int main()
{
    updatable_priority_queue<std::string, int, std::greater<int>> q;

    q.insert("six", 6);
    q.insert("seven", 7);
    q.insert("eight", 8);
    q.insert("nine", 9);
    q.insert("ten", 10);
    q.insert("one", 1);
    q.insert("two", 2);
    q.insert("three", 3);
    q.insert("four", 4);
    q.insert("five", 5);

    assert(q.size() == 10);
    assert(q.exists("six"));
    assert(!q.insert("four", 10));

    // sift up
    q.update("seven", 0);
    q.update("five", 5);
    q.update("six", 4);

    // sift down
    q.update("one", 11);
    q.update("four", 4);
    q.update("three", 6);

    while (!q.empty())
    {
        std::cout << q.top().value << '\t' << q.top().priority << std::endl;
        q.pop();
    }
}

Edit: Forgot to mention, sift_up and sift_down algorithms are on separate review here

\$\endgroup\$
1
\$\begingroup\$

Missing headers:

#include <cassert>
#include <functional>      // for std::less
#include <unordered_map>
#include <vector>

The self_reporting type doesn't need two constructors. If we accept by value, we get most of the benefits with less code to maintain (the only benefit to overloading is if we have to deal with types with expensive move, which is far from normal).

self_reporting(value_type v, self_reporting** pp)
    : value(std::move(v)), registry(pp)
{
    report();
}

You could simplify the use of self_reporting by implementing * and -> to give it pointer/wrapper-like syntax, instead of (or as well as) the get() method.

const value_type& operator*() const noexcept
{
    return value;
}

value_type& operator*() noexcept
{
    return value;
}

const value_type* operator->() const noexcept
{
    return &value;
}

value_type* operator->() noexcept
{
    return &value;
}
struct priority_comparator
{
    const priority_compare cmp_;
    bool operator()(const queue_element_type & lhs,
                    const queue_element_type & rhs) const
    {
        return cmp_(lhs->priority, rhs->priority);
    }

The 1-argument constructor of updatable_priority_queue probably ought to be declared explicit.


Since the only use for cmp_ is to create a priority_comparator many times, why not simply create and store that comparator at construction time? Like this:

private:
    /* there's no benefit being a public type */
    struct priority_comparator
    {
        const priority_compare cmp_;
        bool operator()(const queue_element_type & lhs,
                        const queue_element_type & rhs) const
        {
            return cmp_(lhs.get().priority, rhs.get().priority);
        }
    };

    const priority_comparator cmp_;

public:
    explicit updatable_priority_queue(priority_compare cmp = {})
        : cmp_{std::move(cmp)}
    {}

Note that this shouldn't change the run-time size of any instances.

Then the usage-sites all become simpler. For example:

    assert(std::is_heap(queue_.begin(), queue_.end(), cmp_));

(Hmm, in passing, we could encapsulate that into a function - assert(invariant()) is easier to read, safer to modify and clearer in intent.)

Oh, there's one use of the inner cmp_, but that's easily accessed:

    if (cmp_.cmp_(p->priority, new_priority))

(Or you could overload priority_comparator::operator() to compare P objects as well).


Some nice things I liked:

  • I'm pleased to see you using std::swap; so that argument-dependent lookup works correctly in your template methods.
  • You've provided example of use, to make changes easier to test.
  • Asserting the invariant at start and end of the non-const methods could be useful for testing and bug-tracing.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.