標準テンプレートライブラリには、各種アルゴリズムも用意されています。
様々なコンテナに対して、イテレータ経由でアクセスする方法が取られています。
種類も膨大にあるので、いくつか抜粋して紹介します。
まずはソートです。
配列ベースのコンテナに対して使用する事が出来ます。
実は、配列もコンテナの１つです。
イテレータはポインタ変数だと説明しました。
イテレータの代わりに、アドレスを渡す事で用意されたアルゴリズムが使えます。
では、int型の配列を作ってソートするプログラムを作ってみましょう。
各種アルゴリズムを使用するには、algorithmヘッダをインクルードしなければなりません。
<sample program cpp022-01>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
int main()
{
const int COUNT = 10;
int data[COUNT];
srand((unsigned int)time(NULL));
for (int i = 0; i < COUNT; i++) {
data[i] = rand() % 100;
}
std::sort(data, &data[COUNT]);
for (int i = 0; i < COUNT; i++) {
std::cout << data[i] << " ";
}
std::cout << std::endl;
return 0;
}
|
<実行結果>
7 23 39 46 48 65 71 79 81 88 続行するには何かキーを押してください・・・
要素数１０の配列を用意し、乱数を１０個格納しました。
ソートを行うためのsort関数は「名前空間std」に所属しています。
引数を説明しなければなりません。
std::sort(data, &data[COUNT]); |
sort関数の引数は、「先頭アドレス」と「最後のデータの次のアドレス」です。
0 1 2 3 4 5 6 7 8 9 10
+--+--+--+--+--+--+--+--+--+--+
data | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+
↑ ↑
ここと ここのアドレス
「先頭アドレス」は配列名で行けますね。
「最後のデータの次のアドレス」は要素数が１０なのでdata[10]のアドレスを指定すれば良いです。
今まで説明していませんでしたが、イテレータを使う時も同じ考え方です。
例えばベクタを用意して、
it = vecData.begin(); |
と書けば、最初のデータのアドレスがイテレータに入ります。
it = vecData.end(); |
と書けば「最後のデータの次のアドレス」が入ります。
実際にベクタでやってみましょう。
<sample program cpp022-02>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
int main()
{
const int COUNT = 10;
std::vector<int> vecData;
srand((unsigned int)time(NULL));
for (int i = 0; i < COUNT; i++) {
vecData.push_back(rand() % 100);
}
std::sort(vecData.begin(), vecData.end());
for (int i = 0; i < COUNT; i++) {
std::cout << vecData[i] << " ";
}
std::cout << std::endl;
return 0;
}
|
<実行結果>
0 3 23 33 47 48 59 62 85 87 続行するには何かキーを押してください・・・
ベクタの場合は引数にイテレータを使っています。
では、リストではどうでしょう？
<sample program cpp022-03>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <list>
int main()
{
const int COUNT = 10;
std::list<int> lstData;
srand((unsigned int)time(NULL));
for (int i = 0; i < COUNT; i++) {
lstData.push_back(rand() % 100);
}
std::sort(lstData.begin(), lstData.end());
std::list<int>::iterator it;
for (it = lstData.begin(); it != lstData.end(); it++) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
|
<コンパイル結果>
error C2784: 'unknown-type std::operator -(std::move_iterator<_RanIt> &,const std::move_iterator<_RanIt2> &)' : テンプレート 引数を 'std::move_iterator<_RanIt> &' に対して 'std::_List_iterator<std::_List_val<std::_List_simple_types<int>>>' から減少できませんでした
エラーになりました。
実際にはもっと色々なメッセージが表示されいていましたが割愛します。
実はイテレータにも種類があって、リストのイテレータからsort関数は利用できないのです。
リスト構造は配列ベースと異なるため、ソートはリスト自体のメンバ関数として持っています。
アルゴリズムとは離れますが、一応作ってみましょう。
<sample program cpp022-04>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <list>
int main()
{
const int COUNT = 10;
std::list<int> lstData;
srand((unsigned int)time(NULL));
for (int i = 0; i < COUNT; i++) {
lstData.push_back(rand() % 100);
}
lstData.sort();
std::list<int>::iterator it;
for (it = lstData.begin(); it != lstData.end(); it++) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
|
<実行結果>
14 30 31 39 60 78 78 91 92 93 続行するには何かキーを押してください・・・
標準テンプレートライブラリのアルゴリズムを使っていませんのでヘッダファイルは外しました。
簡単に出来ているように見えますが、リストのソートは効率が悪いので、あまり使う事は無いでしょう・・・
さて、これまでのサンプルを見ると、全て昇順ソートだと言う事が分かります。
降順にソートしたい場合どうすれば良いでしょう。
sort関数にはオーバーロードされた関数が１つあります。
元の関数のプロトタイプ宣言は、
void sort(_RanIt _First, _RanIt _Last); |
先頭と最後（の次の）イテレータを渡すようになっています。
オーバーロードされた関数のプロトタイプ宣言は、
void sort(_RanIt _First, _RanIt _Last, _Pr _Pred); |
３番目の引数があります。
ここには、並べ替えの判断基準を設定するのですが、今回はＣ言語風に関数ポインタを設定してみます。
コンテナはベクタを使います。
<sample program cpp022-05>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
bool Compare(const int lhs, const int rhs);
int main()
{
const int COUNT = 10;
std::vector<int> vecData;
srand((unsigned int)time(NULL));
for (int i = 0; i < COUNT; i++) {
vecData.push_back(rand() % 100);
}
std::sort(vecData.begin(), vecData.end(), Compare);
for (int i = 0; i < COUNT; i++) {
std::cout << vecData[i] << " ";
}
std::cout << std::endl;
return 0;
}
bool Compare(const int lhs, const int rhs)
{
if (lhs > rhs) {
return true;
}
return false;
}
|
<実行結果>
95 92 76 71 52 44 43 40 13 2 続行するには何かキーを押してください・・・
これを使えば、構造体のソートなども出来そうですね。
クラスや関数オブジェクトなど、もっとＣ＋＋の知識が増えれば書き方も変わってきます。
少しずつで構いませんので、進んでいきましょう。