[C++] STL

 

 

 

Standard Template Library. C++에 이미 정의돼있는 라이브러리를 의미한다.

 

STL에는 데이터를 저장하는 객체인 Container / 여러 가지 편리한 메서드를 제공하는 Algorithm과 Functions / Container의 객체를 가리키는 Iterator 로 총 4가지 종류가 있다. 이 중 Container에 대해 살펴보자.

 

 

 

1. Array

 

int arr[10]; 에서 사용하는 C-style 배열과는 다르다.

 

 

 

 

 

왼쪽과 같이 Random Access 방식으로 요소에 접근 할 때는 오류를 뱉지 않지만, 오른쪽과 같이 array STL을 사용해서 요소에 접근 시 오류를 뱉는다.

 

런타임 시간에 invalid index를 체크해준다.

 

 

 

2. vector

 

 

vector 컨테이너 내부 요소들은 continuous memory space를 유지한다.

따라서 Random Access가 가능해 배열과 array처럼 vector[1] 등으로 요소에 접근 할 수 있다.

 

데이터를 넣을 때는 push_back 함수를 사용한다.

 

공간이 부족하면 더 큰 공간을 할당받고 이전 메모리들을 새로 할당받은 공간에 복사한다. (Overhead가 발생한다)

 

새로 이사간다고 생각하면 된다. 이전 공간은 free되고 vector의 begin부분은 새로 이사한 메모리 공간의 시작 부분으로 설정된다.

 

따라서 이사를 자주 가야 하는 상황에서는 쓰지 않는게 좋다. 차라리 적당한 크기의 array를 사용하는 편이 합리적인 경우가 있다.

 

각 Container의 특징을 바탕으로 상황에 적합한 Container를 사용하자.

 

 

 

3. list

 

 

위의 두 Container들과 다르게 memory space를 continuous하게 사용하지 않는다.

따라서 [ ] 연산자를 오버라이드하지 못해  Random Access도 불가능하다.

 

Linked List 자료구조를 생각하면 편하다.

 

 

 

 

 

가용 공간들을 Linked List 방식으로 관리한다. (malloc lab을 explicit방식으로 구현할 때와 유사하다..)

next와 prev 포인터로 다음 값과 이전 값으로 접근 할 수 있다.

 

push_back과 push_front를 사용해 데이터를 넣을 수 있다.

 

begin() 함수로 첫 원소에 접근 할 수 있고, end() 원소로 마지막 + 1 원소에 접근 할 수 있지만, Random Access가 불가능해 begin() + a 방식으로는 요소에 접근할 수 없다.

 

n번째 요소의 값이 궁금하면 begin에서 next를 n번 하거나

next(begin(), n) 으로 next함수에 인자를 주면 된다.

 

 

 

4. deque

 

 

double ended queue의 약자로 vector와 list의 특성을 모두 가지는 Container이다.

 

Chunk 단위로 데이터를 다루고, Chunk끼리는 list의 특성을 가지고 Chunk 내부에서는 vector의 특성을 가진다.

 

Random Access는 가능하지만, begin() + n 방식으로는 요소에 접근할 수 없다.

push_back / push_front / pop_back / pop_front 함수로 데이터를 다룬다.

 

 

 

 

위의 상황에서 pop_front 함수를 실행하면 chunk0은 사라지고 begin은 2 3 4 chunk의 시작 부분으로 위치하게 된다.

각각의 chunk의 크기가 같아야 Random Access를 사용 할 수 있음에 주의하자.

 

크기가 계속 늘어나는 경우에도 vector처럼 이사가지 않는다.

 

 

 

5. Set

 

 

Set Container를 살펴보기 전에 functor 개념을 살펴보자.

 

언어마다 functor 개념은 다르다. 일단 C++ 에서의 functor에 대해 살펴보자.

 

functor는 function call opeator인 () 를 오버라이드 한 객체이다.

functor를 function value 처럼 사용한다.

 

그 자체로 객체이기 때문에 멤버 변수를 가질 수 있다.

 

 

 

IntSub과 IntAdd는 functor이다.

 

 

C++에서 Set Container는 원소들을 중복 없이, 특정한 순서로 저장한다.

 

 

 

 

set 을 정의할 때 자료형과 functor를 입력한다.

 

새로운 원소가 들어오면 맨 처음 원소부터 시작해서 쭉 비교하는 작업을 수행한다.

 

비교 시 functor가 사용되고, 위의 예시에서는 functor의 반환 값이 0인 경우 저장하지 않는다. (사실 반환값이 bool인데 int로 잘못 적었다)

 

Print(s) 함수의 결과는 2 1 이다.

 

 

 

6. Map

 

 

Map Container는 데이터를 key - value 쌍으로 묶어서 저장한다.

key 값은 중복을 허용하지 않고, value 값은 상관없다.

 

 

 

 

key 값이 중복인지 확인하고 특정 방식으로 정렬되어야 하기 때문에 역시 functor가 사용된다.

 

functor는 어떤 순서로 정렬할지와 중복을 어떻게 확인하는지 정의한다!

 

 

 

https://www.geeksforgeeks.org/the-c-standard-template-library-stl/?ref=lbp

 

 

플로우차트를 참고해 Container를 선택하자.