cola de prioridad de acceso aleatorio

Question

de prioridad de la cola

estoy poniendo en práctica un priority_queue mejorada con acceso aleatorio.

template <class T, class Container = std::vector<T> >
class Heap {
public:
    Heap() {}

    Heap(const Container& container) {
        container_ = container;
        std::make_heap(container_.begin(), container_.end());
    }

    Heap<T, Container>& operator=(const Heap<T, Container>& heap) {
        if (this != &heap)
            container_ = heap.container_;

        return *this;
    }

    void push(const T& x) {
        container_.push_back(x);
        std::push_heap(container_.begin(), container_.end());
    }

    void pop() {
        std::pop_heap(container_.begin(), container_.end());
        container_.pop_back();
    }

    const T& top() {
        return container_.front();
    }

    const Container& getContainer() const {
        return container_;
    }

    T& operator[](size_t n) {
        return container_[n];
    }

    typename Container::const_iterator begin() const {
        return container_.begin();
    }

    typename Container::const_iterator end() const {
        return container_.end();
    }

    size_t size() const {
        return container_.size();
    }

    T& base() {
        return container_.back();
    }

    Container::iterator erase(Container::iterator position) {
        return container_.erase(position);
    }

private:
    Container container_;
};

estoy tomando el camino correcto?

• Se ha corregido el constructor unario.
• Mejora de código.

Answer 1

no se ve tan grande para mí:

• El constructor unario debe tomar argumento por referencia const.
• El operador de asignación no comprueba para la auto-asignación.
• El método getContainer() muestra una falta de claridad en la interfaz -? ¿Por qué simplemente exponer el detalle de implementación de esa manera
• Lo más importante es: ¿por qué quiere una "cola de prioridad de acceso aleatorio"

Answer 2

Su método pop () pueden violar el ordenamiento montón. Utilice pop_heap () en lugar de pop_back (). Parece que no puedo encontrar ningún otro fallo en este momento.

Se puede probar fácilmente tal implementación empujando en unos números enteros aleatorios y pop () uno por uno. Usted debe obtener de nuevo en el orden establecido. Esto se conoce como pila de clasificación.

Sugerencias:

• En lugar de devolver una referencia al contenedor podría implementar un iterador const a esta clase.

• Tenga en cuenta que no se debe cambiar la clave del elemento de acceso aleatorio, ya que puede destruir la estructura del montón. Si necesita dicha funcionalidad se debe implementar una función change_key que cambiaría la tecla con seguridad y mantener el orden montón.