[C++] STL 정리

STL(Standard Template Library)

: C++의 템플릿을 사용하여 표준으로 정리된 라이브러리

- 반복자 / 컨테이너 / 알고리즘 함수객체 등의 라이브러리로 구성

컨테이너(Container)

: 컨테이너란 기본 자료형과 유저가 정의한 자료형을 담는 일종의 자료구조

1. 시퀀스 컨테이너

일반적인 자료구조와 동일한 형태 (vector / list / string / deque ...)

자료를 입력한 순서대로 저장하기 때문에 저장, 검색, 알고리즘에 불리함

적은 양의 자료나 검색 속도가 중요하지 않은 경우에 사용

2. 연관 컨테이너

일정한 규칙에 따라 자료를 조직화하여 저장 (set / map / multiset / multimap ...)

자료를 정렬하여 저장하기 때문에 검색에 유리

많은 양의 자료나 검색 속도가 중요한 경우에 사용

3. 어댑터 컨테이너

시퀀스 컨테이너를 변형시켜 스택 큐 우선순위 큐 형태로 저장(queue, stack, ...)

자주쓰는 STL 정리

1. vector 

: 동적배열, 임의의 위치에 있는 원소 접근과, 뒤에서 원소를 추가하는 연산은 O(1)을 보장

#include <iostream>
#include <vector>
using namespace std;
int main(){
	//int 자료형을 저장하는 동적배열
	vector<int> vec1;
	//double 자료형을 저장하는 동적배열
	vector<double> vec2;
	//사용자가 정의한 Node 구조체를 저장하는 동적배열
	vector<node> vec3;
	//벡터의 초기 크기를 n으로 설정
	vector<int> vec4(n);
	//벡터의 초기 크기를 n으로 설정하고 1로 초기화
	vector<int> vec5(n, 1);
	//크기가 n*m인 2차원 벡터를 선언하고 0으로 초기화
	vector<vector<int> > vec6(n, vector<int>(m, 0));
	//벡터의 맨 뒤에 원소(5) 추가
	vec1.push_back(5);
	//벡터의 맨 뒤 원소 삭제
	vec1.pop_back();
	//벡터의 크기 출력
	printf("%d\n", vec1.size());
	//벡터의 크기를 n으로 재설정
	vec1.resize(n);
	//벡터의 모든 원소 삭제
	vec1.clear();
	//벡터의 첫 원소의 주소, 마지막 원소의 다음 주소 리턴
	vec1.begin();
	vec1.end();
	//[a, b) 주소 구간에 해당하는 원소 삭제
	vec1.erase(vec1.begin(), vec1.end());//모든 원소 삭제
	//vec7은 vec1의 2번째 원소부터 마지막 원소까지 복사하여 생성
	vector<int> vec7=vector<int>(vec1.begin()+2, vec1.end());
	return 0;
}

2. stack

#include <iostream>
#include <stack>
using namespace std;
int main(){
	//int자료형을 저장하는 스택 생성
	stack<int> st;
	//원소(4) 삽입
	st.push(4);
	//맨 위 원소 팝
	st.pop();
	//맨 위 원소 값 출력
	printf("%d\n", st.top());
	//스택이 비어있다면 1 아니면 0
	printf("%d\n", st.empty());
	//스택에 저장되어 있는 원소의 수 출력
	printf("%d\n", st.size());
	return 0;
}

3. queue

#include <iostream>
#include <queue>
using namespace std;
int main(){
	//int자료형을 저장하는 큐 생성
	queue<int> q;
	//원소(4) 삽입
	q.push(4);
	//맨 위 원소 팝
	q.pop();
	//맨 위 원소 값 출력
	printf("%d\n", q.front());
	//큐가 비어있다면 1 아니면 0
	printf("%d\n", q.empty());
	//큐에 저장되어 있는 원소의 수 출력
	printf("%d\n", q.size());
	return 0;
}

4. deque

: 동적 배열, 임의의 위치에 있는 원소 접근과, 앞과 뒤에서 원소를 추가하는 연산은 O(1)을 보장

#include <iostream>
#include <deque>
using namespace std;
int main(){
	//int 자료형을 저장하는 동적배열 생성
	deque<int> dq;
	//배열 맨 앞에 원소(5) 추가
	dq.push_front(5);
	//배열 맨 뒤에 원소(5) 추가
	dq.push_back(5);
	//배열 맨 앞의 원소 삭제
	dq.pop_front();
	//배열 맨 뒤의 원소 삭제
	dq.pop_back();
	//나머지는 vector와 동일하다.
	return 0;
}

5. set

: 균형잡힌 이진트리, 원소 삽입과 삭제, 탐색 등의 연산은 O(log n)을 보장

