[C++ STL] 선형 검색(find 알고리즘)과 단순 연결 리스트

[C++ STL] 선형 검색(find 알고리즘) 그리고 단순 연결 리스트

먼저 C++에서의 선형 검색에 대해 알아보자.

STL의 일반화된 선형 검색 알고리즘인

find는 다음과 같이 구현된다.

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

지원하는 임의의 자료구조에 대해 검색을 수행한다.

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

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

애초에 [first , last]가 하나의 선형적인 구간이라고 가정하지 않는다면 무의미

이러한 find 알고리즘이 정말 일반적이라면

배열 뿐만 아니라 단순 연결 리스트의 검색도 가능해야 한다.

다음은 연결 리스트의 구성과 이러한 노드들의 목록을

훑을 때 사용하는 코드의 예시이다.

int_node들의 리스트는 하나의 선형 순차열이므로,

선형 검색 알고리즘을 다시 작성하는 것은 낭비이다.

 find를 재사용하는 게 바람직한데, 어떻게 해야 할까?

기존에는 단순하게 ++first라는 포인터 연산으로

다음 요소를 얻었지만, 지금은 검색하고자 하는 것이

배열이 아니라 하나의 연결 리스트이기 때문에

그런 포인터 연산은 통하지 않는다.

p가 int_node를 가리킨다면, 다음 노드는

++p (p+1)가 아니라 p->next이다.

이러한 문제는 C++의 연산자 오버로드로 해결할 수 있다.

우리가 원하는 행동을 하도록 구체적으로 정의하면 된다.

그런데 int_node* 형식의 인수들에 대해

operator++를 다시 정의하는 것은 불가능하다.

때문에 int_node*처럼 보이면서도 operator++를

좀 더 적절하게 정의하는 간단한 래퍼 클래스를 만들면 된다.

int_node 뿐만아니라 next 포인터를 가진

어떠한 형식의 노드에도 작동하도록 설계

이제 로프를 사용하지 않고도 특정한 값을 가진

int_node를 찾을 수 있다. find 함수를 재사용 해보자.

find(node_wrap<int_node>(list_head) , node_wrap<int_node>(), val)

두 번째 인자 node_wrap<int_node>()는 기본 생성자를 호출.

널 포인터를 가진다. 즉 리스트의 마지막을 나타낸다.

node_wrap이라는 래퍼는 사소해 보여도, 상당히 놀라운 기능을 한다.

위에 정의한 int_node는 어떻게 보면 C++이 나오기도 전에 정의된

구조체일 수도 있다. 이렇게 오래된 자료구조와 새로운 알고리즘

find를 함께 사용할 수 있게 되었다. 즉 node_wrap 클래스는

오래된 자료구조와 새로운 알고리즘 사이의 중재자 역할을 한다.

또한 모든 멤버 함수들은 인라인으로 정의되어 있다.

때문에 효울성을 전혀 손상시키지도 않는다.

오늘은 STL의 선형 검색 알고리즘 (find 알고리즘)과

단순 연결 리스트에 대해 알아 보았다.

이제부터 C++ STL의 개념적인 이야기보다

좀 더 원론적인 이야기를 포스팅해나가겠다.