[STL] C++에서 Map에 대해 알아보자

Posted on | Edited on | In

안녕하세요. 오늘은 C++ STL에 대한 글을 써보려 합니다. 본래 저는 STL과 같은 기본적인 글은 잘 쓰지 않으려 했습니다. 워낙 Documentation도 잘 되어 있는 편이고, 블로그의 글 주제로 쓰기에는 적합하지 않다고 생각했습니다.

하지만 오늘 이 글을 쓰게 된 계기는 제가 알고리즘 풀이를 몇 번 진행하면서 제가 주로 쓰고 있는 Java 언어와 다소 차이가 있는 것으로 확인이 된 자료구조가 몇 있었습니다. 그래서 각 언어에서 비슷한 자료구조의 형태가 STL이나 API로 지원된다하더라도 언어에 따라 사용하는 방법이나 각 함수들에 대한 기능에 대해서는 짚고 넘어가야 할 필요가 있다고 느꼈습니다.

What is STL ?

STL은 C++에서 제공하는 Standard Template Library입니다. C++ 언어는 기존의 C언어에서 클래스나 상속, 접근 지정자 등이 추가된 객체 지향 프로그래밍 언어라고 알고 계십니다. 맞습니다. 그런데 그런 좋은 기능 + 표준 템플릿 라이브러리가 포함되어 있습니다.

실제로 저는 C++ 프로그래밍 했을 때 STL보다는 Boost 라이브러리를 많이 사용했습니다. Boost 라이브러리는 C++ 언어로 제공되는 부가 라이브러리 중 하나로 네트워크 프로그래밍에 유용한 Asio 등을 제공하여 C++를 쉽고 더 강력하게 표현해주는 아주 우수한 라이브러리입니다.

더욱 좋은 것은 Boost에서 제공하는 시스템 자원 (Thread, Semapore 등)을 System Call 형태가 아닌 Library Call 형태로 제공하여 Linux, Windows 등의 OS의 제약없이 크로스 플랫폼으로 사용할 수 있다는 것도 한몫하고 있죠.

하지만 이런 라이브러리들은 모두 3rd party 라이브러리라고 해서 프로그래밍 언어 개발사에서 공식적으로 제공해주는 것이 아닌 제3자가 개발한 것이기 때문에 그 기능이 온전하거나 인증받은 코드라고 하기엔 조금 거리가 먼 점이 있습니다. 그래서 이러한 라이브러리를 표준으로 인증받은 모음집을 STL이라고 합니다.

Container

컨테이너는 STL에서 제공하는 데이터를 저장하는 객체 (자료구조) 들입니다. 보통 저는 vector, pair, list, map, stack, queue를 주로 많이 사용하는 편입니다. 이 글에서는 map에 대해서 다뤄보도록 하겠습니다.

Map

자료구조 맵(Map)은 <Key, Value> 형태로 되어 있는 자료구조입니다. 주로 매핑하는 용도로 많이 사용하는 자료구조이며 정렬된 형태로 제공한다는 것이 특징입니다. Key 값을 찾을 때 시간복잡도가 O(1)을 자랑할 정도로 매우 성능이 좋습니다.

1
2
3
4
5
6
7
8
9
10
#include <map>

using std::map;

int main(int argc, char **argv)
{
    map<int, int> map;
    
    return 0;
}

기본적인 사용 방법은 위와 같습니다. 먼저 map 코드를 include하고, 네임스페이스룰 추가해줍니다. 그리고 자신이 원하는 <Key, Value> 형태의 데이터 타입을 선언하고 변수 이름을 선언하면 첫 번째 Map 생성이 완료됩니다.

Key Point

Map을 사용하는 포인트는 바로 좌표 지점을 저장할 때 사용하는 Pair나 Point의 자료를 보관할 때 매우 유리합니다. Map 역시 2차원 배열처럼 2차원 Map으로도 사용할 수 있기 때문에 이러한 자료들을 보관하고 쉽게 꺼내오는 데 있어 팔방미인이라고 할 수 있습니다.

처음 Map 자료구조를 선언하면 아무것도 없습니다. 따라서 값을 넣어줘야 하는데, 값을 넣는 방법에는 두 가지 방법이 있습니다.

How to insert value

먼저 첫 번째 방법은 insert 메소드를 사용하는 방법입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <map>
#include <pair>

using std::map;
using std::pair;

int main(int argc, char **argv)
{
    map<int, int> m;
    m.insert(pair(1, 2));
    
    return 0;
}

insert 메소드를 사용할 때는 두 개의 인자가 아닌 1개의 인자를 사용합니다. 그렇다면 이 쌍을 넣을 수 있는 방법으로는 Pair 자료구조를 사용해서 넣는 방법이 있습니다. 혹은 C++에서 제공하는 make_pair 함수를 사용하는 것 또한 방법이 될 수 있습니다.

두 번째 방법은 C++ 프로그래밍 언어에서 제공하는 operator를 사용하는 방법입니다.

1
2
3
4
5
6
7
8
9
10
11
#include <map>

using std::map;

