[C++] 6. C++ STL(Standard Template Library)

본글은 최근에 Pwnable 문제중 C언어, Python뿐만 아니라 C++로 이루어진 문제를 접하는 경우가 많아져서 Python, Java와 다른 C++만의 문법이나 차이점등을 정리하기 위해 작성한 글입니다.
잘못된 부분이 있다면 댓글로 알려주시기 바랍니다.

(예시 코드등은 TCP 스쿨의 자료를 참고했습니다.)
https://www.tcpschool.com/cpp/intro

---

1. STL(Standard Template Library)

C++ 언어는 일반화 프로그래밍이라는 특징을 가지고 있습니다. 이러한 특징은 Java처럼 데이터를 중시하는 객체 지향 프로그래밍 언어와 달리 프로그램의 알고리즘에 중점을 둡니다.

 

STL은 이러한 C++의 일반화 프로그래밍의 한 축으로 자료 구조, 함수, 알고리즘등을 쓰기 쉽게 정형화하여 라이브러리화 해둔것을 말합니다. 라이브러리화를 해두면 필요에 따라 가져와서 쓰거나 만들수 있기 때문에 유용한 방식입니다.

C++에서 STL은 크게 3가지로 구분할 수 있는데 컨테이너, 반복자,알고리즘으로 구분할 수 있습니다.

 

1) 컨테이너(Container)

STL에서 말하는 컨테이너는 같은 타입의 여러 자료를 저장하는 클래스 템플릿들의 집합으로 볼 수 있습니다.

big-O가 최소화 될 수 있도록 자료형을 고라서 컨테이너를 선택해 만들면 성능을 극대화 할 수 있는 장점을 가지고 있습니다.

(big-O는 알고리즘 효율 표기법으로 이 알고리즘이 얼마나 효율적인가를 알 수 있게 표기하는 방법으로 최악의 실행시간을 표기하여 최악의 경우 걸리는 실행 시간을 나타냄)

 

컨테이너는 자료를 저장하는 방식과 관리 방식에 따라 여러 형태로 나뉘는데 크게 3가지로 다음과 같이 구분가능합니다.

컨테이너 종류	설명	컨테이너
시퀀스 컨테이너	데이터를 선형으로 저장하고, 특별한 제약이나 규칙이 없는 일반적인 컨테이너	vector, deque, list, forwad_list
연관 컨테이너	데이터를 일정 규칙에 따라 조직화 하여 저장 관리하는 컨테이너	set, multiset, map, multimap
컨테이너 어댑터	간결함과 명료성을 위해 인터페이스를 제한한 시퀀스나 연관 컨테이너의 변형 구조 단, 반복자를 지원하지 않으므로 STL 알고리즘에서 사용 불가	stack, queue, priority_queue

 

2) 반복자(Iterator)

반복자는 포인터와 비슷한 개념으로 컨테이너의 데이터 위치를 가르키며, 컨테이너의 원소를 순회하는 방법을 추상화한 객체들을 뜻합니다. 반복자를 이용하면 포인터와 비슷하게 컨테이너 내 원소들에 접근할 수 있게 됩니다.

사용되는 원소들은 아래와 같습니다.

• input Iterators : 값들의 시퀀스를 읽는데 사용
• output Iterators : 값들의 시퀀스를 쓰는데 사용
• forward Iterators : 읽고 쓰며 앞으로 움직일때 사용
• bidirectional Iterators : forward Iterators의 특징을 가지고 앞뒤로 움직이기 가능
• random access Iterators : 자유롭게 움직이기 가능

3) 알고리즘(Algorithm)

알고리즘은 정렬, 삭제, 검색, 연산등의 활동을 수행하는 작업을 정의해놓은 템플릿 함수를 말합니다. 이때 STL의 목적은 알고리즘의 효율적인 구현을 제공하는 것이 목적이기에 STL 알고리즘 함수나 STL 컨테이너 멤버함수를 사용하여 구현하고 있습니다.

사용되는 함수는 다음과 같습니다.

• sort : 정렬 함수
• find : 검색 함수
• transform : 변경 함수
• for_each : first부터 last까지 원소들의 각각에 대해서 함수를 실행하는 함수
• generate : 생성하는 함수
• binary_search : 이진탐색으로 검색하는 함수

STL은 템플릿인 만큼 종류가 매우 다양하고 각 STL마다 특징도 다릅니다. 어떤 STL의 경우 검색만 효율적이라거나 데이터 삽입할 때 효율적이거나 하는등 효율적인 부분이 다릅니다. 하지만 이러한 STL은 컨테이너들로부터 독립적이기 때문에 라이브러리의 복잡성을 줄일 수 있었습니다. 또한 템플릿 사용으로 런타임 타형성 보다 효과적인 컴파일 타임 다형성을 제공하기에 잘 쓸 수 만 있다면 시간이 절약되고 간편하게 사용할 수 있는 매우 좋은 라이브러리라고 할 수 있습니다.

(런 타임 다형성 == 응용 프로그램이 동작되는 때 메서드의 호출, 컴파일 타임 다형성 == 기계어 코드로 변환되는 컴파일 때 메서드 호출)

---

Reference

1. https://www.tcpschool.com/cpp/cpp_iterator_intro

2. https://dense.tistory.com/entry/cpp-stl

3. https://ssocoit.tistory.com/24

4. https://velog.io/@nana-moon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%85%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95big-O-notation%EC%9D%B4%EB%9E%80