先頭へ戻る

要素を探索する | Programming Place Plus 新C++編

Programming Place Plus トップページ新C++編

先頭へ戻る

このページの概要

このページでは、std::vector や std::string から、目的の値を持った要素や、ある条件に合った要素を見つけ出す方法を取り上げます。また、2つ以上の条件を組み合わせたり、否定形を使ったりする複雑な条件指定の方法についても取り上げています。

以下は目次です。要点だけをさっと確認したい方は、「まとめ」をご覧ください。



探索

目標としている蔵書リストのプログラムのことを考えると、登録されている本の情報を簡単に探し出す機能が必要かもしれません。たとえば、書名や著者名で検索する機能です。このページでは、このような機能を実現するために、std::vector や std::string から、ある目的に合った要素を見つけだす処理を取り上げます。一般的に、このような処理を探索(サーチ)(search)と呼びます。

探索の実現方法についてはさまざまな研究がなされていて、いくつもの手法(アルゴリズム (algorithm))が考案されています。そういったものを知っていれば、C++ を使って自力でプログラムを書くことが可能ですが、標準ライブラリにはすでにいくつか用意されたものがあるので、原則としてこちらを使うべきです。

探索の手法についてはアルゴリズムとデータ構造編【探索】で解説しています(C言語による解説です)。

どんな機能でもそうですが、標準ライブラリに用意されているものを差し置いて、自力で作ろうとしてはいけません。標準ライブラリは、よく検討された仕様にもとづいて、よく検討された効率的で安全な実装がなされており、多くのプログラマが使っているという事実によってよく検証されています。自力で書いたコードには、おそらくここまでの信頼度はないでしょう。標準ライブラリの機能で実現できないなら、標準でないライブラリを探してみることから始めましょう。それでも求めているものが見つからないときに、自力での実装を検討します。

探索に関する標準ライブラリの機能を使うには、#include <algorithm> の記述が必要です。

このページで紹介する機能は一部にすぎないので、より詳しく知りたければ、リファレンスサイト(cpprefjpcpprefernce.com)などで確認してください。

特定の値を持った要素を探す (std::find関数)

まずは、特定の値を持った要素を探す方法です。この目的には、std::find関数を使います。

細かい仕様や、ここで紹介していない機能については、リファレンスサイト(cpprefjpcppreference.com)で確認してください。

std::find関数には、要素を探す範囲をあらわす2つのイテレータと、探したい要素の値を指定します。結果としてイテレータが得られ、要素が発見できていたら、その要素を指し示しています。発見できなかった場合は、探索範囲の末尾として指定したイテレータが得られます。

std::find関数は、指定された範囲内を手前側から末尾側へ向かって順番に探す挙動になっています(このような手法を線形探索 (linear search) と呼びます)。そのため、最初に見つけた要素を指し示すイテレータが得られます。

線形探索については、アルゴリズムとデータ構造編【探索】第1章で解説しています。

【上級】より効率的である二分探索を望むなら、std::lower_bound関数(cpprefjpcppreference.com)を使います。std::binary_search関数(cpprefjpcppreference.com)もありますが、これは要素があるかないかが分かるだけであり、その要素の位置が分からないため、std::find関数の代わりになるものではありません。

【上級】【C言語プログラマー】C言語の bsearch関数も使えなくはないですが、C++ にはもっと便利で安全な方法があるので、基本的に使う機会はありません。

次のサンプルプログラムは、std::vector から、3 という値の要素を探索しています。

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {1, 2, 3, 4};

    auto it = std::find(std::cbegin(v), std::cend(v), 3);
    if (it == std::cend(v)) {
        std::cout << "not found.\n";
    }
    else {
        std::cout << "found: " << *it << "\n";
    }
}

実行結果:

found: 3

2つのイテレータを使って範囲を指示する考え方は、「要素を取り除く」のページで erase関数を使うときに登場しました。範囲の先頭にある要素を指し示すイテレータと、範囲の末尾にある要素の1つ後ろを指し示すイテレータのペアで指定します。ほとんどのケースで、探索範囲は対象の配列全体になるでしょうから、先頭のイテレータを std::cbegin関数や std::begin関数で、末尾のイテレータを std::cend関数や std::end関数で取得するのが簡単です。

