[ft_containers] 4. map 이해하기

이 과제의 통곡의 벽, map을 본격적으로 구현하기 전에 STL에 있는 맵의 기능을 제대로 이해할 필요가 있을 것 같으니 자세히 살펴보고자 한다.

 

map이란?

맵은 key와 value로 이루어진 pair를 정렬하여 저장하는 자료구조이다.

key는 원소를 정렬하고 원소를 식별하기 위해 사용하는 유일한 값이다. 즉, 하나의 맵 내부에서 key값은 중복될 수 없음!

key를 이용하여 map 내부에 저장되어 있는 특정한 value를 find 할 수 있다.

 

key와 value의 타입은 서로 다를 수 있으며, 내부의 value type은 다음과 같이 typedef 되어있음.

typedef pair<const Key, T> value_type;

 

이러한 map은 STL 내부에서는 Red-Black 트리로 구현되어 있어 탐색과 삽입/삭제 모두 O(logN)의 시간복잡도를 보장하고 있다.

 

 

 

map 내부 요소의 정렬

map 내부에서 정렬은 템플릿 인자로 들어오는 Compare 객체에 의해 일어나게 된다.

Compare 객체는 맵 자체의 초기화와 함께 초기화되는데, 기본적으로 less로 초기화된다.

template <class Key, class T, class Compare = less<Key>,
          class Allocator = allocator<pair<const Key, T>>>
class map {
	....
}

 

less 객체는 다음과 같은 템플릿 클래스이다. 

template <class T> struct less : binary_function <T,T,bool> {
  bool operator() (const T& x, const T& y) const {return x<y;} // 기능적으로는 < 연산자와 동일한 기능이다.
};

c++ 98에서는 binary_function이라는 클래스를 상속받아 구현이 되어 있는데, c++ 11 이상에선 deprecated된 요소이다.

 

 binary_function 클래스 자체는 다음과 같은 typedef 만을 포함하고 있다.

template <class Arg1, class Arg2, class Result>
  struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
  };

 

 

 

map의 속성

Associative -> 맵에 들어있는 원소는 container에 저장된 원소의 절대적 메모리 주소가 아닌 key에 의해 참조됨.

Ordered -> 맵 내부의 원소는 항상 Compare 함수가 지정한 규칙에 의해 key에 따라 정렬되어있음. 삽입이나 삭제가 일어나더라도 이 순서는 유지되어야 함.

Map -> 각 value는 반드시 key에 map 되어있음. 

unique key -> key는 반드시 컨테이너 내부에서 유일한 값이어야 함.

Allocator-aware -> 내부의 저장공간의 동적 할당과 반환을 위해 Allocator를 사용함.

 

 

map의 템플릿 인자

template <class Key, class T, class Compare = less<Key>,
          class Allocator = allocator<pair<const Key, T>>>
class map {
	....
}

Key : key의 타입. 클래스 내부에서 key_type으로 alias됨.

T : value의 타입. 클래스 내부에서 mapped_type으로 alias 됨.

Compare : 두 개의 Key 타입 인자를 받아 bool 타입의 결과를 리턴하는 binary predicate. 기본적으로 a < b 의 값을 리턴하는 less<T>로 지정되어있고, 별도로 지정해 줄 수도 있음. 클래스 내부에서 key_compare로 alias됨.

Alloc : 내부 공간의 동적 할당을 위해 사용되는 allocator 객체. 클래스 내부에서 allocator_type으로 alias됨.

 

 

map의 멤버타입

member type	definition	notes
key_type	The first template parameter (Key)
mapped_type	The second template parameter (T)
value_type	pair<const key_type,mapped_type>
key_compare	The third template parameter (Compare)	defaults to: less<key_type>
value_compare	Nested function class to compare elements	see value_comp
allocator_type	The fourth template parameter (Alloc)	defaults to: allocator<value_type>
reference	allocator_type::reference	for the default allocator: value_type&
const_reference	allocator_type::const_reference	for the default allocator: const value_type&
pointer	allocator_type::pointer	for the default allocator: value_type*
const_pointer	allocator_type::const_pointer	for the default allocator: const value_type*
iterator	a bidirectional iterator to value_type	convertible to const_iterator
const_iterator	a bidirectional iterator to const value_type
reverse_iterator	reverse_iterator<iterator>
const_reverse_iterator	reverse_iterator<const_iterator>
difference_type	a signed integral type, identical to: iterator_traits<iterator>::difference_type	usually the same as ptrdiff_t
size_type	an unsigned integral type that can represent any non-negative value of difference_type	usually the same as size_t

 

 

