削除関係のアルゴリズムは６つあります。以前にも説明した内容が含まれますが、改めて１章割いて説明 します。
削除のアルゴリズムについて非常に重要な点は、"実際には削除されていない"というあまりに意外 な点です。ではどうやっているかというと、削除したい要素を、後続の要素で上書きしています。その 結果、末尾近くには要素が残ったままになるので、削除のアルゴリズムを実行してもコンテナ全体のサイズは 変化しません。本当の意味で削除したい場合には、削除のアルゴリズムを実行した後で、更にerase()を呼び出す 必要があります。これについては後で見てみましょう。
まず基本形となるremove()です。第１引数と第２引数で指定した範囲内 の要素を調べ、第３引数で指定した値と同じ値をもつ要素を削除します（したように見せかけます）。
#include <algorithm>
#include <vector>
#include <iostream>
int main()
{
using namespace std;
vector<int> nums;
nums.push_back( 3 );
nums.push_back( 6 );
nums.push_back( 4 );
nums.push_back( 3 );
nums.push_back( 5 );
// vectorの中から3を削除する
remove( nums.begin(), nums.end(), 3 );
// 結果を出力する
vector<int>::iterator it = nums.begin();
while( it != nums.end() )
{
cout << *it << endl;
++it;
}
return 0;
} |
さて、出力結果はどうなるでしょう。このようになります。
6 4 5 3 5
元々５つの要素があり、そこから予定では２個の「３」を削除したので、出力結果は残りの３個の要素が出力 されることを期待したはずです。しかし出力されるのは５個の要素で、しかも４個目には存在してはならない「３」 が含まれています。
これがSTLの削除アルゴリズムの特徴です。しかし、次のようにプログラムを書けばremove()で問題なく動作 します。
#include <algorithm>
#include <vector>
#include <iostream>
int main()
{
using namespace std;
vector<int> nums;
nums.push_back( 3 );
nums.push_back( 6 );
nums.push_back( 4 );
nums.push_back( 3 );
nums.push_back( 5 );
// vectorの中から3を削除する
vector<int>::iterator end_it = remove( nums.begin(), nums.end(), 3 );
// 結果を出力する
vector<int>::iterator it = nums.begin();
while( it != end_it )
{
cout << *it << endl;
++it;
}
return 0;
} |
remove()は戻り値として、削除後の状態として有効な範囲の末尾を指すイテレータを返します。そこで、この 戻り値を受け取っておき、それをコンテナの新しい末尾として利用すればいいのです。上のプログラムの出力結果 はこうなります。
6 4 5
これで期待通りの出力結果になりました。しかし、このようにしていても、nums.end()はやはり５つ目の要素の 後ろを指していますから、うっかりnums.end()を使おうものなら、間違った結果になってしまうことに変わりは ありません。そこで、本当の意味で要素を削除する方法を知っておく必要があります。本当の意味での削除を行う には、erase()を併用します。次のようにすればいいです。
#include <algorithm>
#include <vector>
#include <iostream>
int main()
{
using namespace std;
vector<int> nums;
nums.push_back( 3 );
nums.push_back( 6 );
nums.push_back( 4 );
nums.push_back( 3 );
nums.push_back( 5 );
// vectorの中から3を削除する
vector<int>::iterator end_it = remove( nums.begin(), nums.end(), 3 );
// 本当の意味での削除を実行する
nums.erase( end_it, nums.end() );
// 結果を出力する
vector<int>::iterator it = nums.begin();
while( it != nums.end() )
{
cout << *it << endl;
++it;
}
return 0;
} |
結果を出力するときのwhileループに、nums.end()を使っていますが、出力結果は次のように正しいものに なります。
6 4 5
erase()は、第１引数で指定した位置から、第２引数で指定した位置までの要素を削除します。remove() とは違って、本当の意味での削除です。削除開始位置は、remove()の戻り値で受け取った位置、削除終了位置 は、コンテナ本来の終端位置になります。これで、いらない部分だけが綺麗に削除されます。
ただし、list の場合には、この方法ではなく、単純に list のメンバ関数 remove() を呼び出す方が 効率的です。
#include <algorithm>
#include <list>
#include <iostream>
int main()
{
using namespace std;
list<int> nums;
nums.push_back( 3 );
nums.push_back( 6 );
nums.push_back( 4 );
nums.push_back( 3 );
nums.push_back( 5 );
// list の中から 3 を削除する
nums.remove( 3 );
// 結果を出力する
list<int>::iterator it = nums.begin();
while( it != nums.end() )
{
cout << *it << endl;
++it;
}
return 0;
}
|
STL には、同じ名前の関数が多数定義されていることがありますが、コンテナに同名のメンバ関数が存在 する場合は、メンバ関数のものを使う方が効率的です。
remove_if()は、第３引数に叙述関数を使って、条件に合う要素だけを 削除するというものです。
#include <algorithm>
#include <vector>
#include <iostream>
class CSample
{
public:
// 引数の値が３の倍数のときtrueを返す叙述関数
bool operator()(int num) const { return ( num % 3 == 0 ); }
};
int main()
{
using namespace std;
vector<int> nums;
nums.push_back( 3 );
nums.push_back( 6 );
nums.push_back( 4 );
nums.push_back( 3 );
nums.push_back( 5 );
// vectorの中から３の倍数の要素を削除する
vector<int>::iterator end_it = remove_if( nums.begin(), nums.end(), CSample() );
// 本当の意味での削除を実行する
nums.erase( end_it, nums.end() );
// 結果を出力する
vector<int>::iterator it = nums.begin();
while( it != nums.end() )
{
cout << *it << endl;
++it;
}
return 0;
}
|
このプログラムでは、remove_if()は、３の倍数の要素を削除します。出力結果は、
4 5
となります。
削除のアルゴリズムといっていいものか分かりませんが、remove_copy()は、 ある要素を他のコンテナにコピーしつつ、指定された値については削除を行います。従って、いらないものを削除 した結果を、他のコンテナに格納し直すために使います。
#include <algorithm>
#include <vector>
#include <iostream>
int main()
{
using namespace std;
vector<int> nums, nums2;
nums.push_back( 3 );
nums.push_back( 6 );
nums.push_back( 4 );
nums.push_back( 3 );
nums.push_back( 5 );
nums2.resize( nums.size() ); // nums2のサイズを、numsのサイズに合わせて変更
// ３を削除しながら、numsをnums2にコピーする
vector<int>::iterator end_it = remove_copy( nums.begin(), nums.end(), nums2.begin(), 3 );
// 結果を出力する
vector<int>::iterator it = nums2.begin();
while( it != end_it )
{
cout << *it << endl;
++it;
}
return 0;
} |
第１引数と第２引数で、コピー元の範囲を指定します。第３引数は、コピー先のコピー開始位置を指定します。 第４引数は、削除したい値を指定します。戻り値は、コピー先の要素の中で、最後にコピーされた要素の次の位置 です。
remove_copy()は、remove()とcopy()を組み合わせたアルゴリズムです。copy()については、次章 で説明します。
例によって、最後に_ifが付いたら、条件が叙述関数になります。つまり、remove_copy()の第４引数を、削除したい 値ではなく、削除したい要素が持つべき条件を指定するようにします。
#include <algorithm>
#include <vector>
#include <iostream>
class CSample
{
public:
// 引数の値が３の倍数のときtrueを返す叙述関数
bool operator()(int num) const { return ( num % 3 == 0 ); }
};
int main()
{
using namespace std;
vector<int> nums, nums2;
nums.push_back( 3 );
nums.push_back( 6 );
nums.push_back( 4 );
nums.push_back( 3 );
nums.push_back( 5 );
nums2.resize( nums.size() ); // nums2のサイズを、numsのサイズに合わせて変更
// ３の倍数の要素を削除しながら、numsをnums2にコピーする
vector<int>::iterator end_it = remove_copy_if( nums.begin(), nums.end(), nums2.begin(), CSample() );
// 結果を出力する
vector<int>::iterator it = nums2.begin();
while( it != end_it )
{
cout << *it << endl;
++it;
}
return 0;
}
|
remove_if()のところで使ったものと同じ叙述関数を使いました。３の倍数の値をもつ要素を削除しながら、コピーを 実行します。
remove_copy_if()は、remove_if()とcopy()を組み合わせたアルゴリズムです。copy()については次章。
unique()は、指定範囲内に同じ値が連続して並んでいる場合、それらをまとめて１ つの要素にします。つまり、重複を排除するアルゴリズムです。勘違いしないで欲しいのは、連続している場合にだけ 有効だということです。離れたところに同じ値があっても、それらは削除されません。ちなみに"unique"は「ユニーク」と 呼びます。「唯一の」「他にはない」といったような意味です。
unique_if()という名前のアルゴリズムは存在しませんが、叙述関数を使うこともできます。単純なunique()は、第１引数 と第２引数で範囲を指定するだけですが、ここに第３引数を加えて、そこに叙述関数を指定すればいいです。
#include <algorithm>
#include <vector>
#include <iostream>
int main()
{
using namespace std;
vector<int> nums;
nums.push_back( 3 );
nums.push_back( 6 );
nums.push_back( 3 );
nums.push_back( 3 );
nums.push_back( 5 );
// 連続する値を削除する
vector<int>::iterator end_it = unique( nums.begin(), nums.end() );
// 本当に削除する
nums.erase( end_it, nums.end() );
// 結果を出力する
vector<int>::iterator it = nums.begin();
while( it != nums.end() )
{
cout << *it << endl;
++it;
}
return 0;
}
|
実行結果は次のようになります。
3 6 3 5
連続した同じ値は「３」ですが、最初の「３」は連続していないので削除対象外です。連続している２つの「３」 の部分でだけ削除処理が行われますが、あくまでも重複の排除なので、１つは残します。
removeという名前が付かないので忘れがちになりますが、unique()の場合も、実際には削除が行われませんので、 本当に削除したければ、erase()を呼び出す必要があります。
最後の削除アルゴリズムは、unique_copy()です。remove_copy()のunique() 版です。つまり、連続する重複を排除しつつ、他のコンテナにコピーします。
こちらもどういう訳か、unique_copy_if()というアルゴリズムは存在していません。叙述関数を使う場合は、 最後に１つ引数を追加します。通常のunique_copy()の引数は３つで、第１・２引数でコピー元の範囲を、第３ 引数で、コピー先の最初の位置を指定します。
#include <algorithm>
#include <vector>
#include <iostream>
int main()
{
using namespace std;
vector<int> nums, nums2;
nums.push_back( 3 );
nums.push_back( 6 );
nums.push_back( 3 );
nums.push_back( 3 );
nums.push_back( 5 );
nums2.resize( nums.size() ); // nums2のサイズを、numsのサイズに合わせて変更
// 連続する３を削除しつつ、numsをnums2にコピーする
vector<int>::iterator end_it = unique_copy( nums.begin(), nums.end(), nums2.begin() );
// 結果を出力する
vector<int>::iterator it = nums2.begin();
while( it != end_it )
{
cout << *it << endl;
++it;
}
return 0;
}
|
削除する要素の選択条件が異なるだけで、remove_copy()やremove_copy_if()と同じことです。