#include <iostream>
#include <set>
using namespace std;
int main(){
	//int 자료형을 저장하는 균형잡힌 이진트리 생성
	set<int> s;
	//원소(5) 삽입
	s.insert(5);
	//6값을 가지는 원소를 찾음 있다면 해당 원소의 주소값,  없다면 s.end()리턴
	if(s.find(6)!=s.end())
		printf("존재합니다.\n");
	else
		printf("없습니다.\n");
	//저장된 원소의 수를 리턴
	printf("%d\n", s.size());
	//모든 원소 삭제
	s.clear();
	//해당 주소의 원소 삭제
	//2번째 원소 삭제
	s.erase(++s.begin());
	return 0;
}

6. pair

: 2개의 데이터를 저장할 수 있는 변수, 비교 연산시 1순위 first 2순위 second 로 판별

#include <iostream>
#include <utility>
using namespace std;
int main(){
	//int, int 자료형을 저장하는 변수 선언
	pair<int, int=""> p;
	//(4, 5)를 p에 저장
	p=make_pair(4, 5);
	//c++11부터 가능
	p={4, 5};
	return 0;
}

7. map

딕셔너리 자료구조, 원소 삽입과 삭제, 탐색 등의 연산은 O(log n)을 보장

#include <iostream>
#include <map>
using namespace std;
int main(){
	//int 자료형을 key로 int 자료형을 데이터로 저장하는 딕셔너리 자료구조 생성
	map<int, int=""> m;
	//(4, 5)원소 삽입
	m.insert(make_pair(4, 5));
	//또는
	m[4]=5;
	//key와 연관된 원소를 pair<키 자료형, 데이터 자료형> 형태로 리턴함
	printf("%d\n", m.find(4).second);
	//key와 연관된 원소의 개수를 리턴함
	printf("%d\n", m.count(4));
	//저장된 원소의 수를 리턴함
	printf("%d\n", m.size());
	//모든 원소 삭제
	m.clear();
	//해당 주소의 원소 삭제
	m.erase(++m.begin());
	return 0;
}

8. algorithm

: 여러가지 알고리즘이 들어있는 헤더파일

#include <iostream>
#include <vecto>
#include <algorithm>
using namespace std;

bool cmp(const int a, const int b){
	return a>b;
}

int main(){

	int arr1[100000];
	vector<int> arr2[100000];
	int n=100000;

	//sort
	//첫 원소의 주소와 마지막 원소의 다음 주소를 인자로 넘겨준다.
	sort(arr1, arr1+n);
	sort(arr2.begin(), arr2.end());
	//비교 함수도 만들어서 같이 넘겨줄 수 있다.
	sort(arr1, arr1+n, cmp);

	//stable_sort
	//사용법은 같다.
	stable_sort(arr1, arr1+n);

	//lower_bound
	//첫 원소의 주소와 마지막 원소의 다음 주소와 비교할 원소를 넘겨준다.
	//구간내의 원소들은 정렬되어 있어야한다.
	//리턴 값은 해당 원소의 주소값이다. 없다면 arr1+n을 리턴한다.
	//또는 arr2.end()를 리턴한다.
	int idx=lower_bound(arr1, arr1+n, 42)-arr1;
	printf("%d\n", idx);

	//upper_bound
	//사용법은 같다.
	vector<int>::iterator it=upper_bound(arr2.begin(), arr2.end(), 54);
	if(it!=arr2.end())
		printf("%d\n", *it);

	//max_element
	//첫 원소의 주소와 마지막 원소의 다음 주소를 인자로 넘겨준다.
	//구간내의 최대값을 가지는 원소의 주소를 리턴한다.
	printf("%d\n", *max_element(arr1, arr1+n));

	//min_element
	//사용법은 같다.
	printf("%d\n", *min_element(arr2.begin(), arr2.end()));

	//unique
	//첫 원소의 주소와 마지막 원소의 다음 주소를 인자로 넘겨준다.
	//구간내의 중복된 원소를 구간의 끝부분으로 밀어주고 마지막 원소의 다음 주소를 리턴한다.
	//구간내의 원소들은 정렬되어 있어야한다.
	//보통 erase와 함께 중복된 원소를 제거하는 방법으로 사용한다.
	arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());

	//next_permutation
	//첫 원소의 주소와 마지막 원소의 다음 주소를 인자로 넘겨준다.
	//구간내의 원소들의 다음 순열을 생성하고 true를 리턴한다.
	//다음 순열이 없다면 false를 리턴한다.
	//구간내의 원소들은 정렬되어 있어야한다.
	int arr[10];
	for(int i=0;i<10;i++)
		arr[i]=i;
	do{
		for(int i=0;i<10;i++)
			printf("%d ", arr[i]);
		printf("\n");
	}while(next_permutaion(arr, arr+10));

	return 0;
}

 

참고자료 1 : http://code-algalon.tistory.com/188

참고자료 2 : http://baactree.tistory.com/29