[C++] STL에 대해

- C++을 배우면서 단계를 밟다보니 vector 템플릿 클래스에 대해 얼핏 알게 되었다. 이와 더불어 STL에 속하는 컨테이너라는 것을 알게 되어 이를 정리할 필요성을 느껴 이 글을 작성하게 되었다.

 

1. STL

- STL은 무엇일까? Standard Template Library의 약자이다. 그럼 그게 뭔데?

- 표준 템플릿 라이브러리라고도 하며 C++ 표준 라이브러리이다. 컨테이너(자료구조), 반복자, 함수 객체, 알고리즘 등으로 이루어진 라이브러리라고 할 수 있다. 여기서 잠깐, 라이브러리가 무엇일까?

 

★ 라이브러리 : 소프트웨어를 개발할 때, 재사용이 필요한 기능을 언제든지 필요한 곳에 호출하여 쓸 수 있게 클래스나 함수로 모아둔 것을 의미한다. 특정 기능만을 수행할 수 있도록 제작된 것이라고 할 수 있다. 예를 들어 STL, MFC, DirectX와 같은 것들이 있다.

 

- 만약 STL이 없다고 한다면 C++을 사용할 때, 알고리즘이나 자료구조에 해당하는 것들을 일일이 구현해야하며, 그 구현한 것을 템플릿을 사용하지 않고 구현했다면, 한 자료형에만 얽매여 있는 경우로 사용해야 한다.

- 그래서 표준 템플릿 라이브러리는 알고리즘과 자료구조를 제공하는 것과 동시에 그것들이 템플릿으로 구현하여 자료형에 구애받지 않게 사용자 역량에 따라 자유자재로 쓸 수 있도록 한 것이다.

- 현재는 STL을 통해 C++의 사용 영역을 확장시키는 형식으로 발전하고자 하니 STL을 알아두는 것이 좋다.

 

2. STL의 구성요소

- 각각의 구성요소는 무슨 의미를 가지고 있을까?

2.1 컨테이너

- 컨테이너는 객체를 저장하는 객체, 자료구조라고 한다. 클래스 템플릿으로 구현되어 있으며

- 표준 시퀀스 컨테이너(Standard Sequence Container)와 표준 연관 컨테이너(Standard Associative Container)로 구성되어 있다. 이 둘의 차이가 무엇이냐.

 

● 표준 시퀀스 컨테이너(Standard Sequence Container)

- 컨테이너 원소가 자신만의 삽입 위치(순서)를 갖는 컨테이너다. 선형구조를 띠고 있다. vector, list, deque 그리고 C++11에서 제공하는 array가 대표적인 예다.

- 삽입되는 순서에 따라 원소의 위치가 결정되고 바뀌지 않는다.

- 컨테이너의 끝에 데이터를 추가하고 제거하기 위한 push_back()과 pop_back() 멤버함수를 가진다.

 

● 표준 연관 컨테이너(Standard Associative Container)

- 저장 원소가 삽입 순서와 다르게 특정 정렬 기준에 의해 자동 정렬되는 컨테이너다. 비선형 구조를 띠고 있다. set, multiset, map, multimap이 대표적인 예다.

- 삽입 순서와 상관 없이 정렬 기준에 따라 원소의 위치가 결정된다.

 

- 위의 기준과 달리 컨테이너는 하나의 연속된 메모리에 데이터를 저장하는지에 따른 기준으로 두 개로 나뉜다.

 

● 배열 기반 컨테이너

- 데이터 여러 개를 하나의 메모리 단위에 연속해서 저장합니다.

- operator[] 연산자를 이용해 컨테이너 원소에 접근할 수 있다.

- vector, deque

 

● 노드 기반 컨테이너

- 데이터 하나를 하나의 메모리 단위에 저장합니다.

- list, set, multiset, map, multimap

 

- STL에서는 어떤 컨테이너들이 제공될까? 아래에 정리해보겠다. 

● 순차 컨테이너

- 배열(array), 동적 배열(vector), 양방향 큐(deque), 단방향 리스트(forward_list), 양방향 리스트(list)

● 연관 컨테이너

- 정렬된 유일 key 집합(set) + value의 집합(map)

- 정렬된 중복허용 key 집합(multiset) + value의 집합(multimap)

● 비정렬 연관 컨테이너(ordered는 정렬된 이라는 의미로 이해하면 된다고 한다.)

- 유일 key 해시(unordered set) + value의 해시(unordered map)