std::find関数から得られるイテレータを、変数it で受け取っています。このイテレータは、要素が発見できた場合は、発見した要素を指し示しており、要素が発見できなかった場合には、範囲の末尾として指定したイテレータと同じものになっています。したがって、if (it == std::cend(v)) のように判定することで、要素が発見できなかったことが分かります。発見できなかった場合のイテレータは、探索範囲外を指しているので、デリファレンス(*it のようにして、要素へアクセスすること)をしないように注意してください。

なお、指定するイテレータは、通常のイテレータでも constイテレータでもよく、逆イテレータでも受け付けます。結果として得られるものは、指定した種類のイテレータと同じ型です。このサンプルプログラムでは、constイテレータを指定しているので、得られる結果も constイテレータです。そのため、*it = 0; のように、見つけた要素の値を書き換えることはできませんが、通常のイテレータを指定していれば、要素の書き換えも可能です。

条件に合う要素を探す (std::find_if関数)

続いて、特定の条件に合う要素を探す方法です。この目的には、std::find_if関数を使います。

細かい仕様や、ここで紹介していない機能については、リファレンスサイト(cpprefjpcppreference.com)で確認してください。

std::find関数では探したい値を指定しましたが、std::find_if関数では条件を指定します。それ以外の違いはありません。ちょうど、std::remove関数と std::remove_if関数のような関係性です(「要素を取り除く」のページを参照)。

次のサンプルプログラムは、std::vector から、値の1桁目が 0 である要素を探索しています。

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {25, 16, 40, 22, 39};

    auto it = std::find_if(std::cbegin(v), std::cend(v), [](int e){ return e % 10 == 0; });
    if (it == std::cend(v)) {
        std::cout << "not found.\n";
    }
    else {
        std::cout << "found: " << *it << "\n";
    }
}

実行結果:

found: 40

条件の指定にはラムダ式を使います。ラムダ式については、「要素を取り除く」のページで説明したので、ここでは省略します。

条件に合わない要素を探す (std::find_if_not関数)

条件に合わない要素を探す std::find_if_not関数もあります。条件の意味が逆になる以外の違いはありません。

細かい仕様や、ここで紹介していない機能については、リファレンスサイト(cpprefjpcppreference.com)で確認してください。

次のサンプルプログラムは、std::vector から、値が 5 の倍数 “ではない” 要素を探索しています。

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {25, 16, 40, 22, 39};

    auto it = std::find_if_not(std::cbegin(v), std::cend(v), [](int e){ return e % 5 == 0; });
    if (it == std::cend(v)) {
        std::cout << "not found.\n";
    }
    else {
        std::cout << "found: " << *it << "\n";
    }
}

実行結果:

found: 16

条件式の意味を逆にすれば、std::find_if関数で同じ結果を得られます(std::find_if(std::cbegin(v), std::cend(v), [](int e){ return e % 5 != 0; });)。

条件に合うすべての要素を探す

std::find関数、std::find_if関数、std::find_if_not関数では、最初に発見した要素へのイテレータしか得られません。しかし、指定した値や条件に合う要素は複数存在している可能性もあり、そのすべてを発見したい場面もあります。そのような場面として考えられるパターンはいくつかあります。

  1. 該当する要素が何個あるか知りたい
  2. 該当する要素の値を書き換えたい
  3. 該当する要素ごとに処理を行いたい(書き換えはしない)
  4. 該当する要素を取り除きたい

3番は、範囲for文の中で if文を使えば書けます。

4番は、「要素を取り除く」のページで説明した std::remove_if関数を使って実現できます。ほかの2つについては、それぞれに使える機能が標準ライブラリに用意されています。

条件に合う要素の個数を調べる

