file d'attente de priorité d'accès aléatoire

Question

continue List to priority queue

Je mettre en œuvre une priority améliorée avec un accès aléatoire.

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

Est-ce que je prends le bon chemin?

• Correction du constructeur unaire.
• Code amélioré.

Answer 1

ne semble pas terrible pour moi:

• Le constructeur unaire devrait prendre l'argument par référence const.
• L'opérateur d'affectation ne vérifie pas l'auto-affectation.
• La méthode getContainer() montre un manque de clarté dans l'interface - pourquoi exposer simplement les détails de l'implémentation comme ça? Plus important encore: pourquoi voulez-vous une "file d'attente prioritaire d'accès aléatoire"?

Answer 2

Votre méthode pop() peut violer l'ordre du tas. Utilisez pop_heap() au lieu de pop_back(). Je n'arrive pas à trouver un autre bug maintenant.

Vous pouvez facilement tester une telle implémentation en introduisant des entiers aléatoires et en les pop() un par un. Vous devriez les récupérer dans l'ordre. C'est ce qu'on appelle le tri de tas.

Suggestions:

• au lieu de retourner un arbitre au conteneur vous pourriez mettre en œuvre un const iterator à cette classe.

• Notez que vous ne devez pas modifier la clé de l'élément accédé aléatoirement car cela risque de détruire la structure de tas. Si vous avez besoin d'une telle fonctionnalité, vous devez implémenter une fonction change_key qui changerait la clé en toute sécurité et maintiendrait l'ordre de tas.