C++ 스터디. standard template library

c++ STL(표준 템플릿 라이브러리)는 Alexander Stepanov가 c++ 프로그래밍을 위해 고안한 라이브러리로, c++ standard library에 큰 영향을 미쳤다.

https://en.wikipedia.org/wiki/Standard_Template_Library

 

STL의 종류

• container: https://en.cppreference.com/w/cpp/container
  • sequence container(순차적 컨테이너)
    • vector, list, deque, arrays, forward_list
  • container adaptor
    • 기존의 컨테이너를 새로운 인터페이스에 맞게 조정하는 역할
    • queue(deque 기반), priority_queue(vector기반), stack(리스트 기반)
  • associative container
    • 키-값 쌍의 형태로 데이터 저장. 키-값 사이에 관계가 있음 → 연관(associative)이라고 표현
    • rb트리로 구현
    • 정렬된 자료구조. 탐색에 O(logN)
    • set, multiset, map, multimap
  • unordered associative container
    • 컨테이너 내부 요소들의 순서가 정해지지 않는 자료구조 → unordered라고 표현
    • 해시함수를 사용하여 데이터를 저장 → 검색속도 O(1)
    • unordered_set, unordered_multiset, unordered_map, unordered_multimap
  • 사용법

#include <vector> // vector STL
using namespace std;
int main() {
	vector<int> vec;
}

 

• 분류기준 그림

• algorithm: https://en.cppreference.com/w/cpp/algorithm
  • 정렬, 검색, 변형 등의 다양한 알고리즘 제공
  • 다양한 컨테이너에 적용 가능
  • 사용법

  #include <vector>
  #include <algorithm>
  using namespace std;
  int main() {
  	vector<int> items = {4, 2, 1, 3, 2};
  	sort(items.begin(), items.end()); // items = {1, 2, 2, 3, 4}
  }
  

• functor(function object): https://www.geeksforgeeks.org/functors-in-cpp/
  • 함수처럼 동작하는 객체
  • 람다표현식을 써도 똑같이 작동하지만 c++11 이전 버전에서는 람다 못씀. 대체제로 사용
  • stl 알고리즘의 인자에 넣을 수 있음.(sort함수에 정렬규칙 추가할 때 등)
  • 사용법

  // 1. functor 사용
  #include <bits/stdc++.h>
  using namespace std;
  
  // A Functor
  class increment
  {
  private:
  	int num;
  public:
  	increment(int n) : num(n) { }
  
  	// This operator overloading enables calling
  	// operator function () on objects of increment
  	int operator () (int arr_num) const {
  		return num + arr_num;
  	}
  };
  
  int main()
  {
  	int arr[] = {1, 2, 3, 4, 5};
  	int n = sizeof(arr)/sizeof(arr[0]);
  	int to_add = 5;
  
  	transform(arr, arr+n, arr, increment(to_add));
  
  	for (int i=0; i<n; i++)
  		cout << arr[i] << " ";
  }
  
  ////////////////////////////////////////////////////////////////////////
  
  // 2. functor 대신 람다 표현식 사용
  #include <iostream>
  #include <algorithm>
  
  int main()
  {
      int arr[] = {1, 2, 3, 4, 5};
      int n = sizeof(arr) / sizeof(arr[0]);
      int to_add = 5;
  
      // 람다 표현식으로 변환
      auto increment_lambda = [to_add](int arr_num) {
          return to_add + arr_num;
      };
  
      // transform 함수에 람다 표현식 전달
      std::transform(arr, arr + n, arr, increment_lambda);
  
      for (int i = 0; i < n; i++)
          std::cout << arr[i] << " ";
  
      return 0;
  }
  

• iterator: https://en.cppreference.com/w/cpp/iterator
  • 컨테이너의 원소에 접근하고 순회하는 인터페이스 제공하는 객체
  • 포인터와 유사한 동작
  • 컨테이너 내부 구조에 종속X, 일관된 방식으로 데이터에 접근 가능
  • 사용법

#include <vector> // vector STL
using namespace std;
int main() {
	vector<int> vec = {1, 2, 3};
	auto it = vec.begin();
	std::advance(it, 5);
	cout << *it;
}

int main() {
    vector<int> vec = {1, 2, 3};
    auto it = vec.begin();
    it += 2;             // advance 안써도됨
    cout << *it << endl; // 3 된다
}

 

템플릿을 통한 STL 구현의 이점

• STL은 template을 사용해서 제네릭 프로그래밍을 지원함.
  • 여러 데이터 타입에 대해 동일한 알고리즘, 데이터 구조 적용시킬 수 있게됨.(템플릿의 장점)
    • STL algorithm이 컨테이너에 독립적일 수 있게 되었다.
      • algorithm은 iterator를 통해 컨테이너의 원소에 접근하는데, iterator는 컨테이터의 종류에 상관없이 동일한 인터페이스를 제공하기 때문
        • 예) x.begin(), x.end()
• template은 컴파일타임 다형성을 지원하기 때문에 런타임 다형성보다 실행시 성능이 좋다.
  • 이에 따라, 컴파일타임이 길어질 수 있다.