4. STL

STL은 Standard Template Library 으로서 CPP에서 제공하는 컨테이너 라이브러리이다.

생각보다 기능이 많으므로, 간단하게 알아보고 필요할떄 자세하게 찾아보자.

0. 반복자, iterator

컨테이너들을 순서대로 접근하고 싶을 때 사용한다. 일종의 포인터.

참고로 값 변경도 가능한데, 막고싶으면 const_iterator을 사용하면 된다.

list<int> ls = {10, 20, 30};


list<int>::iterator iter; // 이렇게 직접 iter 객체를 생성해도 된다.
ls.begin(); ls.end(); // 또는 이렇게 해당 객체에서 iter 포인터를 얻어와도 됨.
/*
	참고로 begin은 0번 인덱스, end()는 마지막 null 값을 가르키고 있다고 이해하면 된다.
	begin 이상 end 미만. 마지막값은 포함하지 않는다.
*/

list<int>::const_iterator citer; // 값 변경을 원하지 않는다면 const_iterator 사용

 

iter = ls.begin();
citer = ls.end();

*iter = 100; // 이렇게 포인터로 값 변경이 가능하다.
// *citer = 300; cosnt는 값 변경 불가능.

 

 

 

1. Container

컨테이너는 같은 타입의 여러 객체를 저장하는 곳, 쉽게 말해 자료형을 쓰기 편하게 확장해준거라고 보면 된다.

STL에서 컨테이너는 크게 3종류로 나뉘는데, 이는 다음과 같다.

종류	설명	예시
시퀸스(iterable)	데이터를 순서대로 저장	vector, deque, list, forward_list
연관(set, map)	데이터를 일정 규칙에 따라 저장	set, map, multiset, multimap
컨테이너 어댑터	기능을 제한하여 원하는 구조로 사용	stack, queue, priority_queue

 

2. 시퀸스 컨테이너(sequence)

2-1 vector

막써도 되는 만능 자료형. 크기가 자동으로 늘어나는 동적 배열. stack과 비슷하게 입력 값을 뒤에 추가하기 좋다.

연속된 메모리 공간을 사용해서 인덱스접근이 빠르지만 중간삽입/ 이미 할당된 메모리 공간을 확장할려면 저장된 값 전체를 다른 공간으로 옮겨야해야 해서 시간이 많이걸린다.

vector<자료형> 객체이름();

vector<int> v // 빈 컨테이너
vector<int> v = { 10, 20, 30, 40 } // cpp 멤버 초기화 형식으로 생성도 가능.
//참고로 v.assign(인수) 으로 하면 생성자와 똑같은 기능임.

vector<int> v(n) // 기본값으로 초기화된 n개
vector<int> v(n,x) // 값 x로 초기화
vector<int> v(다른 벡터) // 벡터 복사(값 복사)
vector<int> v(v.begin() v.end()) // 이런 식으로 초기화/생성도 가능
v.swap(v2) // 벡터의 값 서로 바꾸기

v.size() // 할당된 원소의 갯수
v.capacity() // 현재 예약된(사용중인) 메모리의 갯수
v.resize(n, x) // 해당 벡터의 크기를 n으로 변경함. x는 초기화값. 생략가능

v.at(i); // v[i]와 같음. i번째 원소 값. 참고로 .at()을 사용해야 예외처리가 작동한다. 
v.back() // 마지막 원소 값
v.front() // 첫번쨰 원소 값

p = v.begin() // 첫번째 원소를 가르키는 iter
p = v.end() // 마지막 원소를 가르키는 iter. 참고로 [b,e)임.
p = v.rbegin() // begin과 같지만 거꾸로 반복함. 리버스
p = v.rend() // 마찬가지

q = v.erase(p) // p가 가르키는 원소를 삭제하고 다음 값 포인터를 반환함. 
q = v.erase(begin, end) // 포인터로 삭제하는 방법. 이 역시 [b,e)임.
q = v.insert(p,x) // 포인터 p에 값 x 삽입. 삽입한 위치 포인터(값:x) 반환.
v.insert(p,n,x) // 포인터 p에 x를 n개 삽입.

v.pop_back() // pop. 마지막 원소 제거
v.push_back() // push. 마지막 원소에 추가


v.clear() // 모든 원소 제거
v.empty() // 비었는지 확인, capacity와는 상관없음.

 

