표준 템플릿 라이브러리 (STL) 2, Map

🤯 언리얼을 하기 위해 C++ 기억 되살리기 프로젝트

표준 템플릿 라이브러리 (STL) 2, Map

1. 맵 (Map)

• 키(key)와 값(value)의 쌍들을 저장
• 키는 중복될 수 없음
• C++ 맵은 자동 정렬되는 컨테이너 (키 기준)
• 이진 탐색 트리(binary search tree) 기반
  • 오름차순

#include <map>
int main()
{
    std::map<std::string, int> simpleScoreMap;

    simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));

    simpleScoreMap["Mocha"] = 0;

    return 0;
}

2. std::pair<key, value>

pair<first_type, second_type>

• 두 데이터를 한 단위로 저장하는 구조

std::pair<std::string, int> student1("Coco", 10);
simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));

pair.first 혹은 pair.second 로 키나 값을 가져올 수 있음.

3. insert()

• 새 요소를 map에 삽입한다
• 반복자와 bool 값을 한 쌍으로 반환
  • 반복자는 요소를 가리키고
  • Bool 값은 삽입 결과를 알려줌
• 키를 중복으로 삽입할 수 없음

// <iteerator, true> 반환
simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));

// <iterator, flase> 반환
simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 0));

4. operator[]

• key에 대응하는 값을 참조로 반환
• map에 키가 없으면 새 요소를 삽입
• map에 키가 이미 있으면 그 값을 덮어씀

std::map<std::string, int> simpleScoreMap;

simpleScoreMap["Coco"] = 10;                // 새 요소 삽입
simpleScoreMap["Coco"] = 50;                // "Coco"의 값을 덮어쓴다

5. 요소 찾기, 두 맵 교환, 맵 비우기, 요소 제거, 두 키를 비교하는 함수

5-1. 요소 찾기

#include <map>
int main()
{
    std::map<std::string, int> simpleScoreMap;
    simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));

    std::map<std::string, int>::iterator it = simpleScoreMap.find("Mocha");     // 키를 찾아라
    if (it != simpleScoreMap.end())             // 그 위치의 반복자를 반환
    {                                           // 못찾는 경우 요소를 가리키지 않는 반복자인 end() 반환
        it->second = 80;
    }

    return 0;
}

• map에서 key를 찾으면 그에 대응하는 값을 가리키는 반복자
• 못찾으면 end() 반환
  • end()는 요소를 가리키는 반복자가 아님.. 마지막 요소의 그 다음 위치를 가리킴.

5-2. 두 맵 교환, 맵 비우기

• swap
  • void swap(map& other);
  • 두 map의 키와 값을 서로 바꾼다
• clear
  • void clear();
  • map을 비운다

5-3. 요소 제거

• erase
  • map의 요소들을 제거한다 ```cpp std::map<std::string, int>::iterator foundIt = simpleScoreMap.find(“Coco”); simpleScoreMap.erase(foundIt);

  simpleScoreMap.erase(“Coco”); // 또다른 방식 (키로 찾아서 제거) ```

5-4. 비교 ⭐⭐⭐

// StudentInfo.h
class StudentInfo
{
    public:
        // 생성자들
    private:
        std::string mName;
        std::string mStudentID;
};

// Main.cpp
int main()
{
    std::map<StudentInfo, int> scores;
    scores.insert(std::pair<StudentInfo, int>(StudentInfo("Poppy", "a556"), 30));
    scores.insert(std::pair<StudentInfo, int>(StudentInfo("Lulu", "a112"), 70));
}

// 위 코드는 '비교하는 연산자가 없다~' 식의 에러가 난다.
// 나 정렬하는 방법 모르니까 삽입도 못해 ㅇㅅㅇ 나는 기본적으로 정렬이 되는 map이야

💡 map은 자동 정렬 되는 컨테이너. 그래서 반드시 두 키를 비교하는 함수를 만들어야 함!

bool StudentInfo::operator<(const StudentInfo& other) const
{
    if (mName == other.mName)
    {
        return mStudentID < other.mStudentID;
    }

    return mName < other.mName;
}

요소들을 정렬하는 또 다른 방법 ⭐⭐⭐

• map을 만들 때 비교함수(comparer)를 넣을 수도 있음
• 남이 만들어놓을 구조체에 함부로 접근할 수 없을 땐 이렇게 작성하자

struct StudentInfoComparer
{
    bool operator()(const StudentInfo& left, const StudentInfo& right) const
    {
        return (left.getName() < right.getName());
    }
};

// Main.cpp
std::map<StudentInfo, int, StudentInfoComparer> Scores;

5-5. map 의 장점과 단점

• 장점
  • std::List나 std::vector보다 탐색 속도가 더 빠름
    • 찾고자 하는 키가 존재하고, 이진 트리로 구성되어 있으니 O(log N)으로 줄어드니 O(N)보다 빠름
• 단점
  • 자동으로 정렬됨
  • 해쉬맵(hashmap)이 아님. 해시맵은 O(1)라서 훨씬 빠름.
  • C++11에 해결책이 있음

6. 셋 (Set)

• 역시 정렬되는 컨테이너
  • 셋은 맵과 거의 같다
• 중복되지 않는 키를 요소로 저장
  • 맵에서 값을 빼버린 것과 같음
• 역시 이진 탐색 트리 기반
  • 오름차순

#include <set>
int main()
{
    std::set<int> scores;
    scores.insert(20);
    scores.insert(100);

    for (std::set<int>::iterator it = scores.begin(); it != scores.end(); ++it)
    {
        std::cout << *it << std::endl;
    }

    return 0;
}