目次
配列 とは
配列 とは、最も基本的なデータ構造のひとつで、同じ型のデータを線形に並べたものだ。 誰もが最初に学ぶデータ構造であり、色々と応用範囲が広い。
パフォーマンス的には、ランダム・アクセスは O(1) と高速だ（どの位置の要素も定数時間で高速にアクセス出来る）。
途中への要素挿入削除は、その箇所以降のデータを移動する必要があり、処理時間は O(N) となるので、要素数が多い場合、挿入削除は行わない方がよい。
C言語では固定長の通常配列がよく使用される。静的なメモリ確保とも呼ばれる。
int ar[100]; // int 型、100個の要素を持つ配列を宣言
ローカル変数として配列を宣言すると、中身は不定になる。
グローバル変数として配列を宣言すると、要素は全て 0 で初期化される。
malloc, free を使って動的にメモリを確保すれば、動的配列を実現できる。
int *ar = (int *)malloc(sizeof(int)*100); // int 型*100個分のメモリを確保
// ar[0] ～ ar[99] を利用可能
free(ar); // 不要になったらメモリ解放
C++ では、通常配列に加えて、固定長配列コンテナクラス std::array を使用することが出来る。
動的配列が必要な場合は std::vectorを使用する。
要素数が多く、かつ先頭にも要素を頻繁に挿入・追加したい場合は std::deque を使用する。
これらはクラス化されており、size() で要素数を取得できるなど、便利な機能がたくさん用意されている（詳細はリンク先を参照）。
また、vector, deque の要素領域は動的に確保されるが、確保したメモリは自動的に解放してくるので安心だ。
#include <vector> // vector を使うためのおまじない
.....
{
std::vector<int> v;
.....
v.resize(123); // 後でサイズを変更したり出来る
} // スコープを抜けると、v が使用したメモリは自動的に解放される
i 番目の要素を ar[i] で参照することが出来る。ただし i は 0 以上の整数。最初の要素は ar[0] だ。
配列の初期化
C/C++ の配列は以下のように、初期化リストを使って、要素を初期化することが出来る。
int ar[] = {1, 2, 3, 4, 5};
C++11 以上であれば、vector, list 等の コンテナクラスも初期化リストを使って以下のように初期化することが出来る。
std::vector<int> ar{1, 2, 3, 4, 5};
要素数
通常配列の要素数は sizeof(ar)/sizeof(ar[0]) で取得出来る。
C++11 以上であれば std::end(ar) - std::begin(ar) で要素数を取得できる。
※ std::begin(), std::end() は C++11 で導入されたマクロのようなもので、配列の先頭位置、最後の要素の次の位置を返す。
C++ コンテナクラス（std::vector, std::array 等）であれば、ar.size() で要素数を取得出来る。
上記が返す値の型は符号なし整数（size_t）である。
C/C++ では配列のサイズを越えて要素をアクセスしているかどうかを自動的にはチェックしてくれない、 必要があれば、自分でそのチェックを行わなくてはいけない。
全要素に対するループ
全要素に対するループは、以下のように記述する。通常配列では ar.size() とは書けないので、前節で紹介したものに置き換える必要がある。 ※ int にキャストしてるのは、size() が返す型が符号無しのために、警告が出るのを防ぐためだ。ループ変数として int ではなく unsigned int を使ってもよい。
for(int i = 0; i < (int)ar.size(); ++i) {
ar[i] を参照・変更;
}
上記のループ条件は、添字がサイズより小さいかどうかで判断しているが、下記のように、サイズに等しくなるまでループするという書き方もある。
こちらの書き方であれば、std::list::iterator の様に大小比較が出来ないイテレータでも大丈夫だ。
※ イテレータとはなんらかの要素を指し示すもので、ポインタを抽象化したものだ。詳しくは ここ を参照。
for(int i = 0; i != ar.size(); ++i) {
ar[i] を参照・変更;
}
上記は、最初の要素から最後の要素までをループする書き方だったが、逆に最後の要素から最初の要素までをループしたい場合は、下記の様に記述することが出来る。
for(int i = ar.size(); --i >= 0; ) {
ar[i] を参照・変更;
}
コンテナクラスであれば、イテレータを使って要素にアクセスすることも可能だが、配列類の場合はその必然性が無いので、
普通の配列と同じように [] 演算子を使った方が、ソースが分かりやすくなる場合がある。
あとで std::list などに交換する可能性があるのであれば、イテレータを用いておいた方が、変更コストを抑えられる可能性がある。
しかし、コンテナを自由に取り替えられるというのは幻想にすぎない（Scott Meyers氏談）
ので、無理やりイテレータを使うことはないと考えている。
コンテナクラス v;
for(auto itr = v.begin(); itr != v.end(); ++itr) {
*itr を参照・変更;
}
添字ではなくポインタでループすることも出来る。
std::vector<int> v(10); // サイズ10個の動的配列
const int *first = &v[0]; // 最初の要素へのポインタ
const int *last = &v[v.size()]; // 最後の要素の次へのポインタ
while( first != last ) { // 最後の要素になるまでループ
std::cout << *first << "\n";
++first;
}ore
範囲指定
配列の一部の範囲を指定する方法には2種類ある。
- 範囲の先頭へのイテレータ・ポインタと要素数を指定する
- 範囲の先頭へのイテレータ・ポインタと範囲の最後の要素の次へのイテレータ・ポインタを指定する
後者の場合、範囲の最後の要素へのイテレータ・ポインタではなく、その次へのものだと言うことをよく理解しておいて欲しい。
例えば「int a[100]」という通常配列があり、a[10]～a[14] までの5個の要素の範囲を指定する場合、 前者の方法では「&a[10], 5」となり、後者であれば「&a[10], &a[15]」となる。
「vector<int> v(100)」の場合、v[10]～v[14] の範囲をイテレータで示すと、前者は「v.begin()+10, 5」、後者は「v.begin()+10, v.begin()+15」となる。
前者を「first, sz」、後者を「first, last」で表すと、「last - first = sz」という関係がある。 なので、範囲が空かどうかを判定するには last - first が0かどうかを見るとよい。ただし、ランダムアクセス可能なイテレータ以外は差分計算できないので、 「first == last」かどうかで範囲が空かどうか、「first != last」で範囲が空でないかどうかを判定するのが標準的な書き方だ。
C++標準アルゴリズムは、後者の範囲指定方法を採用している。
[first, last) の範囲処理するには、以下の書き方を使う。
※ [first, last) は範囲を指定する数学的な記法である。[first は、fisrtを含み（「以上」を意味する）、(first は first を含まない。
同様に last] は last を含み（「以下」を意味する）、last) は last を含まない（「未満」を意味する）ことを意味する。
while( first != last ) {
*first を参照・または変更
++first;
}
演習問題：
- int型、要素数 123個 の通常配列を宣言し、for文を使って、要素の値を 0, 1, 2, ... 122 に初期化しなさい。
- int型、要素数 123個 の vector オブジェクトを宣言し、for文を使って、要素の値を 0, 1, 2, ... 122 に初期化しなさい。
- 最初と最後の要素の次への const int* 型ポインタ first, last をとり、範囲 [first, last) の要素を全て表示する関数 void print(const int *first, const int *last) を定義し、動作確認しなさい。
- const vector<int> &v を引数にとり、その要素を全て表示する関数 void print(const vector<int> &v) を定義し、動作確認しなさい。
const int SZ = 123;
int ar[SZ];
for(int i = 0; i < SZ; ++i) {
ar[i] = i;
}
const int SZ = 123;
std::vector<int> ar(SZ);
for(int i = 0; i < SZ; ++i) {
ar[i] = i;
}
void print(const int *first, const int *last) {
while( first != last ) {
std::cout << *first++ << " ";
}
std::cout << "\n";
}
void print(const vector<int> &v) {
for(int i = 0; i < (int)v.size(); ++i) {
std::cout << v[i] << "\n";
}
std::cout << "\n";
}
要素を参照するだけのアルゴリズム
以下に、要素を参照するだけ（要素の値を変更しない）の代表的なアルゴリズムをいくつか上げておく。
合計・平均・標準偏差
まずはよくある例で、配列に入っている要素の合計・平均・
標準偏差を求めるアルゴリズムだ。
※ 「標準偏差」とは、データ群のばらつき度合いを表す値。標準偏差をσとすると、統計的には平均±1.96*σ の範囲に95%のデータが存在することになる。
配列要素の合計を計算するコードは以下のように書ける。
std::vector<int> ar{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int sum = 0; // 合計を求める変数
for(int i = 0; i < (int)ar.size(); ++i) { // 全部の要素について
sum += ar[i]; // 合計に追加
}
std::cout << "sum = " << sum << "\n"; // 結果を表示
合計を求める変数を用意し、0に初期化しておき、全要素をループして、その変数に要素を足し込んでいけば、合計を求めることが出来る。
std::vector<int> ar{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int sum = 0; // 合計を求める変数
int sum2 = 0; // 自乗合計を求める変数
int N = ar.size();
for(int i = 0; i < N; ++i) { // 全部の要素について
sum += ar[i]; // 合計に追加
sum2 += ar[i]*ar[i];
}
double ave = (double)sum / N; // 平均
double stdev = sqrt((double)sum2/N - ave*ave); // 標準偏差
std::cout << "sum = " << sum << "\n"; // 結果を表示
std::cout << "ave = " << ave << "\n";
std::cout << "stdev = " << stdev << "\n";
上記は、合計・平均・標準偏差を求めるコードの例だ。 ar[i] だけでなく ai[i]^2 の合計も求めておく。あとは、標準偏差の公式どおりに計算するだけだ。
単に合計を求めるだけであれば、C++標準アルゴリズムの accumulate() を使うとよい。
第１引数に開始位置、第２引数に最後の要素の次の位置、第３引数は初期値で通常は0を指定する。
std::vector<int> ar{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int sum = std::accumulate(ar.begin(), ar.end(), 0);
// 通常配列との統一性から以下のような記述が推奨されてはいるが、筆者は上記の方がなんとなく好きだ
//int sum = std::accumulate(std::begin(ar), std::end(ar), 0);
accumulate() は通常配列に対しても使用できる。
通常配列は begin(), end() メンバ関数が無いので、std::begin(配列名), std::end(配列名) を使用するしかない。
int ar[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int sum = std::accumulate(std::begin(ar), std::end(ar), 0);
演習問題
- 型 int で要素数１万個の配列を作り、要素を [0, 99] の範囲の一様乱数でみたし、合計・平均・標準偏差を求めなさい。
ただし、乱数は rand(), random_device, メルセンヌツイスター のそれぞれを使用し、結果を比較しなさい。
#include <iostream>
#include <random>
using namespace std;
void printAveSD(const int ar[], int N)
{
int sum = 0;
int sum2 = 0;
for (int i = 0; i < N; ++i) {
sum += ar[i];
sum2 += ar[i] * ar[i];
}
double ave = (double)sum / N; // 平均
double std = sqrt((double)sum2/N - ave*ave); // 標準偏差
std::cout << "sum = " << sum << "\n";
std::cout << "ave = " << ave << "\n";
std::cout << "sum2 = " << sum2 << "\n";
std::cout << "std = " << std << "\n";
}
int main()
{
const int N = 100;
int ar[N];
for (int i = 0; i < N; ++i) {
ar[i] = rand() % 100; // [0, 99]
}
printAveSD(ar, N);
std::random_device rnd; // 乱数生成器
for (int i = 0; i < N; ++i) {
ar[i] = rnd() % 100; // [0, 99]
}
printAveSD(ar, N);
std::mt19937 mt(rnd()); // メルセンヌ・ツイスタ 擬似乱数生成器
for (int i = 0; i < N; ++i) {
ar[i] = mt() % 100; // [0, 99]
}
printAveSD(ar, N);
return 0;
}
最大値・最小値
配列に入っている要素の最大値・最小値を求めるのもよくある話だ。
最大値・最小値を入れる変数を宣言し、それぞれをその型の最小値・最大値で初期化しておく。
あとは、全要素をループし、要素と最大値・最大値を比べ、大きければ・小さければ変数を更新する。
比較・更新部分は「maxv = srd::max(maxv, ar[i]);」と書くことも出来る。
std::vector<int> ar{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int maxv = INT_MIN;
int minv = INT_MAX;
for(int i = 0; i < (int)ar.size(); ++i) {
if( ar[i] > maxv )
maxv = ar[i];
if( ar[i] < minv )
minv = ar[i];
}
std::cout << "min = " << minv << "\n";
std::cout << "max = " << maxv << "\n";
演習問題
- 型 int で要素数100個の配列を作り、要素を [0, 9999] の範囲の一様乱数でみたし、最大値・最小値を求めなさい。
#include <iostream>
#include <array>
#include <random>
int main() {
std::random_device rnd;
std::array<int, 100> ar;
for(int i = 0; i != ar.size(); ++i)
ar[i] = rnd() % 10000;
int maxv = INT_MIN;
int minv = INT_MAX;
for(int i = 0; i != ar.size(); ++i) {
maxv = std::max(maxv, ar[i]);
minv = std::min(minv, ar[i]);
}
cout << "max = " << maxv << "\n";
cout << "min = " << minv << "\n";
return 0;
}
個数を数える
配列に入っている特定の値の要素を数えたい場合もままある。
そのような場合は、カウントする変数（これをカウンタと呼ぶ）を用意し、0 に初期化しておき、
全要素をループし、要素が条件を満たせばカウンタをインクリメントする。
std::vector<int> ar{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int nEven = 0; // 偶数の個数
for(int i = 0; i != ar.size(); ++i) {
if( ar[i] % 2 == 0 ) // 偶数ならば
++nEven; // カウンタをインクリメント
}
std::cout << "nEven = " << nEven << "\n";
標準アルゴリズムの std::count(first, last, val) を用いて、個数を数えることも出来る。
第1, 2引数の first, last で個数を数える範囲 [first, last) を指定し、第３引数に個数を数える要素の値を指定する。
#include <algorithm>
.....
std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int cnt = std::count(v.begin(), v.end(), 1); // 1 の個数を数える
条件判定を行う関数を用意しておけば、指定条件の個数を数えることが出来る。
#include <algorithm>
bool isEven(int x) { return x % 2 == 0; } // 偶数かどうかを判定する関数
.....
std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int cnt = std::count_if(v.begin(), v.end(), isEven); // 偶数の個数を数える
第３引数には、関数オブジェクト（ファンクタとも呼ばれる）を渡すことも出来る。
関数オブジェクトとは、以下の例の様に operator()() が定義されたクラスのことだ。
struct IsEven {
bool operator()(int x) { return x % 2 == 0; } // 偶数かどうかを判定
};
.....
std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int cnt = std::count_if(v.begin(), v.end(), IsEven()); // 偶数の個数を数える
簡単な判定関数の場合、C++11以上であれば、ラムダ式を使った方がコードがわかりやすくなる。
C++11 未満では、関数オブジェクトを渡すにはファンクタが必要だったが、ちょっとまんどくさかった。
ラムダ式を使えば関数オブジェクトに対応するものを簡潔に記述することが出来る。
ラムダ式とは [](仮引数) { 関数本体 } という形式で、関数をオブジェクトとして定義するものだ。
int cnt = std::count_if(v.begin(), v.end(), [](int x) { return x%2 == 0; }); // 偶数の個数を数える
演習問題
- 個数を数えるサンプルコードをビルドし、正しく動作することを確認しなさい。
- 型 int、要素数１万の配列を作り、要素を [0, 9] の範囲の一様乱数でみたし、要素の値が0～9それぞれの個数を数え、表示しなさい。
#include <iostream>
#include <vector>
#include <random>
using namespace std;
int main()
{
std::random_device rnd; // 乱数生成器
const int N = 10000; // 配列要素数
const int RAND_UPPER = 10; // 乱数値上限 [0, RAND_UPPER)
std::vector<int> v(N);
for (auto itr = v.begin(); itr != v.end(); ++itr) {
*itr = rnd() % RAND_UPPER; // 乱数設定
}
std::vector<int> cnt(RAND_UPPER); // カウンター用配列
for (auto itr = v.begin(); itr != v.end(); ++itr) {
cnt[*itr] += 1; // 各値の個数をカウント
}
for (int i = 0; i != cnt.size(); ++i) {
std::cout << i << ": " << cnt[i] << "\n";
}
return 0;
}
線形探索
前から、または後ろから一つづつチェックすること。
処理時間は O(N) だ。
以下は、先頭から要素を検索し、発見した場合はそのインデックス（[0, size()) の範囲）を返し、見つからなかった場合は -1 を返す関数の例だ。
int find(const std::vector<int> &v, int val)
{
for(int i = 0; i != v.size(); ++i) {
if( v[i] == val ) // 同じ値の要素を発見した場合
return i;
}
return -1; // 発見できなかった場合
}
配列の先頭からではなく、末尾から検索したい場合は、以下のように記述するとよい。
int find(const std::vector<int> &v, int val)
{
for(int i = v.size(); --i >= 0;) {
if( v[i] == val ) // 同じ値の要素を発見した場合
return i;
}
return -1; // 発見できなかった場合
}
C++標準アルゴリズムには線形探索のためのアルゴリズムも用意されている。
std::find(first, last, value) は、[first, last) の範囲を検索し、value を発見した場合は、そこへのイテレータを、発見できなかった場合は、last を返す。
std::vector<int> ar{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
auto itr = std::find(ar.begin(), ar.end(), 5); // 5 を検索
if( itr != ar.end() ) {
// 発見出来た場合
} else {
// 発見出来なかった場合
}
std::find() が便利なのは、通常配列に対しても同様にコール出来るという点だ。
int ar[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
auto itr = std::find(std::begin(ar), std::end(ar), 5); // 5 を検索
if( itr != end(ar) ) {
// 発見出来た場合
} else {
// 発見出来なかった場合
}
※ コンテナクラスは オブジェクト.begin() で先頭位置へのイテレータを取得できるが、通常配列には begin() メンバ関数が無い。 そこで、std::begin(配列名) という書き方を使用する。
ううむ、こうして見ると、コンテナクラスでも begin(v), end(v) を使った方がいいような気がしてきだぞ・・・
値を検索するだけでなく、std::find_if(first, last, func) を使えば、条件に合う要素を探すこともできるぞ。
第1, 2引数で範囲を、第3引数で条件を与える関数へのポインタ、または関数オブジェクトを渡す。
下記は、偶数を検索する例だ。
int ar[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
auto itr = std::find_if(begin(ar), end(ar), [](int x) { return x%2 == 0; }); // 偶数を検索
if( itr != end(ar) ) {
// 発見出来た場合
} else {
// 発見出来なかった場合
}
演習問題：
- 引数に first, last を取り、[first, last) の範囲で、ix+1 番目要素が、ix 番目要素のちょうど２倍になっている（ar[ix] * 2 == ar[ix+1]）位置（ix）へのポインタを返す関数
const int *find_twice(const int *first, const int *last) を実装し、動作確認しなさい。
例：{1, 1, 3, 2, 4, 5} であれば、2 の位置（すなわち ix = 3 へのポインタ）を返す
次がちょうど２倍になっている要素が無い場合は、last を返しなさい。
const int *find_twice(const int *first, const int *last)
{
if( first == last ) return last;
int prev = *first++; // ひとつ前の値
while( first != last ) {
if( *first == prv * 2 ) // 一つ前の値の倍だった時
return first - 1; // ひとつ前のアドレスを返す
prev = *first++;
}
return last;
}
// 別解
const int *find_twice(const int *first, const int *last)
{
if( first == last ) return last; // 範囲が空だった場合
auto prev = last;
if( first == --prev ) reutrn last; // 要素が一つだけだった場合
while( first != prev ) {
if( *first * 2 == *(first + 1) ) // 次の値が２倍だった時
return first; // そのアドレスを返す
++first;
}
return last;
}
二分探索
二分探索は、配列要素が昇順にソートされている場合に利用できるアルゴリズムだ。
検索範囲の中央位置の値と検索する値を比べ、検索する値の方が小さければ前半を検索範囲に、値の方が大きければ後半を検索範囲にし、
検索範囲が０になるまで再帰的に検索する。
例えば、{1, 2, 3, 4, 5, 6, 7, 8, 9} という配列があり、2 を検索する場合を考える。
配列の中央は 5 なので、5 と 2 を比べる。2 の方が小さいので、マッチする値は、存在するとすれば前半の {1, 2, 3, 4} の中にしか存在しないので、
前半のみを検索対象にすればよい。
{1, 2, 3, 4} は要素数が偶数であり中央が無いが、先頭＋切り捨て(要素数/2) で中央位置を決めるとすると、3 が中央位置となる。これは検索する値より大きいので、
また前半の {1, 2} が検索対象となる。次は 2 が中央値となり、検索する値とマッチすることになる。
線形探索の処理時間は O(N) であるが、「二分探索」を行うことで、O(Log2 N) と高速に検索を行うことが出来る。
※ 被検索データ数が千倍になると O(N) では千倍の処理時間を要するが、O(Log2 N) であれば、約10倍の処理時間で済む。
一般的に、要素を昇順に並べ替えるには O(N*Log2 N) の時間がかかるので、毎回ソートを行ってから二分探索を行うと、
合計の処理時間はかえって増大する。
が、データが変更されず、同じデータを何回も検索する場合は、最初に１回だけソートを行って、その後何度も二分探索を行った方が、
毎回線形探索するよりもトータルで高速になる。
ちなみに、配列ではなく、要素が順序付けされた二分木のデータ構造を用いると、挿入・削除・検索時間が全て O(Log2 N) になる。
データの挿入・削除と検索が同時に行われるような場合は、ソート済み配列を二分探索するよりも速度が速くなることがある。
二分木データ構造を用いたものとして、C++ 標準クラスでは set が用意されているので、こちらも参照しておいて欲しい。
下記は、二分探索を用いて、要素が範囲に含まれるかどうかを判定する関数の実装例だ。
検索範囲を引数にとり、中央値と比べ、自分自身を再帰的にコールしている。
再帰コールを1回行う度に、検索範囲は半分になる。なので、再帰コールの深さは最大 Log2 N （程度）となる。
// [first, last) を二分探索、要素が範囲に含まれるかどうかを判定
bool binary_search(const int *first, const int *last, int val)
{
if( first >= last ) // 範囲が空
return false; // 発見できなかった場合
const int *ptr = first + (last - first) / 2; // 中央位置へのポインタ、last = first + 1 の場合は、ptr = first となる
if( *ptr == val )
return true; // 発見
if( val < *ptr ) // 検索している要素は ptr よりも前にある場合
return binary_search(first, ptr, val);
else // 検索している要素は ptr よりも後ろにある場合
return binary_search(ptr + 1, last, val);
}
下記は、要素があるかどうかだけでなく、存在する場合は、それへのポインタを返す関数の実装例だ。
この実装例では、{1, 1, 2, 3} のようにデータに重複があると、どれかへのポインタを返すので、場合によっては不都合が起こる。
// [first, last) を二分探索、データに重複があると、どれかへのポインタを返す
const int *binary_search_ptr(const int *first, const int *last, int val)
{
if( first >= last )
return 0; // 発見できなかった場合
const int *ptr = first + (last - first) / 2; // 中央位置へのポインタ、last = first + 1 の場合は、ptr = first となる
if( *ptr == val )
return ptr; // 発見
if( val < *ptr ) // 検索している要素は ptr よりも前にある場合
return binary_search_ptr(first, ptr, val);
else // 検索している要素は ptr よりも後ろにある場合
return binary_search_ptr(ptr + 1, last, val);
}
C++標準アルゴリズムには bool std::binary_search(first, last, val) があり、val が範囲 [first, last) に含まれるかどうかを判定してくれる。
これは、先の binary_search() と同じものだ。
本節で示した関数の引数型は const int * 固定であったが、標準アルゴリズムの方はテンプレート関数になっていて、任意の型へのポインタ、
またはランダムアクセス可能なイテレータを指定することが出来る。
検索を行いマッチする位置を返すものとしては std::lower_bound(first, last, val), std::upper_bound(first, last, val) がある。
前者は val 以上の最初の値へのイテレータを、後者は val より大きい最初の値へのイテレータを返す。
例えば、ar[] = {1, 2, 2, 3} に対し、lower_bound(begin(ar), end(ar), 2) をコールすると &ar[1] が、
upper_bound(begin(ar), end(ar), 2) をコールすると &ar[3] が返って来る。
ご理解いただけるであろうか？
以下は、lower_bound(), upper_bound() を関数で実装した例だ。
// *ptr >= val となる最初の ptr を検索
const int *lower_bound(const int *first, const int *last, int val)
{
if( first >= last ) return last;
const int *ptr = first + (last - first) / 2; // 中央位置へのポインタ、last = first + 1 の場合は、ptr = first となる
if( val <= *ptr )
return lower_bound(first, ptr, val);
else
return lower_bound(ptr + 1, last, val);
}
// *ptr > val となる最初の ptr を検索
const int *upper_bound(const int *first, const int *last, int val)
{
if( first >= last ) return last;
const int *ptr = first + (last - first) / 2; // 中央位置へのポインタ、last = first + 1 の場合は、ptr = first となる
if( val < *ptr )
return upper_bound(first, ptr, val);
else
return upper_bound(ptr + 1, last, val);
}
また、標準アルゴリズムには std::equal_range(first, last, val) というものもあり、これはマッチする範囲、 すなわち lower_bound() と upper_bound() が返す値のペアを返す。
演習問題：
- この節で定義した lower_bound(), upper_bound() のテストプログラムを作成し、正しく動作していることを確認しなさい。 （もし、バグをみつけたら筆者に報告してね ;^p）
- int型、10個の要素、それらが昇順に並んでいる配列を作り、std::binary_search(), std::lower_bound(), std::upper_bound() の動作を確認するプログラムを作り、試してみなさい。
- int型、100万個の要素の [0, 100万) の範囲のランダムな要素を持つ配列を作り、ソートを行った後、 [0, 100万) のランダムな値を先頭の1万個、10万個、100万個全体のそれぞれから std::binary_search で二分検索する場合と線形探索する場合の処理時間を比較しなさい。 ※ ヒント：配列 ar のソートは std::sort(begin(ar), end(ar)); で行うことが出来る。
- std::pair<const int *, const int *> equal_range(const int *first, const int *last, int val) を自分で実装し、動作確認しなさい。
int main()
{
std::vector<int> v{10, 20, 20, 30, 40, 60, 60, 60, 90, 100}; // 要素数10個
const int SZ = v.size();
auto begptr = &v[0];
auto endptr = &v[0] + SZ;
auto ptr = ::lower_bound(begptr, endptr, 5);
if( ptr == begptr )
cout << "OK\n";
else
cout << "NG\n";
ptr = ::lower_bound(begptr, endptr, 10);
if( ptr == begptr )
cout << "OK\n";
else
cout << "NG\n";
ptr = ::lower_bound(begptr, endptr, 15);
if( ptr == begptr + 1)
cout << "OK\n";
else
cout << "NG\n";
ptr = ::lower_bound(begptr, endptr, 20);
if( ptr == begptr + 1)
cout << "OK\n";
else
cout << "NG\n";
ptr = ::lower_bound(begptr, endptr, 60);
if( ptr == begptr + 5)
cout << "OK\n";
else
cout << "NG\n";
ptr = ::lower_bound(begptr, endptr, 100);
if( ptr == begptr + 9)
cout << "OK\n";
else
cout << "NG\n";
ptr = ::lower_bound(begptr, endptr, 110);
if( ptr == begptr + 10)
cout << "OK\n";
else
cout << "NG\n";
//std::vector<int> v{10, 20, 20, 30, 40, 60, 60, 60, 90, 100}; // 要素数10個
ptr = ::upper_bound(begptr, endptr, 5);
if( ptr == begptr )
cout << "OK\n";
else
cout << "NG\n";
ptr = ::upper_bound(begptr, endptr, 10);
if( ptr == begptr + 1) // 20 の位置
cout << "OK\n";
else
cout << "NG\n";
ptr = ::upper_bound(begptr, endptr, 15);
if( ptr == begptr + 1) // 20の位置
cout << "OK\n";
else
cout << "NG\n";
ptr = ::upper_bound(begptr, endptr, 20);
if( ptr == begptr + 3) // 30の位置
cout << "OK\n";
else
cout << "NG\n";
ptr = ::upper_bound(begptr, endptr, 60);
if( ptr == begptr + 8) // 90 の位置
cout << "OK\n";
else
cout << "NG\n";
ptr = ::upper_bound(begptr, endptr, 100);
if( ptr == begptr + 10)
cout << "OK\n";
else
cout << "NG\n";
ptr = ::upper_bound(begptr, endptr, 110);
if( ptr == begptr + 10)
cout << "OK\n";
else
cout << "NG\n";
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
std::vector<int> v{10, 20, 20, 30, 40, 60, 60, 60, 90, 100}; // 要素数10個
const int SZ = v.size();
auto begptr = &v[0];
auto endptr = &v[0] + SZ;
if( !std::binary_search(begptr, endptr, 5) )
cout << "OK\n";
else
cout << "NG\n";
if( std::binary_search(begptr, endptr, 10) )
cout << "OK\n";
else
cout << "NG\n";
if( !std::binary_search(begptr, endptr, 15) )
cout << "OK\n";
else
cout << "NG\n";
if( std::binary_search(begptr, endptr, 20) )
cout << "OK\n";
else
cout << "NG\n";
if( std::binary_search(begptr, endptr, 30) )
cout << "OK\n";
else
cout << "NG\n";
if( std::binary_search(begptr, endptr, 40) )
cout << "OK\n";
else
cout << "NG\n";
if( !std::binary_search(begptr, endptr, 50) )
cout << "OK\n";
else
cout << "NG\n";
if( std::binary_search(begptr, endptr, 60) )
cout << "OK\n";
else
cout << "NG\n";
if( !std::binary_search(begptr, endptr, 70) )
cout << "OK\n";
else
cout << "NG\n";
if( std::binary_search(begptr, endptr, 90) )
cout << "OK\n";
else
cout << "NG\n";
if( std::binary_search(begptr, endptr, 100) )
cout << "OK\n";
else
cout << "NG\n";
if( !std::binary_search(begptr, endptr, 110) )
cout << "OK\n";
else
cout << "NG\n";
//std::vector<int> v{10, 20, 20, 30, 40, 60, 60, 60, 90, 100}; // 要素数10個
auto ptr = std::lower_bound(begptr, endptr, 5);
if( ptr == begptr )
cout << "OK\n";
else
cout << "NG\n";
ptr = std::lower_bound(begptr, endptr, 10);
if( ptr == begptr )
cout << "OK\n";
else
cout << "NG\n";
ptr = std::lower_bound(begptr, endptr, 15);
if( ptr == begptr + 1)
cout << "OK\n";
else
cout << "NG\n";
ptr = std::lower_bound(begptr, endptr, 20);
if( ptr == begptr + 1)
cout << "OK\n";
else
cout << "NG\n";
ptr = std::lower_bound(begptr, endptr, 60);
if( ptr == begptr + 5)
cout << "OK\n";
else
cout << "NG\n";
ptr = std::lower_bound(begptr, endptr, 100);
if( ptr == begptr + 9)
cout << "OK\n";
else
cout << "NG\n";
ptr = std::lower_bound(begptr, endptr, 110);
if( ptr == begptr + 10)
cout << "OK\n";
else
cout << "NG\n";
//std::vector<int> v{10, 20, 20, 30, 40, 60, 60, 60, 90, 100}; // 要素数10個
ptr = std::upper_bound(begptr, endptr, 5);
if( ptr == begptr )
cout << "OK\n";
else
cout << "NG\n";
ptr = std::upper_bound(begptr, endptr, 10);
if( ptr == begptr + 1) // 20 の位置
cout << "OK\n";
else
cout << "NG\n";
ptr = std::upper_bound(begptr, endptr, 15);
if( ptr == begptr + 1) // 20の位置
cout << "OK\n";
else
cout << "NG\n";
ptr = std::upper_bound(begptr, endptr, 20);
if( ptr == begptr + 3) // 30の位置
cout << "OK\n";
else
cout << "NG\n";
ptr = std::upper_bound(begptr, endptr, 60);
if( ptr == begptr + 8) // 90 の位置
cout << "OK\n";
else
cout << "NG\n";
ptr = std::upper_bound(begptr, endptr, 100);
if( ptr == begptr + 10)
cout << "OK\n";
else
cout << "NG\n";
ptr = std::upper_bound(begptr, endptr, 110);
if( ptr == begptr + 10)
cout << "OK\n";
else
cout << "NG\n";
getchar();
}
// ソート済み範囲を線形探索
bool linear_search(const int *first, const int *last, int val)
{
while( first != last ) {
if( *first == val ) // 発見
return true;
if( *first > val ) // ソート済みなので、これ以降にはマッチするものは無い
break;
++first;
}
return false;
}
void measure_linear_srch(const int *first, const int *last)
{
std::random_device rnd; // 乱数生成器
const int RAND_UPPER = 1000*1000; // 乱数範囲 [0, RAND_UPPER)
const int LOOP = 100; // 100回検索して、平均処理時間を求める
auto start = std::chrono::system_clock::now(); // 計測スタート時刻を保存
for (int i = 0; i < LOOP; ++i) {
int r = rnd() % RAND_UPPER;
volatile bool b = ::linear_search(first, last, r); // volatile は最適化でこの行が消されないため
}
auto end = std::chrono::system_clock::now(); // 計測終了時刻を保存
auto dur = end - start; // 要した時間を計算
// 要した時間をミリ秒（1/1000秒）に変換して表示
std::cout << (double)std::chrono::duration_cast(dur).count()/LOOP << " milli sec \n";
}
void measure_bin_srch(const int *first, const int *last)
{
std::random_device rnd; // 乱数生成器
const int RAND_UPPER = 1000*1000; // 乱数範囲 [0, RAND_UPPER)
const int LOOP = 100; // 100回検索して、平均処理時間を求める
auto start = std::chrono::system_clock::now(); // 計測スタート時刻を保存
for (int i = 0; i < LOOP; ++i) {
int r = rnd() % RAND_UPPER;
volatile bool b = std::binary_search(first, last, r); // volatile は最適化でこの行が消されないため
}
auto end = std::chrono::system_clock::now(); // 計測終了時刻を保存
auto dur = end - start; // 要した時間を計算
// 要した時間をミリ秒（1/1000秒）に変換して表示
std::cout << (double)std::chrono::duration_cast(dur).count()/LOOP << " milli sec \n";
}
int main() {
std::random_device rnd; // 乱数生成器
const int RAND_UPPER = 1000*1000; // 乱数範囲 [0, RAND_UPPER)
std::vector<int> v(1000*1000); // 100万個
for (int i = 0; i != v.size(); ++i) {
v[i] = rnd() % RAND_UPPER; // [0, RAND_UPPER) 範囲乱数生成
}
std::sort(v.begin(), v.end()); // 昇順にソート
measure_bin_srch(&v[0], &v[0] + 10000); // 先頭の1万個の検索時間を計測
measure_bin_srch(&v[0], &v[0] + 100000); // 先頭の10万個の検索時間を計測
measure_bin_srch(&v[0], &v[0] + 1000000); // 先頭の100万個の検索時間を計測
measure_linear_srch(&v[0], &v[0] + 10000); // 先頭の1万個の検索時間を計測
measure_linear_srch(&v[0], &v[0] + 100000); // 先頭の10万個の検索時間を計測
measure_linear_srch(&v[0], &v[0] + 1000000); // 先頭の100万個の検索時間を計測
}
std::pair<const int *, const int *> equal_range(const int *first, const int *last, int val)
{
const int *lptr = ::lower_bound(first, last, val); // 先頭位置
const int *uptr = lptr; // 末尾位置
while( uptr != last && *uptr == val ) // 値が等しければ末尾位置を次に進める
++uptr;
return std::pair<const int *, const int *>(lptr, uptr); // マッチする範囲を返す
}
int main() {
std::vector v{10, 20, 20, 30, 40, 60, 60, 60, 90, 100}; // 要素数10個
const int SZ = v.size();
auto begptr = &v[0];
auto endptr = &v[0] + SZ;
auto r2 = ::equal_range(begptr, endptr, 20);
r2 = ::equal_range(begptr, endptr, 15);
r2 = ::equal_range(begptr, endptr, 60);
r2 = ::equal_range(begptr, endptr, 100);
r2 = ::equal_range(begptr, endptr, 110);
}
要素を修正するアルゴリズム
昇順に値を設定
int 型配列 ar[N] の要素の値を 0, 1, ... N-1 に設定したい場合は、以下のように記述出来る。
int ar[N];
for(int i = 0; i != N; ++i)
ar[i] = i;
範囲 [first, last) に i から始まる値を設定したい場合は、以下のように記述する。
while( first != last ) {
*first++ = i++;
}
この処理はかなりよく出てくるので、これを１行で書くためのアルゴリズム std::iota(first, last, 初期値) が C++11 で追加された。
使用例は以下のとおり。簡単である。
#include <numeric> // for std::iota
.....
std::vector<int> v(50);
std::iota(v.begin(), v.end(), 0); // v に 0, 1, ... 49 を設定
演習問題：
- std::iota() を使って、std::vector<int> v(100); の要素を 1, 2, ... 100 に設定し、表示して結果を確認しなさい。
#include <iostream>
#include <numeric> // for std::iota
int main()
std::vector<int> v(100);
std::iota(v.begin(), v.end(), 1); // v に 1, 2, 3, ... 100 を設定
for(auto x : v ) std::cout << x << " ";
std::cout << "\n";
return 0;
}
挿入・削除
配列の途中の要素を挿入・削除する場合は、それ以降のデータを後ろ・前に移動しなくてはいけない。
コンテナクラスであれば、それを自動的にやってくれるが、通常配列では自分でその処理を行わなくてはいけない。
下記は ptr 位置に要素 val を挿入し、末尾データは破棄する例だ。末尾位置（最後の要素の次）は last で指定する。
挿入は、データの移動は後ろから行うのがポイントだぞ。
// ptr: 挿入位置
// last: 配列末尾位置（最後の要素の次）
// val: 挿入要素
void insert(int *ptr, int *last, int val)
{
for(int *dst = last - 1; --dst >= ptr; )
*(dst + 1) = *dst; // 要素をひとつ後ろにずらす
*ptr = val;
}
int main() {
int v[] = {3, 1, 4, 1, 5};
insert(begin(v)+2, end(v), 2); // [2] の位置に 2 を挿入。最後の 5 は破棄
return 0;
}
以下は、ptr 位置の要素を削除する例。末尾位置は last で指定する。
// ptr: 削除位置
// last: 配列末尾位置（最後の要素の次）
void erase(int *ptr, int *last)
{
while ( ++ptr < last )
*(ptr - 1) = *ptr; // 要素をひとつ前にずらす
}
int main() {
int v[] = {3, 1, 4, 1, 5};
erase(begin(v)+2, end(v)); // [2] の要素を削除。最後の 5 はそのまま
return 0;
}
演習問題：
- 挿入・削除のサンプルコードをビルド・実行し、動作確認しなさい。
- サンプルコードを見ずに、insert(int *ptr, int *last, int val), erase(int *ptr, int *last) を実装し、動作確認しなさい。
重複削除
以下は、同じ値の要素が続く場合は、２番め以降を削除する（{3, 1, 1, 4, 4, 4, 1, 5, 5} → {3, 1, 4, 1, 5}）コードの例だ。
重複があるたびに、前節の erase() を呼んでもいいのだが、そうすると処理時間が O(N^2) になってしまう。
下記のように、参照位置と書き込み位置の２つのポインタを使用すると O(N) で処理を行うことが出来る。
// [first, last) の重複を削除し、新しい last を返す
int *uniq(int *first, int *last)
{
if( first >= last ) return last; // 空の場合
int prev = *first++; // ひとつ前の値
int *dst = first; // 書き込み先の位置
for(;;) {
while( first != last && *first == prev ) // 重複部分をスキップ
++first;
if( first == last ) break;
*dst++ = prev = *first++; // １文字移動
}
return dst; // 新しい終端位置を返す
}
標準アルゴリズムにも、重複削除のための関数が用意されている。std::uniq(first, last) : iterator がそうだ。
範囲 [first, last) を調べ、重複があればそれを削除し、要素を前に詰める。リターン値として最後の有効な要素の次へのイテレータを返す。
vector 等のコンテナの全体を渡しても、コンテナのリサイズは行ってくれないので、それを自分で行う必要がある。
#include <algorithm> // std::unique
.....
std::vector<int> v{3, 3, 1, 1, 1, 4, 1, 5, 5, 5};
auto itr = std::uniq(v.begin(), v.end()); // 重複要素を削除し、要素を前に詰める
// {3, 1, 4, 1, 5, ?, ?, ?, ?, ?} となる。
// 5 の次の位置へのイテレータを返す
v.erase(itr, v.end()); // 不要な部分を削除
不要な部分を削除する部分は、ランダム・アクセス可能なイテレータであれば「v.resize(itr - v.begin());」、 そうでなければ「v.resize(std::distance(v.begin(), itr));」と書くことも出来る。
演習問題：
- 重複削除のサンプルコード（独自実装、std::uniq 両方）をビルド・実行し、動作確認しなさい。
- サンプルコードを見ずに、int *uniq(int *first, int *last) を実装し、動作確認を行いなさい。
順序反転
以下は、要素順序を反転する関数。
範囲 [first, last) 間にデータがある間、両端の要素を swap で入れ替え、範囲を狭めていく。
void reverse(int *first, int *last) // last は最後の要素の次を指す
{
while( first < --last ) { // 範囲間に要素がある場合
std::swap(*first, *last); // 両端の要素を交換
++first;
}
}
標準アルゴリズムにも、順序反転のための関数が用意されている。std::reverse(first, last) がそうだ。
反転したい範囲を引数に指定してコールするだけ。簡単だ。
#include <algorithm> // std::reverse
.....
std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
std::reverse(v.begin(), v.end());
for(auto x : v ) std::cout << x << " "; // 結果表示
std::cout << "\n";
演習問題：
- 順序反転のサンプルコードをビルド・実行し、動作確認しなさい。
- サンプルコードを見ずに、void reverse(int *first, int *last) を実装し、動作確認を行いなさい。
シャッフル
下記は Fisher-Yates shuffle と呼ばれるシャッフル アルゴリズムのコードです。
トランプの各カードを配列に格納している場合に有効です。
[first, last) の範囲において、first のカードを自分自身またはそれ以外のどれかとランダムに交換します。 そして、first をひとつ先に進め、範囲のカード枚数が1枚になるまで繰り返します。
#include <random>
void shuffle(int *first, int *last)
{
std::random_device rnd; // 乱数生成器
std::mt19937 mt(rnd()); // メルセンヌツイスター 乱数生成器
while( first + 1 < last ) { // +1 for 最後の１個はシャッフルする必要がない
// *first と [first, last) のどれかを交換
int *dst = first + mt() % (last - first);
std::swap(*first, *dst);
++first;
}
}
上記関数が定義されていれば、下記の様に呼び出すことが出来る。
std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
shuffle(&v[0], &v[0]+v.size());
C++11 標準アルゴリズムには std::shuffle(first, last, 乱数生成器) が用意されている。
通常はこれを使用するとよいだろう。
#include <iostream>
#include <algorithm> // std::shuffle
#include <vector>
#include <random>
int main() {
std::vector<int> v(52);
for(int i = 0; i != v.size(); ++i) v[i] = i;
std::random_device rnd;
std::mt19937 mt(rnd()); // メルセンヌツイスター 乱数生成器
std::shuffle(v.begin(), v.end(), mt); // シャッフル
for(auto x : v ) std::cout << x << " "; // 結果表示
std::cout << "\n";
}
演習問題：
- トランプの各カードを 0 ～ 51 の数値で表し、サイズ52の配列に順番にカードを格納し、それをシャッフルし、表示するコードを書きなさい。
- サンプルコードを見ずに、void shuffle(int *first, int *last) を実装し、動作確認を行いなさい。
ソート
ソートアルゴリズムは昔からかなり研究されていて、多くのアルゴリズムが存在する。
ここでは、「バブルソート」のみ取り上げる。
バブルソートは、もっとも単純でわかりやすいソートアルゴリズムだが、処理時間は O(N^2) と非常に遅い。
が、基本の基本なので理解しておいて欲しい。
考え方は単純で、[first, last) の範囲を昇順にソートしたいのであれば、その範囲の最小値を最初に移動する。 そして first をひとつ進め、範囲に含まれる要素数が１になるまで繰り返すというものだ。 最小値が浮かび上がってくる様が、泡が浮かび上がってくるようなので「バブルソート」と呼ばれる。
最小値を浮かび上がらせる処理が O(N) で、それをN回繰り返すのでトータルの処理時間は O(N^2) となる。
// [first, last) の一番小さい要素を first 位置に移動
// last - first >= 2 と仮定
void bubble(int *first, int *last)
{
last -= 2;
while( first <= last ) {
if( *last > *(last + 1) ) {
std::swap(*last, *(last + 1)); // 小さい方を前方に移動
}
--last;
}
}
void bubbleSort(int *first, int *last)
{
while( last - first >= 2 ) { // 要素数が２以上の間ループ
bubble(first, last); // [first, last) の一番小さい要素を first 位置に移動
++first;
}
}
標準アルゴリズムには std::sort(first, last) が用意されている。
使い方は上記の bubbleSort(first, last) と同じだが、内部的にはより高速なアルゴリズムを使っている（はずだ）。
なお、first, last にはポインタ、またはランダムアクセス可能なイテレータ（vector::iterator は可能だが、list::iterator は不可）を指定できる。
（※ ちなみに std::list には list::sort() というソート専用メソッドがある）
使用例：
std::vector<int> v(1000); // 1000個の要素をもつベクター
v[0] ～ v[999] の値をランダムに設定;
std::sort(v.begin(), v.end()); // 昇順にソート
演習問題：
- 昇順ではなく降順にソートするようにバブルソートを書き換え、動作確認しなさい。
- データ数1万個、10万個、100万個について、バブルソートと std::sort() の速度比較を行いなさい。
void bubble(int *first, int *last)
{
last -= 2;
while( first <= last ) {
if( *last < *(last + 1) ) {
std::swap(*last, *(last + 1)); // 大きい方を前方に移動
}
--last;
}
}
#include <iostream>
#include <vector>
#include <algorithm> // std::sort
#include <random>
#include <chrono>
using namespace std;
std::random_device g_rnd;
// [first, last) の一番小さい要素を first 位置に移動
// last - first >= 2 と仮定
void bubble(int *first, int *last)
{
last -= 2;
while( first <= last ) {
if( *last > *(last + 1) ) {
std::swap(*last, *(last + 1)); // 小さい方を前方に移動
}
--last;
}
}
void bubble_sort(int *first, int *last)
{
while( last - first >= 2 ) { // 要素数が２以上の間ループ
bubble(first, last); // [first, last) の一番小さい要素を first 位置に移動
++first;
}
}
void measure_bubble_sort(int N)
{
std::vector<int> v(N);
for (int i = 0; i < N; ++i) {
v[i] = g_rnd() % 1000*1000;
}
auto start = std::chrono::system_clock::now(); // 計測スタート時刻を保存
::bubble_sort(&v[0], &v[0] + v.size());
auto end = std::chrono::system_clock::now(); // 計測終了時刻を保存
auto dur = end - start; // 要した時間を計算
// 要した時間をミリ秒（1/1000秒）に変換して表示
std::cout << N << ": " << std::chrono::duration_cast(dur).count() << " milli sec \n";
}
void measure_std_sort(int N)
{
std::vector<int> v(N);
for (int i = 0; i < N; ++i) {
v[i] = g_rnd() % 1000*1000;
}
auto start = std::chrono::system_clock::now(); // 計測スタート時刻を保存
std::sort(v.begin(), v.end());
auto end = std::chrono::system_clock::now(); // 計測終了時刻を保存
auto dur = end - start; // 要した時間を計算
// 要した時間をミリ秒（1/1000秒）に変換して表示
std::cout << N << ": " << std::chrono::duration_cast(dur).count() << " milli sec \n";
}
int main() {
measure_std_sort(10000);
measure_std_sort(10000*10);
measure_std_sort(10000*100);
measure_bubble_sort(10000);
measure_bubble_sort(10000*10);
measure_bubble_sort(10000*100);
cout << "\nHIT ANY KEY.\n";
getchar();
return 0;
}
エラトステネスのふるい
配列は多数のフラグとして使用することが出来る。
以下は「エラトステネスのふるい」といって、素数の一覧を表示する有名なアルゴリズムだ。
#include <iostream>
#include <vector>
int main()
{
const int N = 1000;
std::vector<bool> isPrime(N+1, true); // 素数フラグを全部ONに
for(int i = 2; i < N; ++i) {
if( isPrime[i] ) { // 素数フラグがONならば
cout.width(8); // 表示桁数を８に
cout << i; // 素数として表示
for(int k = i+i; k <= N; k+=i)
isPrime[k] = false; // 素数の倍数の素数フラグを全てOFFに
}
}
cout << "\n";
return 0;
}
1000以下の数の分の素数フラグを配列で用意しておく。 isPrime[i] は i が素数かどうかを表すものとしている。
最初に全てのフラグをON（true）にしておき、最初から順に見ていき、フラグがONであれば、それを素数として表示する。
そして、その倍数のフラグを全てOFFにする。
この手順で、1000以下の素数を全て表示することができる。
演習問題：
- 素数のサンプルコードをビルド・実行し、動作確認しなさい。
- ふるいのアルゴリズムを使って100万以下の素数をすべて表示するコードを書いて、動作確認しなさい。
- サンプルソースコードを見ずに、ふるいのアルゴリズムを使って1000以下の素数をすべて表示するコードを書いて、動作確認しなさい。
参考
