• 1

• 468
• 2
• 8

• 468
• 2
• 8

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();
 }
}