내일배움캠프 15일차 - C++ 문법 : STL

STL (Standard Template Library)

C++ 표준 라이브러리의 일부로, 컨테이너, 알고리즘, 반복자 등의 템플릿 기반 요소를 포함한다.

이것을 활용하면 다양한 자료구조와 알고리즘을 직접 구현하지 않고도 사용할 수 있다.

---

컨테이너

데이터를 담는 자료구조를 말한다.
데이터를 담는 방식(또는 제공하는 메서드)에 따라 여러가지 컨테이너를 제공한다.

1) 모든 컨테이너는 템플릿으로 구현되어 있어 다양한 타입의 데이터를 저장할 수 있다.

2) 모든 컨테이너는 메모리 관리를 내부적으로 하므로 메모리 해제를 직접 고려하지 않아도 된다.

3) 대부분 컨테이너는 반복자를 제공한다. 반복자를 사용하여 컨테이너를 순회할 수 있다.

vector

벡터는 배열을 닮은 컨테이너이다.

1) 배열의 크기가 유동적으로 조절되며 임의접근이 가능하다.

2) vector의 삽입/ 삭제는 맨뒤에 하는 것이 좋다. (작업한 칸 뒤로 칸들이 밀리거나 당겨지는데 O(n)만큼 시간이 걸림)

map

특정 키를 활용하여 값을 저장하고 검색하는 컨테이너이다.

1) 키-값 쌍은 pair<<const Key, Value> 형태로 저장된다.

2) 키 값을 기준으로 내부 데이터가 자동으로 오름차순 정렬된다.

3) 중복된 키 값을 허용하지 않는다.

4) 삽입 시 insert()나 []를 사용해 아래의 형태로 작성할 수 있다.

 - myMap.insert(make_pair(key, value));

 - myMap.insert({key,value});

 - myMap[key] = value;

5) 맵을 for문으로 순회할 시 pair값으로 받는다. pair는 '.first', '.second'로 키와 값을 참조한다.

key기준 오름차순으로 자동정렬되어 출력된다.

6) find()를 사용해 존재하는 특정 키를 iterator(반복자)형태로 반환한다. 키가 존재하지 않으면 map.end()를 반환한다.

알고리즘

#include <algorithm>

STL은 다양한 컨테이너와 독립적으로 동작하는 범용 알고리즘을 제공한다.

특정 원소 값을 찾거나, 정렬을 하는 등의 알고리즘 작업을 한 줄 내로 사용할 수 있고, 반복자를 사용하여 STL 컨테이너들에게 공통적으로 적용할 수 있다는 장점이 있다.

※ 반복자(Iterator): 컨테이너의 요소를 추상화 하여 일관된 방식으로 접근할 수 있도록 도와주는 기능.

sort

sort(arr, arr + size, comp);

sort(vec.begin(), vec.end(), comp);

컨테이너 내부의 데이터를 정렬하는 함수이다.

1) 일반적으로 기본 자료형(int, double 등)에 대해 오름차순으로 정렬된다.

2) 사용자 정렬 함수 bool comp(a, b) 를 정의하여 인자로 받으면 return값에 따라 순차적으로 정렬된다.

 - 사용자 정렬 함수에서 첫 번째 인자 a는 앞에 있는 원소를 의미한다.

 - return값이 true이면 a와 b의 순서는 유지된다.

 - return값이 false면 a와 b의 순서를 바꾼다.

find

find(first, last, value)

컨테이너 내부에서 특정 원소를 찾아 해당 원소의 반복자를 반환하는 함수.

 - first부터 last-1까지 탐색하여 원소를 찾으면 해당 원소를 가리키는 반복자를 가리킨다.

 - 원소를 찾지 못하면 last를 가리키는 반복자를 반환한다.

vector에서 사용하는 find

배열에서 사용하는 find

반복자(Iterator)

반복자는 컨테이너의 요소에 대한 일관된 접근 방법을 제공하는 변수이다.

알고리즘이 특정 컨테이너의 내부 구조에 상관없이 똑같이 동작할 수 있도록 돕는다.

순방향 반복자

 : 앞에서부터 뒤로 순차적으로 순회하는 반복자

 - begin(): 컨테이너의 첫 번째 원소를 가리키는 반복자

 - end(): 컨테이너의 마지막 원소 다음을 가리키는 반복자

※ end()는 컨테이너의 마지막 원소 다음인 '아무것도 아닌' 것을 반환하므로 주로 '모든 원소를 순회했다' 혹은 '알고리즘 탐색 실패'를 표현할 수 있다.

역방향 반복자

 : 마지막 원소부터 첫번째 원소까지 역순으로 순회하는 반복자

 - rbegin(): 컨테이너의 마지막 원소를 가리키는 역방향 반복자

 - rend(): 컨테이너의 첫 번째 원소 이전을 가리키는 역방향 반복자

※ rend()는 첫 번째 원소가 아닌 첫 번째 원소 이전을 반환하므로 end()와 비슷한 역할을 한다.