STL (Standard Template Library)

STL

Visutl Studio C++에 탑재된 STL : http://www.dinkumware.com/

STL 최초 구현한 HP의 버전 계승 : http://www.sgi.com/tech/stl/

널리 사용되는 안정성 높은 STL : http://stlport.org/

UNIX 기반 및 boland C++ STL : http://www.roguewave.com/home/

ObjectSpace : http://www.recursionsw.com/

안정성이 강화된 STL : http://horstmann.com/safestl.html

템플릿 기반 라이브러리

수치 계산, 과학 계산용 : http://www.oonumerics.org/blitz/

함수형 프로그래밍 : http://www.cc.gatech.edu/~yannis/fc++/

표준화 목적의 라이브러리 : http://www.boost.org/

  http://www.boostpro.com/ 

디자인 패턴 라이브러리 : http://sourceforge.net/projects/loki-lib/

선형 대수(매트릭스 연산 지원) : http://www.simunova.com/en/node/24

수치 계산 라이브러리 : http://shoup.net/ntl/

STL soft : http://synesis.com.au/stlsoft

array  vector  deque  list  (multi)set/map  push_front()  N/A  Linear  Constant Constant  N/A  push_back()  N/A  Constant  Constant  Constant  N/A  추가  N/A  Linear  Linear  Constant  Log  첫 원소 접근  Constant  Constant  Constant  Constant  Constant  마지막 원소 접근  Constant  Constant  Constant  Constant  Constant  임의 원소 접근  Constant  Constant  Constant  Linear  Log  <컨테이너별 연산 시간 복잡도>

STL의 범위 표현 : [first, last) 

ex)    for (int i=vector1.begin(); i != vector1.end(); ++i) {...}

Container

sequence container(시퀀스 컨테이너)

vector<T> #include <vector>

deque<T> #include <deque>

list<T> #include <list>

+ vector

맨 앞에서의 삽입과 삭제가 선형시간, deque 보다 느림.

다른 연산들은 deque와 동일하거나 빠름.

**. 삽입/삭제시 반복자/레퍼런스가 유효하다는 가정은 하지 말자.

- 생성

vector<T> vector1;

vector<T> vector1(n, value); //n개의 value로 초기화하여 생성

vector<T> vector1(n) //n개 생성

vector<T> vector1(first, last); //다른 Container를 복사하여 생성

vector<T> vector1(vector2); //vector2를 복사하여 생성

vector<T> vector1 = vector2; //vector2를 복사하여 생성

- 삽입

vector1.push_back(value);

vector1.insert(position, value); //해당 위치(position)에 value 삽입

vector1.insert(position, n, value); //해당 위치(position)에 n개의 value 삽입

vector1.insert(position, first, last); //해당 위치(position)에 first~last의 값 삽입

**. insert는 memory reallocation 발생.

- 크기

vector1.capacity(); //vector1의 할당된 현재 크기.

vector1.reserve(n); //vector1에 n개의 크기를 할당.(reallocation 방지 가능)

- 삭제

vector1.pop_back(); //vector1의 마지막 원소 삭제

vector1.back(); //vector1의 마지막 원소를 가져옴

vector1.erase(vector1.begin()); //vector1의 첫 원소 삭제

vector1.erase(first, last); //vector1의 first~last의 원소 삭제

vector1.front(); //vector1의 첫 원소를 가져옴

- 대입

=

vector1.assign(first, last); //erase(begin(), end()); 

                                 insert(begin(), first, last); 와 동일

vector1.swap(vector2); //교환

- 접근자

iterator begin() : 맨 앞을 가리키는 반복자

iterator end() : 맨 뒤를 가리키는 반복자

iterator rbegin() : 맨 앞을 가리키는 역 반복자(역순회용)

iterator rend() : 맨 뒤를 가리키는 역 반복자(역순회용)

size_type size() const : 원소 개수

size_type max_size() const : 저장될 수 있는 최대 개수

size_type capacity() const : reallocation 없이 저장될 수 있는 원소의 최대 개수

bool empty() const : 비어있는 경우 true

reference front() : 맨 앞의 원소 레퍼런스 리턴

reference back() : 맨 뒤의 원소 레퍼런스 리턴

reference operator[](size_type n) : 맨 앞에서 n번째 원소의 레퍼런스 리턴

reference at(size_type n) : 맨 앞에서 n번째 원소의 레퍼런스 리턴

                                     (n이 실제 크기 초과시 out-of-range 예외 발생)

상수 벡터 사용시 상수 반복자를 리턴하는 아이들(용도는 동일)

const_iterator begin() const

const_iterator end() const

const_iterator rbegin() const

const_iterator rend() const

const_reference front() const

const_reference back() const

const_reference operator[](size_type n) const

const_reference at(size+type n) const

+ deque

vector와 거의 동일.

맨 앞에서의 삽입/삭제가 상수시간, vector보다 빠름.

다른 연산들은 동일하거나 느림.

중간에 삽입/삭제가 빈번하다면 list.

**. 삽입/삭제시 반복자/레퍼런스가 유효하다는 가정은 하지 말자.

- 생성자 : vector와 동일

- 삽입

vector와 동일+ (reserve는 없음)

deque1.insert(position, value); //해당 위치(position)에 값 삽입

deque1.push_front(value); //맨 앞에 값 삽입

deque1.puch_back(value); //맨 뒤에 값 삽입

- 삭제 : vector와 동일+ (deque1.erase(..) , deque1.pop_front(..) )

- 대입 : vector와 동일

- 접근자

vector에서 제공되는 연산+ (capacity는 없음)

그러므로, begin, end, rbegin, rend, size, max_size, empty, operator[], at, front, back

+ list

중간에서 삽입/삭제 빈번한 경우, 멀이 떨어진 위치로 이동할 필요가 없는 경우 사용.

임의 접근 반복자 포기 => 삽입/삭제의 상수 시간 연산