int main(int argc, char **argv)
{
    map<int, int> m;
   	m[1] = 2;
    
    return 0;
}

operator는 함수 없이 수식을 사용하는 방법입니다. 오히려 더 깔끔하고 pair를 사용하지 않고도 넣을 수 있기 때문에 이 방법이 더 가독성이 좋다고 할 수 있습니다. 하지만 여기에는 함정이 숨겨져 있습니다.

Insert method vs Operator

operator가 존재한다면 Insert 메소드는 deprecated 해도 될 것입니다. 하지만 왜 두 가지 방법이 모두 존재하는 걸까요? 거기에는 아주 미세한 차이가 숨겨져 있습니다.

  • Insert Method
    • Map에서 Key와 Value를 넣는 메소드.
    • 기존의 키값이 중복될 경우, 이 메소드는 무시함
  • Operator
    • 기존의 키값이 중복될 경우, 새로운 값으로 대체

Insert Method를 사용하게 되면, 기존의 키값이 중복되었을 때, 이 메소드는 그저 무시됩니다. 말그대로 기존의 키값을 가지고 있는 value를 지킨다는 것이죠. 즉 키값이 중복될 경우, 기존의 값을 우선한다는 것입니다.

하지만 operator를 사용할 경우, 기존의 키 값이 존재한다하더라도 현재의 코드를 중시합니다. 따라서 기존의 키에 존재했던 값은 제거되고, 새로운 값으로 대체되는 것입니다.

하지만 Java에서는 그렇지 않습니다.

맞습니다. Java 언어에서 Map을 사용할 경우, put 메소드를 사용하여 Key, Value를 추가하게 되는데, 이 때는 기존의 키 값이 무시되고, 새로운 값으로 대체가 되죠.

각 언어에서 비슷한 메소드나 방법이 제공되더라도 미세한 차이가 있기 때문에 이 부분은 짚고 넘어가야할 것입니다.

How to get Value

그럼 Map에서 값을 가져오려면 어떻게 해야할까요?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <map>

#define	SIZE	10

using std::cout;
using std::endl;
using std::map;

int main(int argc, char **argv)
{
    map<int, int> m;
    for(int i = 0; i < SIZE; i++)
    	m[i] = i + 1;
    
    for(int i = 0; i < SIZE; i++)
    {
        auto it = m.find(i);
        cout << "<" << it->first << "," << it->second << ">" << endl;
    }
   
    return 0;
}

Key의 값을 기준으로 value를 찾을 때는 find 함수를 사용할 수 있다. 이 때, find 메소드로 찾게 되면, iterator로 값을 반환한다. first는 Key, second는 value로 값을 출력시킬 수 있다.

Iterator

Iterator는 STL에서 제공하는 반복자로 보통 우리가 자료구조를 사요하게 되면 Index 번호를 사용해서 해당 자료구조의 크기나 길이를 반복 길이로 삼고 반복문을 잡곤 한다.

하지만 STL에서는 반복자인 Iterator가 지원된다.

  • input iterators
  • output iterators
  • forwards iterators
  • bidirectional iterators
  • random access iterators

iterator는 총 5개의 종류를 가지고 있다. 시퀀스를 읽기만 할 때는 input, 시퀀스를 쓸 때만 할 때는 output, 읽고 쓰기도 가능하고 앞으로 움직일 수도 있는 forward, 뒤로도 움직일수도 있는 biorectional, 그리고 그것보다도 더 자유로운 random access가 있다.

하지만 Map에서는 Iterator 사용이 좋지만은 않습니다. Set에서도 마찬가지지만 이러한 연관 컨테이너에서 검색을 수행하는 데 보통 사용되는데, 컨테이너에서 직접 호출하는 멤버 함수 대신 Iterator로 함수를 직접 구현해서 쓰는 분들도 계시는데, 이는 지극적으로 비추천합니다. 반복자 자체가 포인터를 사용한다는 면목도 있고, 성능에 대한 인증성이 불투명하기 때문입니다.

find 메소드로 우리는 key값을 이용해 해당 value를 찾을 수 있었는데요. 그렇다면 반대로 value를 기준으로 key 값을 찾는 메소드가 있을까요?

결론은 없습니다. find 메소드는 오직 key 값으로 value만 찾을 수 있고, 반대로 value를 가지고 key를 찾아내려면 직접 구현해야 하는데, O(n) 시간복잡도로 간단하게 이렇게 구현할 수 있을 것 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <map>

#define	SIZE	10

using std::cout;
using std::endl;
using std::map;

int main(int argc, char **argv)
{
    map<int, int> m;
    for(int i = 0; i < SIZE; i++)
    	m[i] = i + 1;
    
    int val = 2;
    
    for(auto it = m.begin(); it != m.end(); ++it)
    {
        if(it->second == val)
            cout << it->first;
    }
   
    return 0;
}

Map의 시작지점에서부터 끝지점까지 반복하고, 해당 second 값을 비교해보면, 간단히 알 수 있겠죠? 알고리즘이 어렵지 않기 때문에, 사실상 구현은 되어 있지 않아도 쉽게 찾을 수 있겠습니다.

0%