<STL> map

Map의 특성

• Map은 Key와 Value 쌍을 특별한 순서로 저장하고 있는 연관 컨테이너(Associative Container)다.
• 이진 트리(Red-Black Tree)로 구현되어있고, Key를 통해 Value에 접근하고자 할 때, [] 연산자를 사용해서 접근할 수 있다.
  • RB Tree는 쉽게 말하면 자가 균형 이진 트리이다. 

https://hanseongbugi2study.tistory.com/94

<algorithm> Red-Black Tree (RB Tree)

• Map은 Key의 중복을 허용하지 않는 고유한 특징을 가지고 있다.
• Key와 Value는 다양한 자료형을 넣을 수 있다.
  • int, double과 같은 기본 자료형
  • 사용자가 정의한 자료형 (Custom Class)

Map의 구성

생성자

• map의 생성자는 기본 생성자, 복사 생성자로 이루어져 있다,
• 비교 클래스를 통해 정렬 방식을 결정할 수 있다.
  • 이는 우선 순위 큐와 비슷하게 정렬 순서를 결정하는 것임
  • 정렬 대상은 Key이다.

#include <iostream>
#include <map>
#include <string>
using namespace std;

struct mycomp {
    bool operator()(const string& left, const string& right) const{
        return left > right;
    }
};

void printMap(const string& name, const map<string, int>& m) {
    cout << "-----" << name << "-----\n";
    for (pair<string, int> item : m)
        cout << item.first << "->" << item.second << '\n';
    cout << '\n';
}
void printMap(const string& name, const map<string, int, mycomp>& m) {
    cout << "-----" << name << "-----\n";
    for (auto item : m)
        cout << item.first << "->" << item.second << '\n';
    cout << '\n';
}



int main() {
    map<string, int>m1; // 기본 생성자

    m1["First"] = 5;
    m1["Second"] = 6;
    m1.insert({ "Third",5 });
    m1.insert(make_pair("Forth", 40));

    printMap("m1", m1);

    map<string, int>m2(m1.begin(), m1.end()); // 복사 생성자, 인자를 (iterator, iterator)로 받음
    printMap("m2", m2);

    map<string, int>m3(m2); // 복사 생성자, 인자를 다른 map으로 받음
    printMap("m3", m3);

    map<string, int, mycomp> m4; // 기본 생성자, 비교자 클래스를 정의 후 연결

    m4["First"] = 5;
    m4["Second"] = 6;
    m4.insert({ "Third",5 });
    m4.insert(make_pair("Forth", 40));

    printMap("m4", m4);

    return 0;
}

// 출력
-----m1-----
First->5
Forth->40
Second->6
Third->5

-----m2-----
First->5
Forth->40
Second->6
Third->5

-----m3-----
First->5
Forth->40
Second->6
Third->5

-----m4-----
Third->5
Second->6
Forth->40
First->5

 

반복자

• map의 iterator는 Bidirectional iterator(양방향 반복자)이다.
  • 양방향 반복자는 입출력이 모두 가능한 반복자이다.
  • 즉,  증가 연산자(++)를 사용하면 순방향으로, 감소 연산자(--)를 사용하면 역방향으로도 이동할 수 있다.
• 원소에 접근할 때 iterator 뿐만 아니라 [] 연산자를 통해서도 접근할 수 있다.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int>m;

    m.insert({ "first",100 });
    m.insert({ "second",200 });
    m["third"] = 300;

    for (map<string, int>::iterator iter = m.begin(); iter != m.end(); iter++) {
        cout << iter->first << " -> " << iter->second << '\n';
    }
    cout << '\n';

    cout << "m[\"third\"] -> " << m["third"] << '\n';

    return 0;
}

// 출력
first -> 100
second -> 200
third -> 300

m["third"] -> 300

 

장단점

장점