정렬같은 알고리즘은 멤버 함수로 제공.

**. 삽입/삭제시 반복자가 무효화 되지 않는다.(삭제된 원소에 대한 반복자만 무효화)

list1.splice(..) 제공.

list1.reverse()  제공.

- 생성자 : vector와 동일

- 삽입   : vector와 동일 (reserve 없음)

- 삭제

vector와 동일+

erase는 삭제 후 할당된 길이가 줄어들지만 remove는 end() 만 줄고 할당된 영역은 그대로임.

list1.remove(value); //해당 값 제거

list1.remove(T pred); //함수의 조건으로 제거

- splice

list1.splice(i1, list2); //지정위치(i1) 앞에 list2 내용 삽입, list2의 원소는 삭제.

list1.splice(i1, list2, i2); //list2의 i2 원소를 list1의 i1 앞에 삽입 후 list2에선 삭제.

list1.splice(i1, list2, i2, j2);//list2의 [i2, j2)의 원소 삭제하고 list1의 i1 앞에 삽입.

- 정렬

list1.sort(); //정렬

list1.sort(T comp); //비교함수를 받아 정렬

list1.unique(); //인접한 중복요소 제거

list1.unique(T comp); //함수의 조건으로 인접한 중복 제거

list1.merge(list1, list2); //합체

list1.merge(const list<T>& otherList);

list1.merge(const list<T>& otherList, T comp);

- 접근자 : vector와 동일 (capacity, operator[], at 없음)

- 대입   : vector와 동일 (=, assign, swap)

sorted associative container (정렬 연관 컨테이너)

: 이진 검색트리(balanced binary search tree) 이용

set<Key> #include <set>

multiset<Key> #include <set>

map<Key, T> #include <map>

multimap<Key, T> #include <map>

+ set, multiset : (key)

set : 중복자동제거, 자동정렬

multiset : 중복허용,     자동정렬

- 생성자 : multiset 동일

set();

set(Compare);

set(first, last);

set(first, last, Compare);

set(otherSet);

- 삽입 : multiset 동일

set1.insert(value); //값 삽입

set1.insert(position, key); //삽입될 위치에 대한 힌트(position)와 값(key)

set1.insert(first, last); //[first, last) 삽입

inserter의 사용

copy(c.begin(), c.end(), inserter(set1, set1.end());

set 관련 연산 알고리즘과 inserter를 사용

set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), inserter(set3, set3.end()));

set 관련 연산 알고리즘

includes, set_union, set_intersection, set_difference, set_symmetric_difference

- 삭제 : multiset 동일

set1.erase(key); //key 삭제

set1.erase(i); //iterator로 삭제

set1.erase(i, j); //iterator i~j 까지 삭제

- 접근자

vector와 동일

key로 정보를 얻는 멤버 함수 : 

find : 주어진 key 값을 갖는 원소를 찾아줌.

      (가장 첫번째가 아닐 수 있다. : generic find algorithm과 다름)

lower_bound : 주어진 key 값을 갖는 첫번째 원소를 찾음.

upper_bound : 주어진 key 값을 갖는 마지막 원소를 찾음.

equal_range : 주어진 key 값을 갖는 첫번쨰와 마지막 원소를 쌍으로 찾아줌.

count : 개수

- 대입 : =, swap(멤버 함수 제공), assign 없음.

+ map, multimap : (key, value)

map : 중복자동제거, 자동정렬

multimap : 중복키허용,   자동정렬

EX) 내적계산시 map이 vector보다 훨씬 빠르다.

- 생성자 : set, multiset과 동일

- 삽입 

map[k] = t; //operator[]를 사용한 대입(multimap은 안됨)

(k,t)가 삽입된 상태에서 (k,t1)이 삽입되면 (k,t1)만 남는다.

i->second = t; //iterator i를 통한 값 수정

- 삭제   : set, multiset과 동일 (성능도 동일)

- 접근자 : set, multiset과 동일 (multimap은 operator[] 못씀)

- 대입   : set, multiset과 동일 (=, swap)

hashed associative container (해쉬 연관 컨테이너) : 해쉬 테이블 이용

STL에선 제공하고 있지 않음.

Iteratorrandom > bidirectional > forward > output/input

input iterator (==, !=, *, ++) - 읽기 종류 : find - istream iterator(입력 스트림 반복자) EX) istream_iterator<char> in(cin); istream_iterator<char> eos; find(in, eos, 'x'); cout << *(++in) << endl; output iterator (==, !=, *, ++) - 쓰기 종류 : copy - ostream_iterator EX) list<int> list1; ostream_iterator<int> out(cout, "\n"); copy(list1.begin(), list1.end(), out); forward iterator (==, !=, *, ++) - 읽기/쓰기 종류 : replace, deque, search bidirectional iterator (==, !=, *, ++, --) - 읽기/쓰기/양방향 이동(--) 종류 : reverse, list, set, multiset, map, multimap random access iterator (==, !=, *, ++, --, +=, -=, +, -, <, >, <=, >=) 종류 : binary_search, vector, deque, sort (sort와 deque는 효율적인 조합이 될 수 있다.)insert iterator 데이터 삽임을 위한 반복자. 1. back_insert_iterator<Container> : Container의 push_back 멤버 함수 사용. EX) copy(deque1.begin(), deque1.end(), back_insert_iterator< vector<int> >(vector1)); EX) copy(deque1.begin(), deque1.end(), back_inserter(vector1)); 2. front_insert_iterator<Container> : Container의 push_front 멤버 함수 사용. vector 사용 불가.(vector는 push_front 멤버 함수가 없음.) EX) copy(&array1[0], &array1[100], front_inserter(deque1)); 3. insert_iterator<Conatainer> : Container의 insert(iterator, value) 멤버 함수 사용. 모든 컨테이너 타입에 사용 가능. 원하는 곳에 삽입 가능. EX) copy(&array1[0], &array1[100], inserter(deque1, deque1.begin() + 1)); //array를 deque1에 deque1.begin()+1 부터 삽입 stream iterator istream_iterator (input iterator) EX) merge(vector1.begin(), vector1.end(), istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(list1)); //vector1과 입력값(cin)을 list1로 합침 ostream_iterator (outpu iterator) EX) merge(vector1.begin(), vector1.end(), list1.begin(), list1.end(), ostream_iterator<int>(cout, " ")); //vector1과 list1의 데이터 출력(공백 구분) mutable random access iterator vector<T>::iterator 대입 연산 수행.(*i = ...) const random access iterator(상수 반복자) vector<T>::const_iterator) 대입 연상 불가. 상수 컨테이너 사용시 상수 반복자를 사용해야 한다. EX) const vector<int> vector2(100, 0); vector<int>::const_iterator i = vector2.begin();

