vector에서 중복 원소 제거

 

vector에서 중복 원소를 제거하는 방법이다.

 

unique가 실행될 때 각 원소는 자신의 양 옆 원소와 비교하여 중복을 제거한다.

• 그러므로 O(n)에 수행되지만 정렬된 상태에서만 정상 작동한다.
• 버블 정렬과 비슷한 방식이며 뒤로 몰아 놓은 중복 원소들의 시작 지점 반복자를 반환한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
ostream& operator<<(ostream& os, const vector<T> v)
{
    for (T e : v)
        os << e << ' ';

    return os;
}

void main()
{
    vector<int> v = {1, 2, 1, 3, 2, 1, 3, 2};

    cout << "제거 전: " << v << endl;

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    cout << "제거 후: " << v << endl;
}

 

출력

제거 전: 1 2 1 3 2 1 3 2
제거 후: 1 2 3

 

중복을 허용하지 않을 뿐만 아니라 정렬된 상태를 유지해야 한다면 그냥 set을 쓰면 된다.

 

#include <iostream>
#include <set>

using namespace std;

template <typename T>
ostream& operator<<(ostream& os, const set<T> v)
{
    for (T e : v)
        os << e << ' ';

    return os;
}

void main()
{
    set<int> st = {1, 2, 1, 3, 2, 1, 3, 2};

    cout << st << endl;
}

 

출력

1 2 3

 

set의 성질을 이용해 vector에서 간단하게 중복을 제거할 수도 있다.

 

그냥 set에 모든 원소를 넣었다가 빼면 된다.

 

#include <iostream>
#include <vector>
#include <set>

using namespace std;

template <typename T>
ostream& operator<<(ostream& os, const vector<T> v)
{
    for (T e : v)
        os << e << ' ';

    return os;
}

void main()
{
    vector<int> v = {1, 2, 1, 3, 2, 1, 3, 2};

    cout << "제거 전: " << v << endl;

    set<int> st(v.begin(), v.end());
    v = vector<int>(st.begin(), st.end());

    cout << "제거 후: " << v << endl;
}

 

출력

제거 전: 1 2 1 3 2 1 3 2
제거 후: 1 2 3