削除の STLアルゴリズム | Programming Place Plus C++編【標準ライブラリ】 第21章

トップページC++編

C++編で扱っている C++ は 2003年に登場した C++03 という、とても古いバージョンのものです。C++ はその後、C++11 -> C++14 -> C++17 -> C++20 と更新されており、今後も 3年ごとに更新されます。
なかでも C++11 での更新は非常に大きなものであり、これから C++ の学習を始めるのなら、C++11 よりも古いバージョンを対象にするべきではありません。特に事情がないなら、新しい C++ を学んでください。 当サイトでは、C++14 をベースにした新C++編を作成中です。

この章の概要

この章の概要です。


削除の STLアルゴリズム

この章では、STLアルゴリズムの中から、対象の要素を削除するものを取り上げます。

STLアルゴリズムにおいて、「削除」とは論理的なものであることを注意してください。つまり、実際に要素の個数が減るわけではなく、削除されなかった後続の要素によって「上書き」されているだけです。そして、削除後の新しい有効範囲の末尾を返して、そこより後ろの要素を使わせないことで実現しています。新しく末尾になった位置よりも後ろに何があるかは実装依存です。

なお、変更を行う STLアルゴリズム(第20章)と同じく、要素を削除する STLアルゴリズムは、連想コンテナに対しては使用できません

remove

remove関数は、指定の範囲内の要素のうち、指定の値と一致する要素をすべて削除します。

namespace std {
    template <typename ForwardIterator, typename T>
    ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);
}

第1、2引数が対象の範囲を表し、第3引数で指定した値と一致する要素を削除します。戻り値は、削除を行った後の、新たな末尾(削除されなかった最後の要素の次)を指すイテレータです。

対象が std::list の場合には、メンバ関数の remove関数(第6章)を使った方が効率的です。ただし、メンバ関数の remove関数は、本当に要素を取り除くので、STLアルゴリズムの remove関数とは挙動が異なります。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

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

    std::vector<int>::iterator it = std::remove(v.begin(), v.end(), 1);

    std::for_each(v.begin(), it, Println);
    std::cout << "-------" << std::endl;
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

0
2
3
-------
0
2
3
1
3

この章の冒頭に書いているように、削除の STLアルゴリズムは、実際には要素を削除していません。そのため、戻り値で返されるイテレータを受け取って、それを新たな「末尾」とするようにしてください。上のサンプルプログラムのように、削除後に endメンバ関数の結果を使うと、削除したはずの要素が登場してしまいます。

また、実際には要素が削除されていないため、sizeメンバ関数が返す結果も変化しないことに注意してください

STLコンテナに対して remove関数を使い、本当に要素を削除したい場合には、追加処理が必要になります。

まず、std::list の場合は、前述したとおり removeメンバ関数がありますから、そちらを使えば済みます。連想コンテナの場合は、削除の STLアルゴリズムは使えないので、そもそも remove関数は使えません。代わりに、eraseメンバ関数があるので、これを使うことになります。その他のコンテナでは、eraseメンバ関数と組み合わせる必要があります。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

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

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

    std::for_each(v.begin(), v.end(), Println);
}

実行結果

0
2
3

すべての STLコンテナには、イテレータを2つ渡して、その範囲内の要素を削除する eraseメンバ関数があります(第4章)。std::remove関数が返した新しい「末尾」を指すイテレータと、endメンバ関数で取得した古い「末尾」を指すイテレータを渡すことで、削除されるべき要素を本当に取り除くことができます。

remove_if

remove_if関数は、指定の範囲内の要素のうち、指定の条件を満たす要素をすべて削除します。

namespace std {
    template <typename ForwardIterator, typename Predicate>
    ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
}

第1、2引数が対象の範囲を表し、第3引数の単項叙述関数で削除の条件を指定します。要素を elem とすると、pred(elem) が true を返す要素すべてが削除されます。戻り値は、削除を行った後の、新たな末尾(削除されなかった最後の要素の次)を指すイテレータです。

対象が std::list の場合には、メンバ関数の remove_if関数(第6章)を使った方が効率的です。ただし、メンバ関数の remove_if関数は、本当に要素を取り除くので、STLアルゴリズムの remove_if関数とは挙動が異なります。

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

namespace {
    bool IsEven(int elem)
    {
        return elem % 2 == 0;
    }
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

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

    std::vector<int>::iterator it = std::remove_if(v.begin(), v.end(), IsEven);

    std::for_each(v.begin(), it, Println);
    std::cout << "-------" << std::endl;
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

1
1
3
-------
1
1
3
1
3

本当に要素を取り除きたいときの方法は、remove関数と同様なので省略します。

remove_copy

remove_copy関数は、指定の範囲内の要素のうち、指定の値と一致する要素をすべて省き、残りの要素をもう1つの範囲へコピーします。つまり、remove関数と copy関数(第20章)が組み合わされたものです。

namespace std {
    template <typename InputIterator, typename OutputIterator, typename T>
    OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
}

第1、2引数がコピー元の範囲、第3引数がコピー先の範囲の先頭です。第4引数の値と一致する要素についてはコピー対象から省かれます。戻り値は、最後にコピーされた要素の次を指すイテレータです。

copy関数と同様に、コピー先に十分な領域があることが前提になることに注意してください。挿入イテレータ(第25章)の使用を検討するのも良いでしょう。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

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

    std::vector<int> result(5);

    std::vector<int>::iterator it = std::remove_copy(v.begin(), v.end(), result.begin(), 1);
    std::for_each(result.begin(), it, Println);
}

