標準ライブラリpriority_queueの実装

10882 ワード

優先度キューは、通常のキューに比べて、最初にキューに入る要素ではなく、最も優先度の高い要素が最初にキューに挿入されます.
その実装は標準ライブラリが提供するheapアルゴリズムを採用している.このシリーズアルゴリズムは全部で4つの関数を提供した.使用方法は次のとおりです.
まず、コンテナを作成し、要素を入れます.

vector<int> coll;
insertNums(coll, 3, 7);
insertNums(coll, 5, 9);
insertNums(coll, 1, 4);

printElems(coll, "all elements: ");

印刷結果:

all elements: 
3 4 5 6 7 5 6 7 8 9 1 2 3 4

そしてmake_を呼び出しますHeap,このアルゴリズムは[beg,end)内の要素をスタック化する.

make_heap(coll.begin(), coll.end());

printElems(coll, "after make_heap: ");

印刷結果:

after make_heap: 
9 8 6 7 7 5 5 3 6 4 1 2 3 4

pop_を呼び出しますheap,このアルゴリズムは[beg,end)がすでにheapであることを保証しなければならない.そして、スタックの上の要素(実はbeginが指す要素)を最後に置いて、[begin.end-1)内の要素をheapに再調整しなければならない.

pop_heap(coll.begin(), coll.end());
coll.pop_back();
printElems(coll, "after pop_heap: ");

印刷結果:

after pop_heap: 
8 7 6 7 4 5 5 3 6 4 1 2 3

次にpush_を呼び出しますheap,このアルゴリズムは[beg,end−1)がすでにheapであることを保証し,その後[beg,end)全体をheapに調整しなければならない.

coll.push_back(17);
push_heap(coll.begin(), coll.end());

printElems(coll, "after push_heap: ");

印刷結果:

after push_heap: 
17 7 8 7 4 5 6 3 6 4 1 2 3 5

最後にsort_を使いますHeapは[beg,end)をheapから秩序配列に変換するので,[beg,end)がすでにheapであることを前提とする.

sort_heap(coll.begin(), coll.end());
printElems(coll, "after sort_heap: ");

印刷結果:

after sort_heap: 
1 2 3 3 4 4 5 5 6 6 7 7 8 17

完全なテストコードは次のとおりです.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
void insertNums(T &t, int beg, int end)
{
    while(beg <= end)
    {
        t.insert(t.end(), beg);
        ++beg;
    }    
}

template <typename T>
void printElems(const T &t, const string &s = "")
{
    cout << s << endl;
    for(typename T::const_iterator it = t.begin();
        it != t.end();
        ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
}


int main(int argc, char const *argv[])
{
    vector<int> coll;
    insertNums(coll, 3, 7);
    insertNums(coll, 5, 9);
    insertNums(coll, 1, 4);

    printElems(coll, "all elements: ");

    //        heap
    make_heap(coll.begin(), coll.end());

    printElems(coll, "after make_heap: ");

    //           ，        
    pop_heap(coll.begin(), coll.end());
    coll.pop_back();
    printElems(coll, "after pop_heap: ");

    coll.push_back(17);
    push_heap(coll.begin(), coll.end());

    printElems(coll, "after push_heap: ");

    sort_heap(coll.begin(), coll.end());
    printElems(coll, "after sort_heap: ");

    return 0;
}

以上のアルゴリズムに基づいて、標準ライブラリの優先キューpriority_を実現します.Queue、コードは次のとおりです.

#ifndef PRIORITY_QUEUE_HPP
#define PRIORITY_QUEUE_HPP

#include <vector>
#include <algorithm>
#include <functional>

template <typename T, 
          typename Container = std::vector<T>, 
          typename Compare = std::less<typename Container::value_type> >
class PriorityQueue
{
public:
    typedef typename Container::value_type value_type; //  T
    typedef typename Container::size_type size_type;
    typedef Container container_type;
    typedef value_type &reference;
    typedef const value_type &const_reference;


    PriorityQueue(const Compare& comp = Compare(),
                  const Container& ctnr = Container());
    template <class InputIterator>
    PriorityQueue (InputIterator first, InputIterator last,
                   const Compare& comp = Compare(),
                   const Container& ctnr = Container());
    void push(const value_type &val)
    {
        cont_.push_back(val);
        //          
        std::push_heap(cont_.begin(), cont_.end(), comp_); 
    }

    void pop()
    {
        //        ，    
        std::pop_heap(cont_.begin(), cont_.end(), comp_);
        cont_.pop_back();
    }

    bool empty() const { return cont_.empty(); }
    size_type size() const { return cont_.size(); }
    const_reference top() const { return cont_.front(); }

private:
    Compare comp_; //    
    Container cont_; //    
};

template <typename T, typename Container, typename Compare>
PriorityQueue<T, Container, Compare>::PriorityQueue(const Compare& comp,
                                                    const Container& ctnr)
    :comp_(comp), cont_(ctnr)
{
    std::make_heap(cont_.begin(), cont_.end(), comp_); //  
}

template <typename T, typename Container, typename Compare>
template <class InputIterator>
PriorityQueue<T, Container, Compare>::PriorityQueue (InputIterator first, 
                                                     InputIterator last,
                                                     const Compare& comp,
                                                     const Container& ctnr)
    :comp_(comp), cont_(ctnr)
{
    cont_.insert(cont_.end(), first, last);
    std::make_heap(cont_.begin(), cont_.end(), comp_);
}

#endif //PRIORITY_QUEUE_HPP

次のことに気づきました.
1.優先キュー内には、mapおよびsetと一致するソートルールが保存されます.
2.前にheapアルゴリズムについてmake_を除いてHeap以外は、以前に構築されたheapであることを保証する必要があります.ここでは、コンストラクション関数でmake_を呼び出します.heapは、後の様々なheapアルゴリズムが合法であることを保証した.
3.もう一つ、Tが容器のタイプと一致しない場合、例えばPriorityQueue>では、私たちのvalue_typeはintを優先します.結局、私たちが操作しているオブジェクトはコンテナです.
テストコードは次のとおりです.

#include "PriorityQueue.hpp"
#include <iostream>
using namespace std;

int main(int argc, char const *argv[])
{
    PriorityQueue<float> q;
    q.push(66.6);
    q.push(22.3);
    q.push(44.4);


    cout << q.top() << endl;
    q.pop();
    cout << q.top() << endl;
    q.pop();

    q.push(11.1);
    q.push(55.5);
    q.push(33.3);
    q.pop();

    while(!q.empty())
    {
        cout << q.top() << " ";
        q.pop();
    }
    cout << endl;


    return 0;
}

Install netCDF under mac os

メモ帳の日時を簡単に入力するツール