[C++ STL] C++의 선형 검색

[C++ STL] C++의 선형 검색

전 포스팅에서 보았던 C로 작선된 find1은 char 형식의

배열만을 검색할 수 있었다. C++의 경우에는 템플릿을

이용해서 함수 인수의 형식을 매개변수화할 수 있으므로,

find1을 char 이외의 형식에 대해 일반화하는 것이 가능하다.

template <typename T>

T* find2 (T* first , T* last, T value);

상당히 명백하고도 직관적인 일반화이다.

하지만 STL은 약간은 덜 명백한 일반화를 사용한다.

template <typename Iterator. typename T>

Iterator find (Iterator first, Iterator last, const T& value){

while (first != last && *first != value)

++first;

return first;

}

이런 형태의 find가 find2보다 나은 점은 무엇일까?

find가 더욱 일반적이라는 데 있다. find2에는 

first, last가 포인터이어야 한다는 테한이 있지만,

find에는 그런 제한이 없다. 물론 포인터 연산의

구문을 사용하기는 하지만, Iterator가 반드시

포인터이어야 하는 것은 아니다. 

Iterator가 포인터 같은 인터페이스를 지원하기만 하면 된다.

find는 1차원적인 요소들의 순차열이라는 개념을 지원하는

임의의 자료구조에 대해 검색을 수행하는 하나의 일반적 알고리즘이다.

1. 선형 검색을 위해 필요한 것은, 하나의 요소를 조사하고,

2. 다음 요소로 넘어가고, 3. 모든 요소들을 처리했는지 판정하는 것이다.