비교 연산자
v1 == v2	v1과 v2의 모든 원소가 같은가? (bool)
v1 != v2	v1과 v2의 모든 원소 중 하나라도 다른 원소가 있는가?
v1 < v2	문자열 비교처럼 v2가 v1보다 큰가?
v1 > v2	문자열 비교처럼 v1이 v2보다 큰가?
v [i]	v의 i번째 원소 참조(값얻기 or 값 변경하기)

 

2-2 deque (double-ended queue)

입력값을 앞, 뒤로 추가 삽입이 많이 필요한 경우 사용한다.

벡터와 비슷하지만 내부 구조가 벡터처럼 연속된 메모리공간을 쓰지않고, 일정 단위(chunk)별로 저장을 해서 추가 메모리 할당량이 많은 경우 확장에 유리하다. 다만 벡터와 마찬가지로 앞,뒤가 아닌 중간삽입 수행시 속도가 매우 느리다.

// vector와 비슷한데, 아래와 같은 메서드를 제공해준다.
deque<int> dq = {20, 30};
dq.push_back(30);
dq.push_front(30);

dq.pop_back();
dq.pop_front();

 

2-3 List

인덱스접근(임의 접근)이 필요없고 삽입 삭제가 많을 때 유용한 자료형이다. 내부는 이중 연결리스트로 구현되어있다.

값 접근 속도가 deque, vector보다 느리지만 아래와 같이 중간 삽입/삭제가 많은 작업을 많이 할 때에는 리스트가 훨씬 최적화가 잘되어있어 빠르다.

함수	설명
swap()	두 요소의 위치를 바꿈
reverse()	리스트 전체를 역순으로 바꿈
sort()	리스트 전체를 정렬함.
unique()	같은 값이 붙어있는경우, 하나로 만듬 ( 1, 3, 3, 3, 1 ->1, 3, 1)
merge()	두 리스트를 합병 정렬함.
splice(포인터, 리스트)	두 리스트를 연결하거나 한쪽에 붙임.
.remove(값)	해당 값을 모두 제거한다.
.remove_if(함수)	해당 조건이 참(true)인 모든 원소를 제거한다.

 

2-4 forward_list

순방향 리스트. 리스트에서 메모리를 최적화한 버전으로 무조건 순방향으로만 접근할 수 있다.

기능은 리스트와 큰 차이 없다.

 

3. 연관 컨테이너 (associate)

map이나 set같은 자료형들. 아 참고로 앞에 multi가 붙은 건 키의 중복을 허용한다는 의미다.

3-1 pair

두 객체를 하나의 쌍으로 표현하기 위해 사용한다.

보통 map 같은 곳에 쓸려고 key-set이 한 쌍인 자료형을 위해 만들어진 컨테이너.

참고로 비교 연산자나 sort가 가능하다. (첫번째 인자 기준, 같으면 두번쨰 인자까지 비교)

pair<클래스1,클래스2> p;
p.first // 클래스 1 반환
p.second // 클래스 2 반환

make_pair(x1, x2)// 값 x1, x2를 pair로 만들어서 반환

 

3-2 set

set<객체> 객체이름;
set<int> st;
st.insert(10); // 해당 값 추가
st.erase(10); // 해당 값 삭제 (전부)

 

3-3 map

map<key, value> 객체이름;
map<string, int> mp;

mp.insert(pair<string,int>("키값", 80));
mp["키값"] = 80;

 

4. 컨테이너 어댑터

Stack, Queue, Priority_queue

stack이나 queue 같은 자료형을 직관적으로 사용하기 위해 만든 컨테이너.

해당 자료구조의 비정상적인 접근을 차단해주고 메서드 이름을 깔끔하게 정리했다.

다만 내부구조는 기본 컨테이너들(vector)과 동일하다. 그래서 어댑터라고 부른다.

메서드	설명
.empty()	스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
.size()	스택 요소의 총 개수를 반환함.
.top()	스택의 제일 상단에 있는 (마지막 값)에 대한 참조를 반환함.
.push()	스택의 제일 상단에 요소를 삽입함.
.pop()	스택의 제일 상단에 있는 요소를 삭제함.
.front()	(큐만 해당) 제일 앞의 요소에 대한 참조를 반환함.
.back()	(큐만 해당) 제일 뒤의 요소에 대한 참조를 반환함.

참고로 우선순위 큐 (priority_queue)는 가장 큰 값이 맨 앞으로 오게되는 큐이다. (자동정렬)