맵(Map)

맵(Map)

 

키(Key)와 값(Value)의 쌍들을 저장

키는 중복될 수 없음

C++ 맵은 키를 기준으로 자동 정렬되는 컨테이너.... 으윽....

이진 탐색 트리(binary search tree) 기반

> 오름차순

---

맵의 장점

 

std::list나 std::vector보다 탐색 속도가 더 빠름

> key를 기준으로 값이 크냐 작냐를 비교하며 찾아감 (이진트리, O(logN))

(양쪽으로 나뉘어서 한쪽만 봐 내려가면 거진 logN)

> list나 vector는 앞에서부터 모든 요소들을 훑어야 한다 (O(N))

(for문이 1부터 size까지 돈다면 N)

 

 

맵의 단점

 

자동으로 정렬됨

해쉬맵(hashmap)이 아님. 따라서 O(1)이 아님

C++11에 해결책이 있음

---

 

셋(Set)

 

역시 정렬되는 컨테이너

중복되지 않는 키를 요소로 저장함

역시 이진 탐색 트리 기반 (오름차순)

 

맵에서 value를 뺀, key만 있는게 셋이다!

 

장점과 단점 맵과 같음

 

 

#include <iostream>
#include <map>
#include <set>
 
class StudentInfo
{
public:
    StudentInfo(const char* name, const char* studentID)
        : mName(name), mStudentID(studentID)
    {
 
    }
 
    // STL 맵은 항상 정렬되기 때문에
    // 반드시 두 키를 비교하는 함수 operator<()를 만들어야 함
    bool operator<(const StudentInfo& other) const
    {
        if (mName == other.mName)
        {
            return mStudentID < other.mStudentID;
        }
 
        return mName < other.mName;
    }
 
    const std::string& getName() const
    {
        return mName;
    }
 
    const std::string& getStudentID() const
    {
        return mStudentID;
    }
 
private:
    std::string mName;
    std::string mStudentID;
};
 
struct StudentInfoComparer
{
    // 남이 만든 구조체라서 접근할 수도, 바꿀 수도 없을 때는
    // (어쩔 수 없이) map을 만들 때 비교함수(comparer)를 넣어야 함
    // struct도 class도 가능하지만 class라고 보기에는 애매...(그렇다고 struct라고 보기도...)
    // getter 없으면 friend 써야함
    bool operator()(const StudentInfo& left, const StudentInfo& right) const
    {
        if (left.getName() == right.getName())
        {
            return left.getStudentID() < right.getStudentID();
        }
 
        return (left.getName() < right.getName());
    }
};
 
