[C++] lexicographical 이란?

STL의 <algorithm> 에 들어있는 lexicographical_compare 라는 함수가 있다.

그런데 lexicographical이 뭐지?

lexicographical의 사전적 의미는 '사전 편찬의' 이다.

그러면 lexicographical order 는 '사전에 편찬되는 순서' 일 것이다.

사전에서 'childern' 이라는 단어를 찾고 있다고 생각해보자.

일단 우리는 c로 시작하는 섹션으로 갈 것이다.

그리고 그 다음 글자부터 한글자 한글자씩... ca, cb, cc... ch가 나올 때 까지 밑으로 훑어 내려 간다.

그렇다면 'chill' 이라는 단어는 children을 찾기 전에 나타날까, 아니면 찾은 후에 더 아래에 위치하고 있을까?

c.h..i..l.... a.. b.. c.. d! 섹션에서 children이라는 단어가 나타날 것이다. chil 'l' 은 더 뒤에 있게 된다.

말인 즉슨, 'childern' 'chill' 두 단어를 비교했을 때 'children' 이 8글자로 더 길지만 'chill'이라는 5글자 짜리 단어가 더 '큰' 단어가 된다는 말이다. 

즉 lexicographical_compare는 '이 순서' 대로 요소를 비교 한다는 뜻이 된다.

lexicohraphical_compare 는 첫번째 요소가  두번째 요소 보다 'lexicographically less' 하면 true를 반환한다.

혹은 두 요소가 같은 경우를 포함 해서 두번째 요소가 더 작다면 false를 반환 한다.

그럼 lexicographical_compare('children', 'chill')(편의상 이렇게 표현함) 는 무엇을 반환할까? true를 반환하게 되는 것이다. 

이것은 첫번째 타입이고,  'less' 말고 다른 비교 연산을 인자로 줄 수 있는 두번째 타입도 있다. 

 

첫번째 타입의 구현 방식은 다음과 같다.

template <class InputIterator1, class InputIterator2>
  bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2)
{
  while (first1!=last1)
  {
    if (first2==last2 || *first2<*first1) return false;
    else if (*first1<*first2) return true;
    ++first1; ++first2;
  }
  return (first2!=last2);
}

InputIterator1의 처음과 끝, InputIterator2의 처음과 끝을 인자로 받는다.

first1, first2를 순회하는 이터레이터로 사용한다.

while (첫번째 요소의 끝에 도달할 때까지)

{     

       if ( 두번째 요소의 끝에 도달 했거나, 현재 위치의 두번째 요소 값이  첫번째 요소 값 보다 작으면) return false;

       else if (첫번째 요소의 값이 두번째 요소의 값 보다 작으면) return true;

        위 두개가 아니면 두 요소의 크기는 같으므로 다음 비교를 위해 요소의 위치를 한칸씩 ++ 해준다.

}

첫번째 요소의 끝에 도달할 때까지 리턴이 되지 않았다면 두 요소의 각 위치의 값이 계속 똑같았다는 말이 된다.

그러면 두번째 요소가 만약 끝에 도달 하지 않았다면 두번째 요소가 더 크다는 것이 되므로 true를 반환 하게 될 것이다.

혹은 두번째 요소도 끝에 도달 했다면 처음부터 끝까지 똑같은 요소밖에 없었으니 두 요소가 같다는 것이 되므로 false를 반환 하게 된다.

위 세줄이 return (first2 != last2) 를 풀어 쓴 것이다.

 

비교 함수를 인자로 받는 두번째 타입은 단순히 비교 하는 연산자를 함수로 대체해 주면 될 것이다.