1 count, find, binary_search, lower_bound, upper_bound, 그리고 equal_range 를 제대로 파악해 두자. #

위에 나열된 알고리즘들은 무언가를 찾으려고 할때 사용 가능한 것들이다. 우선 탐색범위를 알려주는 반복자쌍이 필요하다. binary_search, lower_bound, upper_bound, equal_range 는 정렬된 범위에 사용가능 하며 일반적으로 로그수행시간을 갖는다. 하지만 정렬된 범위가 아니라면 선형시간 알고리즘은 conunt, find 류의 알고리즘을 사용해야 한다.

1.1 정렬되지 않은 범위 #

1.1.1 count #

찾는값이 몇개 존재하는지 리턴.

list<Object> lw;

…

if(count(lw.begin(), lw.end(), w)) {

    …

}

이런식으로 원하는 값이 존재하는지 판단할때 사용가능하다. 하지만 단지 존재하는지 만을 판단하고 싶을 경우 count는 값이 존재하더라도 몇개인지를 판단하기 위해서 끝까지 검색을 하므로 find를 사용하는것이 좋다.

1.1.2 find #

찾는값의 위치를 리턴. 없다면 end() 반복자를 리턴.

특정 범위에 원하는 값이 존재하는지를 비교하기 위해서 사용된다. 일반적으로 operator== 을 사용하며 find_if 를 사용하여 자신이 원하는 방식으로 비교하는 함수자를 사용하는 find 알고리즘을 사용할수 있다.

list<Object>::iterator i = find(lw.begin(), lw.end(), w);

if(i != lw.end()) {

    … // 컨테이너에 존재하는 경우

}

또한 count 와는 다르게 find의 경우는 리턴되는 반복자를 통해서 검색한 데이타의 위치를 알수 있다. 즉 범위의 끝 반복자(end반복자)와 같은 값이라면 해당 범위에 존재 검색 대상의 데이타가 존재하지 않는것이지만 끝 반복자가 아닐경우는 데이타가 존재하며 위치는 리턴된 반복자인 것이다.

1.2 정렬된 범위 #

특정 영역이나 컨테이너의 정렬은 EffectiveSTL31, EffectiveSTL34 를 참고하며 정렬에 필요한 비교 연산자에 관한 EffectiveSTL19 의 내용도 참고한다.

1.2.1 binary_search #

정렬된 범위에서 어떤 값이 존재하는지를 알아 보는데에 사용한다. C 라이브러리의 bsearch 와는 달리 binary_search는 값이 있는지 없는지만을 bool 값으로 리턴한다. 비교는 동등성 비교(operator==)를 사용.

1.2.2 lower_bound #

값을 찾는데 사용. 이 알고리즘은 원하는 값을 가진 객체의 첫째 사본의 위치를 리턴하던지 못찾았을 경우에는 그 값이 삽입될 적당한 위치를 가리키는 반복자를 리턴한다.
find 와 마찬가지로 lower_bound 의 리턴값이 원하는 값을 가리키고 있는지 검사를 해야 해당 범위안에 있는지 없는지를 판단할수 있다. 하지만 lower_bound는 상등성 비교를 하용하므로 주의할 점이 있다.

vector<Object>::iterator i = lower_bound(vw.begin(), vw.end(), w);

if( i != vw.end() && *i == w )

{

    // 찾은경우

}

else

{

    // 못찾은 경우

}

간단하게 생각할 경우 이런식으로 사용이 가능해 보이지만 상등성 검사이므로 operator== 를 이용해서 비교하면 문제가 생길수 있다.
상등성, 동등성에 대한 내용과 상등성 비교를 제대로 하기 위한 방법은 EffectiveSTL19 를 참조하도록 하자. 주의 할점은 lower_bound 가 사용한 비교함수와 결과검사시 사용하는 비교함수가 동일해야 한다는 점이다.(정렬할때 사용하는것도 동일해야 하지 않나?)

1.2.3 equal_range #