int main()
{
    // 빈 맵을 생성한다
    std::map<std::string, int> simpleScoreMap;
 
    // 같은 크기(size)와 데이터를 갖는 map을 생성 (복사 생성자 호출)
    std::map<std::string, int> copiedSimpleScoreMap(simpleScoreMap);
 
    // pair<first_type, second_type> : 두 데이터를 한 단위로 저장하는 구조
    // insert() : 새 요소를 map에 삽입한다.
    // std::pair<iterator, bool> insert(const value_type& value);
    // -> 반복자와 bool 값을 한 쌍으로 반환 : 반복자는 요소를 가리키고, bool값은 삽입 결과를 알려줌
    
    simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));   // <iterator, true>를 반환
    simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 0));     // <iterator, false>를 반환
                                                                       // 키를 중복으로 삽입할 수 없음
    simpleScoreMap.insert(std::pair<std::string, int>("Coco", 50));
 
    // operator[] : key에 대응하는 값을 참조로 반환한다.
    // map에 키가 없으면 새 요소를 삽입!! (기본 생성자를 호출하던지 기본 값으로 설정한 후, 참조를 반환)
    // map에 키가 이미 있으면 그 값을 덮어 씀
    simpleScoreMap["Choco"] = 0;     // 새 요소를 삽입한 후, 반환된 참조에 0이라는 값을 대입
    simpleScoreMap["Choco"] = 773;    // "Choco"의 값을 덮어 쓴다
 
    if (simpleScoreMap["Lulu"])    // 1. operator[]가 동작하여 "Lulu"라는 키에 0이라는 값이 맵이 들어간다.
   {                             // 2. "Lulu"키에 대응하는 값은 0이므로 false. else 문을 실행한다.
        simpleScoreMap["Lulu"] = 50;
    }
    else
    {
        // 3. 이미 "Lulu"키에 대응하는 값(0)이 있으므로 insert() 함수는 값을 변경하지 않는다.
        // 여전히 "Lulu"키에 대응하는 값은 0.
        simpleScoreMap.insert(std::pair<std::string, int>("Lulu", 100));
    }
 
    // 자동 정렬
    // key가 string이라 알파벳 순으로 자동 정렬됨
    for (std::map<std::string, int>::iterator it = simpleScoreMap.begin(); it != simpleScoreMap.end(); ++it)
    {
        // first : key, second : value
        std::cout << "(" << it->first.c_str() << ", " << it->second << ")" << std::endl;
    }
    std::cout << std::endl;
 
    // find() : map에서 key를 찾으면 그애 대응하는 값(value)을 가리키는 반복자를 반환
    // 못 찾으면 end()를 반환
    std::map<std::string, int>::iterator it = simpleScoreMap.find("Mocha");
    if (it != simpleScoreMap.end())
    {
        it->second = 80;
    }
 
    // swap() : 두 map의 키와 값을 서로 맞바꾼다
    // 시작이 되는 노드를 가리키는 주소만 바꾸면 swap이 될테니 비싼 연산은 아님
    std::map<std::string, int> anotherScoreMap;
    anotherScoreMap.insert(std::pair<std::string, int>("Nana", 7));
 
    anotherScoreMap.swap(simpleScoreMap);
 
    // clear() : map을 비운다.
    anotherScoreMap.clear();
 
    // erase() : map의 요소들을 제거한다
    // void            erase(iterator position);
    // size_type     erase(const key_type& key);
    // void            erase(iterator first, iterator last);
    std::map<std::string, int>::iterator foundIt = simpleScoreMap.find("Nana");
    simpleScoreMap.erase(foundIt);
 
    simpleScoreMap.erase("Nana");
 
    
    // 사용자 정의 자료형을 키로 사용하기
    std::map<StudentInfo, int> scores;
    
    // STL 맵은 항상 정렬되기 때문에(삽입할 때마다 비교)
    // 클래스 안에 반드시 두 키를 비교하는 함수 operator<()를 만들어야 함
    scores.insert(std::pair<StudentInfo, int>(StudentInfo("Poppy", "a556"), 30));
    scores.insert(std::pair<StudentInfo, int>(StudentInfo("Lulu", "a123"), 70));
    scores.insert(std::pair<StudentInfo, int>(StudentInfo("Poppy", "a556"), 50));    // 키가 같으므로 삽입 X
 
    for (std::map<StudentInfo, int>::iterator it = scores.begin(); it != scores.end(); ++it)
    {
        std::cout << "(" << it->first.getName().c_str() << ", " << it->second << ")" << std::endl;
    }
    std::cout << scores.size() << std::endl << std::endl;
    
    // 위 방법을 못쓰는 경우, map을 만들 때 비교함수(comparer)를 넣을 수도 있음
    std::map<StudentInfo, int, StudentInfoComparer> anotherScores;
    
    anotherScores.insert(std::pair<StudentInfo, int>(StudentInfo("Poppy", "a556"), 30));
    anotherScores.insert(std::pair<StudentInfo, int>(StudentInfo("Lulu", "a123"), 70));
    anotherScores.insert(std::pair<StudentInfo, int>(StudentInfo("Poppy", "a556"), 50));    // 키가 같으므로 삽입 X
    
 
    // 맵에서 value를 빼면 셋!
    std::set<int> scores_set;
    scores_set.insert(20);
    scores_set.insert(100);
    scores_set.insert(100);    // 키가 같으므로 삽입 X
 
    for (std::set<int>::iterator it = scores_set.begin(); it != scores_set.end(); ++it)
    {
        std::cout << *it << std::endl;
    }
 
 
    return 0;
}

 

실행 결과

 

 

출처 : 포큐아카데미 C++ 언매니지드 프로그래밍