STL 라이브러리는 객체 지향 기법의 일부 기능만 사용한다. 상속은 거의 사용하지 않으며 다형성은 느리다는 이유로 완전히 배제한다. 컨테이너 클래스는 내부적인 관리에 반드시 필요한 기능만을 가지며 필요한 모든 기능을 완벽하게 캡슐화하지 않는다. 컨테이너들은 알고리즘을 제공하는 전역 함수와 결합되어야 제 기능을 발휘할 수 있다.
STL의 주요 알고리즘들은 전역 함수로 제공되며 임의의 컨테이너에 대해 똑같은 방법으로 적용할 수 있다. 그래서 STL을 일반적이라고 한다. 이때 각 알고리즘과 컨테이너를 결합하기 위한 접착제로 반복자가 사용되며 상이한 컨테이너 구조에도 알고리즘이 잘 실행될 수 있도록 완충 역할을 하기도 한다. 컨테이너가 제공하는 반복자와 알고리즘이 요구하는 반복자가 다를 경우 효율상의 문제로 가끔 결합하지 못하는 조합도 있다.
대부분의 알고리즘 함수들은 algorithm 헤더 파일에 원형이 선언되어 있으므로 이 헤더를 반드시 인클루드해야 한다. 학술적으로 STL을 깊이있게 연구해 보고 싶다면 이 헤더 파일을 분석해 보는 것이 좋다. 물론 라이브러리란 어차피 남이 만든 걸 공짜로 쓰자는 취지이므로 사용만을 목적으로 한다면 굳이 그럴 필요가 없을 것이다. 그러나 때로는 장황한 설명이나 예제보다 실제 코드가 더 확실한 설명이 될 수도 있으므로 가끔은 헤더 파일을 직접 들춰 보는 것이 알고리즘을 이해하는 지름길이 될 수도 있다.
알고리즘은 기능에 따라 읽기, 변경, 정렬, 수치 4가지로 크게 분류되는데 이름으로부터 대충의 기능을 유추할 수 있다. 기능별 분류외에 컨테이너를 직접 변경하는 것과 복사본을 생성하는 것으로 분류하기도 하고 함수 객체를 취하는 버전과 그렇지 않은 버전으로 분류하기도 한다. 이 장에서는 기능 분류순으로 알고리즘을 하나씩 실습해 보되 STL의 기본 구조와 철학을 이해하고 있다면 대부분 어렵지 않으므로 간단한 사용법과 예제 위주의 레퍼런스 형식으로 정리하기로 한다. 양이 많기 때문에 모든 함수의 사용법을 완전히 숙지하는 것은 어려우므로 제공되는 함수의 목록만 파악해 두었다가 필요할 때 참조하는 형식으로 활용하는 것이 좋다.
읽기 알고리즘은 컨테이너를 변경하지는 않으며 컨테이너로부터 원하는 정보를 구하기만 하는 알고리즘이다. find는 가장 기본적인 알고리즘인 검색 기능을 제공하는데 한참 앞에서 이미 소개했고 충분한 실습까지 해 보았으므로 이미 익숙할 것이다.
InIt find(InIt first, InIt last, const T& val);
입력 반복자 두 개로 검색 대상 구간을 지정하여 검색하고자하는 값을 세 번째 인수로 전달한다. first ~ last 구간에서 val 값을 가지는 요소가 있는지 검색하여 그 반복자를 리턴한다. 만약 val이 발견되지 않으면 last가 리턴된다.
|
예 제 : find |
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
void main()
{
string names[]={"김정수","구홍녀","문병대",
"김영주","임재임","박미영","박윤자"};
vector<string> as(&names[0],&names[7]);
vector<string>::iterator it;
it=find(as.begin(),as.end(),"안순자");
if (it==as.end()) {
cout << "없다" << endl;
} else {
cout << "있다" << endl;
}
}
문자열 벡터에서 특정한 문자열이 있는지 검색해 보았다. 예제에서는 뻔히 없는 문자열에 대해 검색을 지시했으므로 "없다"는 결과가 출력될 것이다. find는 구간을 순차 검색하며 요소를 비교할 때는 요소 타입의 == 연산자로 비교한다. 따라서 검색을 위한 특별한 조건은 필요없지만 컨테이너에 요소가 많으면 검색 속도는 느려진다.
find는 최초로 조건을 만족하는 요소 하나만 검색하는데 만약 구간내에 일치하는 모든 요소를 검색하고 싶다면 다음과 같이 루프를 돌리면 된다. 최초 구간의 처음에 반복자를 두고 이 반복자 이후를 검색하며 하나가 검색될 때마다 다음 위치로 이동한 후 더 이상 발견되지 않을 때까지 검색을 반복하는 것이다. 이 예제의 경우는 조건을 만족하는 요소가 하나밖에 없지만 여러 개 있다면 전부 검색될 것이다.
vector<string>::iterator it;
for (it=as.begin();;it++) {
it=find(it,as.end(),"김정수");
if (it==as.end()) break;
cout << *it << "이(가) 있다." << endl;
}
이 외에 마지막 인수로 조건자를 취하는 find_if 함수도 있는데 이 함수를 사용하면 완전히 일치하는 요소뿐만 아니라 원하는 조건을 만족하는 요소를 검색할 수 있다.
InIt find_if(InIt first, InIt last, UniPred F);
find는 요소를 비교할 때 == 연산자를 사용하지만 find_if는 사용자가 지정한 단항 함수 객체 F로 비교한다. 구간내의 매 요소에 대해 F 함수를 호출하여 true가 리턴되는 요소를 검색하는데 F가 어떤 식으로 비교를 수행하는가에 따라 다양한 방식으로 요소값을 점검할 수 있다. 완전히 일치하는 것뿐만 아니라 부분 일치나 포함 여부 등으로도 검색 가능하다. 다음 예제는 이름에 "영"자가 포함된 사람들을 검색한다.
|
예 제 : find_if |
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool HasYoung(string who)
{
return (who.find("영") != string::npos);
}
void main()
{
string names[]={"김정수","구홍녀","문병대",
"김영주","임재임","박미영","박윤자"};
vector<string> as(&names[0],&names[7]);
vector<string>::iterator it;
for (it=as.begin();;it++) {
it=find_if(it,as.end(),HasYoung);
if (it==as.end()) break;
cout << *it << "이(가) 있다." << endl;
}
}
HasYoung 함수는 문자열을 인수로 전달받아 "영"이라는 부분 문자열이 포함되어 있는지 검사하여 그 결과를 리턴하며 find_if는 이 함수가 true를 리턴하는 요소를 검색한다. find가 ==로 완전히 같은 요소만 비교하는데 비해 find_if는 조건을 직접 점검할 수 있으므로 훨씬 더 일반화된 검색이 가능하다. 실행 결과는 다음과 같다.
김영주이(가) 있다.
박미영이(가) 있다.
함수 포인터 대신 () 연산자를 정의하는 함수 객체를 사용할 수도 있는데 다음과 같이 수정해도 결과는 동일하다.
struct HasYoung {
bool operator() (string who) const {
return (who.find("영") != string::npos);
}
};
it=find_if(it,as.end(),HasYoung());
이 방법에 대해서는 앞 장에서 이미 충분히 연구를 해 보았는데 이후 가급적이면 소스가 짧은 쪽으로 예제를 작성하기로 한다. 다음 함수는 반복자 구간에서 인접한 두 요소가 같은 값을 가지는 위치를 검색한다.
FwdIt adjacent_find(FwdIt first, FwdIt last [, BinPred F]);
함수의 원형을 표기하는 방법에 대해서는 앞 장에서도 설명을 한 적이 있는데 레퍼런스만을 읽는 사람들을 위해 다시 한 번 더 반복하기로 한다. 이 책에서는 짧게 표기하기 위해 축약된 원형을 사용하는데 문서상의 정확한 원형은 이보다 훨씬 더 복잡하게 작성되어 있다. 알고리즘 함수들은 예외없이 템플릿으로 정의되어 있으므로 다음과 같이 원형을 표기하는 것이 원론적이다.
template<class ForwardIterator>
ForwardIterator adjacent_find(
ForwardIterator _First,
ForwardIterator _Last
);
template<class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(
ForwardIterator _First,
ForwardIterator _Last,
BinaryPredicate _Comp
);
템플릿 인수의 이름이 너무 설명적으로 작성되어 있어 원형이 굉장히 길다. 매번 이렇게 템플릿 정의문을 일일이 밝히는 것은 귀찮고 외우기에도 너무 길기 때문에 반복자와 함수 객체에 대해서는 InIt, RanIt, UniOp, BinPred 등의 짧은 약자를 사용하며 반복자 구간을 표시하는 형식 인수의 이름도 first, last로 통일하였다. 이 약자에 대해서는 앞 장에서 이미 설명을 한 바 있다.
또한 조건자를 취하는 버전과 그렇지 않은 버전이 중복 정의되어 있어 조건자는 생략 가능한데 이런 인수에 대해서는 [ ] 괄호로 생략 가능함을 표기하기로 한다. 함수 객체는 포인터의 NULL처럼 지정되지 않았다는 특이값이 존재하지 않으므로 디폴트 인수 기능을 사용할 수 없어 두 원형으로 따로 정의할 수밖에 없다. 이후의 원활한 학습을 위해 표기법에 대해 부연 설명을 했다.
조건자가 없는 함수는 인접한 두 요소를 == 연산자로 비교하므로 두 요소가 같은 위치를 찾는다. adjacent_find는 구간을 순회하면서 앞뒤의 요소값이 같은 위치를 찾아 앞쪽 반복자의 위치를 리턴한다. 인접한 두 요소가 같은 것이 없으면 last가 리턴된다. 다음 예제는 벡터에서 같은 값이 두 번 연속으로 나오는 위치를 검색한다.
|
예 제 : adjacent_find |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void main()
{
int ari[]={1,9,3,6,7,5,5,8,1,4};
vector<int> vi(&ari[0],&ari[9]);
vector<int>::iterator it;
it=adjacent_find(vi.begin(),vi.end());
if (it != vi.end()) {
printf("두 요소가 인접한 값은 %d입니다.\n",*it);
}
}
정수 벡터에서 인접 요소를 검색했는데 보다시피 5가 두 개 연속적으로 들어 있다. adjacent_find로 검색한 결과 앞쪽 5의 반복자가 리턴될 것이다.
두 요소가 인접한 값은 5입니다.
조건자가 있는 함수를 사용하면 == 연산자 대신 조건자 함수 객체를 사용하여 두 요소의 조건을 점검하는데 이 함수의 비교 방식에 따라 앞쪽 요소가 더 큰 최초의 쌍, 인접한 값이 2배되는 쌍, 서로 소인 쌍 등을 검색할 수도 있다. 두 요소의 어떠한 관계든지 검색 가능하다. 예제를 다음과 같이 수정해 보자.
bool divisor(int a, int b)
{
return (a%b == 0);
}
....
it=adjacent_find(vi.begin(),vi.end(),divisor);
if (it != vi.end()) {
printf("최초로 발견된 약수 관계는 %d,%d입니다.\n",*it,*(it+1));
}
divisor 함수는 두 정수 a, b를 전달받아 a가 b로 나누어 떨어지는지를 검사한다. adjacent_find로 divisor 조건자를 지정하면 앞 요소가 뒷 요소의 배수(뒷 요소가 앞 요소의 약수)인 최초의 쌍을 검색할 것이다. 예제에서는 이 조건을 만족하는 최초의 값이 9와 3이다. 만약 이 조건을 만족하는 모든 쌍을 검색하고 싶다면 루프를 돌리면 된다. 다음 예제는 문자열 중 이중 공백을 찾는다.
|
예 제 : adjacent_find2 |
#include <iostream>
#include <algorithm>
using namespace std;
bool doublespace(char a, char b)
{
return (a==' ' && b== ' ');
}
void main()
{
const char *str="기다림은 만남을 목적으로 하지 않아도 좋다.";
const char *p,*pend=&str[strlen(str)];
for (p=str;;p++) {
p=adjacent_find(p,pend,doublespace);
if (p==pend) break;
cout << p-str << "위치에 이중 공백이 있습니다." << endl;
}
}
문장을 쳐 넣다 보면 실수로 공백을 두 번 입력하는 경우도 있는데 인접한 두 문자가 공백이면 그 위치를 출력하도록 했다. find에 비해 인접한 두 요소의 값을 한꺼번에 검사해 볼 수 있다는 점이 다르다.
8위치에 이중 공백이 있습니다.
37위치에 이중 공백이 있습니다.
다음 함수는 첫 번째 반복자 구간에서 두 번째 반복자 구간 중 하나가 최초로 발견되는 지점을 찾는다. 각 구간은 물론 순방향 반복자를 지원하는 임의의 컨테이너를 지시할 수 있으므로 벡터에서 리스트의 한 요소를 검색하거나 반대로도 검색할 수 있다.
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2 [, BinPred F]);
이 함수는 첫 구간의 모든 요소와 두 번째 구간의 모든 요소에 대해 이중 루프를 돌며 두 값이 조건을 만족하는지 검사한다. 디폴트 조건은 == 이지만 마지막 인수로 이항 조건자를 지정하면 원하는 조건을 지정할 수 있다.
|
예 제 : find_first_of |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void main()
{
int ar1[]={3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3};
int ar2[]={2,4,6,8,0};
int *p=find_first_of(&ar1[0],&ar1[25],&ar2[0],&ar2[4]);
if (p!=&ar1[25]) {
printf("최초의 짝수는 %d번째의 %d입니다.\n",p-ar1,*p);
}
}
두 개의 정수 배열을 선언하고 ar1에서 ar2에 있는 값 중 하나가 발견되는 최초의 지점을 찾는다. 예제에서 ar2에 모든 짝수를 나열해 두었으므로 ar1의 최초로 짝수인 수가 검색될 것이다.
최초의 짝수는 2번째의 4입니다.
여러 개의 조건 중 하나라도 만족하는 요소를 검색하고 싶을 때 이 함수를 사용한다. C 표준 문자열 함수 중 strpbrk와 유사한데 최초로 나타나는 모음을 검색한다거나 공백으로 인정될만한 문자들을 검색할 때 이 함수가 사용된다. find_first_of는 임의 타입의 컨테이너에 대해 사용할 수 있으므로 훨씬 더 활용 범위가 넓다.