vectorの重複要素の削除は、まずソートしてから std::unique / erase という定番手法があるが、現在の要素の順番を崩さないまま行いたい場合もある。
こうしたケース用に、何か定番の方法があるのかと調べたら、こちらのサイトを見ただけでも実にいろいろなやり方があるらしい。
とりあえず、要素の大きさとか重複率とか気にせず、速度や効率にこだわらなければ、結局 std::set を使うベタな方法が個人的には一番分かりやすかった。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
std::vector<int> v = { 1, 78, 6, 3, 55, 41, 6, 3, 7, 1 }; std::set<int> found; for( auto it = v.begin(); it != v.end(); ) { if( found.count( *it ) ) { it = v.erase( it ); } else { found.insert( *it ); ++it; } } |
なおstd::setのメンバ関数countは1か0を返すだけ。std::findを使うよりシンプルに書ける。
テンプレート関数を作っておくと、どんな型を突っ込んだvectorでもだいたい使えるので楽かもしれない。(というか自分用に作った)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
template<typename T> void unique_erase_nosort( std::vector<T>& v ) { std::set<T> found; auto it = v.begin(); while( it != v.end() ) { if( found.count( *it ) ) { it = v.erase( it ); } else { found.insert( *it ); ++it; } } } |
ついでに std::remove_if と c++11以降のラムダ式も使ったバージョン。std::deque版。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
template<typename T> void unique_erase_nosort( std::deque<T>& d ) { std::set<T> found; auto new_end = std::remove_if( d.begin(), d.end(), [&found]( const T& val ) { if( found.count( val ) ) return true; found.insert( val ); return false; } ); d.erase( new_end, d.end() ); } |
これは、setのinsert関数の返値を使うともっとシンプルに書ける、とこちらのサイトで知った。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
template<typename T> void unique_erase_nosort( std::deque<T>& d ) { std::set<T> found; auto new_end = std::remove_if( d.begin(), d.end(), [&found]( const T& val ) { return !found.insert( val ).second; } ); d.erase( new_end, d.end() ); } |
setのメンバ関数 insert は、引数１つのバージョンだと std::pair<iterator,bool>を返す。挿入に成功するとsecondにはtrueが入る。なるほど便利。
C++Builder10.2.3で確認。
