• https://cplusplus.com/reference/map/map/?kw=map

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;

Description

• Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order.
  
  👉 맵은 특정 순서에 따라 키 값과 매핑된 값의 조합으로 형성된 요소를 저장하는 연관 컨테이너

• In a map, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key. The types of key and mapped value may differ, and are grouped together in member type value_type, which is a pair type combining both: typedef pair<const Key, T> value_type;
  
  👉 key는 고유한 식별자. value는 key에 따라 저장되는 값. key와 mapped value의 유형은 다를 수 있음.

• Internally, the elements in a map are always sorted by its key following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).
  
  👉 내부 비교 object에 의해 map 안의 원소들은 key에 따라 항상 정렬됨.

• map containers are generally slower than unordered_map containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.
  
  👉

Member types

Member functions

OCCF

constructor

• https://cplusplus.com/reference/map/map/map/
• 기본생성자, 범위생성자, 복사생성자 있음
• rbtree 생성. rbtree 생성자에서 동적할당 일어나게 됨

destructor

• https://cplusplus.com/reference/map/map/~map/
• 할당해줬던 rbtree node들 다 해제해주기 (clear 쓰기)

operator=

• https://cplusplus.com/reference/map/map/operator=/
• 대입연산자 오버로딩
• 기존의 node clear 해주고 대입할 노드들 차례대로 insert.

Iterators

begin

• https://cplusplus.com/reference/map/map/begin/
• minimum 노드(leftmost 노드) iterator 반환.
• 만약 트리 size가 0이면 end(== leaf node == _TNULL) iterator 반환.

end

• https://cplusplus.com/reference/map/map/end/
• leaf node(== _TNULL) iterator 반환.

rbegin

• https://cplusplus.com/reference/map/map/rbegin/
• end()를 base로 하는 reverse_iterator 반환.

rend

• https://cplusplus.com/reference/map/map/end/
• begin()을 base로 하는 reverse_iterator 반환.

Capacity

empty

• https://cplusplus.com/reference/map/map/empty/
• rbtree size가 0이면 true 반환하도록 구현했음.

size

• https://cplusplus.com/reference/map/map/size/
• rbtree의 size 반환하도록 했음

max_size

• https://cplusplus.com/reference/map/map/max_size/
• rbtree의 _node_alloc.max_size() 사용.

std의 max_size와 ft max_size가 같을 수 있었던 이유

• 내 rbtree node는 pointer 3개(parent, left, right), value_type data 1개, int 1개(color) 로 구성 돼있다.
• gcc의 node는 pointer 3개, value_type data 1개, enum 1개(color)로 구성 돼있다.
• 그냥 생각해보면 클래스 객체의 사이즈는 pointer(8byte) * 3 + value_type(pair<int, int> 라고 할 때 8byte라고 가정) + int or enum(4 byte) = 36byte여야 할 것 같은데
• 실제로 확인해보면 40byte가 된다.
• 64bit 컴퓨터 기준 클래스를 인스턴스화 할 때 변수에 할당되는 메모리는 8바이트 단위인 것 같다. 그렇기 때문에 8 * 4 < 32 <= 8 * 5 를 만족하는 40byte가 할당되게 되는 듯.
• 어쨌든 gcc의 노드와 내 rbtree node의 변수 크기와 개수가 똑같기 때문에 max_size도 std와 똑같이 맞출 수 있게 됐다.

추가) virtual 키워드에 대해

• 준영님과 내 rbtree node의 변수가 모두 똑같았음에도 node size가 달랐었다.
• 이유는 준영님이 쓰신 virtual 소멸자 때문.
• virtual 키워드를 쓰는 순간 vtable에 접근하기 위한 pointer가 생성돼야 하고, pointer(8byte)가 추가로 할당 되었던 것!

Element access

operator[]

• https://cplusplus.com/reference/map/map/operator[]/
• key가 없다면 새로 insert.
• tree에 있는 key search 해서 해당 key의 mapped_type 반환.

Modifiers

insert

