STL::associative container

영어로 제목적으니 있어보인다

지난시간에는

지난시간에 학습한 sequence container들은 말 그대로 원소를 보관하는 컨테이너 였다면 이번에 공부할 내요은 연관컨테이너이다.

쉽게 설명하면 파이썬의 맵 기능이라고 보면 될듯하다

set

#include <iostream>
#include <set>

template <typename T>
void set_print(std::set<T>& s) {
    std::cout << "[ ";
    for (typename std::set<T>::iterator itr = s.begin(); itr != s.end(); ++itr) {
        std::cout << *itr << " ";
    }
    std::cout<< "]" << std::endl;
}

int main() {
    std::set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(5);
    s.insert(4);
    s.insert(3);
    s.insert(6);

    std::cout << "In order" << std::endl;

    set_print(s);

    std::cout << "finding 2: ";
    auto itr = s.find(2);
    if (itr != s.end()) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    std::cout << "finding 7:  ";
    itr = s.find(7);
    if (itr != s.end()) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }
}

pyhton의 set과 같은 역할을 수행한다.

• 추가 혹은 삽입의 경우 O(logN)

set 자료형의 경우 해당 elem이 있는지 없는지의 여부가 중요한것이지, 어디에 위치하는지는 중요하지 않다. 따라서 중복도 정리해버리고 알아서 정렬해서 숫자를 내버린다.

find

find의 경우 set 안에 해당원소가 있는지 없는지 알려주는 기능을 수행한다. 이 기능은 백터에서 수행했다면 O(n)이 걸린다. 백터에서는 전체를 검사해야하기 때문이다. 하지만 set에서는 트리형태로 구성이 되어있기때문에 탐색시간이 매우 절약된다. 또한 BST는 안되더라도 최대한 균형을 잡기위해 노력한다.

놀랍게도 대부분의 set은 레드블랙트리로 구현된다고 한다.
쉬운내용은 아니니깐 한번 읽어보면 좋을것같다.

중복원소를 허락하는경우 mulitset을 사용한다.

클래스 객체를 set에 넣기

그냥 넣으면되는거 아닐까 싶지만 그러면 출력과정에서 우선순서 판단때문에 오류가 발생한다.

#include <iostream>
#include <set>
#include <string>

template <typename T>
void print_set(std::set<T>& s) {
    std::cout << "[ ";
    for (const auto& elem : s) {
        std::cout << elem << " " << std::endl;
    }
    std::cout << " ] " << std::endl;
}
class Todo_list {
    int priority;
    std::string job_desc;

    public:
    Todo_list(int priority, std::string job_desc)
        : priority(priority), job_desc(job_desc) {}
    };

int main() {
    std::set<Todo_list> todos;

    todos.insert(Todo_list(1, "Work A"));
    todos.insert(Todo_list(2, "Work B"));
    todos.insert(Todo_list(3, "Work C"));
    todos.insert(Todo_list(2, "Work D"));
    todos.insert(Todo_list(1, "Work E"));
}

이러한 코드가 있을 때, 이는 오류가 발생한다.
그 이유는 즉, Todo_list 안에 operator "<"을 정의하는 내용이 없기 때문이다.
자세한 구현은 링크를 보고 따라하면 좋을것같다.

map

set과 거의 유사하지만, value만 가지는게 아니라 key값도 가진다.

이 자료형에는 key, value가 필요하기때문에
선언을 할 때,

std::map<std::string, double> map_list;

처럼 두 값을 선언해야하고
insert 역시

map_list.insert(std::pair<std::string, double>("ABC", 1233));

처럼 작성해야한다.

맵의 경우 operator[]을 이용해서 새로운 값을 추가할 수 있다.

map_list["BBC"] = 13.22

만약 해당 키가 없다면 값이 추가되고 있다면 value가 대체된다.

값이 보고싶다면 map["abc"]를 쓰면 되는데 이때 주의할 점은, 만약 값이 없는 없더라도 defalut에 의하여 0을 반환해버린다는 점이다.

기타 set, map

multi_set, multi_map

중복원소를 허락하는 set, map 자료형이다.

unordered_set, unordered_map

정렬되지않은셋과맵

정렬하지 않고 출력을 랜덤하게 해준다...

대신 엄청난 기능이 있는데 바로 insert, erase, find 전부 O(1)이라는점이다.
이는 unordered가 해시함수를 사용하기 때문이다.

물론 해시함수의 특성상 collision이 계속 발생하면 O(n)이 걸릴수도 있다.(기존의 set, map은 무조건 O(logN)이다.)

따라서 정확히 설계된것이 아니라면 그냥 기존의 것을 쓰는것이 낫다.