위의 lower_bound 가 복잡할 경우 equal_range 를 사용하도록 한다. equal_range는 반복자 쌍으로 구성된 pair 객체를 반환하는데, 첫째 반복자는 lower_bound가 반환하는 그것과 같고 둘째 반복자는 upper_bound가 반환하는 찾고자 하는 것과 동등한 값을 가진 범위의 끝의 바로 다음과 같다. 간단하게 동등한 범위를 나타내는 반복자를 리턴한다.
equal_range 의 사용하기 쉬운점은 리턴되는 두개의 반복자가 같은 값일 경우 찾을려고 했던 값이 존재하지 않는 다는 의미이다.
두번째로 distance 를 이용하여 두 반복자 사이의 거리를 구한다면 범위내의 객체의 개수를 얻을수 있다는 것이다.

1.2.4 upper_bound #

upper_bound는 위에서도 언급한 것처럼 lower_bound 와는 반대로 찾고자 하는 것과 동등한 값을 가진 범위의 끝(큰쪽)을 리턴하거나 그 값이 없다면 해당 값이 삽입되기 가장 적당한 위치를 리턴한다.
여때까지는 컨테이너에서 동일한 값을 찾는 경우를 예를 들었지만 사실 시간 같은 경우 특정 값보다 작게 되는 위치라던가 크게 되는 위치등을 찾기를 원할 경우가 있을수 있다. 이 경우 lower_bound, upper_bound 등을 사용하면 쉽게 처리가 가능하다.

Timestamp ageLimit;

…

vt.erase(vt.begin(), lower_bound( vt.begin(),  // vt에서 ageLimit 보다

                                vt.end(),      // 오래된 것을 모두 없앤다.

                                ageLimit));

만약 포함한 것을 없앨 경우

Timestamp ageLimit;

…

vt.erase(vt.begin(), upper_bound( vt.begin(),  // vt에서 ageLimit 보다

                                vt.end(),      // 오래되 거나 동등한

                                ageLimit));    // 것을 모두 없앤다.

또한 upper_bound는 동등한 값을 가진 것들을 삽입된 순서대로 저장되도록 할때 에서 쉽게 사용이 가능하다.

Object obect;

…

lp.insert(upper_bound(lp.begin(),          // newPerson 의 앞에 

                      lp.end(),            // 오든지 동당한 객체중 가장 마지막의

                      newPerson,           // 것 뒤에 newPerson을 삽입한다.

                      PersonNameLess()),

                      newPerson);

1.3 표준 연관 컨테이너 #

위의 lower_bound, equal_range, upper_bound 는 범위를 나타내는 두개의 반복자를 대상으로 모두 동작하며 시퀀스 컨테이너같은 경우 그대로 적용가능 하다. 하지만 연관 컨테이너의 경우는 비슷한 동작을 하는 자체적인 함수를 제공하며 당연히 그 함수들의 성능이 더욱 뛰어나다.
표준 연관 컨테이너에는 위에서 언급한 대부분의 알고리즘들이 존재하지만 binary_search 는 존재하지 않는다. 비슷한 동작을 위해서 count 를 사용할수 있다. 연속 컨테이너에서 처럼 count가 존재하는 모든 데이타를 검색한다고 생각할수 있지만 연관 컨테이너는 자체적으로 정렬되어 있는 형식이기 때문에 연속 컨테이너의 equal_range 처럼 효율적으로 동작하므로 안심하고 사용해도 좋다.

2 정리 #

우리가 궁금한것	사용할 알고리즘		사용할 멤버 함수
정렬되지 않은 범위	정렬된 범위	set 이나 map	multiset 이나 multimap
원하는 값이 있는가?	find	binary_search	count	find
원하는 값이 있다면 첫번째 객체는 어디에?	find	equal_range	find	find 또는 lower_bound
원하는 값의 앞에 있지 않는 값을 가진 첫째 객체는 어디에 있나요?	find_if	lower_bound	lower_bound	lower_bound
원하는 값의 뒤에 있는 값을 가진 첫째 객체는 어디에 있나요?	find_if	upper_bound	upper_bound	upper_bound
원하는 값을 가진 객체는 몇개 인가요?	count	equal_range	count	count
원하는 값을 가진 객체는 모두 어디에 있나요?	find(계속 호출)	equal_range	equal_range	equal_range