[C++] Container 2 : set , map

 

1. Header

Set header <set> 에는 'set' 과 'multiset',

Map header <map> 에는 'map' 과 'multimap'

이 정의되어 있다. 

 

4개의 컨테이너를 동시에 다루는 이유는

(1) 모두 균형잡힌 이진트리(Red-Black Tree)로 구현되었으며

(2) method 가 거의 동일하기 때문이다.

 

모든 method 를 다루지는 않는다. 많이 쓰이는 method 들을

'생성->순회 or 탐색 -> 제거 -> 정리'

순서로 정리해 보자.

2. Construction

(1) insert method 를 이용하여 하나씩 삽입하는 것이 직관적인 방식일 것이다.

    int arr[]={6, -5, 3, 11, -1};
    set<int> s1;
    map<int,int> m1;

    for(int i=0;i<5;i++) {
        s1.insert(arr[i]);
        m1.insert({i, arr[i]});  
        // m1.insert( pair<int,int>(i,arr[i]) ); 와 같다.
    }

map 의 경우

m1[i]=arr[i];

처럼 삽입하는 것이 가능한데 주의해야 할 점이 있으니 글의 마지막에서 따로 언급한다.

 

(2) insert 는 range 를 이용할 수 있다.

위의 코드에 새로운 set 과 map 을 추가해보자.

    int arr[]={6, -5, 3, 11, -1};
    set<int> s1,s2;
    map<int,int> m1,m2;

    for(int i=0;i<5;i++) {
        s1.insert(arr[i]);
        m1.insert({i, arr[i]});
    }
    s2.insert(begin(arr), end(arr));
    m2.insert(begin(m1), end(m1));

마지막 두 라인에서 range insertion 이 사용되었다.

 

(3) 그런데, 생성자 역시 range insertion 을 사용할 수 있다.

    int arr[]={6, -5, 3, 11, -1};
    set<int> s1;
    map<int,int> m1;

    for(int i=0;i<5;i++) {
        s1.insert(arr[i]);
        m1.insert({i, arr[i]});
    }
    set<int> s2(begin(arr), end(arr)); 
    // s2(s1) 과 같다. 여기서는 arr 에 집중한 코드로 이해한다.
    
    map<int,int> m2(begin(m1), end(m1));  
    // m1 전체를 복사하는 경우라면 m2(m1) 이 더 간단하다. 
    // 그러나 일부분만 복사하는 경우를 위해 위의 코드를 사용했다.

위의 (2) 와 비교하면 이쪽이 더 간결하다.

하지만 이미 존재하는 set 이나 map 에 추가하는 경우라면 insert 를 써야할 것이다.

 

(4) 특정 위치에 새로운 자료들을 삽입하는 상황이라면 'advance' 와 'inserter' 를 사용해야 한다.

이와 관련된 내용은 다른 글에서 따로 다룬다.

 

(5) <iterator> header 에 정의된 begin, end 는 모든 container 헤더에 정의되어 있다. 

위의 코드에서 평범한 배열에

begin(arr), end(arr)

를 사용한 것에 주목하자.  다른 container 들도 이 함수들을 사용하는 것이 일관성이 있어 좋아 보인다.

예를 들어 v 가 벡터일 때, v.begin() 보다 begin(v) 를 사용하는 것을 개인적으로 선호한다.

 

3.  begin( ),  end( ),  rbegin( ),  rend( )  method

순서가 유지되는 set, map 에서는 key 를 순서대로 다룰 수 있게 해 준다. 

but, 위 문단에서 말한 것처럼 개인적으로

method 를 사용한 s1.begin() 보다

<iterator> 에 정의된 being 함수를 사용한  begin(s1) 을 선호한다. 

딱히 퍼포먼스에 차이가 있는 것은 아니니 취향에 따라 쓰면 될 듯.

 

4. 탐색 : find( k ), count( k ), lower_bound( k ), upper_bound( k )

균형 잡힌 이진트리를 사용하는 이유는 순서를 유지하고 탐색을 용이하게 만들기 위해서 일 것이다.

(1) find( K ) method 는 iterator를 반환한다. (Get iterator to element with key 'k')

위의 예에서 사용된 set s1 , map m1 의 경우

 

- s1.find(-5) 과 m1.find(-5) 는 각각 begin(s1)과 begin(m1) 을 리턴한다. (가장 작은 값이므로)

k 를 key로 가지는 경우 해당 순서의 iterator를 반환한다는 뜻.

 

- s1.find(1000) 과 m1.find(1000) 는 각각 end(s1) , end(m1)을 리턴.(존재하지 않은 key)

 

(2) count(k)

key 가 k 인 요소의 갯수를 반환한다. 

중복이 허용되지 않는 set, map 은 0, 1 의 값이 반환된다.

multiset, multimap 에서는 2 이상의 값이 반환될 수 있다.

 

(3) lower_bound(k), upper_bound(k)

lower_bound(k) : k 이상인 최초 원소의 iterator를 리턴.

upper_bound(k) : k 초과의 최초 원소의 iterator를 리턴.

 

범위를 지정하려면 <algorithm> 헤더의 lower_bound, upper_bound 를 사용한다.

 

5. 삭제 : erase(iter) , erase(start_iter, end_iter)

* 주의 :  find(k) 의 k 는 key 값이지만 erase(iter) 의 iter는 iterator 이다.

따라서 key 가 k인 원소를 제거하려면 먼저 find 로 iter를 반환받아 사용해야 한다.

s1.erase(s1.find(k));

범위로 사용할 때 [start_iter, end_iter) 로 end_iter 가 포함되지 않는다. 

 

6. 청소 : clear()

s1.clear( );

는 모든 원소를 제거한다.  

 

 

P.S. 

map 원소 추가 방법은 손쉽게

m1[1000]=-1000;

로 이루어질 수 있다.

 

문제는 이미 존재하는 key 인 경우 '삽입'이 아닌 '갱신'이 된다.

 

또 다른 문제점을 살펴 보자.

    int arr[]={6, -5, 3, 11, -1};
    set<int> s1;
    map<int,int> m1;

    for(int i=0;i<5;i++) {
        s1.insert(arr[i]);
        m1.insert({i, arr[i]});
    }

    if(m1[1000]==m1[3]);
    printf("key: %d , value: %d\n",1000, m1[1000]);

for loop 에서 m1 은 key 가 0~5 까지 생성되었다.

 

if 문에서 존재하지 않는 key 인 1000 을 이용해 비교했는데, 이 순간

m1[1000]=default-value; 

로 생성된다. 따라서 이후에는 key가 1000 인 원소 m1[1000] 이 존재하게 된다. 

 

m1[key] 의 형태로 다룰 때는 약간 주의가 필요하다.