Algorithm

#include <algorithm>

STL algorithm 의 유형

1. in-place 버전

수행 결과가 동일한 컨테이너에 놓이는 경우

EX) sort(&a[0], &a[1000]); //배열 a의 정렬 결과가 다시 배열 a에 저장된다.

2. 복사 버전

수행 결과가 다른 컨테이너에 놓이는 경우

EX) reverse_copy(&a[0], &a[1000], &b[0]); //배열 a의 처리 결과가 배열 b에 저장된다.

3. 함수(조건자:predicate, bool형)를 인자로 가지는 버전

Generic에서 함수를 넘기는 가장 편한 방법 : 클래스로 정의된 함수 객체를 사용하는 것.

EX) sort(&a[0], &a[1000], greater<int>());

Generic Algorithm 들..

nonmutating sequence algorithm (변경 불가 시퀀스 알고리즘)

알고리즘 적용 대상 컨테이너를 직접 수정할 수 없는 알고리즘

find

adjacent_find

count

for_each

mismatch

equal

search

mutating sequence algorithm (변경 가능 시퀀스 알고리즘)

알고리즘 적용 대상 컨테이너의 내용을 변경할 수 있는 알고리즘

copy

fill

generate

partition

shuffle

remove

replace

reverse

swap

transform

unique

sorting-related algorithm (정렬 관련 알고리즘)

시퀀스를 정렬/머지 하는 알고리즘.

검색 연산, 셋 관련 연산을 하는 알고리즘.

sort(퀵소트)

stable_sort(힙소트)

partial_sort(머지소트)

nth_element(intro sort)

binary_search

lower_bound

upper_bound

equal_range

merge

inplace_merge

includes

set_union

set_intersection

set_difference

set_symmetric_difference

make_heap

pop_heap

push_heap

sort_heap

min_element

max_element

lexicographical_compare

next_permutation

generalized numeric algorithm (범용 수치 알고리즘)

accumulate, partial_sum, adjacent_difference, inner_product

몇몇 algorithm 함수들

reverse()

#include <algorithm>

vector, deque, list, 배열

reverse(first, end);

EX) reverse(vector1.begin(), vector2.end());

find()

#include <algorithm>

vector, deque, list, 배열

find(first, end, find_char);

EX) vector<char>::iterator where = find(vector1.begin(), vector1.end(), 'f');

merge()

#include <algorithm>

vector, deque, list, 배열

result는 오름차순 정렬. container들은 각기 다른 type이여도 가능.

merge(first1, last1, first2, last2, result);

accumulate()

#include <numeric>

accumulate(first, last, init); //덧셈

accumulate(first, last, init, binary_op); //EX : binary_op에 곱셈 함수를 넘길 수 있다.

multiplies() #include <functional>

편의를 위해 제공되는 곱셈 함수()를 갖는 class.

sort()

vector, deque, 배열

성능 고려하여 모든 container를 수용하지 않고 대신 각 container에 sort 함수가 있다.

sort는 퀵 소트를 약한 변형한 것이다.

copy()

copy(first, last, result);

replace()

replace(first, last, x, y); //x를 찾아 y로 치환

binary_search()

vector, 배열에서 효율적

EX) bool found = binary_search(vector1.begin(), vector1.end(), 5);

unique_copy() : 중복 값을 제외하고 복사

rotate() : 원소를 회전시킴

random_shffle() : 무작위로 섞음.

for_each() 

mismatch() : 다른 부분 찾기

distance() : 파일 크기 계산

equal() : 동일한지 검사

nth_element() : 상위 n만큼 추출

merge() : 두 시퀀스 합치기

includes() : 원소 존재 여부 확인

set_union() : 합집합

set_intersection : 교집합

set_difference() : 차집합

set_symmetric_difference() : 두 집합의 배타적인 집합

STLport의 PQ를 이용하여 원하는 priority_queue의 구현 가능.

max_element() : 정렬하지 않고도 최대값 추출

min_element() : 정렬하지 않고도 최소값 추출

next_permutation() : 새로운 조합형태 생성

valarray() : 배열 타입 연산 지원

accumulate() : 시퀀스 원소 합산

auto_ptr()  : delete 문 없이 닫기 괄호를 만난는 순간 소멸자를 호출하여

         사용하지 않는 메모리를 자동으로 해제해준다.

(일종의 garbage collector)

ex] auto_ptr<int> p(new int);

STL adapter

STL component의 interface 변경 용도

container adapter

+ stack container adapter : FILO

stack<T> : deque 로 구현된 stack

stack<T, deque<T>> : deque 로 구현된 stack

stack<T, vector<T>> : vector로 구현된 stack

stack<T, list<T>> : list  로 구현된 stack

지원 함수 : empty, size, top, push, pop

**. 값을 가져올땐 : top으로 가져온 후 pop으로 제거한다.

+ queue container adapter : FIFO

queue<T> : deque로 구현된 queue

queue<T, list<T>> : list 로 구현된 queue

queue<T, deque<T>> : deque로 구현된 queue

지원 함수 : empty, size, front, back, push, pop

**. 값을 가져올땐 : front으로 가져온 후 pop으로 제거한다.

