STL 시퀀스 컨테이너, 연관 컨테이너 정리

일시불 -

대원칙 : 컨테이너의 원소 접근은 반복자로 한다.

STL 시퀀스 컨테이너

벡터 (vector)

임의의 위치의 원소에 접근 [], at : $O(1)$

맨 뒤에 원소 추가 및 제거 push_back, pop_back : amortized $O(1)$

임의의 위치 원소 추가 및 제거 insert, erase : $O(n)$

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);
    
    for (std::vector<int>::size_type i = 0; i < vec.size(); i++)
    {
        std::cout << "vec " << i+1 << "th elem" << vec[i] << std::endl;
    }
}

반복자(iterator)

반복자는 컨테이너에 iterator 멤버 타입으로 정의되어 있음

vector에서 반복자를 사용하려면 begin(), end()함수를 사용

// 전체 벡터를 출력하기
for (std::vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
std::cout << *itr << std::endl;
}
상수 반복자

cbegin(), cend()

역반복자

rbegin(), rend()

상수 역반복자

crbegin(), crend()

erase함수 사용 시 반복자가 가리키는 대상 삭제되지 않도록 주의

리스트

임의 위치에 추가 및 삭제 : $O(1)$

메모리가 비연속적이므로 임의 위치에 접근 불가능

BidirectionalIterator: itr을 사용해 itr++, itr--, ... 같은 연산만 가능

#include <iostream>
#include <list>
int main()
{
    std::list<int> lst;
    lst.push_back(10);
    lst.push_back(20);
    lst.push_back(30);
    lst.push_back(40);
    for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); ++itr)
    {
        std::cout << *itr << std::endl;
    }
}

덱(deque - double ended queue)

  • 실행 속도를 위해 메모리를 희생하는 컨테이너
  • 데이터를 블록으로 저장, 이 블록을 가리키는 벡터 필요
  • 복잡도
    • 임의의 위치의 원소에 접근 []. at : $O(1)$
    • 원소 추가 및 제거 push_front, pop_front, push_back, pop_back : $O(1)$
      • 블록을 새로 할당하므로 상수 시간 소요
    • 임의의 위치 원소 추가 및 제거 insert, erase : $O(1)$

결론

  • 일반적인 상황에서는 벡터를 사용한다.
  • 맨 끝이 아닌 중간에 원소들을 추가하거나 제거하는 작업이 많고, 원소들을 순차적으로만 접근한다면 리스트를 사용
  • 맨 처음과 끝 모두에 원소들을 추가하거나 제거하는 작업이 많으면 덱 사용

STL 연관 컨테이너

키 - 값 연관 구조를 가지는 컨테이너

특정 키가 컨테이너 상에 존재하는지 여부 : 셋, 멀티셋

특정 키에 대응되는 값이 무엇인지 : 맵, 멀티맵

셋

원소가 트리 구조로 정렬되어 있음

복잡도

  • 임의의 위치의 원소에 접근 불가
  • 원소 추가 및 제거 insert : $O(logN)$
    • 블록을 새로 할당하므로 상수 시간 소요
  • 임의의 위치 원소 추가 및 제거 insert, erase : $O(1)$
#include <iostream>
#include <set>

template <typename T>
void print_set(std::set<T> &s)
{
    // 셋의 모든 원소들을 출력하기
    for (typename std::set<T>::iterator itr = s.begin(); itr != s.end(); ++itr)
    {
        std::cout << *itr << " ";
    }
}

template <typename T>
void isElem(std::set<T> &s, T num)
{
    auto itr = s.find(num);
    if (itr != s.end())
    {
        std::cout << "Yes" << std::endl;
    }
    else
    {
        std::cout << "No" << std::endl;
    }
}

int main()
{
    std::set<int> s;

    s.insert(10);
    s.insert(50);
    s.insert(20);
    s.insert(40);
    s.insert(30);

    print_set(s); //순서대로 정렬돼서 나온다

    isElem(s, 20);
    isElem(s, 25);
}

인스턴스를 Set의 원소로 받고 싶다면, 해당 클래스에 대해 operator<가 정의되어 있지 않으므로

struct DataCmp
{
    bool operator()(const Data &t1, const Data &t2) const
    {
        if (t1.priority == t2.priority)
        {
            return t1.data < t2.data;
        }
        return t1.priority > t2.priority;
    }
};

와 같이 구조체를 선언한 다음,

std::set<Data, DataCmp> Datum;

와 같이 set의 템플릿 인자로 넘겨주게 되면 set에서 DataCpm를 사용해 객체 비교를 수행한다.

맵

키와 그에 대응되는 값을 보관하는 자료구조

template <class T1, class T2>
struct std::pair
{
    T1 first;
    T2 second;
};

Data.insert(std::pair<T1, T2>(Key1, Value1));

pair객체를 사용할 때마다 템플릿 인자를 넣어 선언해야 하는 번거로움이 있어서 make_pair함수와 []연산자로 선언 가능

Data.insert(std::make_pair(Key1, Value1));
Data[Key2] = Value2;

이때 Key, Value의 타입은 자동으로 할당됨

template <typename K, typename V>
void print_map(std::map<K, V> &m)
{
    // 맵의 모든 원소들을 출력하기
    for (auto itr = m.begin(); itr != m.end(); ++itr)
    {
        std::cout << itr->first << " " << itr->second << std::endl;
    }
}

itr->first는 해당 원소의 키를, itr->second는 해당 원소의 값을 리턴함.

또는 range-based-for로 대체하면

void print_map(Std::map<K,V> &m)
{
	for (const auto& kv : m)
    {
        std::cout << kv.first << " " << kv.second << std::endl;
    }
}

멀티 맵, 멀티 셋

생략

정렬되지 않은 셋과 맵(unordered_set, unordered_map)

insert, erase, find 모두 $O(1)$에 수행됨

해시 함수(Hash function)

임의의 크기를 갖는 데이터를 고정된 크기의 데이터로 대응시키는 함수

저장할 수 있는 해시값의 개수가 충분하다면, 해시 매핑에 상수 시간이 소요됨

해시 함수를 통해서 unordered_set, unordered_map은 평균적으로 $O(1)$시간으로 원소의 삽입/탐색이 수행 가능

최악의 경우 $O(N)$ 시간 소요

결론

  • set

    • 데이터의 존재 유무만 알고싶다

  • map

    • 데이터에 대응되는 데이터를 저장하고 싶다

  • multiset

  • 중복 데이터를 허용

  • insert, erase, find 모두 O(logN)

  • 최악의 경우 O(logN)

  • multimap

    • 중복 키를 허용
    • insert, erase, find 모두 O(logN)
    • 최악의 경우 O(logN)

  • unordered_set, unordered_map

    • 속도가 중요해서 최적화가 필요한 경우
    • insert, erase, find 모두 O(1)
    • 최악의 경우 O(N)
    • 해시함수와 상자 개수를 잘 설정해야 한다