[ C++ ] STL 정리

1. STL이란?

Standard Template Library 의 약자

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

 

2. 컨테이너

 

기본 자료형과 유저가 정의한 자료형을 담는 일종의 자료구조

 

2.1 시퀀스 컨테이너

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

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

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

 

2. 연관 컨테이너

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

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

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

 

3. 어댑터 컨테이너

시퀀스 컨테이너를 변형시켜 사용한다.

 

3. STL 정리

 

3.1 vector

 

벡터는 동적배열이며 크기를 지정하지 않아도 사용 가능하다.

임의의 위치에 있는 원소 접근과, 뒤에서 원소를 추가하는 연산은 O(1)을 보장한다.

#include <vector>

vector<자료형> 이름;
vector<자료형> 이름(크기);
vector<자료형> 이름(크기,초기화할숫자);
vector<vector<자료형>> 이름(n,vector<자료형>(m, 0); // m*n 배열 생성 및 0으로 초기화

이름.push_back(원소);  //맨뒤에 추가
이름.pop_back(원소);  //맨뒤에서 삭제
이름.size(); //크기
이름.resize(크기);  // 크기 재설정
이름.clear();  //원소 모두 삭제
이름.begin(); 
이름.end();  //시작과 끝 주고

이름.erase(a, b);  //[a, b) 주소 구간에 해당하는 원소 삭제
vector<자료형> 이름1=vector<자료형>(a, b); //[a, b) 주소 구간에 해당하는 원소 복사해서 생성

 

 

3.2.stack

#include <stack>

stack<자료형> 이름; 
이름.push(n);  //맨 위에 추가 
이름.pop();  //멘 뒤 삭제
이름.top(); //멘 위 원소
이름.empty(); 
이름.size();
swap(stack1 , stack2);

 

3.3.queue

큐(Queue)은 대표적인 FIFO(First In First Out) 구조이다.

 

#include <queue> 

queue<자료형> 이름;
이름.push(n);  //맨 뒤에 추가 
이름.pop();  //맨 앞 삭제
이름.front(); //맨 앞 원소
이름.back(); //맨 뒤 원소
이름.empty(); 
이름.size();
swap(queue1 , queue2);

 

 

3.4. deque

 

deque은 vector의 단점을 보완하기 위해서 만들어진 container 이다.

배열 기반의 구조인것은 같지만 vector는 새로운 메모리가 추가될 때 메모리를 대할당 한 후 복사하는 방식을 쓰는 반면에

deque는 새로운 메모리가 추가될 때마다 새로운 메모리 블록을 할당한다.

 

#include <deque>

deque <자료형> 이름;
deque<자료형> 이름(크기);
deque<자료형> 이름(크기,초기화할숫자);
deque<deque<자료형>> 이름(n,deque<자료형>(m, 0); // m*n 배열 생성 및 0으로 초기화

이름.assign(값,개수)  //값으로 개수만큼의 원수 할당
이름.front();
이름.back();
이름.push_front(값);
이름.pop_front();
이름.push_back(값);
이름.pop_back();
이름.resize(n); // 사이즈 재지정
이름.resize(n,2);  // 사이즈 재지정,만약 크기가 더 커졌을 경우 빈 원소를 2로 초기화
이름.size();
이름.swap(dq1);
이름.insert(위치, 값);
이름.insert(위치, 값, 개수);

//iterator와 사용
deque<int>::iterator iter

이름.begin();
이름.end();
이름.erase(iter);  //iter가 가르키는 값 삭제,제거한 곳의 iterator 를 반환

 

3.5.set

노드 기반 컨테이너 이며 균형 이진트리로 구현되어있다

Key라 불리는 원소들의 집합으로 이루어진 컨테이너이다. (key값은 중복이 허용X)

원소가 insert 멤버 함수에 의해 삽입이 되면, 원소는 자동으로 정렬된다.

#include <set>

set <자료형> 이름;
set<자료형> 이름(크기);
set<자료형> 이름(크기,초기화할숫자);
set<set<자료형>> 이름(n,set<자료형>(m, 0); // m*n 배열 생성 및 0으로 초기화


이름.clear();
이름.count(값); //값의 개수 return(중복안되므로 0,1)
이름.insert(k);
이름.swap(이름2);
이름.size();
이름.max_size();  //남은사이즈 반환


//iterator와 사용
deque<int>::iterator iter

이름.begin();
이름.end();
이름.insert(iter, 값);  //iter가 가리키는 위치 부터 k를 삽입할 위치를 탐색하여 삽입
이름.erase(iter);
이름.erase(start, end);  //[start, end) 범위의 원소를 모두 제거
이름.find(값);  //값을 가르키는 iter rerurn

 

3.6. pair

두 객체를 하나의 객체로 취급 할 수 있게 묶어주는 클래스이다.

데이터 "쌍"을 표현할때 사용한다.

 

pair<[type1], [type2]> p
p.first
p.second
make_pair(변수1, 변수2)

 

3.7.map

 

map은 각 노드가 key와 value 쌍으로 이루어진 트리이다. 중복을 허용하지 않는다.

 

map은 자료를 저장할때 내부에서  key를 기준 자동으로 오름차순 정렬한다.

 

#include <map> 

map <key type, value type> 이름;

/*map에서 데이터를 찾을 때는 iterator을 사용합니다.
데이터를 끝까지 찾지 못했을 경우, iterator는 map.end()를 반환*/
if (m=.find("Alice") != m.end()) {
	cout << "find" << endl;
}

이름.insert({key,value});  //데이터추가
이름.erase(주소); //특정요소 삭제
이름.erase(key);  //key 기준으로 요소 삭제
이름.erase(첨주소, 끝주소) //(첨주소,끝주소] 주소
이름.clear(); //전부 삭제
이름.begin()  //맨 처음
이름.end();  //맨 뒤
이름.erase(주소); //특정요소 삭제

 

3.8. algorithm

bool all_of(InputIterator first, InputIterator last, UnaryPredicate pred); 
//범위 안에 모든 원소들이 조건을 만족하는지 확인한다.

InputIterator find(InputIterator first, InputIterator last, const T& val);
//범위 안에 원소들 중 값이 일치하는 원소를 찾는다.

InputIterator find_if(InputIterator first, InputIterator last,UnaryPredicate pred);
//범위 안에 원소들 중 조건과 일치하는 원소를 찾는다.

typename iterator_traits<ForwardIt>::difference_type count_if(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, UnaryPredicate p);
//특정 값과 일치하는 원소의 개수를 센다.