実行結果

0
2
3

remove_copy_if

remove_copy_if関数は、指定の範囲内の要素のうち、指定の条件を満たす要素をすべて省き、残りの要素をもう1つの範囲へコピーします。つまり、remove_if関数と copy関数(第20章)が組み合わされたものです。

namespace std {
    template <typename InputIterator, typename OutputIterator, typename Predicate>
    OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
}

第1、2引数がコピー元の範囲、第3引数がコピー先の範囲の先頭です。第4引数の単項叙述関数で削除の条件を指定します。要素を elem とすると、pred(elem) が true を返す要素すべてがコピー対象から省かれます。戻り値は、最後にコピーされた要素の次を指すイテレータです。

copy関数や remove_copy関数などと同じく、コピー先に十分な領域があることが前提になることに注意してください。

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

namespace {
    bool IsEven(int elem)
    {
        return elem % 2 == 0;
    }
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

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

    std::vector<int> result(5);

    std::vector<int>::iterator it = std::remove_copy?if(v.begin(), v.end(), result.begin(), IsEven);
    std::for_each(result.begin(), it, Println);
}

実行結果

1
1
3


unique

unique関数は、指定した範囲内に、連続して同じ値の要素(または条件を満たす要素)があったとき、後ろ側の要素を削除することで、重複を取り除きます。

namespace std {
    template <typename ForwardIterator>
    ForwardIterator unique(ForwardIterator first, ForwardIterator last);

    template <typename ForwardIterator, typename BinaryPredicate>
    ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
}

remove関数と同様に、実際には要素は削除されません

第1、2引数が対象の範囲になります。戻り値は、削除を行った後の、新たな末尾(削除されなかった最後の要素の次)を指すイテレータです。

2つ目の形式の場合には、第3引数に、二項叙述関数を指定します。ある1つの要素を elem とし、その後ろの要素を elem2 とすると、pred(elem, elem2) が true を返した場合に、elem2 を削除します。

ここで elem2 が削除された場合に、さらにその後ろに elem3 があるとすると、pred(elem, elem3) を実行します。つまり、隣接する要素が渡されてくるとは限らず、これまでに削除されなかった一番最後の要素と、現在注目している要素とが渡されます

unique関数は、重複を取り除く関数ではありますが、条件を満たす要素同士が隣接していなければならないことに注意してください。たとえば、{1, 2, 2, 3, 4} というデータ列であれば {1, 2, 3, 4} を得られますが、{1, 2, 3, 2, 4} というデータ列の場合には、{1, 2, 3, 2, 4} のままになります。隣接しているかどうかに関わらず重複を取り除きたい場合には、事前にソートを行う必要があります(ソートを行う STLアルゴリズムについては、第23章で取り上げます)。

使用例は次のようになります。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(1);
    v.push_back(2);
    v.push_back(2);

    std::vector<int>::iterator it = std::unique(v.begin(), v.end());
    std::for_each(v.begin(), it, Println);
    std::cout << "-------" << std::endl;
    std::for_each(v.begin(), v.end(), Println);
}

実行結果

0
1
2
-------
0
1
2
2
2

std::list に関しては、メンバ関数版の unique関数があるので、そちらを使った方が効率的です。ただし、std::list の uniqueメンバ関数は、実際に要素を削除します。

unique_copy

unique_copy関数は、指定した範囲内に、連続して同じ値の要素(または条件を満たす要素)があったとき、後ろ側の要素を削除することで重複を取り除き、残った要素をもう1つの範囲へコピーします。つまり、unique関数と copy関数(第20章)が組み合わされたものです。

namespace std {
    template <typename InputIterator, typename OutputIterator>
    OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);

    template <typename InputIterator, typename OutputIterator, typename BinaryPredicate>
    OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
}

第1、2引数がコピー元の範囲、第3引数がコピー先の範囲の先頭です。戻り値は、最後にコピーされた要素の次を指すイテレータです。

1つ目の形式の場合は、値が一致する要素が連続していたら、後ろ側の要素は取り除かれます。2つ目の形式の場合は、第4引数で指定した二項叙述関数で条件を指定します(詳細は、unique関数を参照)。

copy関数と同様に、コピー先に十分な領域があることが前提になることに注意してください。挿入イテレータ(第25章)の使用を検討するのも良いでしょう。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(1);
    v.push_back(2);
    v.push_back(2);

    std::vector<int> result(5);

    std::vector<int>::iterator it = std::unique_copy(v.begin(), v.end(), result.begin());
    std::for_each(result.begin(), it, Println);
}

実行結果

0
1
2


練習問題

問題① {0, 1, 2, 1, 1} という5つの要素が格納された、vector、list、set、配列から、値が 1 の要素を削除する処理をそれぞれ作成してください。配列以外は、実際に要素を削除してください。また、STLアルゴリズムだけでなく、コンテナの持つ機能も考慮に入れてください。

問題② {0, -1, 2, -3, 4} という5つの要素が格納された、vector、list、set、配列から、負数の要素を削除する処理をそれぞれ作成してください。配列以外は、実際に要素を削除してください。また、STLアルゴリズムだけでなく、コンテナの持つ機能も考慮に入れてください。


解答ページはこちら

参考リンク


更新履歴

’2016/11/26 新規作成。



前の章へ (第20章 変更を行う STLアルゴリズム)

次の章へ (第22章 並び替えの STLアルゴリズム)

C++編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る