[C++] Standard Template Library - STL

C++ 템플릿 라이브러리(STL)라고 하면 보통 다음 세 개의 라이브러리를 의미함

• 임의 타입의 객체를 보관할 수 있는 컨테이너 (container)
• 컨테이너에 보관된 원소에 접근할 수 있는 반복자 (iterator)
• 반복자들을 가지고 일련의 작업을 수행하는 알고리즘 (algorithm)

 

시퀀스 컨테이너

시퀀스 컨테이너 (sequence container) : 배열 처럼 객체들을 순차적으로 보관
연관 컨테이너 (associative container) : 키를 바탕으로 대응되는 값을 찾아줌

vector

• 가변 길이의 배열이라고 볼 수 있음
• 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있음
• 따라서 임의의 위치에 있는 원소에 매우 빠르게 접근할 수 있음

#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> vec;
  vec.push_back(10);  // 맨 뒤에 10 추가
  vec.push_back(20);  // 맨 뒤에 20 추가
  vec.push_back(30);  // 맨 뒤에 30 추가
  vec.push_back(40);  // 맨 뒤에 40 추가

  for (int i = 0; i < vec.size(); i++) {
    cout << "vec 의 " << i + 1 << " 번째 원소 : " << vec[i] << endl;
  }
}

시간 복잡도
- 임의의 위치 원소 접근 ([], at) : O(1)
- 맨 뒤에 원소 추가 및 제거 (push_back/pop_back) : amortized O(1) ( 평균적으로 O(1) 이지만 최악의 경우 O(n) )
- 임의의 위치 원소 추가 및 제거 (insert, erase) : O(n)

 

list

• 양방향 연결 구조를 가진 자료형
• 임의의 위치에 있는 원소에 바로 접근할 수 없음. O(n)
• 임의의 위치에 원소를 추가하거나 제거하는 작업을 O(1)로 매우 빠르게 수행 가능

#include <iostream>
#include <list>
using namespace std;

template <typename T>
void print_list(list<T>& lst) {
    cout << "[ ";
    // 전체 리스트를 출력하기 (이 역시 범위 기반 for 문을 쓸 수 있습니다)
    for (const auto& elem : lst) {
        cout << elem << " ";
    }
    cout << "]" << "\n";
}
int main() {
    list<int> lst;

    lst.push_back(10);
    lst.push_back(20);
    lst.push_back(30);
    lst.push_back(40);

    cout << "리스트의 초기 상태 " << "\n";
    print_list(lst);

    for (list<int>::iterator itr = lst.begin(); itr != lst.end(); ++itr) {
        if (*itr == 20) {
            lst.insert(itr, 50);
        }
    }

    cout << "값이 20 인 원소 앞에 50 을 추가 " << "\n";
    print_list(lst);

    for (list<int>::iterator itr = lst.begin(); itr != lst.end(); ++itr) {
        if (*itr == 30) {
            lst.erase(itr);
            break;
        }
    }

    cout << "값이 30 인 원소를 제거" << "\n";
    print_list(lst);
}

반복자는 오직 한 칸 씩 밖에 움직일 수 없음. itr++ 은 가능하지만, itr+5는 불가능! 
메모리 상에 원소들이 연속적으로 존재하지 않을 수 있기 때문에!

리스트는 벡터와 다르게, 원소를 지워도 각 원소들의 주소값들은 바뀌지 않기 때문에 반복자가 무효화 되지 않음

 

deque

•  벡터와 비슷하게 O(1)로 임의의 위치의 원소에 접근 가능
•  맨 앞과 뒤에 원소를 추가/제거 하는 작업도 O(1) 
• 임의의 위치에 있는 원소를 제거/추가 하는 작업은 벡터와 마찬가지로O(n)
• 실행 속도를 위해 메모리를 (많이) 희생하는 컨테이너

#include <deque>
#include <iostream>
using namespace std;

template <typename T>
void print_deque(deque<T>& dq) {
    // 전체 덱을 출력하기
    cout << "[ ";
    for (const auto& elem : dq) {
        cout << elem << " ";
    }
    cout << " ] " << "\n";
}
int main() {
    deque<int> dq;
    dq.push_back(10);
    dq.push_back(20);
    dq.push_front(30);
    dq.push_front(40);

    cout << "초기 dq 상태" << "\n";
    print_deque(dq);

    cout << "맨 앞의 원소 제거" << "\n";
    dq.pop_front();
    print_deque(dq);
}

 

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

 

iterator

• 컨테이너에 원소에 접근할 수 있는 포인터와 같은 객체
• vector 의 경우 반복자를 얻기 위해서는 begin() 함수와 end() 함수를 사용
• * 연산자를 이용해서 itr 이 가리키는 원소를 볼 수 있음 (itr 이 가리키는 원소의 레퍼런스를 리턴)

vec.end() 가 마지막 원소를 가리킨다면 비어있는 벡터를 표현할 수 없음

// 전체 벡터 출력하기
for (vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
    cout << *itr << "\n";
}

std::vector<int>::iterator itr = vec.begin() + 2;
std::cout << "3 번째 원소 :: " << *itr << std::endl;

// 범위 기반 for 문
for (int elem : vec) {
  cout << elem << "\n";
}

 

연관 컨테이너

시퀀스 컨테이너와는 다르게 key-value 구조를 가짐

set

• 순서가 중요하지 않고, 원소의 중복을 허용하지 않음
• 원소가 어디에 있는지가 아니라, 원소가 '있냐/없냐' 만이 중요한 정보  * find 함수 존재
• 원소를 추가하거나 지우는 작업 : O(logN)  * 내부적으로 순서 유지 = Red-Black Tree 구조로 구현 (binary search tree + 균형 유지)

#include <iostream>
#include <set>
using namespace std;

template <typename T>

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

int main() {
  set<int> s;
  s.insert(10);
  s.insert(50);
  s.insert(20);
  s.insert(40);
  s.insert(30);

  cout << "순서대로 정렬되서 나온다" << "\n";
  print_set(s);

  cout << "20 이 s 의 원소인가요? ";
  auto itr = s.find(20);
  if (itr != s.end()) cout << "Yes" << "\n";
  else  cout << "No" << "\n";

  cout << "25 가 s 의 원소인가요? ";
  itr = s.find(25);
  if (itr != s.end()) cout << "Yes" << "\n";
  else  cout << "No" << "\n";
}

직접 만든 클래스 객체를 set에 넣는 경우
클래스 내에서 bool operator<(const MyType& t) const { .. } 비교 연산자를 정의해준다!!

 

multiset

 

map

 

multimap

 

unordered_set

 

unordered_map

 

알고리즘(Algorithm)