공통점
- 원소의 중복 허용 x
- 원소의 중복을 원한다면 map라이브러리내 multimap을 활용
- key : value 구
map
- 내부 원소가 저장되는 자료구조가 '균형 이진 검색 트리(Balanced binary search tree)'로 구현됨
- 내부 원소가 저장될 때 알아서 정렬되어 저장 (default는 오름차순)
- key값이 정렬되므로 key의 순서가 중요한 경우 적합
- 내부 원소가 저장될 때 알아서 정렬되어 저장 (default는 오름차순)
- 삽입, 삭제, 검색의 시간 복잡도 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)) |
| 메모리 사용 | 트리 구조를 유지하기 위해 노드포인터 등 | 해시 테이블 구조를 유지하기 위해 버킷과 해시 함수 |
반응형
'Programming Language > C++' 카테고리의 다른 글
| [C++] set / unordered_set 자료 구조 (3) | 2024.11.26 |
|---|---|
| [C++] RAII(Resource Acquisition Is Initialization) (1) | 2024.11.23 |
| 지시문 #define에 대해서... (2) | 2024.02.02 |
| 포인터 변수 초기화 방법 (1) | 2023.08.06 |
