STL에서 제공하는 알고리즘들은 그 특성에 따라서 몇가지 종류로
분류할수 있다. "Non-mutating algorithms", "Mutating algorithms",
"Sorting algorithms", Generalized numeric algorithms" 등이다.
이제 부터 이러한 분류별로 각각의 분류에 포함된 알고리즘을
설명하도록하겠다. 그러나 워낙에 많은 알고리즘이 존재하고 (대략 50여가지)
이들 알고리즘중에는 거의 사용되어지지 않는 알고리즘들도 있으므로,
자주 사용된다고 생각되는 알고리즘들만을 설명하도록 할것이다.
나머지 알고리즘에 대한 정보를 알기를 원한다면
SGI STL 홈 문서를 참고하길 바란다.
mutating 은 "변화", "변경" 의 뜻을 가진다. None-mutating algorithms
에 포함되는 알고리즘들은 컨테이너들의 원소에 대해서 None-mutating
즉 컨테이너를 변경시키지 않는 특성을 가지고 있다.
예를들어서 search 나, 원소의 갯수를 세는 count 등의 알고리즘은
컨테이너에서 필요한 원소를 찾거나, 계수를 하는 일을 할뿐으로,
컨테이너를 변경(원소를 삭제하거나, 위치를 변경시키거나)하는
일을 수행하지 않을것이다. 그런이유로 이러한 알고리즘들을
None-mutating(변경불가) 알고리즘이라고 부른다.
(말은 무지 복잡한데 개념은 무지 간단하다는걸 알수 있을것이다.)
list 를 선언할때 크기를 5로 지정한걸 주목하라. copy 알고리즘은 자동적으로
컨테이너의 크기를 할당시켜주지 않으므로, 미리 복사될 컨테이너의 크기를
지정해 놓아야 한다. list 를 크기를 할당시키지 않고 copy 해보면 컨테이너의
크기가 할당되지 않으므로, 하나의 값만이 복사됨을 알수 있을것이다. 이럴경우
list 컨테이너에는 5 하나만 들어가게 될것이다.
#include <algorithm>
#include <vector>
int main()
{
vector<char> V;
V.push_back('a');
V.push_back('b');
V.push_back('c');
V.push_back('d');
copy(V.begin(), V.end(), ostream_iterator<char>(cout, " "));
// a b c d 가 출력된다.
cout << endl;
reverse(V.begin(), V.end());
copy(V.begin(), V.end(), ostream_iterator<char>(cout, " "));
// d c b a 가 출력된다.
cout << endl;
}
제목에 현혹되지 말기바란다. 컨테이너에 포함된 원소를 정렬하는 그런 알고리즘들을
뜻하는게 아니다. 여기에서 말하는 Sorting 이란 원소가 미리 정렬되어있는 을 뜻한다.
여기에서 소개될 알고리즘들을 제대로 사용하기 위해서는 각 컨테이너의 원소가
미리 소팅되어 있어야만 제대로된 결과를 얻을수 있기 때문이다.(sort 알고리즘은 제외)
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
인자로 주어지는 first 와 last 이터레이터 사이를 순환하면서 소팅한다.
그런데 그 밑에 있는 오버로딩된 또다른 sort 버젼의 경우 comp 가 추가로 들어가는것을
알수 있다. 이것은 함수객체로써, 비교를 위한 함수를 사용하고자 할때 사용된다.
예를들어서 컨테이너에 들어있는 타입이 int 이거나, string 일경우에는 비교연산이
되므로 굳이 comp 함수객체를 필요로 하지 않을것이다. 그러나 char * 같은경우에는
비교연산이 되지 않으므로, 이럴경우에는 별도의 비교연산을 위한 함수객체가
필요하다.
2개의 컨테이너의 원소를 결합한다. 컨테이너의 원소들은 결합되면서 자동적으로 sort 된다.
만약 원소가 비교연산을 지원하지 않는 타입의 원소라면 비교객체 함수를 정의해서 사용하면 된다.
이외에도 함수객체는 알고리즘의 연산을 방식을 변경하기 위한 용도로도 사용된다.
이 알고리즘을 적용하기 위해서는 각 컨테이너의 원소가 미리 정렬되어 있어야 한다.
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator,
class StrictWeakOrdering>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, StrictWeakOrdering comp);
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryFunction>
T accumulate(InputIterator first, InputIterator last, T init,
BinaryFunction binary_op);
첫번째와 두번째 인자는 알고리즘을 적용할 원소의 범위를
지정하기 위한 이터레이터 이며, 세번째 아규먼트는 초기값이다.
또한 다른 많은 알고리즘과 마찬가지로 함수 객체를 이용해서
알고리즘의 연산방식을 변경시킬수도 있다.
#include <numeric>
#include <vector>
int mysum(int a, int b)
{
return a * b;
}
int main()
{
vector<int> V;
V.push_back(1);
V.push_back(2);
V.push_back(3);
V.push_back(4);
V.push_back(5);
V.push_back(6);
V.push_back(7);
cout << accumulate(V.begin(), V.end(), 0) << endl;
// 120
cout << accumulate(V.begin(), V.end(), 1, mysum) << endl;
// 5040
}
2번째 accumulate 를 적용시킬때는 mysum 이라는 함수 객체를
이용해서 기존의 '+' 연산을 '*' 연산을 하도록 변경했음을
알수 있다.
이것은 두개의 컨테이너의 원소들의 내적을 구하고자
할때 사용된다. 즉 A 와 B 컨테이너의 내적을 구한다면
A0 X B0 +
A1 X B1 + ...
An X Bn
공식을 따르게 될것이다.
Inner_product is an overloaded name; there are actually two inner_product functions.
template <class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, T init);
template <class InputIterator1, class InputIterator2, class T,
class BinaryFunction1, class BinaryFunction2>
T inner_product(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, T init, BinaryFunction1 binary_op1,
BinaryFunction2 binary_op2);
#include <numeric>
#include <vector>
#include <algorithm>
int mysum(int a, int b)
{
return a * b;
}
int main()
{
vector<int> V1;
vector<int> V2;
V1.push_back(1);
V1.push_back(2);
V1.push_back(3);
V1.push_back(4);
V2.push_back(5);
V2.push_back(6);
V2.push_back(7);
V2.push_back(8);
V2.push_back(9);
cout << inner_product(V1.begin(), V1.end(), V2.begin(), 0) << endl;
}
STL(5) - algorithm
윤 상배
dreamyun@yahoo.co.kr
1절. algorithm 에 대해서
지금까지 STL 의 여러가지 기능에 대해서 알아보았는데, 이러한 기능들은 결국 STL 을 이용한 자료구조로써의 기능에 촛점이 맞추어져 있음을 알수 있다. STL은 이러한 자료구조를 쉽고 유연하게 구현해주기 위한 도구라고 할수 있을것이다.
자료구조가 사용되면 빠지지 않고 따라다니는게 있는데, 바로 알고리즘 들이다. (아마도 가장 많이 사용되는게 sort, search 과 같은 알고리즘들일것이다.)
STL 에서는 여러가지 컨테이너들로 구성된 자료구조의 연산을 위한 다양한 알고리즘을 제공한다.
2절. 알고리즘
알고리즘을 사용하기 위해서는 다음과 같이 헤더파일을 선언해 주어야 한다.
STL에서 제공하는 알고리즘들은 그 특성에 따라서 몇가지 종류로 분류할수 있다. "Non-mutating algorithms", "Mutating algorithms", "Sorting algorithms", Generalized numeric algorithms" 등이다.
이제 부터 이러한 분류별로 각각의 분류에 포함된 알고리즘을 설명하도록하겠다. 그러나 워낙에 많은 알고리즘이 존재하고 (대략 50여가지) 이들 알고리즘중에는 거의 사용되어지지 않는 알고리즘들도 있으므로, 자주 사용된다고 생각되는 알고리즘들만을 설명하도록 할것이다. 나머지 알고리즘에 대한 정보를 알기를 원한다면 SGI STL 홈 문서를 참고하길 바란다.
2.1절. None-mutating algorithms
mutating 은 "변화", "변경" 의 뜻을 가진다. None-mutating algorithms 에 포함되는 알고리즘들은 컨테이너들의 원소에 대해서 None-mutating 즉 컨테이너를 변경시키지 않는 특성을 가지고 있다.
예를들어서 search 나, 원소의 갯수를 세는 count 등의 알고리즘은 컨테이너에서 필요한 원소를 찾거나, 계수를 하는 일을 할뿐으로, 컨테이너를 변경(원소를 삭제하거나, 위치를 변경시키거나)하는 일을 수행하지 않을것이다. 그런이유로 이러한 알고리즘들을 None-mutating(변경불가) 알고리즘이라고 부른다. (말은 무지 복잡한데 개념은 무지 간단하다는걸 알수 있을것이다.)
2.1.1절. find
아마도 가장많이 사용되는 알고리즘일 것이다. 컨테이너에서 일정한 범위의 원소들사이에서 원하는 값을 찾는다. 이 범위는 iterator 로 주어진다.
2.1.2절. count
count 는 말그대로 컨테이너에 포함된 원소의 갯수를 계수하기 위해서 사용된다.
2.2절. Mutating algorithms
이것들은 변경가능한 알고리즘들로써, 컨테이너의 원소를 수정할수 있다. 컨테이너 원소를 복사하거나, 교체, 삭제 하는등의 작업을 수행한다. 이러한 작업 수행중에 원소의 내용이 변경되므로 Mutating 알고리즘이라고 한다.
2.2.1절. copy
copy 는 Iterator 로 주어지는 범위의 원소를 다른 컨테이너로 복사하고자 할때 사용한다.
2.2.2절. swap
swap 는 인자로 주어진 2개의 컨테이너의 원소를 교환하기 위해서 사용된다.
2.2.3절. reverse
컨테이너의 원소를 뒤바꾼다. 즉 첫번째 원소는 마지막으로, 마지막원소는 첫번째로 교환하게 된다. 이러한 과정이 아규먼트로 주어진 iterator 사이의 모든 원소에 대해서 발생하게 된다.
2.2.4절. remove
iterator 범위내에서 일치되는 특정 원소를 삭제하고자 할때 사용한다.
2.2.5절. random_shuffle
꽤 재미있는 알고리즘이다. 컨테이너에 포함된 원소를 랜덤하게 위치를 재배열 해주는 일을한다.
2.2.6절. unique
이것은 컨테이너중에 중복된 요소를 없앰으로 오직 유일한 요소들만을 가지도록 만들어준다.
2.3절. Sorting 알고리즘들
제목에 현혹되지 말기바란다. 컨테이너에 포함된 원소를 정렬하는 그런 알고리즘들을 뜻하는게 아니다. 여기에서 말하는 Sorting 이란 원소가 미리 정렬되어있는 을 뜻한다. 여기에서 소개될 알고리즘들을 제대로 사용하기 위해서는 각 컨테이너의 원소가 미리 소팅되어 있어야만 제대로된 결과를 얻을수 있기 때문이다.(sort 알고리즘은 제외)
2.3.1절. sort
가장 간단하며 가장 자주 사용되는 알고리즘이다.
그런데 그 밑에 있는 오버로딩된 또다른 sort 버젼의 경우 comp 가 추가로 들어가는것을 알수 있다. 이것은 함수객체로써, 비교를 위한 함수를 사용하고자 할때 사용된다. 예를들어서 컨테이너에 들어있는 타입이 int 이거나, string 일경우에는 비교연산이 되므로 굳이 comp 함수객체를 필요로 하지 않을것이다. 그러나 char * 같은경우에는 비교연산이 되지 않으므로, 이럴경우에는 별도의 비교연산을 위한 함수객체가 필요하다.
2.3.2절. lower_bound 와 upper_bound
이름에서 알수 있듯이 이것들은 컨테이너에서 원하는 요소와 연속적으로 일치하는 첫번째 위치와 마지막 위치를 알아내기 위해서 사용한다. STL 의 컨테이너를 공부했다면 multimap 이나 multiset 에 같은이름의 함수를 본적이 있을것이다. 이들과 같은 일을한다.
2.3.3절. merge
2개의 컨테이너의 원소를 결합한다. 컨테이너의 원소들은 결합되면서 자동적으로 sort 된다. 만약 원소가 비교연산을 지원하지 않는 타입의 원소라면 비교객체 함수를 정의해서 사용하면 된다. 이외에도 함수객체는 알고리즘의 연산을 방식을 변경하기 위한 용도로도 사용된다. 이 알고리즘을 적용하기 위해서는 각 컨테이너의 원소가 미리 정렬되어 있어야 한다.
2.3.4절. set_union, set_intersection, set_difference
각각 합집합, 교집합, 차집합을 구현하는 알고리즘이다. 때에 따라서 매우 유용하게 사용할수 있을것이다.
또한 컨테이너에 입력되어 있는 원소들은 미리 sort 되어 있어야 한다.
2.4절. Generalized numeric algorithms
이번에는 수치알고리즘에 대해서 알아보도록 하겠다. 이들 수치 알고리즘을 사용하기 위해서는 numeric 를 include 시켜야 한다.
2.4.1절. accumulate
컨테이너의 모든 원소를 더하기 위해서 사용한다.
2.4.2절. partical_sum
partical_sum 은 x0, x0 + x1, x0 + x1 + x3 과 같은 연산을 할때 사용한다.
2.4.3절. adjacent_difference
이것은 x0, x1 - x0, x2 - x1.. 과 같이 인접한 두원소의 차를 구한다.
2.4.4절. inner_product
이것은 두개의 컨테이너의 원소들의 내적을 구하고자 할때 사용된다. 즉 A 와 B 컨테이너의 내적을 구한다면 A0 X B0 + A1 X B1 + ... An X Bn 공식을 따르게 될것이다.
Recent Posts
Archive Posts
Tags