• map은 Key를 기준으로 데이터를 정렬하여 저장하기 때문에 데이터를 검색 시 매우 빠른 속도를 가진다.
• map은 Key-Value 쌍으로 데이터를 저장하기 때문에 데이터를 빠르게 삽입하고 삭제할 수 있다.
• map은 데이터를 저장할 때 Key 값이 중복될 수 없다. 이를 통해 데이터 중복을 방지할 수 있다.

단점

• map은 데이터를 정렬하여 저장하기 때문에 데이터를 삽입하거나 삭제할 때 정렬을 유지하기 위한 추가적인 작업이 필요하다.
  • 이로인해 삽입, 삭제 연산이 느려질 수 있다. (데이터가 상당히 많을 경우)
• map은 데이터를 검색할 때 이진 탐색 알고리즘을 사용한다. 
  • 이진 탐색 알고리즘으로 인해 검색 속도로 O(log n)를 가지게 된다.
  • 이는 unordered_map과 비교했을 때, 상대적으로 느리다.

메소드

• map을 통해 데이터를 삽입하고, 지우고, 찾는 일을 할 수 있다.

삽입 (insert)

• insert 함수나 [] 연산자를 통해 map에 삽입할 수 있다.
• <string, int> 기준으로 std::pair<std::map<string,int>::iterator, bool>이 반환된다.
  • 첫번째 반환 값인 iterator는 삽입된 곳을 가르키는 반복자이다.
  • 두번째 bool은 해당 key가 이미 map에 존재한다면 false, 그렇지 않고 성공적으로 삽입하면 true를 반환한다.
• insert의 매개변수
  1. 단순히 key - value 쌍 하나만 들어가는 경우
  2. iterator, key - value 쌍이 들어가는 경우
  3. 다른 map의 iterator 쌍이 들어가는 경우.
     • (map.begin(), map.end())를 하면 다른 map의 전체가 삽입된다.
• 시간복잡도는 1번의 경우 O(log(N))이 된다. 이때 N은 map의 크기이다.
• 2번의 경우 상수 시간(O(1))에 삽입이 가능하다.
• 3번의 경우 O(범위의 길이 * log(N))이 된다.

#include <iostream>
#include <map>
#include <string>
using namespace std;

void printMap(const string& name, const map<string, int>& m) {
    cout << "-----" << name << "-----\n";
    for (pair<string, int> item : m)
        cout << item.first << "->" << item.second << '\n';
    cout << '\n';
}

int main() {
    map<string, int>m1;

    // Key-Value 쌍을 받는 insert
    m1.insert({ "first",100 });
    m1.insert({ "second",200 });
    m1["third"] = 300;

    printMap("m1", m1);

    // iterator와 Key-Value 쌍을 받는 insert
    m1.insert(m1.find("second"), { "forth", 400 });
    printMap("m1", m1);

    map<string, int> m2;
    // iterator의 범위를 받는 insert
    m2.insert(m1.begin(), m1.find("third"));
    
    printMap("m2", m2);

    return 0;
}

// 출력
-----m1-----
first->100
second->200
third->300

-----m1-----
first->100
forth->400
second->200
third->300

-----m2-----
first->100
forth->400
second->200

• 반복자와 key-value 쌍을 사용하는 경우 map의 끝에 삽입되는 것이 아니라 find 함수를 통해 반환 받은 iterator에 따라 삽입되는 것을 알 수 있다.
• iterator의 범위를 받는 경우 find 함수를 통해 반환 받은 iterator에 의해 삽입이 이루어 진다.
  • 즉, [m1.begin(), m1.find("third")) 가 된다. 
  • 이에 의해 third가 포함되지 않는 것을 알 수 있다.

삽입 시 주의 사항

• map을 사용하면 삽입한 적이 없는데 값이 삽입되어 있는 상황이 발생할 수 있다.

#include <iostream>
#include <map>
using namespace std;

