2

優先キューへのリストの継続

ランダムアクセスで改善されたpriority_queueを実装しています。

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

私は正しい道を歩んでいますか？

  • 単項コンストラクタを修正しました。
  • 改善されたコード。
4

2 に答える 2

1

私にはそれほど良く見えません：

  • 単項コンストラクターは、const 参照によって引数を取る必要があります。
  • 代入演算子は自己代入をチェックしません。
  • このgetContainer()メソッドは、インターフェイスが明確でないことを示しています。なぜ、そのような実装の詳細を単純に公開するのでしょうか?
  • 最も重要なのは、なぜ「ランダムアクセス優先キュー」が必要なのですか?
于 2010-12-12T17:45:30.627 に答える
0

pop() メソッドは、ヒープの順序に違反する可能性があります。pop_back() の代わりに pop_heap() を使用してください。今のところ、他のバグを見つけることができないようです。

このような実装は、ランダムな整数をプッシュして 1 つずつ pop() することで簡単にテストできます。ソートされた順序でそれらを取得する必要があります。これはヒープソートとして知られています。

提案:

  • コンテナーに ref を返す代わりに、このクラスに const イテレーターを実装できます。

  • ヒープ構造を破壊する可能性があるため、ランダムにアクセスされる要素のキーを変更しないでください。このような機能が必要な場合は、キーを安全に変更し、ヒープの順序を維持する change_key 関数を実装する必要があります。

于 2010-12-12T17:43:02.163 に答える