C++ STLメモ4 ソート

STLには,当然の様にソート機能があります。ソートは,データの並べ替えで,小さいものから大きいものへ順番を変えたり,大きいものから小さいものへ順番を変える作業です。abc順やあいうえお順に並び替えるのも含みます。

前提知識:
C++ STLメモ1(STL全般について) :
 http://sato-si.at.webry.info/200602/article_1.html

C++ STLメモ2(vector,dequeの違い) :
 http://sato-si.at.webry.info/200604/article_2.html

C++ STLメモ3(list , mapについて) :
 http://sato-si.at.webry.info/200604/article_2.html


ソートをするには,sort(開始位置,終了位置の一つ先 )でできます。開始位置,終了位置は iteratorのランダムアクセス可能なタイプの型を指定します。
ランダムアクセスのiteratorとは普通の配列の要素のポインタや,deque,vectorなどのitratorが,引数に使えます。
STLのdequeやvectorの型の変数 a があれば,
sort(a.begin( ), a.end( ) ); で,全体をソートできます。引数のa.begin( ), a.end( )で指定する位置を変更することで,配列の一部の範囲でソートが出来ます。
sortを使うには #include <algorithm> が必要です。


#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main( )
{
  deque<int> d;
  d.push_back(5);
  d.push_back(3);
  d.push_back(9);

  sort( d.begin( ), d.end( ) );

  for(int i = 0; i < d.size( ); i++) {
    cout << d[i] << endl;
  }
  return 0;
}


ちなみに,listクラスはこのsortを使うことができません。(itertorがランダムアクセス用じゃないから) listクラスには,list用のsortがあります。しかしながら,list自体は,あまりソートには向いていませんので,お勧めしません。(ランダムアクセスが出来ないとソートしにくい)


sort関数は大小関係を < で判別しています。(昇順です。小さいものから大きいものへ並び替える)
降順・昇順を入れ替えたい場合や,別の条件で判別したい場合は,判別処理のための関数オブジェクトを渡すバージョンのsortを使います。

関数オブジェクトとは, operator() ( 引数一覧 ) { } を持つクラスのオブジェクトで,呼び出し方は通常の関数とよく似ているが,関数名がオブジェクト変数となっているものです。具体的には以下の様なコードが使えます。

class Pr
{
public:
  bool operator()(const int& x, const int& y) const {
    return x > y;
  }
};

int main( )
{
  Pr pr;
  int x = 30, y = 20;

/* pr(x,y)はPrクラスの operator()(x, y) がよばれている。 pr という名前の関数があるのではない!! prは,変数名だ。*/
  if( pr(x,y) )
  {
     // x > y は真である
  }

  return 0;
}

STLでは,関数の引数に,内部の処理関数を渡す手法として,この関数オブジェクトを良く使う。bool operator()(const int& x, const int& y) const の int は型にあわせて変更すれば,大体このクラスでソート処理を行える。以下の様にテンプレートにしてしまうのも,いいかも。

template<typename T>
class Prt
{
public:
  bool operator()(const T& x, const T& y) const {
    return x > y;
  }
};


(関数オブジェクトの operator() ( 引数一覧) 引数一覧 は,一般の関数の引数同様,好きな引数を設定できる。ソートに使うときは,比較に使う型を2つ使っている。)

具体的には,以下の様な使い方をする。


#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

class Pr
{
public:
  bool operator()(const int& x, const int& y) const {
    return x > y;
  }
};


int main( )
{
  deque<int> d;
  d.push_back(5);
  d.push_back(3);
  d.push_back(9);

  sort( d.begin( ), d.end( ), Pr( ) );

  for(int i = 0; i < d.size( ); i++) {
    cout << d[i] << endl;
  }

  return 0;
}


これを使うことによって,sortの大小関係比較が < から > に変更された。(昇順から,降順へ変更された。大きいものから小さいものへ並び替える)

これ以外にも,大小関係の判別するキーの値を個別に設定したりするには,これが必要となる。(たとえば名簿だったら,フリガナ順,郵便番号順,年齢順などを切り替える)


他にも,文字列ならば,大文字小文字を区別せずにソートするのも応用すれば作成することが出来ます。

なお,STLの標準の比較の関数オブジェクトは
#include <functional> をすれば,以下の様な使い方が出来ます。
※もちろん形名は,同じでなければなりません。

deque<形名> a;
/* 中略 a.push_back(何とか) */
sort( a.beign(), a.end(), greater<形名>( ) );     // > で判別。(降順)
sort( a.beign(), a.end(), greater_equal<形名>( ) );   // >= で判別。(降順)
sort( a.beign(), a.end(), less<形名>( ) ););      // < で判別。(昇順)
sort( a.beign(), a.end(), less_equal<形名>( ) );    // <= で判別。(昇順)








実は,STLでは,もっとお手軽にソートする方法があります。

それは・・・map や set を普通に使だけです。

なぜか?


map や setは,内部のデータ構造が二分探索木(正確には赤黒木)となっています。
二分探索木は,データ追加時に,ソートに相当する処理を高速で行っています。

(ランダムアクセスできないデータをソートするのにも活用できます。)


つまり,データをロード(入力)する時点で,mapやsetに入れていき,先頭からiteratorで順番に見ていけば,昇順ソート済みとなっているのです。