map의 멤버함수

생성자

1. default

explicit map (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

기본생성자. 원소가 없는 빈 map을 생성한다.

 

2. range

template <class InputIterator>
  map (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& alloc = allocator_type());

두 개의 Input 이터레이터를 받아 두 이터레이터 사이에 있는 값을 맵에 삽입하여 초기화 한다.

 

3. copy

map (const map& x);

또다른 맵을 복사하여 맵을 초기화한다. 별도의 container를 생성하여 값을 복사해오는 deep copy임.

 

 

이터레이터

(vector와 동일)

 

 

Capacity

empty 

bool empty() const;

컨테이너의 size가 0이면 true 리턴.

 

size

size_type size() const;

현재 container의 사이즈 리턴.

 

max_size

size_type max_size() const;

컨테이너의 최대 크기 리턴.

 

 

접근자

operator []

mapped_type& operator[] (const key_type& k);

맵 내부에 있는 key를 탐색하여 k와 동일한 값이 있다면 해당 k에 mapped 되어있는 value의 참조자를 리턴.

만약 컨테이너 내부에 일치하는 key가 없다면, k를 key로 하는 새로운 원소를 컨테이너에 추가함. 이 때 key와 pair가 되는 value가 없더라도 원소는 추가 되며 컨테이너의 size는 1 증가함. (value는 기본 생성자로 생성됨)

실행 도중 예외 발생 시 컨테이너에는 변화가 없음(원소 추가 이전의 상태를 유지함.)

 

 

수정자

insert

*삽입연산이 끝난 후에도 모든 원소는 정렬된 상태를 유지해야함.

 

1. single element

pair<iterator,bool> insert (const value_type& val);

map에서 key값은 중복될 수 없으므로, 삽입 연산을 하기 전에 해당 key값이 이미 컨테이너에 존재하는 지 체크한 후 삽입이 일어나게 됨.

삽입에 성공하였다면 pair 값으로 삽입된 원소 위치를 가리키는 iterator와 true가 리턴되며, 실패 시 중복되는 키 값을 가진 원소의 iterator와 false가 리턴됨.

 

2. with hint

iterator insert (iterator position, const value_type& val);

원소를 삽입하기위한 탐색을 root부터가 아닌 position부터 시작하게 됨. 이런 식으로 특정한 위치에 더 빠른 시간 내에 원소를 삽입할 수 있게 됨.

마찬가지로 key값이 이미 존재할 경우 값은 삽입되지 않으며, 해당 위치의 이터레이터를 리턴함.

 

3. range

template <class InputIterator>
  void insert (InputIterator first, InputIterator last);

first 부터 last 사이에 있는 원소를 복사하여 map에 삽입함.

 

 

erase

* 삭제 연산이 끝난 후에도 모든 원소는 정렬된 상태를 유지해야함.

1. position

void erase (iterator position);

position에 있는 원소를 삭제.

 

2. key

size_type erase (const key_type& k);

해당 키값을 가진 원소를 삭제. 삭제된 갯수가 리턴됨. 즉, 삭제가 되었으면 1, 아니면 0

 

3. range

void erase (iterator first, iterator last);

first와 last 사이의 모든 원소를 삭제함.

 

swap

void swap (map& x);

현재 컨테이너와 x와 swap. 

 

clear

void clear();

컨테이너에 있는 모든 원소를 삭제.

 

 

 

observers

 

key_comp

key_compare key_comp() const;

내부 값을 정렬하는데 쓰인 key_compare 객체를 리턴함.

 

value_comp

value_compare value_comp() const;

 

 

operations

 

find

iterator find (const key_type& k);

key값이 k인 원소를 찾아 해당 원소의 이터레이터를 리턴. 해당 원소가 없을 경우 end()가 리턴됨.

 

count

size_type count (const key_type& k) const;

 

k를 key로 가지는 원소의 개수를 리턴.

 

lower_bound

 iterator lower_bound (const key_type& k);

 

 

upper_bound

iterator upper_bound (const key_type& k);

 

equal_range

pair<const_iterator,const_iterator> equal_range (const key_type& k) const;
pair<iterator,iterator>             equal_range (const key_type& k);