c++ vector の重複削除

はじめに

c++ の vector の要素の重複の削除方法を 2 つ示します

unique, erase を用いる方法
vector -> set -> vector と変換する方法

問題設定

1 ~ 6 の数字からなり、すべての数字が 2 回出現するベクトル
{1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1}
の重複を削除して、ベクトル
{1, 2, 3, 4, 5, 6}
を得ます。

unique の動作確認

c++ には unique という関数があります。いかにも重複を削除しそうな名称ですが、今回の問題設定で期待する動作はしません。

#include<bits/stdc++.h>
using namespace std;

void printVec(vector<int> &vec) {
    /*
    vector の要素を出力する
    vec: 出力対象のvector
    */
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << ',';
    }
    cout << endl;
}


int main() {
    // 重複削除対象の vector を用意する
    vector<int> vec = {1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1};
    cout << "vec" << endl;
    printVec(vec);
    cout << endl;

    // unique を適用する
    cout << "vec unique" << endl;

    vector<int> vec1 = vec;
    unique(vec1.begin(), vec1.end());
    printVec(vec1);

    cout << endl;

    // sort unique を適用する
    cout << "vec sort unique" << endl;

    vector<int> vec2 = vec;
    sort(vec2.begin(), vec2.end());
    unique(vec2.begin(), vec2.end());
    printVec(vec2);

    cout << endl;
}

/* output
vec
1,2,3,4,5,6,6,5,4,3,2,1,

vec sort unique
1, 2,3,4,5,6,4,4,5,5,6,6,
*/

unique は 隣り合った要素が同一である場合に、重複部分を詰めます。
したがって、隣り合っていない要素の重複は削除されません。
この挙動は名前から受ける印象と異なるので注意しないといつか間違えそう。

unique erase を用いる方法

重複を完全に取り除くためには先にソートして、重複要素が隣り合う形にしなければなりません。
また、unique は vector の重複しない要素を前に集めるだけなので、erase を行い、不要な要素を削除しなければなりません。

#include<bits/stdc++.h>
using namespace std;

void printVec(vector<int> &vec) {
    /*
    vector の要素を出力する
    vec: 出力対象のvector
    */
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << ',';
    }
    cout << endl;
}

int main() {
    // 重複削除対象の vector を用意する
    vector<int> vec = {1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1};

    // unique erase を適用する
    cout << "vec erase" << endl;

    vector<int> vec1 = vec;
    vec1.erase(unique(vec1.begin(), vec1.end()), vec1.end());
    printVec(vec1);

    cout << endl;

    // sort unique erase を適用する
    cout << "vec sort unique erase" << endl;

    vector<int> vec2 = vec;
    sort(vec2.begin(), vec2.end());
    vec2.erase(unique(vec2.begin(), vec2.end()), vec2.end());
    printVec(vec2);

    cout << endl;
}

/* output
vec erase
1,2,3,4,5,6,5,4,3,2,1,

vec sort unique erase
1,2,3,4,5,6,

vector, set, vector と変換する方法

set は重複しないので、vector を set に変換してから vector に直せばよいのではないかと考えました。
python ならこの考え方で list(set())として重複を削除します。

#include<bits/stdc++.h>
using namespace std;

void printVec(vector<int> &vec) {
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << ',';
    }
    cout << endl;
}

int main() {
    vector<int> vec = {1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1};
    cout << "vec" << endl;
    printVec(vec);
    cout << endl;

    // set vector
    cout << "set vector" << endl;

    vector<int> vec3 = vec;
    set<int> set3(vec3.begin(), vec3.end());  // vector を set に変換
    vector<int> vec3_2(set3.begin(), set3.end());  // set を vector に変換
    printVec(vec3_2);
}

/* output
vec
1,2,3,4,5,6,6,5,4,3,2,1,

set vector
1,2,3,4,5,6,
*/

こちらの方法でも重複が削除できます。
sort 関数を持たないコンテナに対して重複削除を行いたいときに sort 関数を用意する必要がないことではないかと思います。

おわりに

list(sort()) は分かりやすいのですが、unique の挙動は私が期待するものではありませんでした。
注意いたします。

2021 05 03

#c++