【C++】挿入イテレータ【back_inserter/front_inserter/inserter】

挿入イテレータ

挿入イテレータ(insert iterator)は、イテレータに対する代入処理を挿入処理に置き換える特殊な出力イテレータです。

C++では用途別に複数の挿入イテレータが定義されています。

種類クラス名ヘルパー関数挿入処理
末尾挿入イテレータback_insert_iteratorback_inserterpush_back
先頭挿入イテレータfront_insert_iteratorfront_inserterpush_front
汎用挿入イテレータinsert_iteratorinserterinsert

目次

末尾挿入イテレータ - back_insert_iterator/back_inserter

back_insert_iteratorは、C++開発では比較的よく使われる挿入イテレータです。ヘルパー関数back_inserterを介して使われることがほとんどです。

std::vector<int> v = {1, 2, 3};
std::back_insert_iterator<std::vector<int>> a(v); // 初期化
auto b = std::back_inserter(v); // ヘルパー関数による初期化

イテレータの操作方法は一般的なイテレータと同じです。値代入時には元コンテナに対してpush_back関数による要素追加が行われる点が特徴です。

std::vector<int> v = {1, 2, 3};
auto i = std::back_inserter(v);
*i = 4; // `v.push_back(4)`と同等処理が行われる
        // v == {1, 2, 3, 4}
i++;    // インクリメント時には特に何も起きない
*i = 5; // v == {1, 2, 3, 4, 5}

なお挿入イテレータに対するインクリメント処理は可能ですが、特になにも行われません。エラーにもならず一般的なイテレータかのように振る舞うため、イテレータを扱うアルゴリズム系の関数にもそのまま適用できるという特徴があります。この特性は次に説明するcopy関数への適用時にも活かされます。

挿入イテレータの活用例

挿入イテレータはアルゴリズム系のテンプレート関数との組み合わせでよく使われます。有名な活用例としては、copy関数を応用した コンテナ要素の追加処理 等が挙げられます。

std::vector<int> v = {1, 2, 3};
std::vector<int> w = {4, 5, 6};
std::copy(w.begin(), w.end(), std::back_inserter(v));
// v == {1, 2, 3, 4, 5, 6}

copy関数の内部処理は以下のようなイメージです。

template <class B, class U, class V>
void copy(B begin, U end, V target) {
  while (begin != end) *target++ = *begin++;
}

よって実質的には次のような処理に展開される事になります。

std::vector<int> v = {1, 2, 3};
std::vector<int> w = {4, 5, 6};
auto begin  = w.begin();
auto target = std::back_inserter(v);
*target++ = *begin++; // v.push_back(w[0]);
*target++ = *begin++; // v.push_back(w[1]);
*target++ = *begin++; // v.push_back(w[2]);
// v == {1, 2, 3, 4, 5, 6}

push_back関数は多くのコンテナクラスで定義されているため汎用的に利用できます。また文字列クラスにもpush_back関数は定義されているため、先程のコピー処理はstd::stringクラスに対しても汎用的に利用できます。

先頭挿入イテレータ - front_insert_iterator/front_inserter

front_insert_iteratorは、挿入処理をpush_front関数呼び出しに置き換えるイテレータです。ヘルパー関数としてfront_inserterが用意されています。

// #include <list>
std::list<int> v = {3};
auto i = std::front_inserter(v);
*i = 2; // `v.push_front(4)`と同等処理が行われる
        // v == {2, 3}
*i = 1; // v == {1, 2, 3}

汎用挿入イテレータ - insert_iterator/inserter

insert_iteratorは、挿入処理をinsert関数呼び出しに置き換えるイテレータです。ヘルパー関数としてinserterが用意されています。

std::vector<int> v = {2};
auto j = std::inserter(v, v.begin());
j = 0; // v == {0, 2}
j = 1; // v == {0, 1, 2}
auto k = std::inserter(v, v.end());
k = 3; // v == {0, 1, 2, 3}
k = 4; // v == {0, 1, 2, 3, 4}

back_insert_iteratorやfront_insert_iteratorの時とは違い、第二引数にコンテナへの挿入位置を指定できる点が特徴です。二回目以降の挿入位置は、前回挿入位置の末尾が基準となる点にも注目してください。なおinsert_iteratorにはイテレータ破壊が起きないという特徴もあります。

本イテレータは内部的にはinsert関数呼び出しが行われています。処理の展開イメージは以下の通りです。

std::vector<int> v = {2};
auto i = v.begin();
i = v.insert(i, 0); // v == {0, 2}
++i;
i = v.insert(i, 1); // v == {0, 1, 2}

このイテレータに対する再代入処理は、イテレータ破壊を回避するためのものです。

イテレータ破壊については以下のページが参考になります。

イテレータ破壊

広告