[맵(map)] 균형 이진 트리 기반의 std::map과 map을 사용하는 이유

map이란?

• Key-Value 구조(또는 Key)만 존재하는 컨테이너인 '연관 컨테이너'의 일종이다.
• 균형 이진 트리 기반 자료구조를 가진다.

우선순위 큐(std::priority_queue)의 경우 힙을 기반으로 하고, 힙은 내부적으로 '완전 균형 이진 트리'로 구성되어 있음

• vector나 list의 단점은 원하는 조건에 해당하는 데이터를 빠르게 찾을 수 없다는 것이다.
• 연관 컨테이너 중 하나인 맵에 데이터를 저장하고 빠른 시간 복잡도로 데이터를 찾을 수 있다.

---

시간 복잡도

• 삽입: O(logN)
• 삭제: O(logN)
• 검색: O(logN)

---

탐색에 있어 std::vector vs std::map

vector 탐색

		vector<Player*> v;	// 벡터가 동적으로 크기가 늘어나면서 복사가 일어날 때
							// 이 복사 비용을 줄이기 위해 포인터가 벡터의 요소가 되도록 함

		// 10만명 입장
		for (int i = 0; i < 100000; i++) {
			Player* p = new Player(i);
			v.push_back(p);
		}

		// 5만명 퇴장
		srand(time(NULL));

		int K = rand() % 100000;

		for (int i = 0; i < 50000; i++) {
			int randIdx = rand() % v.size();

			// 실험을 위해 ID가 K인 원소는 삭제하지 않는다.
			if (randIdx == K) {
				i++;
				continue;
			}

			Player* p = v[randIdx];
			delete p;

			v.erase(v.begin() + randIdx);	// 한 번의 삭제 연산에 O(N)의 시간 복잡도 소모..
		}

		//for (int i = 0; i < v.size(); i++) {
		//	cout << v[i]->_playerId << endl;
		//}
		// 2, 4, 6, 7, 9, 14, 17 .... (50000개)

		// id: K인 유저를 찾으려면?
		size_t vsize = v.size();
		for(int i=0; i< vsize; i++) {
			if (v[i]->_playerId == K) {
				v.erase(v.begin() + i);
				continue;
			}
		}
		// 루프를 돌려야한다. 최악의 경우 O(50000)

map 탐색

		// map<키 타입, 벨류 타입> 
		map<int, Player*> MAP;
		// 10만명 유저 생성
		for (int i = 0; i < 100000; i++) {
			pair<int, Player*> p(i, new Player(i * 100));
			MAP.insert(p);
		}
		// 5만명 유저 퇴장
		srand(static_cast<unsigned int>(time(nullptr)));

		int K = rand() % 100000;

		for (int i = 0; i < 50000; i++) {
			int randKey = rand() % 100000;

			// 실험을 위해 ID가 50000인 원소는 삭제하지 않는다.
			if (randKey == K) {
				i++;
				continue;
			}

			delete MAP[randKey];	// 자원 반환

			MAP.erase(randKey);		// 삭제될 키가 이미 삭제되었다면,
									// erase 함수는 그냥 무시함
		}

		// ID: K인 플레이어를 찾는 것과 삭제하는 것은 각 각 O(logN)에 불과하다
		auto iter = MAP.find(K);
		MAP.erase(iter);