第五回-付録 2 : STL による二分木、priority queue

リストが C++ の標準テンプレートライブラリ (Standard Template Library: STL) に含まれていたのと同様に、
二分木や priority queue も STL に含まれている。

ここではその利用例を紹介する。

二分木の例

STL では map によって二分木が利用できる。
似たものとして、multimap、set、multiset などがある。興味のある人は違いを教科書で調べてみると良いだろう。

使用例は以下のようになる。BTree クラスと同様に「学籍番号＆成績」という例でプログラミングした。

#include <iostream>
#include <map>

using namespace std;

typedef map<int, char, less<int> > result; 
                // map は int (学籍番号) の重複を許さないことに注意
                // 重複を許すのは multimap

int main(){

  result r;

  r.insert(result::value_type(5,'B'));
  r.insert(result::value_type(2,'A'));
  r.insert(result::value_type(1,'D'));
  r.insert(result::value_type(4,'F'));
  r.insert(result::value_type(8,'A'));
  r.insert(result::value_type(9,'C'));

  // イテレータの利用
  result::iterator pos;

  for(pos = r.begin(); pos != r.end(); ++pos){
    cout << pos->first << " " << pos->second << "\n"; 
                      // first が key で second が data
  }

  // 学籍番号 5 番の学生の成績は？
   cout << "key=5, data=" << r[5] << "\n";

  return(0);
}

こちらは (ソースに不完全な部分がないので) 6 つのデータ全てが表示される。

priority queue の例

STL には priority queue も存在する。使用例はこちら。
こちらは map と異なり、学籍番号と成績を一つのデータとして扱わねばならないため、
そのためのクラス datapair を作成した。さらに、datapair クラスのオブジェクトの大小比較を行うための関数オブジェクト dataComparison も作成した。

map に比べるとやや複雑になってしまったが、ライブラリを使うと記述量が格段に少なくなることが分かるだろう。

#include <iostream>
#include <queue>

using namespace std;

class datapair{
  int key;
  char data;

  public: 
   datapair(int k,char d):key(k), data(d){}
   int getkey(){return key;}
   char getdata(){return data;}

};

struct dataComparison{
  bool operator () ( datapair * left, datapair * right){
    return left->getkey() > right->getkey(); 
  }
};

typedef priority_queue<datapair *,vector<datapair* >,dataComparison> result;

int main(){

  result r;

  r.push(new datapair(5,'B'));
  r.push(new datapair(2,'A'));
  r.push(new datapair(1,'D'));
  r.push(new datapair(4,'F'));
  r.push(new datapair(8,'A'));
  r.push(new datapair(9,'C'));

  while(!r.empty()){

    cout << r.top()->getdata() << "\n";
                      // 最も学籍番号が小さいデータを表示

    r.pop();          // 実際にはここで削除される。

  }

  return(0);
}

←第五回-付録1：STL におけるリスト

第五回トップページへ

クラスから入る C++ へ戻る