C++ 표준 템플릿 라이브러리 (Standard Template Library - STL)
보통 C++ 템플릿 라이브러리(STL)을 일컫는다면 아래 3개의 라이브러리 의미
- 임의 타입의 객체를 보관할 수 있는 컨테이너 (container)
= 편지를 보관하는 각각의 편지함이 '컨테이너' - 컨테이너에 보관된 원소에 접근할 수 있는 반복자 (iterator)
= 편지를 보고 원하는 편지함을 찾는 일을 '반복자'가 수행 - 반복자들을 가지고 일련의 작업을 수행하는 알고리즘 (algorithm)
= 편지함에 날짜 순서로 정렬하여 넣는 일은 '알고리즘'이 수행
C++ STL 컨테이너
C++ STL 컨테이너는 크게 두 가지 종류가 있음.
- 시퀀스 컨테이너 (sequence container)
- 배열처럼 객체들을 순차적으로 보관
- vector, list, deque - 연관 컨테이너 (associative container)
- 키를 바탕으로 대응되는 값을 찾아줌
vector ?
- 가변길이 배열
- 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있고, 따라서 임의의 위치에 있는 원소에 매우 빠르게 접근할 수 있음.
- 임의의 위치에 있는 원소에 접근을 O(1) 로 수행할 수 있음
- 단, 맨 뒤에 원소를 추가하는 작업은 amortized O(1).
- 할당된 공간을 다 채웠을 때는 새로운 큰 공간을 다시 할당하고 기존 원소를 복사해야하기 때문에 O(n)으로 수행하지만, 대부분 O(1)으로 수행되기 때문에 amortized O(1) 이라고 함 - 임의의 위치에 원소를 추가하거나 제거하는 것은 O(n)
[], at함수: vector의 임의의 원소에 접근push_back, pop_back 함수: 맨 뒤에 원소를 추가하거나 제거size: 벡터의 크기 리턴size_type: 리턴하는 값의 타입
반복자 (iterator)
반복자는 컨테이너에 iterator 멤버 타입으로 정의되어 있음.
- ex ) vector의 반복자 타입은
std::vector<>::iterator멤버 타입으로 정의
vector의 경우, 반복자를 얻기 위해서begin() 함수와end() 함수를 사용
- begin() : vector의 첫번째 원소를 가리키는 반복자 리턴
- end() : vector의 마지막 원소 한 칸 뒤를 가리키는 반복자 리턴 (
begin() == end()일 경우, 비어있는 벡터를 표현할 수 있기 때문에)
// 반복자 사용 예시
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
vec.push_back(40);
// 전체 벡터를 출력하기
// itr 은 실제 포인터가 아니고 * 연산자를 오버로딩해서 마치 포인터 처럼 동작하게 만든 것
// * 연산자는 itr 이 가리키는 원소의 레퍼런스를 리턴
for (std::vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
std::cout << *itr << std::endl;
}
// int arr[4] = {10, 20, 30, 40}
// *(arr + 2) == arr[2] == 30;
// *(itr + 2) == vec[2] == 30;
std::vector<int>::iterator itr = vec.begin() + 2;
std::cout << "3 번째 원소 :: " << *itr << std::endl;
}템플릿 버전의 경우, 아래와 같이 앞에 typename 을 추가해줘야함 그 이유는, iterator 가 std:vector<T>의 의존 타입이기 때문
for (typename std::vector<T>::iterator itr = vec.begin(); itr != vec.end();
++itr) {반복자를 사용하면 insert와 erase함수 사용 가능 - 모두 O(n)
// 기존 벡터 = 10 20 30 40
// vec[2] 앞에 15 추가
vec.insert(vec.begin() + 2, 15); // 10 20 15 30 40
// vec[3] 제거
vec.erase(vec.begin() + 3);
print_vector(vec); // 10 20 15 40반복자 사용 시 주의점
std::vector<int>::iterator itr = vec.begin();
std::vector<int>::iterator end_itr = vec.end();
for (; itr != end_itr; ++itr) {
if (*itr == 20) {
vec.erase(itr);
}
}위의 코드를 실행하면 error 발생!
컨테이너에 원소를 추가하거나 제거하면, 기존에 사용했던 모든 반복자는 사용할 수 없기 때문.
즉, vec.erase(itr)를 수행하게되면, itr와 end_itr는 무효화되기 때문에 itr != end_itr이 영원히 성립되며 무한루프에 빠지게 됨
해결 방법
for (std::vector<int>::size_type i = 0; i != vec.size(); i++) {
if (vec[i] == 20) {
vec.erase(vec.begin() + i);
i--;
}
}따라서 위와 같이 반복자를 사용하지 않고, erase함수에만 반복자를 바로 만들어서 전달
(사실은 비효율적인 코드 ! 20삭제하고 다시 처음으로 돌아가서 탐색하기 때문)
역반복자 (reverse iterator)
벡터 뒤에서 부터 앞으로 거꾸로 가는 특징
#include <iostream>
#include <vector>
template <typename T>
void print_vector(std::vector<T>& vec) {
// 전체 벡터를 출력하기
for (typename std::vector<T>::iterator itr = vec.begin(); itr != vec.end();
++itr) {
std::cout << *itr << std::endl;
}
}
int main() {
std::vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
vec.push_back(40);
std::cout << "초기 vec 상태" << std::endl;
print_vector(vec);
std::cout << "역으로 vec 출력하기!" << std::endl;
// itr 은 vec[2] 를 가리킨다.
std::vector<int>::reverse_iterator r_iter = vec.rbegin();
for (; r_iter != vec.rend(); r_iter++) {
std::cout << *r_iter << std::endl;
}
}
rend(): 맨 앞 원소의 바로 앞을 가리킴rbegin(): 맨 뒤 원소를 가리킴
범위 기반 for 문 (range based for loop)
컨테이너의 원소를 for 문으로 접근하는 패턴
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
// range-based for 문
// elem에 vec의 원소들이 매 loop마다 복사되어 들어감
// elem = vec[i];
for (int elem : vec) {
std::cout << "원소 : " << elem << std::endl;
}
return 0;
}리스트 (list)
- 양뱡향 연결 구조를 가진 자료형
- 임의의 위치에 있는 원소에 접근을 바로 할 수 없음
- list 컨테이너 자체에서는
시작원소와마지막원소의 위치만 기억하기 때문에, 임의의 위치에 접근하기 위해서는 하나씩 링크를 따라가야 함. 따라서,[]이나at함수가 아예 없음. - 임의의 위치에 원소 추가하는 작업 O(1)
- 원소를
erase해도 반복자가 유효함 ! 각 원소의 주소값은 바뀌지 않기 때문
#include <iostream>
#include <list>
int main() {
std::list<int> lst;
lst.push_back(10);
lst.push_back(20);
lst.push_back(30);
lst.push_back(40);
for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); ++itr) {
std::cout << *itr << std::endl;
}
}list는 vector과 다르게, itr + 5와 같은 연산 불가능! = 임의 위치에 있는 원소 가리킬 수 X
itr++, ++itr, itr-- 와 같은 연산만 수행할 수 있음. = 반복자는 오직 한 칸씩만 움직일 수 있음
덱 (deque - double ended queue)
- 임의의 위치의 원소에 접근 가능
- 맨 뒤에 원소를 추가/제거하는 작업 : O(1)
- 맨 앞에 원소를 추가/제거하는 작업 : O(1)
- 임의의 위치에 있는 원소를 제거/추가하는 작업 : O(n)
- 벡터와 다르게 덱은 원소들이 실제 메모리 상에서 연속적으로 존재하지 X = 원소가 어디에 저장되어 있는지에 대한 정보를 보관하기 위한 추가적인 메모리 필요
그래서 어떤 컨테이너를 사용?
- 일반적으로 벡터 사용
- 만약에 맨 끝이 아닌 중간에 원소들을 추가하거나 제거하는 일을 많이 하고, 원소들을 순차적으로만 접근 한다면 리스트를 사용
- 만약에 맨 처음과 끝 모두에 원소들을 추가하는 작업을 많이하면 덱을 사용
-