注意:mapやsetは,同じキーを持つ値を複数もてません。同じキーを持つ場合は,mulitmapやmultisetを使う必要があります。そうなってくると,あまりお手軽ではありません(^^;



// mapで行う,自動ソート

#include <iostream>
#include <map>

using namespace std;


int main( )
{
  map<int, int> mmc;
  mmc[5] = 5;
  mmc[3] = 3;
  mmc[10] = 10;

  map<int, int>::iterator it;
  for(it = mmc.begin( ); it != mmc.end( ); it++) {
    cout << (*it).second << endl;
  }

  return 0;
}

mapのiterator で参照できる型はpairです。mapは,内部の要素をpairを持つ形で管理しています。
pairとは,firstとsecondという名前の2つのメンバ変数を持つ構造体で,map<int,string> ならば,
pairのfirstはint型で,secondはstring型となります。ここでは,secondはint型

このため,mapのiteratorはdequeやlistのiteratorとは異なるタイプなので,注意が必要です。


// 同じことをsetですると(自動ソート)

#include <iostream>
#include <set>

using namespace std;

int main( )
{
  set<int> si;
  si.insert( 5 );
  si.insert( 3 );
  si.insert( 10 );

  set<int>::iterator it;
  for(it = si.begin( ); it != si.end( ); it++) {
    cout << *it << endl;
  }

  return 0;
}


mapよりは,無駄がなくなりました。

setは,データの型=ソートのキーの型
mapはデータの型とソートのキーの型を個別設定できます。
そのため,mapを使えば,クラス型でのソートなどが,sort関数でわざわざ関数オブジェクトを用意したり,operator< などを用意したりしなくても,簡単でお手軽にソートが出来てしまうわけです。


以下に,sort関数を使った時とmapを使った時の違いをプログラムで書きます。MyClassの大小関係を表すのは,int型メンバ変数 val です。それをsort( ) に渡すためには以下の太字のコードが必要となります。
#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

class MyClass
{
  int val;
public:
  MyClass() : val(0) { } // val = 0;
  MyClass(int n) : val(n) { } // val = n;
  MyClass(const MyClass& v) : val(v.val) { } // val = v.val;

  void SetVal(int n) { val = n; }
  int GetVal( ) const { return val; }

friend bool operator<(const MyClass& p1, const MyClass& p2);
/* friend とは,クラスの外からprivateやprotectedなメンバにダイレクトにアクセスを許可する宣言 */
};

/* MyClassのオブジェクト用 大小関係判別関数 MyClass p1, p2; ...
if( p1 < p2 ) { } などで呼ばれる */
bool operator<(const MyClass& p1, const MyClass& p2) {
  return p1.val < p2.val;
}


int main( )
{
  deque<MyClass> dmc;
  dmc.push_back( MyClass(5) );
  dmc.push_back( MyClass(3) );
  dmc.push_back( MyClass(10) );
  sort( dmc.begin( ), dmc.end( ) );
  for(int i = 0; i < dmc.size( ); i++) {
    cout << dmc[i].GetVal() << endl;
  }

  return 0;
}



これが,mapを使うと以下の様になります。


#include <iostream>
#include <map>

using namespace std;

class MyClass
{
  int val;
public:
  MyClass() : val(0) { } // val = 0;
  MyClass(int n) : val(n) { } // val = n;
  MyClass(const MyClass& v) : val(v.val) { } // val = v.val;

  void SetVal(int n) { val = n; }
  int GetVal( ) const { return val; }

};


int main( )
{
  map<int, MyClass> mmc;
  mmc[5] = MyClass(5);
  mmc[3] = MyClass(3);
  mmc[10] = MyClass(10);

  map<int, MyClass>::iterator it;
  for(it = mmc.begin( ); it != mmc.end( ); it++) {
    cout << (*it).second.GetVal() << endl;
  }

  return 0;
}


上記で(*it).second とは,MyClass型で,設定した値そのものです。

setを使う場合は,自分のクラス用のoperator< を用意しなければならないのは,同じです。(以下参照)
つまり,現実的なソートをする場合は,setよりmapで行ったほうが良いことが分かります。(※メモリを節約しなければならないときは,setの方がよいでしょう。しかし,そこまでするなら,通常のsortを使う方が良い可能性が高い。)


setを使うと以下の様になります。


#include <iostream>
#include <set>

using namespace std;

class MyClass
{
  int val;
public:
  MyClass() : val(0) { } // val = 0;
  MyClass(int n) : val(n) { } // val = n;
  MyClass(const MyClass& v) : val(v.val) { } // val = v.val;

  void SetVal(int n) { val = n; }
  int GetVal( ) const { return val; }

friend bool operator<(const MyClass& p1, const MyClass& p2);
/* friend とは,クラスの外からprivateやprotectedなメンバにダイレクトにアクセスを許可する宣言 */
};

/* MyClassのオブジェクト用 大小関係判別関数 MyClass p1, p2; ...
if( p1 < p2 ) { } などで呼ばれる */
bool operator<(const MyClass& p1, const MyClass& p2) {
  return p1.val < p2.val;
}



int main( )
{
  set<MyClass> si;
  si.insert( MyClass(5) );
  si.insert( MyClass(3) );
  si.insert( MyClass(10) );

  set<MyClass>::iterator it;
  for(it = si.begin( ); it != si.end( ); it++) {
    cout << (*it).GetVal() << endl;
  }

  return 0;
}


同じ値のキーを持つデータを扱いたいときは,multimapやmultisetを使います。mapやsetとは使い方がちょっと違います。

この記事へのコメント

この記事へのトラックバック