c++ stl map

- map이란?

map[key]=value

key와 value로 구성된 자료구조이다.

 

key값으로 해당 원소를 접근한다.(원소= value)

 

즉 배열은 30이라는 원소에 접근할 때 a[1](첫 번째 원소에 30저장 돼있다)과 같은 방식이라면

map은 a[key] (key라는 이름의 인덱스에 30이 저장 돼있다) 와 같은 방식으로 원소에 접근한다.   

 

key 값의 중복을 허용하지 안는다.

 

map은 <key,value> pair 객체를 노드로 갖는 red black tree(binary search tree의 일종)로 구현 돼있다.

 

binary search tree의 경우  트리 최악의 높이는 n이다 반면

red black tree는 o(logn)을 갖는다.

 

 

-해더 파일

#include<map>

 

-생성

map< key_type, value_type , compare , allocator>

 

1) key_type: key의 type 지정

2) value_type: value의 type 지정

3) compare: map의 정렬 기준 (default= 오름 차순)  생략가능

4) allocator: map의 메모리 할당 취소 되는 개체를 나타내는 형식 (defalut= pair<key,value>) 생략가능

 

사용 예시)

map<string,int> m;

* map<string,int> m = a와 같이 a map을 m에 복사할 수 있다.

 

 

-함수

 

1)begin():

시작 요소(이진트리의 루트)를 가리키는 정방향 iterator 반환

 

2)end():

마지막 요소 다음 위치(맨 마지막 요소 다음)를 가리키는 정방향iterator 반환

 

3)rbegin():

끝 요소를 가리키는 역방향 iterator 반환

 

4)rend():

시작 요소 전 위치를 가리키는 역방향 iterator 반환

*역방향 iterator를 iterator로 받을시 map<key_type,value_type>::reverse_iterator로 iterator 생성

 

<역방향 iterator vs 정방향 iterator>

 

5)empty():

map이 비어있으면 1을 리턴 아니면 0을 리턴

 

6)size():

map에 저장된 요소의 갯수 리턴

 

7)clear():

map에 있는 모든 요소 삭제

 

8)max_size():

    저장 가능한 최대 요소 갯수 리턴

 

9)[]과 at:

   요소에 접근시 사용  O(log n)의 시간복잡도

   ex) m["abc"]-> key를 "abc"로 갖는 요소에 접근 // m.at("abc")

   *[]는 범위를 벗어나면 예외 처리x , at은 범위를 체크해서 예외 처리를 해줌 

    (접근 범위 예측이 어려울 경우 안전하게 at을 사용하자)  ps.그냥 존재하는 원소의 key값을 알고 있다면 []쓰자..

 

10) find:

     iterator find (key) key값의 위치를 가리키는 iterator 반환 O(log n)의 시간복잡도

 

11) insert:

     pair<iterator,bool> insert (pair<Key,value>) 의 형태로 

     반환된 pair의 첫 요소는 insert된 위치를 가리키는 iterator , 두번째 요소는 insert 성공 여부를 나타낸다.

     (key와 value자리에 변수 사용 가능)

 

     * insert vs =

      원소 삽입에 있어 insert와 []방식이 있다.

       insert는 key값에 초기 삽입시 ok , 삽인된 value가 있다면 overwrite 되지 안는다. 

       =는 key값으로 초기 삽입 ok , overwrite도 가능하다. 

       (ex. m[key]=3과 같이 삽입 가능)

       ps. insert시 return값으로 무언가를 확인할 필요가 없다면 훨씬 편하니 =를 사용하자   

       

     * insert의 3가지 유형: 

 

      ->첫번째= 위의 설명한것 pair<iterator,bool> insert (pair<Key,value>)   o(log n)의 시간 복잡도를 갖는다.

          ps.가장 많이 쓰인다 사실 이것만 알아도 됨....

   

       ->두번째= iterator insert (iterator position , key-value)  이며

          position은 value를 삽입시 빠르게 삽입하기 위해 삽입 위치에 대한 힌트를 주는 것이다.  상수 시간(대신 힌트를

          가까운 곳에 줘야 함)

       

       ->세번째= void insert( 다른map의 삽입 할 요소들의 시작 iterator , 다른 map의 삽입 할 요소들의 끝 iterator)

          로 다른 map의 원하는 범위 요소들을 삽입하는 것

          즉 다른 map원하는 요소 범위를 현재 map에 복사하는것   요소갯수*o(logn)의 시간 복잡도를 갖는다.

       

 

12)erase:

 

  *3가지 유형

    ->첫번째= void erase(iterator)    iterator가 가리키는 위치 원속 삭제 상수시간 시간복잡도

    ->두번째= void erase(iterator first , iterator last)   first~last직전원속들 삭제 상수시간*원소수 시간복잡도

    ->세번째= size_type erase (key)  key값에 해당하는 원소 삭제 O(log n)의 시간복잡도

 

 

13)lower_bound & upper_bound:  

    iterator lower_bound(key) , iterator upper_bound(key) 

    O(log n)의 시간 복잡도

     

 

    m['a']=value;

    m['b']=value;

    m['c']=value;

    m['d']=value;

    m['e']=value;

 

    m.lower_bound('c')는 m['c']에 해당하는 iterator 반환 (만일 m['c']라는 곳에 원소가 없다면 m['b'])

    m.upper_bound('c')는 m['d']에 해당하는 iterator 반화

 

    즉 lower_bound는 key보다 가장 가깝게 작거나 같은 key에 해당하는 iterator 반환

    upper_bound는 key보다 큰 key에 해당하는 iterator 반환 

 

14) equal_range

pair<iterator,iterator> equal_range (key)

O(log n)의 시간 복잡도

 

pair의 첫번째 요소는 lower_bound 결과의 iterator

두번째 요소는 upper_bound 결과의 iterator 이다.

 

15) count

int count (value)

O(log n)의 시간 복잡도

 

map에 value 값을 갖는 요소를 찾는 함수로 없다면 0 있다면 1을 return한다.