int main() {
	map<int, int> m;
	m.insert({ 2, 2 });
	if (m[1]) {
		cout << "The value of Key 1 is: " << m[1] << '\n';
	}
	m.insert({ 1, 1 });
	for (pair<int,int> item : m) {
		cout << item.first << " : " << item.second << '\n';
	}
	return 0;
}

// 출력
1 : 0
2 : 2

• 위 예제는 map에 Key 1을 가지는 요소가 없는 것을 확인 후 삽입을 하였지만 Key 1에는 1이 아닌 0이 삽입된 상황이다.
• std::operator[]에는 아래와 같은 연산이 일어난다.
  • 참조 당하는 순간 해당 Key와 Value가 없는 경우 만들어서 추가하는 연산이 일어난다.
• 실제 gcc 코드를 살펴보면 이해하기 쉽다.

T& operator[](const key_type& k) {
    return (*((insert(value_type(k, T()))).first)).second;
  }
  void swap(map<Key, T, Compare, Alloc>& x) { t.swap(x.t); }

  // insert/erase

  pair<iterator,bool> insert(const value_type& x) { return t.insert_unique(x); }
  iterator insert(iterator position, const value_type& x) {
    return t.insert_unique(position, x);
  }

• operator[] 함수에서는 인자로 들어온 요소로 pair를 만들어 그대로 insert하는 것을 볼 수 있다.
• map에서 insert 함수는 Key가 unique 하여 해당 Key가 이미 존재한다면 Value를 변경하지 않고, 기존 값 그대로 값을 저장한다.
• map의 insert 함수 내부에서 사용하는 rb_tree의 insert_unique 함수는 아래와 같다.

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, bool>
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const Value& v)
{
  link_type y = header;
  link_type x = root();
  bool comp = true;
  while (x != 0) {
    y = x;
    comp = key_compare(KeyOfValue()(v), key(x));
    x = comp ? left(x) : right(x);
  }
  iterator j = iterator(y);   
  if (comp)
    if (j == begin())     
      return pair<iterator,bool>(__insert(x, y, v), true);
    else
      --j;
  if (key_compare(key(j.node), KeyOfValue()(v)))
    return pair<iterator,bool>(__insert(x, y, v), true);
  return pair<iterator,bool>(j, false);
}

• insert_unique 함수는 해당 key에 대한 node를 찾고, 없으면 실제 삽입과 함께 pair(iterator, true)를 반환한다.
• node가 존재한다면, 기존에 존재하는 iterator와 false를 반환한다.
• 따라서 안전하게 삽입하기 위해서는 아래와 같이 find를 사용하여 같은 key가 있는지 확인하고 삽입을 진행해야한다.

#include <iostream>
#include <map>
using namespace std;

int main() {
	map<int, int> m;
	m.insert({ 2, 2 });
	if (m.find(1) == m.end()) {
		m.insert({ 1, 1 });
	}
	for (pair<int,int> item : m) {
		cout << item.first << " : " << item.second << '\n';
	}
	map<int, string> m2;
	m2.insert({ 2, "string2" });
	if (m2.find(1) == m2.end()) {
		m2[1] = "string1";
	}
	for (pair<int, string> item: m2) {
		std::cout << item.first << " : " << item.second << '\n';
	}
	return 0;
}

// 출력
1 : 1
2 : 2
1 : string1
2 : string2

 

삭제 (Erase)

• map의 삭제는 3가지 경우에 따라 이루어진다.
  1. iterator를 통한 삭제
  2. Key 값을 통한 삭제
  3. iterator의 범위를 통한 삭제
