<map>, <set>

map 컨테이너는 레드 블랙 트리 자료구조를 기반으로 구현되어 있는 STL이다
키 : 값 의 한 쌍으로 저장되며 키는 중복되지 않고 키를 기준으로 내부적으로 정렬이 된다.
 
set은 map과 동일한 자료구조를 사용하지만 키 : 값이 아닌 고유한 값으로만 저장된다.
 

#include <iostream>
#include <map>

int main()
{
    std::map<int, int> intMap;

    // 인덱스를 직접 접근해서 값을 넣거나
    // std::make_pair를 통해 키 : 값 으로 묶어서 요소를 삽입한다.
    intMap[0] = 5;
    intMap[1] = 10;
    intMap.insert(std::make_pair(2, 10));
    
    // initializer_list 방법 모던 c++방식
    intMap.insert({3, 15});


    // 맵이 비어있는지 확인
    const bool isEmpty = intMap.empty();
    
    // 해당하는 키가 있는지 검색할 수 있다.
    // 반환은 Iterator로 반환을 하고 없을 경우 end()가 반환된다.
    std::map<int, int>::iterator intMapIter = intMap.find(1);

    if (intMapIter != intMap.end())
    {
        // end() 같지 않으면 iterator가 가르키는 키의 값은
        // second로 접근이 가능하다.
        std::cout << intMapIter->second << std::endl;
    }

    // 맵에 있는 요소의 갯수를 반환한다.
    const size_t size = intMap.size();

    // 맵에 있는 요소들을 정리한다.
    intMap.clear();


    // Iterator를 통해 순회할 수 있다.
    std::map<int, int>::iterator iter = intMap.begin();
    
    for (; iter != intMap.end(); ++iter)
    {
        // iterator 가르키는 키의 second가 값에 해당
        std::cout << iter->second << std::endl;;
    }

    // 키 값 또는 반복자를 통해 해당하는 키를 제거할 수있다.
    intMap.erase(1);
    intMap.erase(iter);
    intMap.erase(iter, intMap.end());


    return 0;
}

 
 
std::map의 내장함수 시간 복잡도, std::set도 동일

함수	시간 복잡도	설명
clear()	O(1)	모든 요소를 삭제
size()	O(1)	맵에 저장된 요소의 갯수를 반환
empty()	O(1)	맵이 비어 있는지 확인
insert()	O(log n)	특정 위치에 요소 삽입
erase()	O(log n)	특정 위치에 요소를 제거
find()	O(log n)	맵에서 키를 찾음