stl vector の API ドキュメントを調べていたところ、特定の値を持つ要素を削除できるメソッドが vector クラスにないことに気付きました。これは一般的な操作のように思えますが、これを行う方法が組み込まれていないのは奇妙に思えます。
11 に答える
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();
}
グローバル メソッド std::remove を begin および end イテレータと共に使用してから、std::vector.erase を使用して要素を実際に削除します。
ドキュメント リンク
std::remove 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 に感謝します。
ソートされていないベクトルがある場合は、最後のベクトル要素と単純に交換できますresize()
。
順序付けられたコンテナーでは、<code>std::vector::erase() を使用するのが最適です。std::remove()
に が定義されていることに注意してください。ただし<algorithm>
、実際には消去は行われません。(ドキュメントを注意深く読んでください)。
他の回答はこれをうまく行う方法をカバーしていますが、これがベクター API にないことは本当に奇妙ではないことも指摘したいと思います。値のベクターを介した非効率的で線形検索であり、その後に多数が続きますコピーして削除します。
この操作を集中的に行っている場合は、代わりに std::set を検討する価値があります。
述語を使用できるようにするには、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".
より短い解決策 (ベクトル名を 4 回繰り返す必要はありません) は、Boost を使用することです。
#include <boost/range/algorithm_ext/erase.hpp>
// ...
boost::remove_erase(vec, int_to_remove);
http://www.boost.org/doc/libs/1_64_0/libs/range/doc/html/range/reference/algorithms/new/remove_erase.htmlを参照してください。
特にアイテムを消去するために使用できる方法は 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)非効率的な方法:非常に効率的であるように見えますが、消去関数が要素を削除し、すべての要素を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 - REMOVE イディオムとしても知られています。
- 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) で機能します