[코테를 위한 압축 개념] C++ STL 맵(map), 셋(set)

[코테를 위한 압축 개념] C++ STL 맵(map), 셋(set) 

 

 Map

 Map은 연관 컨테이너로 원소를 key와 value의 쌍으로 저장한다. 연관 컨테이너는 균형 이진 트리를 이용하여 O(logN)의 시간복잡도로 원하는 원소를 빠르게 찾을 수 있다.

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

int main(){
    map<int, string> temp;
    return 0;
}

 위와 같이 선언하여 사용할 수 있다.

 

 Map의 사용법

 

 원소 쌍 추가하기

#include <iostream>
#include <map>
using namespace std;
 
int main(){
    map<int, string> temp;
 
    temp.insert({1, "hello"});
    temp.insert(make_pair(2, "world"));
    temp[3] = "map";
 
    cout << temp[1] << '\n';
    cout << temp[2] << '\n';
    cout << temp[3] << '\n';
    
    cout << temp.size() << '\n';
    return 0;
}

 map에 원소 쌍을 추가하는 방법은 여러가지가 있다. insert({key, value}), 또는 key, value을 pair객체로 만들어 insert, 그리고 [key] = value를 이용한 방법이다. 이 때 key의 값은 중복되서는 안된다. 중복 key를 허용하는 multimap이 따로 존재한다. 그리고 vector와 같이 size()를 통해 map의 크기를 확인할 수 있다.

 

 원소 쌍 수정하기

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

int main(){
    map<int, string> temp;
    
    temp[3] = "map";
    cout << temp[3] << '\n';
    
    temp[3] = "change";
    cout << temp[3] << '\n';
    return 0;
}

 key, value 쌍에서 value값을 수정하는 방법은 []을 이용하는게 가장 편하다.

 

 iterator 사용하기

#include <iostream>
#include <map>
using namespace std;
 
int main(){
    map<int, string> temp;
 
    temp.insert({1, "hello"});
    temp.insert(make_pair(2, "world"));
    temp[3] = "map";
 
    map<int, string>::iterator iter;
    
    for(iter = temp.begin(); iter!=temp.end();iter++){
    	cout << iter->first << ',' << iter->second << '\n';
    }
    
    iter = temp.find(2);
    cout << iter->first << ',' << iter->second << '\n';
    
    
    return 0;
}

 iterator는 map<int, string>::iterarot iter; 로 선언 후 사용할 수 있다.

map은 정렬된 균형 이진 트리로 이분 탐색의 lower_bound, upper_bound 또한 유용하게 사용될 수 있다.

 

 unordered_map

 map은 기본적으로 정렬이 된 상태를 유지하기 때문에 데이터가 크면 연산의 시간이 길어질 수 있다. 따라서 문제에 따라 unordered_map이 사용될 때가 있다.

#include <iostream>
#include <unordered_map>
using namespace std;
 
int main(){
    unordered_map<int, string> temp;
    
    return 0;
}

 unordered_map은 map과 별개로 include해서 사용한다.

map과 unordered_map의 차이는 gracefulprograming.tistory.com/3 에서 참고할 수 있다.

 

 Set

 Set은 Map과 유사하나 Key값만 존재하는 연관 컨테이너이다.

#include <iostream>
#include <set>
using namespace std;
 
int main(){
    set<int> temp;
  
    return 0;
}

위와 같이 선언하여 사용할 수 있다. 얼핏 생각하면 priority queue와 같은 역할이 아닌가 싶을수도 있지만, priority queue는 heap 구조임에서 차이가 있다.

 

 Set의 사용법

 Set은 Map과 거의 유사하기 때문에 자세한 설명없이 코드로 보겠다.

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

int main() {
	set<int> temp;
	
	temp.insert(1);
	temp.insert(4);
	temp.insert(10);
	temp.insert(7);
	
	cout << "Size: " << temp.size() << '\n';
	
	set<int>::iterator iter;
	for(iter=temp.begin();iter!=temp.end();iter++){
		cout << *iter << '\n';
	}
	
	iter = temp.find(4);
	cout << *iter << '\n';
	
	temp.erase(4);
	for(iter=temp.begin();iter!=temp.end();iter++){
		cout << *iter << '\n';
	}
	
	temp.clear();
	return 0;
}