+ priority queue : 가장 큰 값이 얻어지는 시퀀스

priority_queue<int>

: vector에 int 저장, less<int> 비교객체 사용 == 가장 큰 원소를 얻게 됨.

priority_queue<int, vector<int>, greater<int>>

: vector에 int 저장, int의 내장 > 연산자 사용 == 가장 작은 원소를 얻게 됨.

priority_queue<float, deque<float>, greater<float>>

: deque에 float 저장, float의 내장 > 연산자 사용 == 가장 작은 원소를 얻게 됨.

지원 함수 : empty, size, top, push, pop

**. 값을 가져올땐 : top으로 가져온 후 pop으로 제거한다.

iterator adapter (STL은 reverse iterator adaptor만 제공)

: 역방향의 새로운 반복자 타입을 만들어 낸다.

보통 reverse_iterator, const_reverse_iterator, rbegin, rend가 있기에

reverse iterator adaptor를 직접 사용하는 경우는 거의 없다.

EX) float rsum = accumulate(vector1.rbegin(), vector1.rend(), (float)0.0);

**. float의 경우 작은 수 부터 큰 수를 더한 경우 round-off 에러가 줄어드는 경향이 있다.

예를 들면, 1 + 0.0000000002 + 0.0000000001 .. = 1

          0.0000000002 + 0.0000000001 + 1 .. = 1.000000000312..

function adapter

+ binder : bind2nd

: 이항함수객체(binary function object)의 두 인자 중 한 개의 인자를 

 특정 값으로 바인드하여 단항함수객체(unary function object)로 변환.

EX) int* where = find_if(&array1[0], &array1[1000], 

                        bind2nd(greater<int>(), 200));

/*

array 0~1000 사이에서 >200 를 만족하는 위치를 찾는다.

greater<int>()는 

bool operator()(int x, int y) const { return x>y; }

인데 bind2nd(greater<int>(), 200)은

bool operator()(int x) const { return x>200; }

으로 만들어 준다.

*/

+ negator : not1, not2

: 반대 의미의 함수 객체로 변환.

 bool을 리턴하는 조건함수객체(predicate function object)의 리턴 값을 반대로 만듦.

EX) int* where = find_if(&array1[0], &array1[1000], 

                        not1(bind2nd(greater<int>(), 200)));

//array 0~1000 사이에서 <=200 를 만족하는 위치를 찾는다.

+ adaptor for pointers to functions (함수 포인터 어뎁터)

함수 포인터를 함수 객체로 변환. (유연성 및 코드 비대화(code bloat) 방지)

단항/이항 함수 포인터를 다른 함수 어뎁터와 함께 사용할 수 있도록 변환.

함수 객체 사용시 코드 비대화 방지를 위해 함수 포인터 전달 방식을 쓸때 사용.

(좀 느리지만 실행파일 크기는 줄어듦)

EX) bool less1   (const string& x, const string& y) { return x < y; }

bool greater1(const string& x, const string& y) { return x < y; }

typedef set<string, pointer_to_binary_function<const string&, const string*, bool>> set_type1;

set_type1 set1(ptr_fun(less1));

se1.insert("the");

...오름차순 정렬 저장..

set_type1 set2(ptr_fun(greater1));

se2.insert("the");

...내림차순 정렬 저장..

function object(함수 객체)

+ operator()를 오버로딩한 클래스(or struct)

template 사용. 효용성과 효율성이 좋다.

EX) MultClass multClass;

accumulate1(vector1.begin(), vector1.end(), 1, multClass);

.. T accumulate(.. first, .. last, T init, BinaryFunction  binary_function) {

 ..

 init = binary_function(init, *first);

 ..

}

+ 일반 함수 사용시 : 비추

함수 포인터를 사용하게 되고 비용이 많아지며 타입이 반드시 일치해야 함.

EX) int multfun(int x, int y) { .. }

accumulate1(vector1.begin(), vector1.end(), 1, &multfun);

   .. T accumulate1(.. first, .. last, T init, T (*binary_function)(T x, T y)){

     ..

     init = (*binary_function)(init, *first);

     ..

   }

간단한 샘플

reverse, find, sort, pair, replace_copy_if, bind2nd, equal_to, remove_if, not1, less, copy

#include <iostream> #include <string> #include <tchar.h> #include <vector> #include <algorithm> #include <functional> using namespace std; template<typename value_t, value_t max> struct random_gen { value_t operator () () { return static_cast<value_t>((static_cast<long>(rand())*(max)) / (RAND_MAX+1)); } }; int main(void) { //reverse() - 반대로 뒤집음 { wstring str(_T("abcdefg")); wcout << str << endl; reverse(str.begin(), str.end()); wcout << str << endl; } //find() - rfind, find_first_of, find_last_of, find_first_not_of, find_last_not_of { wstring str(_T("hi, nice to meet you.")); int pos = str.find(_T("to")); if (pos == wstring::npos) { wcout << _T("not exist") << endl; } else { wcout << _T("exist. pos : ") << pos << _T(" (") << str.substr(pos) << _T(") ") << endl; } } //sort() { wstring str(_T("hi, nice to meet you.")); wcout << _T("origin : ") << str << endl; sort(str.begin(), str.end()); wcout << _T("sorted : ") << str << endl; } //pair & find() { pair<wstring, wstring> filename; wstring str = _T("execution.exe"); int pos = str.rfind(_T(".")); if (pos == wstring::npos) { filename = make_pair<wstring, wstring>(wstring(str.begin(), str.end()), wstring()); } else { filename = make_pair<wstring, wstring>(wstring(str.begin(), str.begin()+pos), wstring(str.begin()+pos+1, str.end())); } wcout << filename.first << _T(".") << filename.second << endl; } //replace_copy_if(), bind2nd(), equal_to() - 특정 문자 변경 { wstring str1 = _T("hi man~, niece to meet you~"); wstring str2; str2.resize(str1.size()); //bind2nd()를 통해 equal_to() 의 2번째 인자를 TCHAR(' ')로 고정시킴 replace_copy_if(str1.begin(), str1.end(), str2.begin(), bind2nd(equal_to<TCHAR>(), TCHAR(' ')), TCHAR('_')); wcout << str1 << endl; wcout << str2 << endl; } //remove_if(), not1(), bind2nd(), less() - 특정 조건 삭제 { vector<int> v(10); generate(v.begin(), v.end(), random_gen<int, 10>()); copy(v.begin(), v.end(), ostream_iterator<int, TCHAR>(wcout)); wcout << endl; vector<int>::iterator end; //bin2nd()로 less()의 두번째 인자를 5로 고정한 후 not1 로 부정형을 만듦 //결국 5 이상의 값을 나타냄. end = remove_if(v.begin(), v.end(), not1(bind2nd(less<int>(), 5))); copy(v.begin(), end, ostream_iterator<int, TCHAR>(wcout)); wcout << endl; } return 0; }