• 시간 복잡도
  • 1번의 경우 상수 시간(O(1))에 삭제가 가능하다.
  • 2번의 경우 map의 크기에 log로 비례한다. O(log(N)
  • 3번의 경우 O(범위의 길이 * log(N)) 이다.

#include <iostream>
#include <map>
#include <string>
using namespace std;

void printMap(const string& name, const map<string, int>& m) {
    cout << "-----" << name << "-----\n";
    for (pair<string, int> item : m)
        cout << item.first << "->" << item.second << '\n';
    cout << '\n';
}

int main() {
    map<string, int>m;

    m.insert({ "One",1 });
    m.insert({ "Two",2 });
    m.insert({ "Three",3 });
    m.insert({ "Four",4 });
    m.insert({ "Five",5 });
    m.insert({ "Six",6 });
    m.insert({ "Seven",7 });
    m.insert({ "Eight",8 });
    m.insert({ "Nine",9 });

    printMap("m", m);

    // iterator로 삭제
    cout << "iterator로 삭제" << '\n';
    auto iter = m.find("Nine");
    m.erase(iter);
    m.erase(m.find("Three"));
    printMap("m", m);

    // Key로 삭제
    cout << "Key로 삭제" << '\n';
    m.erase("One");
    m.erase("Four");
    printMap("m", m);

    // iterator 범위로 삭제
    cout << "iterator 범위로 삭제" << '\n';
    m.erase(m.find("Seven"), m.end());
    printMap("m", m);

    return 0;
}

// 출력
-----m-----
Eight->8
Five->5
Four->4
Nine->9
One->1
Seven->7
Six->6
Three->3
Two->2

iterator로 삭제
-----m-----
Eight->8
Five->5
Four->4
One->1
Seven->7
Six->6
Two->2

Key로 삭제
-----m-----
Eight->8
Five->5
Seven->7
Six->6
Two->2

iterator 범위로 삭제
-----m-----
Eight->8
Five->5

• erase 함수 외에 map의 데이터를 수정하는 함수는 swap과 clear가 있다.
  • swap은 m1.swap(m2)로 사용할 수 있으며, 이는 m1과 m2의 Key-Value를 바꾸는데 사용한다.
  • clear는 m1.clear()로 사용할 수 있으며, 이는 m1의 Key-Value를 모두 제거하는데 사용한다.

연산(Operation)

• map의 연산 기능은 find와 count 함수로 사용 가능하다.
• find는 Key 값을 통해 해당 Key 값을 가지는 Value를 찾는다.
  • 매개변수로 Key 값을 받는다.
  • 시간 복잡도는 O(log(N))이다.
  • find는 매개변수로 들어온 Key가 존재한다면, 해당 노드의 iterator를 반환하고, 그렇지 않으면 map.end()를 반환한다.
• count는 Key 값을 통해 해당 Key 값을 가지는 Value를 찾는다.
  • find와 다른 점은 해당 Key 값을 가지는 Value가 있다면 1을 반환하고, 없다면 0을 반환한다.
  • 시간 복잡도는 O(log(N))이다.

반복자 (Iterator)

• map은 반복자를 통해 순회가 가능하다.
• iterator를 이용해서 삽입, 삭제 연산을 진행할 수 있다.
• iterator는 map의 주소 값을 가지고 있다.

s.begin()	map의 시작이 되는 주소 값 반환
s.end()	map의 마지막 부분에 대한 주소 값 반환(정확히는 마지막 뒤 공백구간)
s.rbegin()	map의 마지막 부분을 시작점으로 지정
s.rend()	map의 첫번 째 부분을 마지막점으로 지정
s.cbegin()	begin()과 동일하지만 const로 설정.
s.cend()	end()와 동일하지만 const로 설정
s.crbegin()	rbegin()과 동일하지만 const로 설정
s.crend()	rend()와 동일하지만 const로 설정

 

 

 

출처

https://hwan-shell.tistory.com/149

C++] map 사용법과 원리

https://kibbomi.tistory.com/212

[C++/STL] Map 분석

https://en.cppreference.com/w/cpp/container/vector/rend

std::vector<T,Allocator>::rend, std::vector<T,Allocator>::crend - cppreference.com

https://80000coding.oopy.io/8af406a3-b3b1-4f3f-b190-2937b23684ed

모르면 큰코 다치는 C++ STL map의 비밀