TechFULの中の人

triple-four’s blog

C++のイテレータのお話【まずは使ってみる編】

こんにちは!TechFULでアルバイトをしているSiiiecです。
今回は、C++イテレータについて使い方を中心にして解説をしたいと思います!

イテレータ is 何?

過去の記事でも一瞬登場しました。

triple-four.hatenablog.com

ざっくりと説明すると、繰り返し処理について抽象化したものです。
標準ライブラリのアルゴリズムと内部データ構造の間を取り持つ存在であり、データ構造に依存しないコーディングを可能にしています。

使用するだけなら、<algorithm>ヘッダの関数に渡したり、範囲for文に使用されているくらいの認識で問題ないと思います。

イテレータの基本

先頭と終端

2つのイテレータbegin, endを用いて半開区間 [begin, end) を定義します。
関数の適用範囲の指定などに使用します。

要素アクセス

*(->)を用いて、ポインタのような要素アクセスを行います。

移動

++, --, +=, -=を使用して、イテレータの移動を行います。
イテレータの種類によって行える演算が異なります。

比較

==,!=,<, >=などのイテレータ同士の比較を行います。
これもイテレータの種類によって行える演算が異なります。

使用例

#include <iostream>
#include <vector>

int main()
{
    using namespace std;

    vector<int> v{12, 23, 34, 45};

    // 最初の要素(12)を示すイテレータ
    auto it = v.begin();
    cout << *it << endl; // 出力は12

    // イテレータを前に2進める
    it += 2;
    cout << *it << endl; // 出力は34

    // 終端を示すイテレータ
    auto itEnd = v.end();
    // イテレータ同士の比較
    cout << (it == itEnd ? "true" : "false") << endl; // 出力はfalse

    return 0;
}

この例を見て、「添字アクセス」でも良いんじゃない?と思った方は正しいです。
このままではイテレータを使う旨味が無いように見えますね。

イテレータを使う利点は、データ構造に依存しないコーディングと書きました。
上の例ではvectorでしたが、(ほぼ)同じコードをlistにも適用することができます。

listはランダムアクセスができないため、+=, -=が使えないことに注意が必要です。

#include <iostream>
#include <list>

int main()
{
    using namespace std;

    list<int> l{12, 23, 34, 45};

    // 最初の要素(12)を示すイテレータ
    auto it = l.begin();
    cout << *it << endl; // 出力は12

    // イテレータを前に2進める
    it++;
    it++;
    cout << *it << endl; // 出力は34

    // 終端を示すイテレータ
    auto itEnd = l.end();
    // イテレータ同士の比較
    cout << (it == itEnd ? "true" : "false") << endl; // 出力はfalse

    return 0;
}

このように、データ構造に依存しないコーディングができるようになります。

使用例から見るイテレータ

基本操作の紹介も済んだので、イテレータを使用して何ができるのか見てみます。

逆順にソートする

逆順にソートするには、

  • std::sort()をしてからstd::reverse()を行う
  • std::sort()に比較関数を渡す

などいくつか方法はありますが、余計な計算がある比較関数を書くのが面倒という問題があります。

逆順ソートを簡単に書くには、逆順イテレータ(reverse iterator)を使います。

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

template <class Container>
void PrintAll(const Container& c)
{
    for (auto e : c)
        std::cout << e << " ";
    std::cout << std::endl;
}

int main()
{
    using namespace std;

    vector<int> v {1, 3, 2, 5, 4};
    PrintAll(v);    // 出力 :1 3 2 5 4 

    // 逆順(降順)ソート
    sort(v.rbegin(), v.rend());
    PrintAll(v);    // 出力 :5 4 3 2 1 
}

sort(v.rbegin(), v.rend())と、普段渡すbegin, endの前にrをつけるだけで逆順ソートができます。

範囲をコピーする

要素が同じコンテナがもう一つ欲しい、という場合に利用できます。

確保済みのコンテナにコピーする