Function Object(함수 객체) Ex) sort( vec.begin(), vec.end(), greater<int>() ); 산술 함수 객체(6개) plus<T>, minus<T>, negate<T>, multiplies<T>, divides<T>, modulus<T> 관계 함수 객체(6개) less<T>, less_equal<T>, greater<T>, greater_equal<T>, equal_to<T>, not_equal_to<T> 논리 함수 객체(3개) logical_and<T> : && 의미 logical_or<T> : || 의미 logical_not<T> : ! 의미 Adapter(함수 객체 어댑터) binder(바인더) bind1st : 첫번째 피연산자를 바인딩 Ex) find_if(vec.begin(), vec.end(), bind1st(greater<int>,10)); // if (10 > *iterator) 의미 bind2nd : 두번째 피연산자를 바인딩 Ex) find_if(vec.begin(), vec.end(), bind2nd(greater<int>,10)); // if (*iterator > 10) 의미 negator(부정자) not1, no2는 리턴값에 not 연산을 씌우며 bool인 함수 객체에만 사용 가능. not1 : 단항 함수 객체의 논리를 반대로 만듦 not2 : 이항 함수 객체의 논리를 반대로 만듦 Ex) not1(bind2nd(less<int>, 10)); // !(*iterator < 10) 의미 Generic Algorithm(제너릭 알고리즘) accumulate() 컨테이너 요소들을 세번째 인수로 지정한 초기값에 모두 더함 Ex) #include <numeric> ret = accumulate( arr, arr+8, 0 ); ret = accumulate( list.begin(), list.end(), 0, plus<int>() ); adjacent_difference() 주어진 열 내에서 인접한 각 요소의 차이를 값으로 하는 새로운 열 생성하여 세번째 인수에 결과를 복사. {0, 1, 1, 2, 3, 5, 8}을 {0, 1, 0, 1, 1, 2, 3}으로 만듦 Ex) #include <numeric> adjacent_difference( list.begin(), list.end(), ret.begin() ); adjacent_difference( list.begin(), list.end(), ret.begin(), times<int>() ); adjacent_find() 중복된 요소가 인접된 최초의 곳을 찾아 해당 위치의 iterator 리턴. Ex) #include <algorithm> Class TwiceOver { public: bool operator() (int val1, int val2) { return val1==val2/2 ? true : false; } } iter = adjacent_find( arr, arr+8 ); iter = adjacent_find( vec.begin(), vec.end(), TwiceOver() ); binary_search() 오름차순 정렬(< 연산자 정렬)되어 있는 가정하에 값 존재 여부를 bool로 리턴. Ex) #include <algorithm> bRet = binary_search( list.begin(), list.end(), value ); bRet = binary_search( list.begin(), list.end(), value, greater<int>() ); copy() 다른 컨테이너로 복사 Ex) #include <algorithm> ostream_iterator<int> ofile( cout, " " ); copy( vec.begin(), vec.end(), ofile ); vector<string> vec2( vec1.size() ); copy( vec1.begin(), vec1.end(), vec2.begin() ); copy_backward() copy()와 동일하지만 요소를 반대 순서로 복사 Ex) #include <algorithm> copy_backward( vec1.begin(), vec1.end(), vec2.begin() ); count() 컨테이너의 특정 값의 개수 Ex) #include <algorithm> int cnt = count( vec.begin(), vec.end(), value ); count_if() 연산 결과가 true로 계산되는 요소의 개수 Ex) #include <algorithm> class Even { public: bool operator()(int val) { return !(val%2); } }; int cnt = count_if( arr, arr+8, bind2nd(less<int>(), 10) ); int cnt = count_if( list.begin(), list.end(), Even() ); equal() 두 열이 같으면 true 리턴. 첫 컨테이너의 요소 개수 만큼 비교하며 기본적으로 == 연산자 사용. Ex) #include <algorithm> class EqualAndOdd { public: bool operator()( int v1, int v2 ) { return ((v1==v2) && (v1%2)); } int arr1[] = {1, 1, 2, 3, 5, 8, 13}; int arr2[] = {1, 1, 2, 3, 5, 8, 13, 21, 34}; bool ret = equal( arr, arr+7, arr2 ); // true bool ret = equal( arr, arr+7, arr2, EqualAndOdd() ); // false fill() 컨테이너 각 요소에 특정 value 대입 Ex) #include <algorithm> fill( vec.begin(), vec.eng(), value ); fill_n() 컨테이너의 특정 개수만큼 특정 value 대입 Ex) #include <algorithm> fill_n( arr, count, value ); fill_n( vec.begin(), count, value ); find() 컨테이너에 특정 value가 첫번째로 같은 iterator 리턴. 없다면 .end() 반환 Ex) #include <algorithm> it = find( arr, arr+8, value ); it = find( vec.begin(), vec.end(), "test" ); find_end() 첫번쨰,두번째 인자는 검색 대상 범위 세번쨰,네번째 인자는 검색할 요소 (문장에서 특정단어가 마지막으로 나오는 위치) 마지막으로 일치되는 열을 찾아 첫 요소의 iterator 리턴하여 없으면 .end() 리턴. Ex) Mississippi 문자열에서 ss 검색시 두번째 ss의 첫 글자 s의 iterator를 리턴. Ex) #include <algorithm> int arr[17] = {7,3,3,7,6,5,8,7,2,1,3,7,6,3,8,4,3}; int seq[3] = {3,7,6}; it = find_end( arr, arr+17, seq, seq+3 ); // arr[10]을 가리킴 find_first_of() 첫번째,두번째 인자는 검색 대상 범위 세번째,네번째 인자는 검색할 요소들 (하나라도 같으면 첫번째 일치하는 시작 iterator 반환) Ex) #include <algorithm> string arr[] = {"Ee", "eE", "ee", "Oo", "oo", "ee"}; string find[] = {"oo", "gg", "ee"}; it = find_first_of( arr, arr+6, find, find+3 ); // arr[2]의 "ee" 리턴 find_if() 처음 일치되는 요소의 iterator 리턴. 없으면 .end() 리턴 Ex) #include <algorithm> it = find_if( vec.begin(), vec.end(), bind2nd(less<int>, val) ); for_each() 각 요소에 연산 처리. 요소 자체를 수정라려면 transform() 사용. 연산이 값을 리턴해도 무시함. Ex) #include <algorithm> template <typename Type> void print_elem(Type elem) { cout << elem << " "; } for_each( vec.begin(), vec.end(), print_elem ); generate() 각 요소에 값 채움 Ex) #include <algorithm> class Gen { public: void operator()() { static int seed = -1; return seed += 2; } }; vector<int> vec(10); generate( vec.begin(), vec.end(), Gen() ); // 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 generate_n() 각 요소에 n 부터 값 채움 Ex) #inlcude <algorithm> class Gen { public: Gen( int seed = 0 ) : _seed( seed ) {} int operator() () { return _seed += 2; } private: int _seed; }; vector<int> vec(10); generate_n( vec.begin(), vec.end(), Gen(10) ); // 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 includes() 두번째 열이 첫번째 열에 모두 포함되어 있다면(존재하면) true 리턴. 두 열 모두 하나의 기준으로 정렬되어 있어야 하며 includes() 호출시 다섯번째 인자로 정렬 연산을 넘겨 줄 수 있음. Ex) #include <algorithm> int arr1[] = {13, 1, 21, 2, 0, 34, 5, 1, 8, 3, 21, 34}; int arr2[] = {21, 2, 8, 3, 5, 1}; sort( arr1, arr1+12 ); sort( arr2, arr2+6 ); bool ret = include( arr1, arr1+12, arr2, arr2+6); // true inner_product() 지정한 초기값에 두 열의 내적(inner product)값을 더함. {2,3,5,8}과 {1,2,3,4}의 내적은 (2*1)+(3*2)+(5*3)+(8*4) = 55 덧셈, 곱셈 연산을 오버라이딩하여 (2+1)-(3+2)-(5+3)-(8+4) = -28 도 가능. Ex) #include <algorithm> int arr1[] = {2, 3, 5, 8}; int arr2[] = {1, 2, 3, 4}; int ret = inner_product( arr1, arr1+4, arr2, 0 ); // 55 vector<int> vec1( arr1, arr1+4 ); vector<int> vec2( arr2, arr2+4 ); int ret = inner_product( vec1.begin(), vec1.end(), vec2.begin(), 0, minus<int>(), plus<int>() ); //-28 merge() 두 정렬된 열을 다섯번째 인자가 가리키는 곳에 합친다. 여섯번째 인자로 정렬 연산자 지정 가능. Ex) #include <algorithm> int arr1[4] = {5,3,2,1}; int arr2[4] = {9,7,6,8}; sort( arr1, arr1+4, greater<int>() ); sort( arr2, arr2+4, greater<int>() ); merge( arr1, arr1+4, arr2, arr2+4, greater<int>() ); inplace_merge() 연속된 컨테이너의 두 정렬 구간 [first, middle), [middle, last) 을 [first, last)에 합치고 정렬한다. 두 구간은 각각 정렬되어있어야 하며 네번째 인자로 정렬 알고리즘 지정 가능. Ex) #include <algorithm> int arr[20] = {29,23,20,17,15,26,51,12,35,40, 74,16,54,21,44,62,10,41,65,71}; int* first = arr; int* middle = arr+10; int* last = arr+20; sort( first, middle ); // 12,15,17,20,23,26,29,35,40,51 sort( middle, last ); // 10,16,21,41,44,54,62,65,71,74 inplace_merge( first, middle, last ); // 10,12,15,16,17,20,21,23,26,29,35,40,41,44,51,54,62,65,71,74 iter_swap() 두 iterator의 값을 바꿈 Ex) #include <algorithm> typedef vector<inti>::iterator Itor; Itor it1 = vec.begin(); Itor it2 = vec.begin()+4; iter_swap( it1, it2 ); lexicographical_compare() 첫째열이 둘째열보다 작거나 같으면 true 리턴. 기본적으로 비교 연산자(<)를 사용하며 다섯 번쨰 인자로 다른 연산 지정 가능. Ex) #include <algorithm> class size_compare { public: boll operator()( const string&a, const string& b ) { return a.length() <= b.length(); } }; string str1[] = {"Piglet", "Pooh", "Tigger"}; string str2[] = {"Piglet", "Pooch", "Eeyore"}; bool ret = lexicographical_compre( str1, str1+3, str2, str2+3 ); // 'c'가 'h'보다 작으므로 false bool ret = lexicographical_compre( str1, str1+3, str2, str2+3, size_compare() ); // Pooh < Pooch 이므로 true max(), min() 두 요소중 큰값/작은값 을 리턴. 세번째 인자로 비교 연산 지정 가능. Ex) #include <algorithm> int val = max(max(max(max(vec[4], vec[3]), vec[2]), vec[1]), vec[0]); int val = min(min(min(min(vec[4], vec[3]), vec[2]), vec[1]), vec[0]); max_element(), min_element() 열 내에서 가장 큰값/작은값의 iterator 리턴. 세번째 인자로 비교 연산 지정 가능. Ex) #include <algorithm> it = max_element( vec.begin(), vec.end() ); it = min_element( vec.begin(), vec.end() ); nth_element() 지정한 n번째 요소보다 작은 요소는 앞쪽으로 이동하고 큰 요소는 뒤쪽으로 이동하도록 재배치. 기본적으로 정렬은 하지 않지만 네번째 인자로 비교 연산자 지정 가능. Ex) #include <algorithm> int arr[] = {29,23,20,22,17,15,26,51,19,12,35,40}; nth_element( arr, arr+6, &arr[12] ); // n번째 요소로 arr+6 지정(26 값) //결과 : 23,20,22,17,15,19,12,26,51,35,40,29 partial_sort(), partial_sort_copy() [first, middle) 의 자리만 정렬하며 [middle, last)는 남은 수들을 정렬하지 않고 배치만 한다. 네번쨰 인자로 배치 연산 지정 가능. Ex) #include <algorithm> int arr[] = {29,23,20,22,17,15,26,51,19,12,35,40}; partial_sort( arr, arr+5, arr+12 ); // 가장 작은 다섯 요소가 정렬됨 // 결과 : 12,15,19,20,29,23,22,26,51,35,40} partial_sum() 각 요소들의 값이 자신의 값과 앞의 요소들의 총합으로 계산된다. 네번쨰 인자로 연산 지정 가능. Ex) #include <numeric> int ret[7]; int arr[7] = {1,3,4,5,7,8,9}; partial_sum( arr, arr+7, ret); // 결과 : 1,4,8,13,20,28,37 vector<int> ret(7); vector<int> vec( arr, arr+7 ); partial_sum( vec.begin(), vec.end(), ret.begin(), times<int>() ); // 결과 : 1, 3, 12, 60, 420, 3360, 30240 partition(), stable_partition() 단항 연산결과가 false인 요소 앞에 true인 요소를 위치시키며 stable_partition()은 상대적 위치까지 유지시켜 줌. (partitoin()은 상대적 위치 보장 못함) {0,1,2,3,4,5,6}에서 짝수 검사시 true는 {0,2,4,6}, false는 {1,3,5}이므로 {0,2,4,6,1,3,5}가 됨. Ex) #include <algorithm> class even_elem { public: bool operator()( int elem ) { return elem%2 ? false : true; } // 짝수면 true }; int arr[] = {29,23,20,22,17,15,26,51,19,12,35,40}; vector<int> vec( arr, arr+12 ); partition( vec.begin(), vec.end(), even_elem() ); // partition 결과 : {40,12,20,22,26,15,17,51,19,23,35,29} stable_partition( vec.begin(), vec.end(), even_elem() ); // stable_partition 결과 : {20,22,26,12,40,29,23,17,15,51,19,35} random_shuffle() 랜덤 배치 수행. 세번째 인자로 [0, 1]사이의 double을 리턴하는 난수 생성 함수 전달 가능. Ex) #include <algorithm> random_shuffle( vec.begin(), vec.end() ); remove(), remove_copy() remove()는 주어진 값을 삭제하고 유효한 값의 마지막 위치를 iterator로 리턴. 컨테이너 크기는 변하지 않기 때문에 리턴되는 iterator부터 .end()까지 erase() 필요. remove_copy()는 삭제한 값을 다른 컨테이너에 복사하므로 remove()보다 적합. Ex) #include <algorithm> int arr[] = {0,1,0,2,0,3,0,4,0,5}; vector<int> vec( arr, arr+10 ); iterator it = remove( vec.begin(), vec.end(), 0 ); // {1,2,3,4,5,3,0,4,0,5} 를 갖으며 리턴 값인 it는 쓰레기 값의 시작위치인 6번째 값 3을 의미 vec.erase( it, vec.end() ); // 쓰레기 값 삭제 하여 {1,2,3,4,5}로 만듦. remove_if(), remove_copy_if() 주어진 연산 결과가 true인 요소 삭제하며 각각 remove(), remove_copy()처럼 동작 Ex) #include <algorithm> class EvenValue { public: bool operator()( int value ) { return value %2 ? false : true; } // 짝수면 true }; int arr[] = {0,1,1,2,3,5,8,13,21,34}; vector<int> vec( arr, arr+10); iterator it = remove_if( vec.begin(), vec.end(), bind2nd(less<int>(), 10) ); //10보다 작으면 삭제 vec.erase( it, vec.end() ); // 결과 : { 13,21,34} int arr2[10]; remove_copy_if( arr, arr+10, arr2, EvenValue() ); // 결과 : {1,1,3,5,13,21} replace(), replace_copy() oldval를 newval로 치환 Ex) #include <algorithm> string sa[] = { "Christopher Robin", "Mr.Winnie the Pooh", "Piglet", "Tigger", "Eeyore" }; vector<string> vec( sa, sa+5 ); string oldval( "Mr.Winnie the Pooh" ); string newval( "Pooh" ); replace( vec.begin(), vec.end(), oldval, newval ); // 결과 : { "Christopher Robin", "Pooh", "Piglet", "Tigger", "Eeyore" } vector<string> vec2; replace_copy( vec.begin(), vec.end(), inserter(vec2, vec2.begin()), newval, oldval ); // 결과 : { "Christopher Robin", "Mr.Winnie the Pooh", "Piglet", "Tigger", "Eeyore" } replace_if(), replace_copy_if() 비교 연산 결과가 treu면 newval로 치환 Ex) #include <algorithm> int new_value = 0; int arr[] = {0,1,1,2,3,5,8,13,21,34}; vector<int> vec( arr, arr+10 ); // 10 미만이면 new_value로 치환 replace_if( vec.begin(), vec.end(), bind2nd(less<int>(), 10), new_value ); // 결과 : {0,0,0,0,0,0,0,13,21,34} reverse(), reverse_copy() 컨테이너 요소의 순서를 반대로 정렬 Ex) #include <algorithm> reverse( li.begin(), li.end() ); list<string> li_copy( li.size() ); reverse_copy( li.begin(), li.end(), li_copy.begin() ); rotate(), rotate_copy() [first, middle) 범위와 [middle, last) 범위를 서로 swap Ex) char ch[] = "boohiss!!"; rotate( ch, ch+3, ch+7 ); // 결과 : hissboo!! Ex) #include <algorithm> int arr[] = {1,3,5,7,9,0,2,4,6,8,10}; vector<int> vec( arr, arr+11 ), vec2(11); rotate( arr, arr+5, arr+11 ); // 결과 : {0,2,4,6,8,10,1,3,5,7,9} rotate_copy( vec.begin(), vec.end()-2, vec.end(), vec3.begin() ); // 결과 : {8,10,1,3,5,7,9,0,2,4,6} search() 첫번째 열에서 두번째 열이 처음 검색된 시작 위치(iterator) 리턴하며 없으면 .end() 리턴 다섯번째 인자로 상등 연산자(==) 오버라이딩 가능. Ex) #include <algorithm> char str[25] = "a fine and private place"; char substr[4] = "ate"; int *pIter = search( str, str+25, substr, substr+4 ); search_n() 검색 대상에서 특정 값이 n만큼 나타나는곳의 위치(iterator) 리턴하며 없으면 .end() 리턴 다섯번째 인자로 상등 연산자(==) 오버라이딩 가능. Ex) #include <algorithm> const char oh = 'o'; char str[26] = "oh my a mouse ate a moose"; char *found_str = search_n( str, str+26, 2, oh ); set_difference() 첫번째 열과 두번째 열의 차집합인 열을 생성. {0,1,2,3} - {0,2,4,6} = {1,3} Ex) set_union() 참조 set_intersection() 첫번째 열과 두번째 열의 교집합인 열을 생성. {0,1,2,3} ∩{0,2,4,6} = {0,2} Ex) set_union() 참조 set_symmetric_diffrence() 첫번째 열과 두번째 열의 차집합과 두번째 열과 첫번째열의 차집합에 대한 합집합의 열을 생성. {0,1,2,3}, {0,2,4,6} 에 대해서 {0,1,2,3} - {0,2,4,6} = {1,3} {0,2,4,6} - {0,1,2,3} = {4,6} 이므로 {1,3,4,6} 생성. Ex) set_union() 참조 set_union() 두 열의 합집합인 열을 생성. 첫번째 열과 두번째 열에 모두 존재하는 요소가 있을 경우 첫번째 열의 요소가 복사됨. {0,1,2,3} ∪ {0,2,4,6} = {0,1,2,3,4,6} Ex) #include <algorithm> string str1[] = {"Pooh", "Piglet", "Tigger", "Eeyore"}; string str2[] = {"Pooh", "Heffalump", "Woozles"}; set<string str1( str1, str1+4), set2( str2, str2+3 ); set<string> ret; set_union( set1.begin(), set1.end(), set2.begin(), set2.end(), inserter(ret, ret.begin()) ); // 결과 : Eeyore, Heffalump, Piglet, Pooh, tigger, Woozles ret.clear(); set_intersection( set1.begin(), set1.end(), set2.begin(), set2.end(), inserter( ret, retbegin() )); // 결과 : Pooh ret.clear(); set_difference( set1.begin(), set1.end(), set2.begin(), set2.end(), inserter( res, res.begin() )); // 결과 : Eeyore, Piglet, Tigger ret.clear(); set_symmetric_difference( set1.begin(), set1.end(), set2.begin(), set2.end(), inserter( ret, ret.begin() )); sort(), stable_sort() 오름차순 정렬(< 사용). 세번째 인자로 정렬 연산 지정 가능. stable_sort()는 컨테이너의 상대적인 순서 보장. 일반적으로 sort()는 quick sort, stable_sort()는 merge quick sort 알고리즘으로 구현됨. Ex) #include <algorithm> char str[] = "LessThan"; stable_sort( arr, arr+8 ); // LTaehnss stable_sort( vec.begin(), vec.end(), greater<string>() ): // ssnheaTL transform() 첫번쨰 형태 : 열의 각 요소에 매개변수로 넘긴 단항 연산후 세번째 인자에 결과 기록 두번째 형태 : 첫번째와 두번째 열에 대해 이항 연산후 네번쨰 인자에 결과 기록 Ex) #include <algorithm> int arr[] = {3,5,8,13,21}; int double_val(int val) { return val+val; } vector<int> vec(5); transform( arr, arr+5, vec.begin(), double_val); // 첫번째 형태 결과 : 6,10,16,26,42 int difference(int val1, int val2) { return abs(val1-val2); } vector<int> vec(5); transform( arr, arr+5, vec.begin(), vec2.begin(), difference ); // 두번째 형태 결과 : 3,5,8,13,21 unique(), unique_copy() 연속된 동일한 값을 하나로 합침. remove() 처럼 컨테이너 크기는 변하지 않아 erase()를 사용하기 때문에 unique_copy()가 적합 Ex) #include <algorithm> int arr[] = {0,1,0,2,0,3,0,4,0,5}; vector<int> vec( arr, arr+10 ); sort( vec.begin(), vec.end() ); it = unique( vec.begin(), vec.end() ); vec.erase( it, vec.end() ); // 결과 : 0,1,2,3,4,5 int arr2[10]; sort( arr, arr+10 ); unique_copy( arr, arr+10, arr2 ); // 결과 : 0,1,2,3,4,5