STL 정리

본인이 PS를 하면서 자주 사용하는 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;
	}

view raw vector.cpp hosted with ❤ by GitHub

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;
	}

view raw stack.cpp hosted with ❤ by GitHub

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;
	}

view raw queue.cpp hosted with ❤ by GitHub

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;
	}

view raw deque.cpp hosted with ❤ by GitHub

5. set

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

	#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;
	}

view raw set.cpp hosted with ❤ by GitHub

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;
	}

view raw pair.cpp hosted with ❤ by GitHub

7. map

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

	#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[5]=6;
	//key와 연관된 원소를 pair<키 자료형, 데이터 자료형> 형태로 리턴함
	printf("%d\n", m.find(4)->second);
	//key와 연관된 원소의 개수를 리턴함
	printf("%d\n", m.count(4));
	//저장된 원소의 수를 리턴함
	printf("%d\n", m.size());
	//해당 주소의 원소 삭제
	m.erase(++m.begin());
	//모든 원소 삭제
	m.clear();
	return 0;
	}

view raw map.cpp hosted with ❤ by GitHub

8. algorithm

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

	#include <iostream>
	#include <vector>
	#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;
	}

view raw algorithm.cpp hosted with ❤ by GitHub