STL C++ : vector 중복원소 제거

STL C++ : vector 중복원소 제거

알게된 배경

 한대의 관리 PC에서 여러대의 디바이스 리눅스 계열 운영체제에 접속하는 디바이스 IP 리스트를 관리하기 위해서는 중복으로 접속을 하면 안되기 때문에 중복 검사하는 알고리즘이 필요 하게 되었었다. 일단 이 디바이스 정보들은 vector에 읽어놓은 상태이다(list를 사용하지 않은 이유는 일반적으로 디바이스 정보는 초기에만 설정을 해주고 나머지는 주로 읽기 때문에 이러한 구성을 선택하였다).

 기존의 수많은 STL 관련 서적들에서는 주로 숫자로 된 원소만 정렬하기 때문에 과연 실무에서 응용이 될지 의문이 들었었는데, 프로젝트를 하다 보니 응용을 하게 되어 다시 정리하게 되었다.

디바이스 리스트의 중복 검사

 일반적인 방법은 디바이스 정보중에 구분이 가능한 유니크(unique)한 요소로 비교하여 중복이 될 경우에는 바로 삭제하면 좋겠지만, vector에서 비교 도중에 삭제할 경우 index가 변경되는등 예상지 못하는 상황이 발생된다(그리고 코드도 복잡해진다).

 때문에 안전한 방법 생각한것은 다음과 같다.

1. 중복 검사중에는 중복으로 판된된 vector의 index만 따로 뽑아서 다른 vector에 저장을 해놓는다.

 이부분은 상황에 따라서 로직을 만들면 된다. 여기서는 잘 알려진 방법인 버블 정렬 하는 방식으로 비교하되 같은지 여부를 체크한다. 이 경우 2개의 중복이 있을 경우 문제가 안되지만, 3개 이상의 중복 원소가 있을 경우에는 문제가 생긴다. 때문에 이를 보완하기 위해서 2, 3단계들을 추가로 진행하는 것이다.

2. 중복 index가 있는 vector는 int같은 숫자 원소를 갖고 있기 때문에 (대부분 STL 교재의 예제에 있는)일반적으로 중복 검사 알고리즘으로 제거를 한다.

3. 중복 검사가 끝난 index들을 재 정렬을 한다.

4. 3에서 정렬한 vector의 index를 읽어서 제거를 한다. 이때 index가 큰 순서대로(배열의 뒤에서 부터) 제거를 한다.

 vector가 뒤에서 줄어들기 때문에 index가 바뀌는 일도 없고, 데이터 삭제시 이동되는 위치가 다르기 때문에 연산량도 줄어들게 된다.

STL vector 중복 제거

#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct deviceinfo
{
    string hostname;
    // 기타 요소
};

vector<int> checkOverlap(const vector<deviceinfo> &devVec)
{
    // 중복되는 원소가 보이면, 해당 index를 indexVec에 넣어주는 알고리즘을 구현한다.
    // 여기서는 devVec의 구조체 안에 hostname이 string을 비교한다고 가정한다.
    vector<int> indexVec;
    auto it = devVec.begin();    // auto는 C++11이상에서 사용
    for(int i=0; i<devVec.size(); ++i)
    {
        for(int j=i+1; j<devVec.size(); ++j)
        {
            if(0 == it[i].hostname.compare(it[j].hostname))
                indexVec.push_back(j);
        }
    }
    return indexVec;
}

void rmOverlap(vector<deviceinfo> &devVec)
{
    vector<int> indexVec = checkOverlap(devVec);

    // index중에서 중복되는 부분을 제거
    sort(indexVec.begin(), indexVec.end(), less<int>() );
    vector<int>::iterator pos;
    pos = unique(indexVec.begin(), indexVec.end() );
    indexVec.erase(pos, indexVec.end() );

    // 중복이 제거된 index를 내림차순으로 정렬
    sort(indexVec.begin(), indexVec.end(), less<int>() );
    // 디바이스 vector에서 중복 index부분을 제거
    pos = indexVec.begin();
    for(; pos != indexVec.end(); ++pos)
    {
        devVec.erase(devVec.begin() + (*pos));
    }
}

일반적으로 알려있는 부분은 이미 다른 사람(과 교재)에서 많이 검중이 되었기 때문에 이를 응용할 경우 비교적 안전하다. 중간에 삭제 삽입이 쉬운 리스트로 중복 검사를 한뒤에 vector로 옮겨서 사용하는 방법도 방법중 하나가 된다.

참고자료

블로그: 중복제거에 대해 간략히 나옴(설명은 없음)

추가수정(2017.6.7)