1番の「該当する要素が何個あるか知りたい」については、std::count_if関数を使うと簡単に実現できます。2つのイテレータで探索範囲を、ラムダ式で条件を指定すると、一致する要素の個数が得られます。

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {8, 11, -10, 0, -5, 13};

    auto count = std::count_if(std::cbegin(v), std::cend(v), [](int e){ return e < 0; });
    std::cout << count << "\n";
}

実行結果:

2

特定の値を持った要素の個数を探す、std::count関数もあります。

// 8 の個数を返す
auto count = std::count(std::cbegin(v), std::cend(v), 8);

条件に合うすべての要素を書き換える

2番の「該当する要素の値を書き換えたい」場合には、std::transform関数が使えます。

std::transform関数の主要な用途は、名前のとおり「トランスフォーム(変身)」です。指定範囲内の要素の値を変換して、新たな要素の並びを作り出します。そのため、新たな配列を作り出すという用途で使えるものですが、元の配列の要素を上書きするという使い方もできます。

たとえば、負の値を持った要素をすべて探し出して、符号を反転して正の値に変換するプログラムを次のように作成できます。

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {8, 11, -10, 0, -5, 13};

    std::transform(std::begin(v), std::end(v), std::begin(v), [](int e){ return (e < 0) ? -e : e; });

    for (auto e : v) {
        std::cout << e << "\n";
    }
}

実行結果:

8
11
10
0
5
13

std::transform関数に渡す情報の1つ目と2つ目は、対象の範囲を表現するイテレータのペアです。3つ目は、各要素に処理を行ったあと、その結果を書き出す先の範囲の先頭を指すイテレータです。4つ目は、各要素に適用する処理を記述したラムダ式です。

探索したい要素の条件は、ラムダ式の中で記述します。これまでにみてきた find系の関数と違って、条件式の記述だけでなく、値の変換のコードまで書く必要があります。つまり、std::transform関数では、ラムダ式の return文に、条件に一致したかどうかをあらわす bool型の値ではなく、変換された後の要素の値を指定します。

探索範囲は、v の先頭から末尾までなので、8, 11, -10, … の順に1つ1つアクセスされ、そのつど値が e にコピーされて、ラムダ式のコードにやってきます。ラムダ式のコードは、e が負数なら符号を反転、負数でなければそのまま return文で返すというものです。返された値は、std::transform関数に渡した3つ目のイテレータが指す先にコピーされます。1つコピーされると、次回のコピー先は1要素分後ろにずらされます。

変換後の値を、変換元とは異なる配列へ書き出す場合、書き込み先の配列の大きさを超えないように注意してください(未解説ですが、std:: back_inserter1 2 などの挿入イテレータという仕組みを使うとうまく書けます)。

複雑な条件

指定する条件を、もう少し複雑なものにしてみます。

論理OR

2つの条件のいずれかを満たしている要素を探してみます。たとえば、「値が 100以上、あるいは 5 の倍数」という条件を考えてみます。この場合、15 や 102 は条件を満たしますが、99 は条件を満たしません。また、100 や 105 は条件を満たします(2つの条件を両方ともを満たすケース)。

このような条件は、論理OR論理和 (logical OR) などと呼ばれます。論理OR は、‘||’ という表記の論理OR演算子 (logical OR operator) を使って記述します。

条件式1 || 条件式2

まず、「条件式1」が評価され、bool型の値に変換されます。これが true だった場合、全体としての結果が true になります。「条件式1」が false に評価された場合には、「条件式2」を評価し、bool型の値に変換され、これが true だった場合、全体としての結果が true に、そうでなければ false になります3

少々ややこしい書き方をしましたが、簡単にいえば「2つの条件式のどちらか一方だけでもいいので、true ならば true。そうでないなら false になる」ということです。

実際のプログラムでは次のように使えます。

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {102, 99, 100, 101, 103};

    auto it = std::find_if(std::cbegin(v), std::cend(v), [](int e){ return e >= 100 || e % 5 == 0; });
    if (it == std::cend(v)) {
        std::cout << "not found.\n";
    }
    else {
        std::cout << "found: " << *it << "\n";
    }
}

実行結果:

found: 102

