先頭へ戻る

要素を取り除く | Programming Place Plus 新C++編

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

先頭へ戻る

このページの概要

このページでは、std::vector や std::string から要素を取り除く(削除する)方法を取り上げます。要素を追加するときにも、メモリ上での動きを理解しなければならない難しさがありましたが、取り除く場合にも同様の難しさがあります。また、適当に末尾に入れておけば済むことも多い追加の処理とちがって、削除の場合には「“この要素を” 取り除く」という指定ができなくてはなりませんから、その方法もいくつか取り上げます。

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



要素を取り除く

前のページでは、std::vector や std::string に要素を追加する方法を説明しました。このページでは、要素を取り除く(削除する)方法をみていきます。

要素を取り除くというのは、たとえば、元の配列が {0, 1, 2, 3} という 4つの要素を持っているとき、2 を取り除いて、{0, 1, 3} にするといったことです。取り除かれた要素よりも後ろにある要素は手前側にずれてきます。{0, 1, なし, 3} のような状態になるわけではありません。

取り除かれた要素より後ろにある要素を指していたイテレータ(past-the-endイテレータも含む)は無効になります。添字もずれるので注意してください。また、要素をずらす作業の分だけ、処理に時間がかかります。この辺りの事情は、(要素がずれていく方向は逆ですが)要素を追加するときと同様です。

また、末尾に入れておけば十分というケースも多い “追加” の処理と違って、取り除くときには「“この要素” を取り除きたい」という指示が必要なことがほとんどです。

要素を取り除くと、当然ながら要素数が減少します。しかし、容量は変化しないことを覚えておきましょう。もし、要素を取り除くことによって、容量も減るのだとすると、現在確保されているメモリを縮小するなり、小さいメモリを改めて確保しなおすなりしなければなりません。3回に分けて要素を取り除こうとしたために、この作業が3回行われるとしたら相当な作業量ですし、要素を再び追加しようとして、結局容量が足らなくなるようなことがあっては意味もありません。こういった事情から、わざわざ容量を減らす価値はほとんどありません。それでも、もし本当に容量を減らしたいというときには、明示的にその手続きを踏むことで実現できます(後述します)。

すべての要素を取り除く

まず、一番わかりやすい、「すべての要素を取り除く」方法からみていきましょう。

すべての要素を取り除くには、clear関数を使います。v.clear(); のように記述するだけで、非常にシンプルです。

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

int main()
{
    std::vector<int> v {0, 1, 2};
    std::string s {"Hello"};

    std::cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";
    std::cout << "size = " << s.size() << ", capacity = " << s.capacity() << "\n";

    v.clear();
    s.clear();

    std::cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";
    std::cout << "size = " << s.size() << ", capacity = " << s.capacity() << "\n";
}

実行結果:

size = 3, capacity = 3
size = 5, capacity = 15
size = 0, capacity = 3
size = 0, capacity = 15

要素がなくなるので、要素数は 0 になります。前述しているとおり、容量は減りません

要素がなくなるという点からいっても当然ですが、削除前に存在していたイテレータはすべて無効になります

末尾の要素を取り除く

次に、末尾の要素を取り除く方法を取り上げます。

末尾の要素なら、後続の要素をずらす必要がないので効率的です。とはいえ、取り除きたい要素は明確であることが多いため、優先的にこの方法を使えばいいというわけではありません。

pop_back関数

末尾の要素を取り除くには、pop_back関数を使います。

#include <iostream>
#include <vector>

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

    v.pop_back();

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

実行結果:

0
1

pop_back関数を、要素がない状態で使うことは、未定義動作であることに注意が必要です。

std::vector v {};
v.pop_back();  // 危険

末尾の要素にアクセスする (back関数)

pop_back関数は単に末尾から要素を取り除くだけです。取り除かれた要素の値が何であったか知りたい場合もあると思いますが、その場合は、back関数と併用します。back関数を使うと、末尾の要素にアクセスすることができます(取り除きはしない)。

back関数によって得られるものは、末尾の要素への参照です。参照については「std::vector」のページで取り上げました。

#include <iostream>
#include <vector>

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

    while (v.empty() == false) {
        std::cout << v.back() << "\n";
        v.pop_back();
    }
}

実行結果:

2
1
0

back関数も pop_back関数と同様に、要素がない状態で使うことは、未定義動作であることに注意が必要です。このサンプルプログラムのように、empty関数を使って、要素があることを確認するなどして、回避してください。

