2022. 5. 30. 22:56ㆍ알고리즘
1. map이란?
map은 각 노드가 key와 value 쌍으로 이루어진 트리입니다. 특히, 중복은 허용하지 않습니다.
따라서 map은 first, second가 있는 pair 객체로 저장되는데 first-key, second-value로 저장됩니다.
c++의 map의 내부 구현은 검색, 삽입, 삭제가 O(logn)인 *레드 블랙트리로 구성되어 있음.
*레드 블랙트리란? 균형(조건) 잡힌 이진 탐색 트리이다.
2.map 기본 형태
map<key,value> map1;
3. map 정렬
map은 자료를 정리할때 내부에서 자동으로 정렬합니다.
map은 key를 기준으로 정렬하며 오름차순으로 정렬합니다.
map<int,int,greater> map1;
4. map 사용법
1)헤더 포함
map을 사용하려면 헤더에 #include <map> 처리를 해야 합니다.
2) map 선언하기
map의 기본 구조는 map <key type, value type> 이름입니다.
map<string, int> m;
3) map에 찾고자 하는 데이터가 있는지 확인하기(search)
map에서 데이터를 찾을 때는 iterator을 사용합니다.
데이터를 끝까지 찾지 못했을 경우, iterator은 map.end()를 반환합니다.
if(m.find("Alice")!=m.end()){
cout<<"find"<<endl;
}
else{
cout<<"not find"<<endl;
}
4) map에 데이터 삽입
map은 중복을 허용하지 않습니다. insert를 수행할 때, key가 중복되면 insert가 수행되지 않습니다.
중복되면 그것은 key의 역할을 제대로 하지않습니다.
m.insert({"leeseungmin",22});
위와 같은 방법을 사용해도 되지만 더편한 방법으로
m[leeseungmin]=22;
위와 같은 코드는 첫번째 코드와 같은데 더 쉽고 간편하게 사용이 가능하다.
5) 반복문 데이터 접근 (first, second)
- 인덱스 기반 반복문 활용한 예제
:인덱스 기반은 iterator을 활용하여 begin()부터 end()까지 찾습니다.
for(auto iter = m.begin(); iter!=m.end(); iter++)
{
cout<<iter->first<<" "<<iter->second<<endl;
}
cout<<<endl;
- 범위 기반 반복문 활용 예제(for-each문)
for(auto iter : m){
cout<<iter.first<<" "<<iter.second<<endl;
}
6) map에서 삭제하기
map에서 데이터를 삭제하기 위해 활용할 함수는 erase와 clear입니다.
1. 특정 위치 요소 삭제
m.erase(m.begin()+n);
2.key값을 기준으로 요소 삭제
m.erase("leeseungmin");
3.map의 모든 요소 삭제
방법 1
m.erase(m.begin(),m.end());
방법 2 clear을 사용-다삭제
m.clear();
'알고리즘' 카테고리의 다른 글
소수구하기 에라토스테네스의 체 (0) | 2022.05.19 |
---|---|
최대 공약수, 최소 공배수 구하는 문제 (0) | 2022.05.19 |
백준 1764 듣보잡 C++ (0) | 2022.05.19 |
팰린드롬(회전문 문제) (0) | 2022.03.23 |
1.시간 복잡도 빅오 표기법 O(N) (0) | 2021.11.05 |