最初に少々ややこしい説明のしかたをしたのには理由があります。きちんと読むと、「条件式1」が true になったときには「条件式2」が評価すらされないことが分かります。「2つの条件のどちらかを満たすかどうか」ということが知りたいわけなので、条件式の一方を調べてみて true なのであれば、もう一方の条件式を調べることに意味がないため、評価自体を省略してしまうのです。このような評価のルールを、短絡評価 (short-circuit evaluation) と呼びます。

短絡評価が行われるため、2つの条件の一方の側が、他方に比べてあきらかに処理に時間がかかるものであるなら、それを「条件式2」に置いたほうが効率的になります。たとえば、std::vector<std::string> から、「ある非常に長い文字列と一致しているか、空文字列である」要素を探したいとします。非常に長い文字列との一致を調べるには、1文字1文字すべて突き合わせる比較が必要なので、(要素の内容次第ですが)時間がかかる可能性があります。一方、空文字列であるかどうかはすぐにわかりますから、「「ある非常に長い文字列と一致しているか」という条件のほうを「条件式2」に置いたほうが効率的になることが期待できます。


条件式を3つ以上組み合わせたい場合は、|| をつなげて条件式を書き並べていけばいいです。たとえば、「値が 100以上、あるいは 5 の倍数、あるいは 7 の倍数」としたければ、e >= 100 || e % 5 == 0 || e % 7 == 0 のように書けます。短絡評価なので、左側の条件式から順番に評価され、true になった時点で、それ以降の条件式は評価されません。

論理AND

2つの条件を両方とも満たしている要素を探してみます。たとえば、「値が 100以上で、かつ、奇数である」という条件を考えてみます。この場合、101 や 103 は条件を満たしますが、99 や 100 は条件を満たしません(99 は奇数だが 100以上ではない。100 は 100以上だが奇数ではない)。

このような条件は、論理AND論理積 (logical AND) などと呼ばれます。論理ANDは、&& という表記の論理AND演算子 (logical AND operator) を使って記述します。

条件式1 && 条件式2

「条件式1」と「条件式2」それぞれを評価した結果が true になる場合にかぎって、結果が true になります。これ以外のパターンでは false になります。

論理AND演算子にも短絡評価のルールがあります。論理AND演算子では、必ず「条件式1」が先に評価され、もし false であったなら、「条件式2」は評価されません4

実際のプログラムでは次のように使えます。

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {102, 99, 100, 101, 103};

    auto it = std::find_if(std::cbegin(v), std::cend(v), [](int e){ return e >= 100 && e % 2 != 0; });
    if (it == std::cend(v)) {
        std::cout << "not found.\n";
    }
    else {
        std::cout << "found: " << *it << "\n";
    }
}

実行結果:

found: 101

論理AND演算子における短絡評価は、「条件式1」を満たすことを前提とした「条件式2」を記述することに利用できます。たとえば、std::vector<std::string> から、「先頭の文字が ‘A’ である文字列」を探すことを考えてみます。この条件を e.at(0) == 'A' のように記述できますが、もし値が空文字列な要素が含まれていたら、範囲外アクセスを起こし、プログラムが強制終了してしまいます。そのため、この条件式を評価する前に、空文字列でないことを確認しなければなりません。そこで、短絡評価を利用して、e.empty() == false && e.at(0) == 'A' と記述します。必ず e.empty() == false が先に評価されるため、空文字列でない場合にだけ、e.at(0) == 'A' を評価させることができます。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::vector<std::string> v {"", "apple", "Apple"};

    auto it = std::find_if(std::cbegin(v), std::cend(v), [](std::string e){ return e.empty() == false && e.at(0) == 'A'; });
    if (it == std::cend(v)) {
        std::cout << "not found.\n";
    }
    else {
        std::cout << "found: " << *it << "\n";
    }
}

実行結果:

found: Apple

