C++ 맵, 셋(map,set)

 

---

<셋>

-Key라 불리는 원소의 집합으로 이루어졌다.

<맵>

-자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료 구조이다.

-key에 대응하는 value도 같이 저장하는 컨테이너로 셋에 value값이 생겼다고 생각하면 된다.

 

-맵셋 모두 레드블랙트리로 구현되어 키값을 기준으로 정렬된.

---

<레드블랙 트리>

-레드블랙 트리리는 아래 이미지처럼 모든 노드는 레드 또는 블랙의 색을 갖고, 모든 null자리에 리프 노드를 둔다.

-루트와 리프노드는 항삭 블랙이고, 루트로부터 임의의 리프 노드에 이르는 경로 상에 레드 노드 두 개가 연속으로 출현하지 못한다.

-루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.

 

이해가 어렵겠지만 결론만 말하자면 위 조건을 만족하게 되면, 삽입,삭제,탐색시 트리에 높이만큼의 시간이 소요되기 때문에 용이해서 이 구조를 쓰는 것이다.

---

<셋 헤더파일>

셋 STL문법을 사용하기 위해서는 헤더 파일을 들고와야 하는데

다음과 같이 작성하면 헤더파일을 들고 올 수 있다.

#include <set>

 

---

<셋 STL문법>

>>선언 하기

set<자료형>(변수이름); 으로 선언할 수 있다.

#include <set>
int main()
{
    set<int> s;
    set<int, greater<int>> s1;// 내림차순 정렬
}

 

>>앞에 있는 값 확인

s.begin(); 을 하면 set에 맨 위에 있는 값을 출력한다.

만약 set이 비워져 있으면 에러가 발생한다.

s.front();

 

>>뒤에 있는 값 확인

s.end(); 을 하면 set에 맨 뒤에 있는 값을 출력한다.

만약 set이 비워져 있으면 이때도 에러가 발생한다.

s.end();

 

>> 크기 확인

s.size();을 하면 현재 set에 들어간 데이터 갯수를 반환한다.

s.size();

 

>> 값 넣기

s.insert(value);을 하면 set에 value값이 들어간다.

s.insert(1);

 

>> 값 빼기

s.erase(key);를 하면 set에 key값이 빠진다.

s.erase(iter);를 하면 set에 iter위치에 값이 빠진다.

s.erase(key);

 

>> 값 찾기

s.find(key);를 했을때, key 값이 찾아지면 그 주소값을 반환하고 못 찾으면 셋에 마지막 주소값을 반환한다.

s.find(key);

 

>>비워져있는지 확인 

s.empty();을 하면 set에 데이터가 없으면 true, 하나라도 들어있으면 false를 반환한다.

s.empty();

---

<맵 헤더파일>

맵 STL문법을 사용하기 위해서는 헤더 파일을 들고와야 하는데

다음과 같이 작성하면 헤더파일을 들고 올 수 있다.

#include <map>

 

---

<맵 STL문법>

>>선언 하기

map<자료형1,자료형2>(변수이름); 으로 선언할 수 있다.

#include <map>
int main()
{
    map<string,ing> m;
    map<string, int, greater<string>> m1;
}

 

>>앞에 있는 값 확인

m.begin(); 을 하면 map에 맨 위에 있는 값(value)을 출력한다.

만약 map 이 비워져 있으면 에러가 발생한다.

m.begin();

 

>>뒤에 있는 값 확인

m.end(); 을 하면 map에 맨 뒤에 있는 값을 출력한다.

만약 map이 비워져 있으면 이때도 에러가 발생한다.

m.end();

 

>> 크기 확인

m.size();을 하면 현재 map에 들어간 데이터 갯수를 반환한다.

m.size();

 

>> 값 넣기

m.insert(value);을 하면 map에 value값이 들어간다.

m.insert(1);

 

>> 값 넣기

m.erase(iter);를 하면 map에 iter위치에 값이 빠진다.

m.erase(m.begin());

 

>> 값 찾기

m.find(key);를 했을때, key 값이 찾아지면 그 주소값을 반환하고 못 찾으면 맵에 마지막 주소값을 반환한다.

m.find(key);

 

>>비워져있는지 확인 

m.empty();을 하면 map에 데이터가 없으면 true, 하나라도 들어있으면 false를 반환한다.

m.empty();