• https://cplusplus.com/reference/map/map/insert/
• 3가지 버전 있음

// single element (1)	
pair<iterator,bool> insert (const value_type& val);
// with hint (2)	
iterator insert (iterator position, const value_type& val);
// range (3)	
template <class InputIterator>  void insert (InputIterator first, InputIterator last);

• single element 버전의 경우 해당 키를 가진 노드가 이미 있으면 그 노드의 iterator, flase를 반환.
  키를 가진 노드가 없으면 해당 노드 삽입 후 그 노드의 iterator, true를 반환.
• with hint 버전의 경우 힌트가 되는 iterator를 인자로 줄 수 있다고 되어있는데, 사실상 rbtree의 규칙에 따라서만 삽입이 이뤄지기 때문에 그냥 single element를 사용해주면 됨. 반환 값은 key가 일치하는 노드의 iterator.
• range 버전의 경우 [first, last) 범위를 insert해주면 됨.

erase

• https://cplusplus.com/reference/map/map/erase/
• 3가지 버전 있음

// (1)	
void erase (iterator position);
// (2)	
size_type erase (const key_type& k);
// (3)	
void erase (iterator first, iterator last);

• 1의 경우 그냥 해당 position에 있는 노드 삭제. iterator가 가리키는 node에 접근할 수 있도록 public 멤버변수 _node를 만들어줬었음. 그래서 _bst.rbDelete(position._node)로 바로 사용해줬음
• 2의 경우 key를 가지고 삭제. 삭제된 노드의 개수를 반환. multimap의 경우 중복키가 가능하지만 그냥 map의 경우 중복키가 불가능하기 때문에 0 아니면 1임.
• 3은 for문에서 후위연산 it = first++를 이용해 it에는 first가 업데이트 되기 전 값이 담기고 first 자체는 다음 노드로 넘어가 있게 해서 delete가 꼬이지 않게 해줬음

swap

• https://cplusplus.com/reference/map/map/swap/
• rbtree의 public 함수로 swap을 만들었음.
• ft::swap을 이용해 rbtree의 멤버변수들을 각각 swap 해줬음

clear

• https://cplusplus.com/reference/map/map/clear/
• [first, last) 범위를 erase.

Observers

key_comp

• https://cplusplus.com/reference/map/map/key_comp/
• key_compare 객체 반환

value_comp

• https://cplusplus.com/reference/map/map/value_comp/
• value_compare 객체 반환.
• value_compare의 생성자가 value_compare(key_compare comp)밖에 없어서 return value_compare(key_compare()); 해줘야 함
• map에서의 value_comp는 value_type.first끼리 비교해주는 것

Operations

find

• https://cplusplus.com/reference/map/map/find/
• 해당 키를 가진 노드가 존재하면 해당 노드 iterator 반환.
• 노드가 존재하지 않으면 end(== _TNULL 가리키는 iterator) 반환.

count

• https://cplusplus.com/reference/map/map/count/
• 해당 키를 가진 노드가 몇 개 있는지 size_type 으로 반환.
• multimap이 아닌 map에선 사실상 0 아니면 1만 리턴.

lower_bound

• https://cplusplus.com/reference/map/map/lower_bound/
• 해당 키보다 같거나 큰 키가 처음 나타나는 노드의 iterator 반환.
  ex) 1,2,3,4에서 lower_bound(3)을 하면 3 위치가 리턴.

upper_bound

• https://cplusplus.com/reference/map/map/upper_bound/
• 해당 키보다 큰 키가 처음 나타나는 노드의 iterator 반환.
  ex) 1,2,3,4에서 upper_bound(3)을 하면 4 위치가 리턴.

equal_range

• https://cplusplus.com/reference/map/map/equal_range/
• lower_bound와 upper_bound를 pair로 묶어서 리턴.
  ex) 1,2,3,4에서 equal_range(3)을 하면 <3,4>가 리턴.

Allocator

get_allocator

• https://cplusplus.com/reference/map/map/get_allocator/
• Alloc 개체를 반환