論理AND演算子と論理OR演算子が混在した複雑な条件を記述することもできます。たとえば、「値が負の数である。または 100以上で、かつ、奇数である」という場合、e < 0 || e >= 100 && e % 2 != 0 と書けます。演算子の優先順位は、論理OR演算子よりも、論理AND演算子の方が高いです。そのため、このコードは e < 0 || (e >= 100 && e % 2 != 0) と同じです。

演算子の優先順位については、APPENDIX の「演算子の一覧」を参照してください。

演算子の優先順位と、どのオペランドから評価されるかは別の話であることに注意してください。オペランドが評価される順番は、一部の例外的な演算子を除いて、定義されていません5。論理AND演算子、論理OR演算子には、短絡評価のルールがあるので、例外的な演算子に当たり、かならず左側のオペランドが先、右側のオペランドが後で評価されます。

さきほどのコードでいえば、|| より && が優先度が高いため、e >= 100 && e % 2 != 0 が優先して評価されそうに思えますが、|| の左側のオペランドが先に評価されます。そうでないと、論理OR演算子の短絡評価のルールに合いません(|| の左側の値が分かる前に、右側を評価するわけにはいかない)。e < 0 が false の場合にのみ、e >= 100 && e % 2 != 0 の評価に進みます。&& の短絡評価のルールに沿って、左側の e >= 100 から評価され、これが true の場合にのみ、右側の e % 2 != 0 が評価されます。

論理否定

最後に、条件を否定する、論理否定(論理NOT) (logical negation、logical NOT) を紹介します。論理AND、論理OR とちがって、登場する条件は1つだけで、その結果を反対にするというものです。

論理否定は、! という表記の論理否定演算子 (logical negation operator) を使って記述します。

!条件式

「条件式」が true の場合は false になり、false の場合は true になります。

これまでのページでも何度か、xxx == false というかたちの条件式を書いたことがありますが、論理否定演算子を使って !xxx のように書けます。

! が目立たず見落としやすいため、! xxx のように、空白をはさむ書き方が好まれることがあります。

次のプログラムは、空文字列でない要素を探しています。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::vector<std::string> v {"", "", "hello"};

    auto it = std::find_if(std::cbegin(v), std::cend(v), [](std::string e){ return !e.empty(); });
    if (it == std::cend(v)) {
        std::cout << "not found.\n";
    }
    else {
        std::cout << "found: " << *it << "\n";
    }
}

実行結果:

found: hello


まとめ


新C++編の【本編】の各ページには、末尾に練習問題があります。ページ内で学んだ知識を確認する簡単な問題から、これまでに学んだ知識を組み合わせなければならない問題、あるいは更なる自力での調査や模索が必要になるような高難易度な問題をいくつか掲載しています。


参考リンク


練習問題

問題の難易度について。

★は、すべての方が取り組める入門レベルの問題です。
★★は、自力でプログラミングができるようなるために、入門者の方であっても取り組んでほしい問題です。
★★★は、本格的にプログラマーを目指す人のための問題です。

問題1 (確認★)

次のうち、結果が true になるものをすべて選んでください。a の値は 10、b の値は 20 とします。

  1. a == 10 && b == 20
  2. a == 10 && b == 10
  3. a != b || a == 0
  4. !(a == b)
  5. !(a == 10 || b == 10)
  6. a % 2 != 0 || a == 10 && b == 20

解答・解説

問題2 (基本★)

std::vector<std::string> の変数から、“Hello” を探すプログラムを作成してください。

解答・解説

問題3 (基本★)

{0, 7, 9, 15, 30, 50} の要素を含んだ std::vector<int> の変数から、値が 30~40 の範囲内にある要素を探すプログラムを作成してください。

解答・解説

問題4 (応用★★)

{0, 7, 9, 15, 30, 50} の要素を含んだ std::vector<int> の変数から、100 を割り切ることができる値を持った要素を探すプログラムを作成してください。

解答・解説

問題5 (応用★★)

std::string の変数から、一番最後にあらわれる . を見つけるプログラムを作成してください。たとえば、“abc.de.fgh.ij” という文字列なら、i の手前にある . を見つけるようにしてください。

解答・解説


解答・解説ページの先頭



更新履歴




はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー