[C++ STL] std::map,std::set (연관 컨테이너)

std::map

std::map은 연관(Associative) 컨테이너 중 하나이다.

 -> 모든 연관 컨테이너는 노드 기반 컨테이너이며 키(Key)를 이용해 객체를 꺼내온다. (비선형 자료구조)

 -> 연관 컨테이너의 종류에는 map, set, multimap, multiset 등이 존재한다.

std::map은 이진 탐색 트리의 자료구조로 구현되어 있으며 그중 Red-Black트리라는 균형 이진 트리로 내부가 구현이 되어있다.

 -> 균형 이진 트리는 삽입/삭제/탐색의 시간 복잡도가 log(N)의 시간 복잡도를 가진다.

 -> 일반 이진 탐색 트리는 최악의 경우 한쪽으로 노드가 쏠려 O(N)의 시간 복잡도를 가짐. 그렇기에 균형 이진트리를 사용. (보완된 이진 탐색 트리라고도 함)

 -> 삽입시 데이터가 자동으로 정렬이 된다. (중위순회,디폴트는 less/오름차순)

 

이진 탐색 트리의 중복 키값을 허용하지 않는다는 규칙이 std::map에도 그대로 적용이 되어있다.

 -> multimap은 중복 키를 허용한다.

거기에 키(key)와 값(value)의 쌍을 저장한다.(std::pair)

 

먼저 std::map을 사용하기 위해서는 <map> 헤더 파일을 추가해야 한다.

기본적인 생성방법

//기본적인 생성방법
std::map<int, int> mp;
 
//복사 생성자가 존재한다.
std::map<int, int> mp2(mp);

map <key_type, value_type>이며. 템플릿의 첫 번째 인자가 key값의 자료형, 두 번째 인자가 저장할 객체의 자료형이다.

 

멤버 함수를 하나씩 살펴보자.

 

1.insert 함수

//기본적인 생성방법
std::map<int, int> mp;
    
 
std::pair<std::map<int,int>::iterator,bool> iter = mp.insert(std::make_pair(3, 4));

insert함수는 새 요소를 map에 삽입한다.

std::map은 내부적으로 데이터를 key와 value의 쌍의 형태로 데이터를 저장하기에 pair로 만들어 데이터를 전달해야 한다.

또한 insert함수 호출 시 first에는 iterator를 second에는 bool값을 가지는 std::pair를 반환하게 되는데 반복자는 삽입한 요소를 가리키게 되며, bool값은 삽입의 결과를 알려준다.

우리가 저장한 요소인 pair값인 3,4를 가리키고 있으며 삽입의 결과가 true인 것을 알 수 있다.

std::map은 중복 key의 허용을 금지한다고 했다. 키가 이미 3이 있는 상태에서 또 key가 3인 요소를 삽입해보면

반복자는 이미 3이라는 key가 존재했기에 해당 요소를 가리키게 되며, 중복 키는 허용이 불가능하기에 second의 bool값이 false로 나온 것. 즉 중복 키일 경우 삽입이 되지 않는다.

중복키의 허용을 금지하기에 요소를 map에 삽입하지 않는다.

std::map은 자동정렬이 되는 컨테이너라고 했다. 실제로 데이터를 랜덤 하게 10개 넣고 확인해보면

//기본적인 생성방법
std::map<int, int> mp;
    
::srand(::time(nullptr));
for (int push = 0; push < 10; ++push)
{
    mp.insert(std::make_pair(rand() % 100, push + 1));
}
 
for (auto iter : mp)
{
    std::cout << iter.first << " " << iter.second << std::endl;
}

key값을 기준으로 자동으로 오름차순 정렬이 되는 것을 알 수 있다.

그렇다면 key값을 사용자 정의 자료형으로 넣으면 어떨까.

class Student
{
public:
    Student(int kor, int eng, int math) : m_kor(kor), m_eng(eng), m_math(math)
    {
        m_avg = (m_kor + m_eng + m_math) / 3;
    }
public:
    int m_kor;
    int m_eng;
    int m_math;
    int m_avg;
};
 
int main()
{    
    //기본적인 생성방법
    std::map<Student, int> mp; // Student를 Key값으로.
    
    ::srand(::time(nullptr));
    for (int push = 0; push < 10; ++push)
    {
        mp.insert(std::make_pair(Student(rand() % 100, rand() % 100, rand() % 100), push + 1));
    }
 
    for (auto iter : mp)
    {
        std::cout << iter.first.m_avg << " " << iter.second << std::endl;
    }
    return 0;
}

컴파일 타임에 에러를 띄우지는 않지만 실행해보면

위와 같은 에러가 뜬다. 즉 정렬의 기준을 정해주기 위해서 < 연산자를 오버 로딩해줘야 하는 것.

class Student
{
public:
    Student(int kor, int eng, int math) : m_kor(kor), m_eng(eng), m_math(math)
    {
        m_avg = (m_kor + m_eng + m_math) / 3;
    }
    bool operator<(const Student& other) const // const꼭 붙여야한다.
    {
        return this->m_avg > other.m_avg; // 내림차순
    }
public:
    int m_kor;
    int m_eng;
    int m_math;
    int m_avg;
};

위와 같이 operator <연산자를 오버 로딩하고 실행해보면

이제는 제대로 정렬이 되어 나오는 모습.

std::map은 key를 기준으로 자동정렬이 되는 컨테이너이기에 key값에 사용자 정의 자료형을 넣는다면 꼭 <연산자를 오버 로딩해야 한다.

 -> 템플릿 인자의 마지막 인자로 함수 객체를 넘기는 방법도 있긴 하지만 굳이 그렇게까지 사용은 x

 

2. operator [] 연산자

//기본적인 생성방법
std::map<int, int> mp;
// map에 새 요소를 넣는 또 다른 방법.
// 3이라는 key값과 10이라는 value를 가진 요소를 삽입한다.
mp[3] = 10;

위와 같이 3이라는 key와 10이라는 value의 쌍이 이미 존재했지만, 해당 key에 접근하여 50이라는 값으로 덮어 씌운다.

 

여기서 주의해야 할 점은. operator [] 연산자를 이용하여 해당 key값에 대응하는 값(value)의 참조를 반환한다고 했다.

//기본적인 생성방법
std::map<int, int> mp;
// map에 새 요소를 넣는 또 다른 방법.
// 3이라는 key값과 10이라는 value를 가진 요소를 삽입한다.
mp[3] = 10;
mp[4] = 50;
mp[5] = 20;
mp[6] = 70;
 
std::cout << mp[3] << " " << mp[4] << " " << mp[5] << " " << mp[6] << std::endl;

즉 위와 같이 내부적으로 들고 있는 멤버 함수인 find를 사용하지 않고도 해당 key값에 접근하여 값을 얻어올 수도 있다는 의미다.

하지만 operator [] 연산자는 이러한 find기능도 있지만, 다른 한 가지 기능이 더 존재하는데. 존재하지 않는 key값을 넣어도 문제가 발생하지 않는 것.

std::cout << mp[10] << std::endl; // key값 10은 현재 map에 존재하지 않는다.

실행해보면

이게 의미하는 바는 operator [] 연산자를 이용하여 key값에 접근할 때,

만약 key값이 존재하지 않는다면 넘겨준 key값과 0이라는 value라는 요소를 새로 만들어 map에 삽입해버린다는 것이다.

-> 사용자 정의 자료형의 경우 기본 생성자를 호출.

실제로 확인해보면 위와 같이 map에 10이라는 key와 0이라는 value의 쌍의 요소를 map에 삽입하였다

만약 프로그래머가 operator [] 연산자를 이용하여 해당 key값에 대응되는 값(value)의 반환의 결과만을 얻고 싶었는데

위와 같이 새 요소가 삽입이 되었다면 원치 않는 결과가 발생할 수 있다.

 -> 그렇기에 주의해서 사용해야 한다.

 

