map

맵은 특정 순서에 따라 키 값과 매핑된 값의 조합으로 형성된 요소를 저장하는 연관 컨테이너다.

맵에서 키 값은 일반적으로 요소를 정렬하고 식별하는 데 사용되며, 매핑된 값은 이 키와 관련된 내용을 저장한다. 키와 매핑된 값의 타입은 서로 다를 수 있으며, 멤버 유형인 value_type으로 함께 그룹화된다.

typedef pair<const Key, T> value_type;

내부적으로, 맵의 요소들은 (비교 유형의) 내부 비교 객체(map::key_comp)에 의해 나타나는 특정한 strict weak ordering에 따라 키가 정렬된다.

맵은 일반적으로 키로 개별 요소에 접근해서 unordered_map 보다 느리지만, 하위 집합에 대한 직접 반복을 허용한다.

맵에서 매핑된 값은 괄호 연산자(operator[])를 사용하여 해당 키에 의해 직접 접근할 수 있다.

맵은 일반적으로 이진 탐색 트리로 구현된다.

컨테이너 속성

• 연관적(Associative) - 연관 컨테이너의 요소는 컨테이너의 절대(absolute) 위치가 아닌 해당 키에 의해 참조된다.
• 정렬된(Ordered) - 컨테이너의 요소는 항상 strict order를 따릅니다. 삽입된 모든 요소에는 이 순서대로 위치가 지정된다.
• 맵(Map) - 각 요소는 키를 매핑된 값에 연결합니다. 키는 요소를 식별하기 위한 것이다.
• 고유 키(Unique keys) - 동일한 키를 가질 수 없다.
• 할당자 인식?(Allocator-aware) - 컨테이너는 할당자 개체를 사용하여 메모리를 동적으로 처리한다.

템플릿 매개변수

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

• Key - 키의 타입.
• T - 맵핑된 값의 타입.
• Compare - 두 요소를 비교하는 함수.
• Alloc - 메모리 관리에 사용되는 allocator객체.

멤버 타입

		typedef Key key_type; // The first template parameter (Key)
		typedef T mapped_type; // The second template parameter (T)
		typedef pair<const key_type, mapped_type> value_type; // defaults to: less<key_type>
		typedef Compare key_compare; // Nested *function class* to compare elements (value_comp)
		typedef Allocator allocator_type; // The fourth template parameter (Alloc)
		typedef typename allocator_type::reference reference;
		typedef typename allocator_type::const_reference const_reference;
		typedef typename allocator_type::pointer pointer;
		typedef typename allocator_type::const_pointer const_pointer;
		typedef typename allocator_type::size_type size_type; // usually the same as size_t
		typedef typename allocator_type::difference_type difference_type; // usually the same as ptrdiff_t

		typedef implementation - defined iterator; // a *bidirectional* iterator to value_type
		typedef implementation - defined const_iterator;
		typedef std::reverse_iterator<iterator> reverse_iterator;
		typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

멤버 함수

• 생성자

empty (1)	
explicit map (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());
range (2)	
template <class InputIterator>
  map (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& alloc = allocator_type());
copy (3)	
map (const map& x);

• (1)empty - 요소가 없는 빈 컨테이너를 구성.

• (2) range - \[first, last] 범위와 같은 수의 요소로 컨테이너를 구성하고 각 요소는 해당 범위의 해당 요소로 구성.

• (3) copy - x에 있는 각 요소의 복사본을 사용하여 컨테이너를 구성.

• 소멸자

• 연산자=

Iterators

• begin - 컨테이너의 첫 요소를 가리키는 반복자를 반환.
• end - 컨테이너 마지막 요소의 다음을 가리키는 반복자를 반환. 어떤 요소도 가리키지 않기때문에 역참조 되지 않는다.
• rbegin - 마지막 요소를 가리키는 반복자를 반환.
• rend - 첫 요소의 이전을 가리키는 반복자를 반환.

Capacity

• empty - 컨테이너가 비어있는지 확인.
• size - 컨테이너에 들어있는 요소의 개수를 리턴.
• max_size - 컨테이너가 보유할 수 있는 최대 요소의 수를 반환.

Element access

• 연산자[]

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

k가 컨테이너에 있는 요소의 키와 일치하면 함수는 매핑된 값에 대한 참조를 반환한다.

k가 컨테이너에 있는 요소의 키와 일치하지 않으면 함수는 해당 키와 함께 새 요소를 삽입하고 매핑된 값으로 참조를 반환한다.

Modifiers

• insert - 컨테이너에 새 요소를 삽입. 동일한 키가 있는지 확인한다. 있는 경우 요소가 삽입되지 않고 기존 요소가 반복자에 반환이 된다.
• erase - 컨테이너에서 요소를 삭제. 범위 삭제도 가능하다.
• swap - 같은 유형의 두 컨테이너의 요소를 교환.
• clear - 모든 요소를 파괴하고 컨테이너의 크기를 0으로 바꾼다.

Observers

• key_comp - 컨테이너에서 키를 비교하는 데 사용되는 비교 개체의 복사본을 반환.
  map의 비교 객체는 생성시 설정된다.

이 객체는 컨테이너에 있는 요소의 순서를 결정한다
함수 포인터 또는 함수 객체로서 요소 키와 같은 유형의 두 개의 인자를 취하며,
첫 번째 인자가 정의된 strict weak ordering에서 두 번째 인자보다 앞서는 것으로 간주되면 true를 반환하고, 그렇지 않으면 false를 반환한다.

만약 인자의 순서 상관없이 계속 false를 반환하는 경우 두 키는 동등한 것으로 간주한다.

• value_comp - 두 요소를 비교하는데 사용하는 비교 객체를 반환한다.

Operations

• find - 컨테이너에서 k와 같은 키를 가진 요소를 검색한다. 있으면 해당 요소를 가리키는 반복자를 반환하고, 없으면 map::end를 반환한다.
• count - k와 동일한 키를 가진 요소를 컨테이너에서 검색하고 일치 항목 수를 반환한다. map의 모든 요소는 고유하기 떄문에, 이 함수는 0또는 1만 반환한다.
• lower_bound - k의 오른쪽 요소중에 k와 같거나 큰값 중 가장 왼쪽에 있는 요소의 반복자를 리턴한다.
• upper_bound - k의 오른쪽 요소중에 k보다 큰값 중 가장 왼쪽에 있는 요소의 반복자를 리턴한다.
• equal_range - k와 동일한 키를 가진 컨테이너의 모든 요소를 포함하는 범위의 경계를 반환한다.
  일치하는 키가 없으면 반환되는 범위의 길이는 0이다.

Allocator

• get_allocator - 할당자 객체를 반환한다.

std::less

template <class T> struct less;

첫 번째 인수가 두 번째 인수보다 작은지 여부를 반환하는 이진 함수 객체 클래스(operator<에서 반환됨).

이 클래스는 정렬, 병합 또는 lower_bound와 같은 표준 알고리즘에 사용할 수 있다.

std::pair

template <class T1, class T2> struct pair;

이 클래스는 서로 다른 유형(T1 및 T2)일 수 있는 값 쌍을 함께 결합한다. 개별 값은 public 멤버인 first와 second를 통해 접근할 수 있다.

멤버 함수

• 생성자
• 연산자=

비멤버 함수

• 비교 연산자 - ==, !=, < , <=, >, >=

---

• std::map
• std::less
• std::pair