事前にコピー元と同数以上の要素数を持つコンテナを用意して、コピーする方法です。

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

template <class Container>
void PrintAll(const Container& c)
{
    for (auto e : c)
        std::cout << e << " ";
    std::cout << std::endl;
}

int main()
{
    using namespace std;

    vector<int> src {12, 23, 34, 56};

    // 事前に同じ大きさのコンテナを用意する方法
    auto copied = vector<int>(src.size());

    PrintAll(copied);   // 出力 :0 0 0 0 

    // コピー
    copy(src.begin(), src.end(), copied.begin());

    PrintAll(copied);   // 出力 :12 23 34 56 
}

コンテナの末尾に追加しながらコピーする

既にあるコンテナ(要素数0でもok)の末尾に追加します。
自分はこちらのほうが上の例より使う機会が多いです。

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

template <class Container>
void PrintAll(const Container& c)
{
    for (auto e : c)
        std::cout << e << " ";
    std::cout << std::endl;
}

int main()
{
    using namespace std;

    vector<int> src {12, 23, 34, 56};

    // コンテナのデータ構造は異なるものでも良い
    auto li = list<int>{98, 87, 76};

    PrintAll(li);   // 出力 :98 87 76 

    // liの末尾に追加でコピー
    copy(src.begin(), src.end(), back_inserter(li));

    PrintAll(li);   // 出力 :98 87 76 12 23 34 56 
}

back_inserter()を使うことで、コンテナの末尾に追加しながらコピーすることができます。
また、イテレータを使っているのでデータ構造が異なるコンテナ同士でコピーを行うこともできます。

コンテナの先頭に追加しながらコピーする

back_inserter()の代わりにfront_inserter()を使うと、コンテナの先頭に追加しながらコピーすることができます。
この場合の実行結果は、56 34 23 12 98 87 76となります。

任意の位置に挿入しながらコピーする

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

template <class Container>
void PrintAll(const Container& c)
{
    for (auto e : c)
        std::cout << e << " ";
    std::cout << std::endl;
}

int main()
{
    using namespace std;

    vector<int> src {12, 23, 34, 56};

    auto copied = vector<int>{111, 222, 333};

    PrintAll(copied);   // 出力 :111 222 333 

    // 指定した位置に挿入しながらコピー
    copy(src.begin(), src.end(), inserter(copied ,copied.begin() + 2));

    PrintAll(copied);   // 出力 :111 222 12 23 34 56 333 
}

inserterでは、指定された位置に挿入しながらコピーができます。

要素に関数を適用したコンテナを作る

元のコンテナはそのままで、それぞれの要素に関数を適用したコンテナが欲しい、ということがよくあります。
std::copy()の代わりに、std::transform()を使用します。

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

template <class Container>
void PrintAll(const Container &c)
{
    for (auto e : c)
        std::cout << e << " ";
    std::cout << std::endl;
}

int main()
{
    using namespace std;

    vector<int> src{12, 23, 34, 56};

    vector<int> result;

    // 関数を適用した結果をコピー
    transform(src.begin(), src.end(), back_inserter(result),
              [](auto in) { return in * 10; }); // 入力をを10倍した結果を返すラムダ式

    PrintAll(result); // 出力 :120 230 340 560 
}

ほかにもalgorithmヘッダには、要素を置換するreplace()など、様々な関数があります。

おわりに

詳細は分からなくてもとりあえずイテレータを使ってみる、ということを目指して紹介しました。
vectorlistではなくコンテナとして抽象化して考えることで、データ構造に依存しないコーディング(何度目)ができるようになります。

次回の記事では、イテレータの詳細について説明したいと思います。
ここまで読んでいただきありがとうございました!Siiiecでした!

参考リンク

cpprefjp.github.io
このサイトには永遠にお世話になりそうです。

運営会社 / サービス

444株式会社

triple-four.com

TechFUL

procon.techful.jp