insert함수와 가장 큰 차이는 중복 key가 존재하면 insert는 삽입하지 않지만 

operator []는 중복 key가 문제가 아니라 해당 key에 해당하는 값(value)의 참조를 반환하기에 값을 덮어씌울 수 있으며

해당 key가 존재하지 않는다면 해당 key와 함께 0이라는 값을 채워 map에 삽입해버린다.

 

3. find 함수 ★

//기본적인 생성방법
std::map<int, int> mp;
mp[3] = 10;
mp[4] = 50;
mp[5] = 20;
mp[6] = 70;
auto iter = mp.find(3);
if (iter != mp.end())
{
   std::cout << iter->second;
}

find함수는 std::map의 핵심 함수. std::map을 사용하는 이유가 저장된 데이터의 탐색이 자주 일어날 때 사용한다.

 -> 데이터가 100만 개가 있더라도, 찾으려는 데이터가 최악의 경우에도 20번 만에 찾을 수 있다. log(N)

 -> vector의 경우에는 최악의 경우 100만 번 탐색 후 찾을 수 있다. O(N)

 

std::map의 find함수는 이름에서 알 수 있듯이 인자로 넘긴 키(key) 값을 넘겨 map에서 탐색 후 반복자를 반환하는 함수.

1. find함수의 인자로 넘긴 값에 해당하는 key가 map에 존재한다면 해당 key와 value의 요소를 가리키는 반복자를 반환한다.

2. 만약 해당하는 key가 없다면 nullptr을 반환하는 것이 아닌 end를 반환한다.

 

find함수는 이게 전부이고, 인자로 넘겨주는 값은 key값이어야 한다는 것을 잊지 말아야 한다.

 

4. erase, clear 함수

//기본적인 생성방법
std::map<int, int> mp;
mp[3] = 10;
mp[4] = 50;
mp[5] = 20;
mp[6] = 70;
auto iter = mp.find(3);
if (iter != mp.end())
   mp.erase(iter); // 반복자를 넘겨주는 방법.
mp.erase(5); // 키 값을 넘겨주는 방법.

erase함수. map에 존재하는 key값의 요소를 삭제한다.

2개의 key에 해당하는 요소 삭제

반복자를 넘겨 제거하는 방법이 존재하고, 키 값을 바로 넘겨 삭제하는 방법이 존재한다.

erase함수는 삭제에 성공하면 1을 반환하며 실패하면 0을 반환한다.

//기본적인 생성방법
std::map<int, int> mp;
mp[3] = 10;
mp[4] = 50;
mp[5] = 20;
mp[6] = 70;
    
mp.clear();

clear함수는 map의 모든 요소를 비운다.

요소에 key나 value가 동적 할당되어있었다면 그것들을 delete 해주지는 않기에 clear전에 delete처리를 해줘야 한다.

 

 

map 컨테이너의 장점

 - 내부적으로 균형 이진트리(레드 블랙트리)로 구현되어 있어 탐색이 빠르다.(log(N))

  -> 탐색이 자주 일어난다면 std::list나 std::vector를 사용하기보단 map을 사용해야 한다.

 

map 컨테이너의 단점

 - 삽입 삭제 시 매번 정렬이 일어난다. (장점이 될 수도 있지만 성능상으로 칠 때)

 

 

std::set

std::map과 거의 동일하다. 다른점은 std::map은 key와 value의 쌍으로 요소를 저장했다면, std::set의 경우에는 key가 value 그 자체이다.

 

먼저 std::set을 사용하려면 <set> 헤더파일을 추가해야 한다.

기본적인 생성방법

//기본적인 생성방법
std::set<int> st;
//복사생성자 지원
std::set<int> st2(st);
    

std::set은 std::map과 달리 key(value)값 하나만을 저장한다는 차이점 이외에는 다를게 없다.

 -> 단 set에서는 operator[]연산자를 지원하지 않는다.