RSS
C++編で扱っている C++ は 2003年に登場した C++03
という、とても古いバージョンのものです。C++ はその後、C++11 -> C++14
-> C++17 -> C++20 -> C++23 と更新されています。
なかでも C++11 での更新は非常に大きなものであり、これから C++
の学習を始めるのなら、C++11
よりも古いバージョンを対象にするべきではありません。特に事情がないなら、新しい
C++ を学んでください。 当サイトでは、C++14 をベースにした新C++編を作成中です。
この章の概要です。
STLアルゴリズムは、コンテナの各要素を処理するために用意された関数群です。膨大な数があるので、ここから数章に分けて順次取り上げていきます。
STLアルゴリズムは、メンバ関数ではなく、std名前空間に含まれる通常の関数になっています。処理対象の要素へはイテレータを介してアクセスするようになっており、特定の種類のコンテナに依存しない、高い柔軟性を持っています。
汎用的であるがゆえに、特定の種類のコンテナに対しては非効率になってしまうアルゴリズムもあります。もし、あるコンテナが、STLアルゴリズムの関数と同名のメンバ関数を持っていたら、普通は、メンバ関数版を使った方が効率的です。
ほとんどの STLアルゴリズムは、<algorithm> という標準ヘッダに含まれています。例外的に、第２３章で登場する数値演算関係の STLアルゴリズムについては、<numeric> という標準ヘッダに含まれます。
まず、もっとも基本的かつ重要な for_each関数を取り上げます。
namespace std {
template <typename InputIterator, typename Function>
Function for_each(InputIterator first, InputIterator last, Function f);
}for_each関数は、２つのイテレータで表現される範囲内にある各要素に対して、f を呼び出します。要素を elem と表現すると、順次、f(elem) を呼び出していく関数ということになります。
この先、紹介する他の関数でも同様ですが、関数宣言の型名にも注意してみてください。for_each の場合、イテレータは InputIterator という名前にしており、これは「入力イテレータ」のことです。第１４章でイテレータのカテゴリを取り上げていますが、この分類と一致した名前が付けられています。
たとえば、以下のサンプルプログラムは、対象の各要素を標準出力へ出力します。
#include <algorithm>
#include <iostream>
#include <vector>
void Println(int elem)
{
std::cout << elem << std::endl;
}
int main()
{
std::vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);
std::for_each(v.begin(), v.end(), Println);
}実行結果：
0
1
2for_each関数の戻り値は、第３引数のコピーです。第３引数に通常の関数を渡す場合にはあまり意味がありませんが、関数オブジェクトを使うと、各要素の処理を行いながら情報を蓄積していき、最後に結果を問い合わせるような使い方が可能になります。
#include <algorithm>
#include <iostream>
#include <vector>
class Printer {
public:
Printer() : mCount(0)
{}
void operator()(int elem)
{
std::cout << elem << std::endl;
++mCount;
}
int GetCount() const
{
return mCount;
}
private:
int mCount;
};
int main()
{
std::vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);
const int count = std::for_each(v.begin(), v.end(), Printer()).GetCount();
std::cout << "count: " << count << std::endl;
}実行結果：
0
1
2
count: 3eqaul関数は、ある２つの範囲内に含まれている要素が一致しているかどうかを調べます。
namespace std {
template <typename InputIterator1, typename InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred);
}どちらの形式でも、第１・第２引数が１つの範囲を表現しており、第３引数でもう１つの範囲の開始点を表現します。範囲の大きさは、第１・第２引数によって決まるので、２つ目の範囲の方が小さくならないように注意する必要があります。
第１・第２引数の型と、第３引数の型が異なっていることに注目してください。これは、２つの範囲が、異なる型のコンテナであって構わないことを示しています。たとえば、次のように vector と list の要素を比較できます。
#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
int main()
{
std::vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);
std::list<int> lst;
lst.push_back(0);
lst.push_back(1);
lst.push_back(2);
std::cout << std::boolalpha
<< std::equal(v.begin(), v.end(), lst.begin())
<< std::endl;
}実行結果：
true２つ目の形式の方は、第４引数に関数や関数オブジェクトを渡して、一致比較の条件を指定できるようになっています。ここで指定する関数や関数オブジェクトは、２つの引数を受け取り、結果として bool型の値を返す必要があります。true を返せば一致しているとみなされ、false を返せば不一致であるとみなされます。
なお、後述しますが、このような関数は、叙述関数と呼ばれています。
たとえば、以下の例では、正確に表現できない小さな誤差を許容した比較を行います。
#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
bool equalDouble(double a, double b)
{
return std::abs(a - b) < std::numeric_limits<double>::epsilon();
}
int main()
{
std::vector<double> v;
v.push_back(0.0);
v.push_back(0.0);
v.push_back(1.0);
std::list<double> lst;
lst.push_back(0.0);
lst.push_back(0.0000000000000001);
lst.push_back(0.9999999999999999);
std::cout << std::boolalpha
<< std::equal(v.begin(), v.end(), lst.begin(), equalDouble)
<< std::endl;
}実行結果：
trueequal関数の第４引数のように、比較結果などを bool型で返す関数は、叙述関数（プレディケート）と呼ばれています。また、引数が１つの場合を単項叙述関数、２つの場合を二項叙述関数と呼びます。
equal関数の宣言を見ると、第４引数の型名が「BinaryPredicate」となっていますが、これは、二項(Binary) の叙述関数(Predicate) であることを表しています。
STL は、叙述関数に関して、同じ引数を与えた場合にはつねに同じ結果を返さなければならないと規定しています。そのため、特に関数オブジェクトを使う場合には、メンバ変数が変化しないようにして注意しなければなりません。叙述関数として使う関数オブジェクトでは、operator() をつねに constメンバ関数にするのが安全でしょう。
問題① for_each関数がどのように実装されているか、想像して自力の実装を書いてみてください。
問題② for_each関数を使って、各要素の平均値を計算する処理を作成してください。
問題③ for_each関数や equal関数は、通常の配列に対しても使用できるでしょうか？ 予想を立てた後、実際にプログラムを書いて確かめてください。
新規作成。
次の章へ （第１９章 readonly な STLアルゴリズム）
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |