特定の値を持つ stl ベクトルから項目を削除するにはどうすればよいですか?
質問
stl ベクターの API ドキュメントを見ていて、特定の値を持つ要素を削除できるメソッドがベクター クラスにないことに気付きました。これは一般的な操作のようですが、これを行うための方法が組み込まれていないのは奇妙に思えます。
解決
std::remove
実際にはコンテナから要素を消去しませんが、渡すことができる新しい終了イテレータを返します。 container_type::erase
コンテナの最後にある余分な要素を実際に削除するには、次のようにします。
std::vector<int> vec;
// .. put in some values ..
int int_to_remove = n;
vec.erase(std::remove(vec.begin(), vec.end(), int_to_remove), vec.end());
他のヒント
削除したい場合は の 項目については、以下の方がもう少し効率的です。
std::vector<int> v;
auto it = std::find(v.begin(), v.end(), 5);
if(it != v.end())
v.erase(it);
または、順序が重要でない場合は、アイテムの移動に伴うオーバーヘッドを回避することもできます。
std::vector<int> v;
auto it = std::find(v.begin(), v.end(), 5);
if (it != v.end()) {
using std::swap;
// swap the one to be removed with the last element
// and remove the item at the end of the container
// to prevent moving all items after '5' by one
swap(*it, v.back());
v.pop_back();
}
begin イテレータと end イテレータを指定してグローバル メソッド std::remove を使用し、その後 std::vector.erase を使用して実際に要素を削除します。
ドキュメントへのリンク
std::削除 http://www.cppreference.com/cppalgorithm/remove.html
std::vector.erase http://www.cppreference.com/cppvector/erase.html
std::vector<int> v;
v.push_back(1);
v.push_back(2);
//Vector should contain the elements 1, 2
//Find new end iterator
std::vector<int>::iterator newEnd = std::remove(v.begin(), v.end(), 1);
//Erase the "removed" elements.
v.erase(newEnd, v.end());
//Vector should now only contain 2
私の間違いを指摘してくれた Jim Buck に感謝します。
他の回答はこれをうまく行う方法をカバーしていますが、これがベクター API にないことはそれほど奇妙ではないことも指摘しておこうと思いました。これは非効率的で、ベクトル内で値を線形検索し、その後、大量のコピーを行って値を削除します。
この操作を集中的に実行している場合は、この理由から、代わりに std::set を検討する価値があるかもしれません。
ソートされていないベクトルがある場合は、最後のベクトル要素と単純に交換できます。 resize()
.
注文したコンテナを使用すると、次のことが最適になります。 std::vector::erase()
. 。があることに注意してください。 std::remove()
で定義されています <algorithm>
, しかし、実際には消去されません。(ドキュメントをよく読んでください)。
より短い解決策 (ベクトル名を 4 回繰り返す必要はありません) は、Boost を使用することです。
#include <boost/range/algorithm_ext/erase.hpp>
// ...
boost::remove_erase(vec, int_to_remove);
こちらも参照 std::remove_if 述語を使えるようにするには…
上記のリンクからの例は次のとおりです。
vector<int> V;
V.push_back(1);
V.push_back(4);
V.push_back(2);
V.push_back(8);
V.push_back(5);
V.push_back(7);
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// The output is "1 4 2 8 5 7"
vector<int>::iterator new_end =
remove_if(V.begin(), V.end(),
compose1(bind2nd(equal_to<int>(), 0),
bind2nd(modulus<int>(), 2)));
V.erase(new_end, V.end()); [1]
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// The output is "1 5 7".
から c++20:
非メンバー関数の導入 std::erase
, 、削除するベクトルと値を入力として受け取ります。
元:
std::vector<int> v = {90,80,70,60,50};
std::erase(v,50);
何も追加せずに実行したい場合は、次のものが含まれます。
vector<IComponent*> myComponents; //assume it has items in it already.
void RemoveComponent(IComponent* componentToRemove)
{
IComponent* juggler;
if (componentToRemove != NULL)
{
for (int currComponentIndex = 0; currComponentIndex < myComponents.size(); currComponentIndex++)
{
if (componentToRemove == myComponents[currComponentIndex])
{
//Since we don't care about order, swap with the last element, then delete it.
juggler = myComponents[currComponentIndex];
myComponents[currComponentIndex] = myComponents[myComponents.size() - 1];
myComponents[myComponents.size() - 1] = juggler;
//Remove it from memory and let the vector know too.
myComponents.pop_back();
delete juggler;
}
}
}
}
特に項目を消去するには 2 つの方法があります。ベクトルを取ってみましょう
std :: vector < int > v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(40);
v.push_back(50);
1) 非効率的な方法: これは非常に効率的であるように見えますが、実際はそうではありません。erase 関数が要素を削除し、すべての要素を 1 だけ左にシフトするためです。したがって、その複雑さはO(n^2)になります。
std :: vector < int > :: iterator itr = v.begin();
int value = 40;
while ( itr != v.end() )
{
if(*itr == value)
{
v.erase(itr);
}
else
++itr;
}
2) 効率的な方法 (推奨) :としても知られています ERASE - イディオムを削除します .
- std::remove は、指定された範囲を、コンテナの先頭にシフトされた指定された要素と比較しないすべての要素を含む範囲に変換します。
- したがって、実際には、一致した要素を削除しないでください。一致しないものを開始にシフトし、新しい有効な終了に反復子を与えるだけです。必要なのは O(n) の複雑さだけです。
削除アルゴリズムの出力は次のとおりです。
10 20 30 50 40 50
Remove の戻り値の型は、その範囲の新しい終端への反復子であるためです。
template <class ForwardIterator, class T>
ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val);
ここで、ベクトルの消去関数を使用して、ベクトルの新しい端から古い端まで要素を削除します。O(1) 時間がかかります。
v.erase ( std :: remove (v.begin() , v.end() , element ) , v.end () );
したがって、このメソッドは O(n) で機能します