v.empty() == false は、先のページで解説する ! という演算子を使って !v.empty() とも書けます。

ちなみに、先頭の要素にアクセスする front関数もあります。使い方や注意事項は同じです。

任意の要素を取り除く

次に、任意の要素を選んで取り除く方法を取り上げます。

繰り返しになりますが、配列の途中にある要素を取り除くと、その位置よりも後ろにある要素が手前側にずらされることになります。イテレータは無効になりますし、添字もずれることになるので注意してください。

erase関数

任意の要素を取り除くには、erase関数を使います。

【上級】【C++20】std::erase関数が追加されました。使い方は std::vector や std::string が持つ erase関数とは異なり、後で取り上げる std::remove関数と組み合わせた仕様になっています。つまり、特定の値をもった要素を探して削除します。1 2

erase関数には、取り除きたい要素を指し示すイテレータを渡します。正しい要素を指していないイテレータを渡してはなりません。

#include <iostream>
#include <vector>

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

    v.erase(std::cbegin(v) + 1);

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

実行結果:

0
2
3

連続している複数の要素をまとめて取り除く

erase関数は、2つのイテレータを使って範囲を表現することにより、連続している複数の要素をまとめて取り除くことができます。範囲の開始位置を1つ目のイテレータで、範囲の終了位置を2つ目のイテレータで指定します。past-the-end イテレータの考え方と同じで、終了位置をあらわすには「1つ後ろ」を指すようにすることに注意してください。

#include <iostream>
#include <vector>

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

    v.erase(std::cbegin(v), std::cbegin(v) + 2);

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

実行結果:

2
3

先頭の要素を指すイテレータと、そこから2つ先の要素を指すイテレータを指定しました。{0, 1, 2, 3} のうち、01 の要素が取り除かれます。


std::string では、取り除きたい要素の位置をあらわす添字と、取り除きたい要素の個数(文字数)を指定できます。

#include <iostream>
#include <string>

int main()
{
    std::string s {"abcde"};

    s.erase(3, 2);

    std::cout << s << "\n";
}

実行結果:

abc

位置の方は、有効な添字を渡さなければなりません。文字数の指定が大きすぎて、文字列の終わりを超えてしまうことは問題ありません(末尾の文字まですべて取り除きます)。3

条件に合う要素を取り除く

要素を取り除きたいと思う場面では、その要素がどこにあるかは分からない(管理していない)ケースもあります。そういう場合は、目的に合った要素を探し出して、その要素を指すイテレータを入手して、erase関数を呼ぶという流れを踏まなければなりません。この過程を自力でやろうとすると割と大変で、バグを入れ込んでしまう可能性も高まります。作業を肩代わりしてくれる方法があるので、これを使うようにします。

std::remove関数

まず、任意の値と一致する要素を探して取り除く方法です。この場合は、std::remove関数を使います。std::remove関数は、std::vector や std::string 自身が持つ機能ではなく、#include <algorithm> という記述が必要です。

std::remove関数には、要素を探す範囲をあらわす2つのイテレータと、探したい値を指定します。ほとんどの場合、範囲は配列全体ですから、std::remove(std::begin(v), std::end(v), 99); のような感じになります。なお、constイテレータは受け付けません。

さて、ここからが分かりづらいところですが、std::remove関数は、指定した値に一致する要素を取り除くのではなく、取り除く対象にならなかった要素を先頭付近に集めるという動作になっています。

元の配列が {1, 2, 2, 3, 1, 2} だとして、ここから 2 という値を持った要素を取り除くとします。普通は {1, 3, 1} になることを望みますが、std::remove関数は {1, 3, 1, ?, ?, ?} のようにします(? がどうなるかは実装次第であり、ここに 2 が残されている可能性もあります)。これでも先頭付近の3つだけに注目すれば、{1, 3, 1} なので、この範囲だけを見るようにすればいいというわけです。std::remove関数は、取り除かれなかった要素の範囲({1, 3, 1})の末尾の次の位置を指すイテレータを返すので、これを受け取って使えばうまくいきます。

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

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

    // v 全体から 2 を探して取り除く。
    // 取り除かれなかった要素の末尾(の次)を指すイテレータを受け取る。
    auto itEnd = std::remove(std::begin(v), std::end(v), 2);

    // 受け取ったイテレータを使って末尾を判断する
    for (auto it = std::cbegin(v); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
}

実行結果:

2
3

