9-7. STL - Map

0. 객체가 많아졌을 때 vector의 문제

각자의 플레이어 아이디를 가지는 객체 player를 생성한다.

#include <iostream>
#include <vector>
#include <list>
#include <deque>

using namespace std;

class Player
{
public:
    Player() : _playerId(0) {}
    Player(int playerid) : _playerId(playerid) {}


public:
    int _playerId;
};

이후 10만명을 입장시키고 랜덤으로 5만명을 퇴장시키게 한다.

int main()
{
    
    vector<Player*> v;

    // 10만명 입장
    for (int i = 0; i < 100000; i++)
    {
        Player* p = new Player(i);
        v.push_back(p);
    }
    
    // 5만명 퇴장
    for (int i = 0; i < 50000; i++)
    {
        int randIndex = rand() % v.size();

        Player* p = v[randIndex];
        delete p;

        v.erase(v.begin() + randIndex);
    }
}

여기에서 playerId가 12345인 플레이어를 찾아낼 수 있을까?

-> 플레이어 숫자 만큼 반복문을 사용 -> 과부하 발생

 

즉 vector와 list는 원하는 특정 조건에 해당하는 데이터를 찾아내기 어려움.

 

1. 연관 컨테이너(Associate Container)

어떤 데이터에 대한 키와 그 데이터를 함께 저장함.

키를 통해 데이터를 찾는 식으로 빠르게 서치 가능.

각 원소들이 정렬된 상태를 유지함.

 

2. map

(1) 각 데이터에 대한 고유 키가 존재(키와 데이터가 1:1로 매칭됨)

int main()
{
    // map ; 균형 이진 트리(AVL)
    map<int, int> m;

    //10만명 입장
    for (int i = 0; i < 100000; i++)
    {
        m.insert(pair<int, int>(i, i*100)); // 키를 i, 데이터를 i*100으로 페어링
    }

 

(2) 무작위로 키-값 쌍을 삭제

    for (int i = 0; i < 50000; i++)
    {
        int randValue = rand() % 50000;

        m.erase(randValue);
        
    }

 

(3) 조건에 해당하는 값 찾기

    // ID 1만인 player 서치
    map<int,int>::iterator findIt = m.find(10000);

결과값으로는 반복자를 리턴함.

만약 반복자가 map의 끝을 가리키고 있으면 값을 찾지 못한 것이므로,

(반복자가 map의 끝을 가리키고 있지 않으면 값을 찾은 것이므로)

    if (findIt != m.end())
    {
        cout << "찾음" << endl;
    }

이렇게 조건문을 만들 수 있다.

 

(4) erase를 두 번 쓰면 어떻게 될까?

정상적으로 제거되면 1을 반환, 이미 지워지거나 이미 없는 값이면 0을 반환한다.

 

(5) insert를 두 번 쓰면 어떻게 될까?

m.insert(make_pair(1, 1234));
m.insert(make_pair(1, 1000));

첫번째 줄은 정상적으로 작동하지만 두번째 줄은 작동하지 않음.

map은 각 데이터에 대응하는 고유한 키 값을 가지기 때문임.

 

(6) 반복자를 이용해 순회

    for (map<int, int>::iterator it = m.begin(); it != m.end(); ++it)
    {
        pair<const int, int>& p = (*it);
        int key = it->first;
        int value = it->second;
    }

반복자가 처음에는 map의 첫부분을 가리키게 하고, 마지막을 가리키면 반복문을 끝내게 한다.

반복자의 값은 pair<const int, int>의 형태로 저장이 되며, 포인터 문법을 사용하여 키와 값을 추출할 수 있다.

 

(7) 데이터가 없으면 추가하고 있으면 수정하기

    map<int,int>::iterator findIt = m.find(10000);
    if (findIt != m.end())
    {
        findIt->second = 200;
    }
    else
    {
        m.insert(make_pair(10000, 10000));
    }

위와 같은 방법으로 만들 수 있고 임의 접근으로도 만들 수 있다.

    m[5] = 500;

m에 5라는 값이 없으면 500을 대입하고, 있으면 500으로 수정한다.

단, 이 방법은 키-값 쌍을 기본적으로 만들기 때문에 주의하여 사용해야 한다.

(없는 값을 서치할 때 위 문법을 사용하면 값을 만들어버릴 수 있음)