[C++] map / unordered_map 자료 구조

공통점

• 원소의 중복 허용 x
  • 원소의 중복을 원한다면 map라이브러리내 multimap을 활용
• key : value 구

---

map

• 내부 원소가 저장되는 자료구조가 '균형 이진 검색 트리(Balanced binary search tree)'로 구현됨
  • 내부 원소가 저장될 때 알아서 정렬되어 저장 (default는 오름차순)
    • key값이 정렬되므로 key의 순서가 중요한 경우 적합
• 삽입, 삭제, 검색의 시간 복잡도 O(log n) 보장
• 트리 구조를 유지하기 위해 노드포인터 등 추가적인 메모리 사용
  • 해시테이블을 유지해야하는 unordered_map에 비해 비교적 메모리 사용이 효율적
• 정렬 기준 커스터마이징 가능
  • map<{key 타입}, {value 타입}, greater<{key 타입}>> : 내림차순

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

map<int, string> m;

void solution() {
	// 삽입
	for (int i = 0; i < 10; ++i) {
		string str = "원소";
		str += char(i + '0');
		m[i] = str;
	}

	// 검색
	map<int, string>::iterator itr1 = m.find(4);
	if (itr1 != m.end()) {
		// 찾음
		cout << itr1->first << "\n"; // 4
		cout << itr1->second << "\n"; // 원소4
	}
	else {
		// 못 찾음
		cout << "nothing" << "\n";
	}

	// 순회
	m[-1] = "원소-1";
	for (map<int, string>::iterator itr = m.begin(); itr != m.end(); ++itr) {
		cout << itr->second << " "; // -1 0 1 2 3 4 5 6 7 8 9
	}

	// 삭제
	m.erase(5);

	map<int,string>::iterator itr2 = m.find(5);
	if (itr2 != m.end()) {
		// 찾음
		cout << itr2->second << "\n";
	}
	else {
		// 못 찾음
		cout << "nothing" << "\n"; // nothing
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}

unordered_map

• 내부 원소가 저장되는 자료구조가 '해시 테이블(Hash table)'로 구현됨
  • 내부 원소가 저장될 때 순서가 보장되지 않음
• 삽입, 삭제, 검색의 평균 시간 복잡도는 O(1)이지만,
  최악의 경우 해시 충돌 시 O(n)
• 해시 테이블 구조를 유지하기 위해 버킷과 해시 함수에 메모리를 추가 사용
  • 기본적으로 더 많은 메모리를 사용할 가능성이 높다.
• 사용자 정의 해시 함수와 동일성조건(equal function)을 지정 가능

  • #include <iostream>
    #include <unordered_map>
    
    // 사용자 정의 타입
    struct Point {
        int x, y;
    
        // 동일성 비교를 위한 == 연산자 정의
        bool operator==(const Point& other) const {
            return x == other.x && y == other.y;
        }
    };
    
    // 사용자 정의 해시 함수
    struct PointHash {
        size_t operator()(const Point& point) const {
            return std::hash<int>()(point.x) ^ std::hash<int>()(point.y << 1); // XOR와 시프트 연산
        }
    };
    
    // 사용자 정의 동일성 비교 함수
    struct PointEqual {
        bool operator()(const Point& a, const Point& b) const {
            return a.x == b.x && a.y == b.y;
        }
    };
    
    int main() {
        // 사용자 정의 타입과 해시/비교 함수 지정
        std::unordered_map<Point, std::string, PointHash, PointEqual> pointsMap;
    
        // 데이터 삽입
        pointsMap[{1, 2}] = "Point A";
        pointsMap[{3, 4}] = "Point B";
    
        // 데이터 출력
        for (const auto& pair : pointsMap) {
            std::cout << "(" << pair.first.x << ", " << pair.first.y << "): " << pair.second << '\n';
        }
    
        return 0;
    }

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

unordered_map<int, string> um;

void solution() {
	// 삽입
	for (int i = 0; i < 10; ++i) {
		string str = "원소";
		str += char(i + '0');
		um[i] = str;
	}

	// 검색
	unordered_map<int, string>::iterator itr1 = um.find(4);
	if (itr1 != um.end()) {
		// 찾음
		cout << itr1->first << "\n"; // 4
		cout << itr1->second << "\n"; // 원소4
	}
	else {
		// 못 찾음
		cout << "nothing" << "\n";
	}

	// 순회
	um[-1] = "원소-1";
	for (unordered_map<int, string>::iterator itr = um.begin(); itr != um.end(); ++itr) {
		cout << itr->second << " "; // 0 1 2 3 4 5 6 7 8 9 -1
	}

	// 삭제
	um.erase(5);

	unordered_map<int,string>::iterator itr2 = um.find(5);
	if (itr2 != um.end()) {
		// 찾음
		cout << itr2->second << "\n";
	}
	else {
		// 못 찾음
		cout << "nothing" << "\n"; // nothing
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}

---

	map	unordered_map
자료구조	균형 이진 검색 트리	해시 테이블
삽입, 검색, 삭제의 시간 복잡도	O(log n)	O(1) (최악 O(n))
메모리 사용	트리 구조를 유지하기 위해 노드포인터 등	해시 테이블 구조를 유지하기 위해 버킷과 해시 함수

---