これでうまくいくものの、色々と不安が残ります。終端のイテレータを std::end関数などを使って取得しなおしてしまう事故はありがちですし、範囲for文が使えない(使うと本当の末尾まで走査してしまう)問題もあります。また、実は要素は取り除かれていないわけですから、要素数も減っていません。

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

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

    auto itEnd = std::remove(std::begin(v), std::end(v), 2);

    // 終端のイテレータを誤る
    for (auto it = std::cbegin(v); it != std::cend(v); ++it) {
        std::cout << *it << "\n";
    }

    // 範囲for文は余計なところまで走査してしまう
    for (auto e : v) {
        std::cout << e << "\n";
    }

    // 要素数は減っていない・・・
    std::cout << "size = " << v.size() << "\n";
}

実行結果:

1
3
1
3
1
2
1
3
1
3
1
2
size = 6

やはり、本当の意味で要素を取り除きたいと思うでしょう。そこで、このページで紹介済みの erase関数と組み合わせます。erase関数には、2つのイテレータを使って要素をまとめて取り除く(こちらは本当の意味で取り除く)機能があるので、これと併用します。

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

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

    // v 全体から 2 を探して取り除く。
    // 取り除かれなかった要素の末尾(の次)を指すイテレータを受け取る。
    auto itEnd = std::remove(std::begin(v), std::end(v), 2);

    // 本当の意味で要素を取り除く
    v.erase(itEnd, std::cend(v));

    // 実際に要素が取り除かれたので、std::cend関数で末尾を判断してかまわない
    for (auto it = std::cbegin(v); it != std::cend(v); ++it) {
        std::cout << *it << "\n";
    }

    // 範囲for文でも問題なくなった
    for (auto e : v) {
        std::cout << e << "\n";
    }

    // 要素数も減っている
    std::cout << "size = " << v.size() << "\n";
}

実行結果:

1
3
1
1
3
1
size = 3

std::remove関数と erase関数を使うところは、次のように1行にまとめてしまえます。変数itEnd も消えるので、まとめたほうがいいでしょう。

v.erase(std::remove(std::begin(v), std::end(v), 2), std::cend(v));

対象範囲が配列全体なのであれば、この1文は定型句のように使えます(2 のところを変えるだけで済みます)。

【C++20】std::erase関数が追加され、std::erase(v, 2); という非常に簡潔なコードで記述できるようになりました。1

std::remove_if関数

std::remove_if関数を使うと、取り除く要素を条件によって指定できます。値の代わりに、条件を指定すること以外は、std::remove関数と同じです。実際には要素は取り除かれませんが、erase関数との併用で、本当の意味で取り除くことができます。なお、#include <algorithm> が必要です。

例として、奇数の値を持つ要素を取り除いてみます。

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

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

    v.erase(std::remove_if(std::begin(v), std::end(v), [](int e){ return e % 2 != 0; }), std::cend(v));

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

実行結果:

2
2
2

[](int e){ return e % 2 != 0; } が条件の指定ですが、これはここまでに登場していない新しい構文です。この記法はラムダ式 (lambda expressions) と呼ばれるものです。先頭の [] が、全体がラムダ式であることを表しており、その後ろの (){} の部分から構成されます。詳しい解説はここではしませんが、std::remove_if関数が要素を1つ1つ、変数e に渡してきます((int e))。{} の中で、変数e の値を使って条件式を記述し、return文を使って、true か false を返すようにします。std::remove_if関数の場合は、true が返された要素を取り除きます。

【C++98/03 経験者】以前は、条件を記述するために、別の関数や関数オブジェクトを使っていました。今でもその方法は使えますが、ラムダ式を使ったほうが簡潔ですし、離れたところにコードを書かなくてすむ利点もあります。

【C++20】std::erase_if関数が追加され、std::erase_if(v, [](int e){ return e % 2 != 0; }); という非常に簡潔なコードで記述できるようになりました。4

ラムダ式の {} の内側で、ラムダ式の外側で宣言されている変数を使いたいときには、[] の内側にその変数の名前を記述します。複数必要なら、[v1, v2, v3] のように書きます。

次のサンプルは、変数value の値の倍数と一致する要素を取り除きます。

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

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

    int value {3};
    v.erase(std::remove_if(std::begin(v), std::end(v), [value](int e){ return e % value == 0; }), std::cend(v));

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

実行結果:

1
2
4
5
7

容量を減らす

要素を取り除いても容量は減りません。メモリの再割り当てに関する重い処理が上乗せされるため、ほとんどの場合、利点がないからです。