- 중복허용 key 해시(unordered multiset) + value의 해시(unordered multimap)

● 그 밖에

- 스택(stack), 큐(queue), 우선순위큐(priority_queue)

 

- 외우려고 하기보다는 이런게 있구나로 이해하고 나중에 필요한 게 있다 싶으면 따로 검색해서 공부하자

 

 2-2. 반복자

- 포인터와 비슷한 개념이라고 받아들이는 것이 좋겠다. 컨테이너의 원소를 가리키고, 가리키는 원소에 접근하여 다음 원소를 가리키는 기능을 제공해주는 것이다.

- 반복자는 컨테이너 내부의 데이터를 가리키고 접근할 수 있어야 한다. 이 말은 * 연산자의 역참조가 가능해야한다는 것이다.

- 다음 원소로 이동하고 컨테이너의 모든 원소를 순회할 수 있어야 한다. 포인터연산과 같이 주소값이 증가하고 감소하는 것이 되어야한다는 얘기 같다.

 

- 정렬되지 않고 선형적으로 데이터를 저장하는 컨테이너를 순차열이라고 하는데 이 컨테이너들은 하나의 시작과 하나의 끝을 갖는다. 이런 모든 컨테이너는 자신만의 반복자를 갖는데, 반복자는 순차열의 한 원소만을 가리키면서 연산에 따라 가리키는 주소값이 변경될 것이다.

 

 3-3. 알고리즘

- 정렬, 삭제, 검색, 연산 등을 해결하는 일반화된 방법을 제공하는 함수 템플릿이다. 함수 템플릿! 자료형에 따라 함수 정의를 만들어내는 템플릿이다. 이 말은 문제를 해결하기 위한 방법을 제공하는 함수 템플릿이라는 의미이다.

- 그 알고리즘에는 일곱 가지 범주로 분류할 수 있다는데 정리된 것은 다음과 같다.

 

● 알고리즘 분류

- 원소를 수정하지 않는 알고리즘

- 원소를 수정하는 알고리즘

- 제거 알고리즘

- 변경 알고리즘

- 정렬 알고리즘

- 정렬된 범위 알고리즘

- 수치 알고리즘

 

- 라고 하는데 내게 익숙하게 보이는 알고리즘은 find 알고리즘과, sort 알고리즘 정도 정리하면서 눈에 들어오는 것 같다.

 

4. 함수 객체

- 알고리즘에서 클라이언트의 의도에 따라 정의된 동작을 하려고 할 때, 사용되는 함수 객체, 함수, 함수 포인터라고 한다.

- 말로는 이해하기 어렵지만 예를 드는 것이 좋겠다. 알고리즘은 함수류를 매개변수로 전달받기도 하는데 그런 상황을 예로 들 수 있는 것은 sort라는 정렬 알고리즘에서 매개변수로 오름차순으로 할 것인지, 내림차순으로 할 것인지 전달 받을 수 있다. 이 때, 이 기능을 갖는 함수가 less<T>()와 greater<T>()가 있다는 것이다.

 

5. 어댑터

- 구성 요소의 인터페이스를 변경한다고 한다.

- 직관적이지 않아, 다른 표현을 알아봤다. 기존의 기능을 제한하여 변형된 것을 의미한다고 한다.

- 원래 vector클래스인데 그 기능을 제한하여 stack으로 사용한다거나, deque의 기능을 제한하여 queue로 사용한다거나 이런 방식인 듯하다.

 

6. 할당기

- 할당기는 메모리 할당 정보와 관련된 것을 캡슐화한 구성 요소라고 한다.

- allocator라고 사용하며, 이는 템플릿 클래스이다.

- 모든 컨테이너는 디폴트로 기본 할당기를 사용하고 기본 할당기 말고 따로 컨테이너에게 템플릿 매개변수로 할당기를 전달할 수 있다.

- 사용자가 직접 메모리 할당 방식을 제어할 수 있게 되어 최적화와 연관이 되어있다고 한다.

 

출처 :

https://program-rest-area.tistory.com/98

[C++ STL] STL 구성요소( 컨테이너, 반복자, 알고리즘, 함수객체, 어댑터, 할당기 )

https://blockdmask.tistory.com/67

[C++] STL 이란.

https://boycoding.tistory.com/124

C++ 잡담. STL

https://thebook.io/006842/ch02/01/

C++14 STL 철저 입문: 2.1 | 순차 컨테이너