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
'Programming > C | C++' 카테고리의 다른 글
[C] printf 출력형식 %d %i %u %X %x %o %p %s %c %C %f %e %E %g %G (2) | 2018.08.29 |
---|---|
[C] 포인터 (0) | 2018.08.21 |
[C] 파일 목록 가져오기 (2) | 2018.08.16 |
[C++] 전처리문의 종류 (0) | 2018.08.05 |
[C] 비주얼스튜디오2013 scanf 오류 해결법 (0) | 2015.11.02 |