しかし、本当に容量を減らしたい場合もあります。要素の追加がこれ以上起こらないと断言できるのなら、余分に確保されたメモリを解放する意味があるかもしれません。

【上級】よくあるのは、reserve関数を使って多めにメモリを確保してから、要素を次々と追加していき、最終的に余分だった分をカットするという場面です。

shrink_to_fit関数

容量を減らすには、shrink_to_fit関数を使います。shrink_to_fit関数は、容量を、現在の要素数と同じになるように減らそうとします。

【C++98/03 経験者】これまで swap技法と呼ばれる方法で実現しましたが、今後は shrink_to_fit関数を使いましょう。shrink_to_fit関数は、要素のコピーを避けられる実装になっているため、効率面でも優れています。

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

int main()
{
    std::vector<int> v {};
    std::string s {};

    for (int i = 0; i < 1000; ++i) {
        v.push_back(i);
        s += "!";
    }

    std::cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";
    std::cout << "size = " << s.size() << ", capacity = " << s.capacity() << "\n";

    v.shrink_to_fit();
    s.shrink_to_fit();

    std::cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";
    std::cout << "size = " << s.size() << ", capacity = " << s.capacity() << "\n";
}

実行結果:

size = 1000, capacity = 1066
size = 1000, capacity = 1188
size = 1000, capacity = 1000
size = 1000, capacity = 1007

実行結果は、Visual Studio 2015 のものです。必ずこの結果と同じになるわけではありません。

注意しなければならないのは、shrink_to_fit関数の効果にははっきりとした強制力がないという点です。「capacity関数が返す結果を、size関数が返す結果と同じになるように容量を減らす」ということになっていますが、結果は実装に任されています5。実際、Visual Studio 2015 の実行結果をみると、std::string の方はきちんと 1000 にならず、1007 という中途半端な結果になっています。

【上級】shrink_to_fit関数は確実でないということで、swap技法という代わりの方法が紹介されることがあります。swap技法は shrink_to_fit関数がなかった古い時代の C++ で使われた方法で、std::string(s).swap(s); のように、元のオブジェクトから一時オブジェクトを作り、元のオブジェクトと交換することで容量の削減を試みます。この一時オブジェクトは、元のオブジェクトと同じ要素を持ちますが、容量は要素数から計算されるため、必要十分な容量だけが確保されます。そのため swap で入れ替えてやれば、容量が減るという寸法です。
しかし、swap技法で減らせるのなら、shrink_to_fit関数でも減らせると思われます。shrink_to_fit関数が、容量を要素数と同じ数にまで減らさないことがあるのは、実装の最適化の都合を許すためであって5、単純に要求が無視されることがあるという意味ではないはずです(たとえば、あるバイト数の倍数でなければメモリの確保が行えないシステムでは、要素数99 に合わせて、容量を 99 にはできないかもしれない)。これは swap技法であれば解決できるという問題ではないでしょう。また、swap技法の方が効率が劣るので(コピーしているため、そのコストとデストラクタのコストがかかる。shrink_to_fit関数ならムーブで済む)、少なくとも swap技法でなければならないのかどうか確認して判断するべきです。

なお、容量が減らされた場合、メモリを確保しなおしている可能性があり、そうなった場合には要素が移動しています。既存のイテレータはすべて無効になるものと考えたほうがいいです。

【C++17】イテレータが無効になることが明確にされました。6


まとめ


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


参考リンク


練習問題

問題の難易度について。

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

問題1 (確認★)

“Hello” という文字列が格納された std::string の変数s に対して、s.clear(); を実行したあとの状態として、正しいものをすべて選んで下さい。

  1. s.length() で得られる結果が 0 になる
  2. s.capacity() で得られる結果が 0 になる
  3. s.empty() で得られる結果が true になる
  4. if (s == "") が true になる

解答・解説

問題2 (基本★)

“Hello, C++ World.” が格納された std::string から文字列を取り除いて、“Hello, World.” にするプログラムを作成してください。

解答・解説

問題3 (基本★★)

1~50 の整数が格納された std::vector を用意し、標準入力によって指定された数の倍数の値を持った要素を取り除くプログラムを作成してください。

解答・解説

問題4 (応用★★★)

標準入力からの入力によって、整数を追加・削除・一覧できるプログラムを作成してください。

解答・解説

問題5 (発展★★★)

std::vector から任意の値を持った要素を取り除く処理を、削除のための各種関数やイテレータを使わず、添字を使ったアクセスのみで記述してください。

解答・解説


解答・解説ページの先頭



更新履歴




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