[C++] STL set / map사용법

C++에서 다양한 STL을 제공하는데, 그 중에서 set과 map을 소개한다. 두 자료구조 모두 공통으로 associative container다.

• Sequential container: array, vector, list
• Associative container: set, map

set

set은 특정 기준에 의해 element가 자동으로 정렬되는 자료구조로 수학적으로는 집합을 의미한다. 따라서 중복된 값을 가질 수 없으며, 만약에 중복된 원소를 갖고자 한다면 multiset을 사용해야 한다.

STL 내부는 balanced binary tree로 구현되어 탐색하는데 시간이 빠르게 걸린다는 장점이 있다.

Template Parameters

Template Parameters	Description
class T	Element type
class Compare = std::less<typename Container::value_type>	Sorting 방식 Default sorting type: descending order
class Alloc = allocator<T>	Allocator type

Member Functions

대표적으로 사용되는 member function만 소개한다.

Member Function	Description
insert	Insert element
erase	Erase elements using value
clear	Clear content
find	Get iterator to element
count	Get number of elements
lower_bound	Return an iterator pointing to the first element in the container
upper_bound	Returns an iterator pointing to the next element in the container

Example

#include <iostream>
#include <set>

using namespace std;

class Node
{
public:
    Node(int _val, int _id): val(_val), id(_id) {}
    int val;
    int id;
};

struct cmp
{
    bool operator() (Node n1, Node n2) {
        if (n1.val == n2.val)
            return n1.id > n2.id;
        else
            return n1.val > n2.val;
    }
};

int main()
{
    set<Node, cmp> set_obj; // descending order, but default is ascending order

    set_obj.insert(Node(10, 1));
    set_obj.insert(Node(20, 2));
    set_obj.insert(Node(30, 3));
    set_obj.insert(Node(40, 4));
    set_obj.insert(Node(50, 5));

    printf("################## List up Set Elements ###################\n");
    for (auto i: set_obj) {
        printf("[%d] %d\n", i.id, i.val);
    }

    set_obj.insert(Node(10, 1));
    set_obj.erase(Node(20, 2));

    printf("############### After Inserting New Elements ##############\n");
    for (auto i: set_obj) {
        printf("[%d] %d\n", i.id, i.val);
    }

    if (set_obj.find(Node(10, 1)) == set_obj.end()) {
        printf("[FAILURE] There is no specific element in the set\n");
    } else {
        printf("[SUCCESS] There is specific element in the set\n");
    }


    return 0;
}

############ List up Set Elements ############
 [5] 50
 [4] 40
 [3] 30
 [2] 20
 [1] 10
 ######### After Inserting New Elements ############
 [5] 50
 [4] 40
 [3] 30
 [1] 10
 [SUCCESS] There is specific element in the set

map

map은 key와 value로 구성되는 자료구조로, set과 마찬가지로 동일한 key를 가지는 element는 가질 수 없다. set과 다른점이 있다면 [] 연산자를 지원하며 insert 함수를 쓰지 않고도 element를 추가 할 수 있다. 참고로 C++에서 map은 RB-tree로 구현되어 있다. 만약 중복의 key를 갖는 원소를 갖고 싶으면 multimap을 사용하면 된다.

Template Parameters

Template Parameters	Description
class Key	Key element type
class Value	Value element type
class Compare = std::less<typename Container::value_type>	Sorting 방식 Default sorting type: descending order
class Alloc = allocator<T>	Allocator type

Set에서 key와 value type에 대해서만 추가가 된다.

Member Functions

Member Function	Description
insert	Insert element
erase	Erase elements using value
clear	Clear content
find	Get iterator to element
count	Get number of elements

Example

#include <iostream>
#include <map>

using namespace std;

class Node
{
public:
    Node(int _val=0, int _id=0): val(_val), id(_id) {}
    int val;
    int id;
};

int main()
{
    map<string, Node> map_obj; // descending order, but default is ascending order

    map_obj["first"] = Node(10, 1);
    map_obj.insert(make_pair("second", Node(20, 2)));
    map_obj.insert(make_pair("third", Node(30, 3)));
    map_obj["fourth"] = Node(40, 4);
    map_obj["fifth"] = Node(50, 5);

    printf("################## List up Set Elements ###################\n");
    for (auto i: map_obj) {
        cout << "[" << i.first << "] - " << i.second.val << endl;
    }

    map_obj.insert(make_pair("first", Node(100, 1)));
    map_obj.erase("fifth");
    map_obj.erase("sixth");

    printf("############### After Updating Map ##############\n");
    for (auto i: map_obj) {
        cout << "[" << i.first << "] - " << i.second.val << endl;
    }

    if (map_obj.find("first") == map_obj.end()) {
        printf("[FAILURE] There is no specific element in the set\n");
    } else {
        printf("[SUCCESS] There is specific element in the set\n");
    }


    return 0;
}

############ List up Set Elements ############
 [fifth] - 50
 [first] - 10
 [fourth] - 40
 [second] - 20
 [third] - 30
 ######### After Updating Map ############
 [first] - 10
 [fourth] - 40
 [second] - 20
 [third] - 30
 [SUCCESS] There is specific element in the set