Effective C++/Effective STL

[Effective STL] 45. 탐색 전략 선택

김디트 2025. 1. 15. 11:39
728x90

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

 

 

 

탐색 전략 선택
  • 빠르고 간단한 방법을 선택하면 된다.
  • 정렬되었는가?
    • binary_search, lower_bound, upper_bound, equal_range
    • 대개 로그시간에 수행된다.
  • 정렬되지 않았는가?
    • count, find

 

 

 

정렬되지 않은 요소 탐색 (count와 find)
list<Widget> lw;
Widget w;
...

// w가 들어있는지 체크한다.

// count를 사용한 방법
if(count(lw.begin(), lw.end(), w))
{
   ...
}

// count를 사용한 방법 2
if(count(lw.begin(), lw.end(), w) != 0)
{
   ...
}

// find를 사용한 방법
if(find(lw.begin(), lw.end(), w) != lw.end())
{
   ...
}
  • 값의 존재 여부만 확인한다면 count가 약간 더 간편하다.
  • 하지만 find가 더 효율적이다.
    • count는 같은 값이 더 있는지를 찾기 위해 범위의 끝까지 탐색하기 때문이다.
  • 값을 가진 객체의 존재 여부 뿐 아니라 객체 그 자체에 대해 알고 싶아면 역시 find가 답이다.
list<Widget>::iterator i = find(lw.begin(), lw.end(), w);
if(i != lw.end())
{
    ... // i는 첫 번째 객체를 가리킨다.
}

 

 

 

정렬된 요소 탐색
  • 탐색 알고리즘 선택지가 훨씬 많다.(binary_search, lower_bound, upper_bound, equal_range)
  • 상등성(equality)이 아니라 동등성(equivalence)으로 비교한다.(항목 19 참조)
    • count, find는 상등성으로 탐색하지만
    • binary_search, lower_bound, upper_bound, equal_range는 동등성으로 탐색한다.
  • binary_search
    • 정렬된 범위에서 어떤 값이 있는지 알아볼 때 사용한다.
    • C 라이브러리의 bsearch와 달리 bool값만을 반환한다.
    • vector<Widget> vw;
...
sort(vw.begin(), vw.end());
Widget w;
...
if(binary_search(vw.begin(), vw.end(), w)) // binary_search를 사용
{
    ...
}
  • equal_range, lower_bound
    • 정렬된 범위가 있고 원하는 값이 어디 있는지 알고 싶다면 사용한다.
    • lower_bound
      • 원하던 요소의 첫째 사본이나 그 값이 삽입될 적당한 위치를 가리키는 반복자를 반환한다.
      • 하지만 사용법에 유의할 것. 아래는 문제 코드
      • vector<Widget>::iterator i = lower_bound(vw.begin(), vw.end(), w);

if(i != vw.end() && *i == w) // 다음 부분에 버그!
{
    ...
}
      • 왜냐하면 *i == w 에서 상등성 검사(equality test)를 하고 있기 때문이다.
        • lower_bound는 동등성을 사용하여 탐색한다.(항목 19 참조)
        • lower_bound에서 사용한 것과 똑같은 비교 함수를 써야 한다.
      • 이런 일들이 번거롭다면... equal_range를 사용하자.
      • 범위 내의 위치를 찾고자 할때도 lower_bound는 유용하다.
      • class Timestamp { ... };

// lhs가 rhs보다 시간적으로 앞서있는지
bool operator<(const Timestamp& lhs, const Timestamp& rhs);

vector<Timestamp> vt;
...
sort(vt.begin(), vt.end()); // 오래된 것이 앞에 오도록 벡터 정렬

Timestamp ageLimit;
...
// ageLimit보다 오래된 것들을 모두 없앤다.
// ageLimit보다 오래 되지 않은 첫 번째 요소의 위치를 찾는 방법으로 lower_bound 사용
vt.erase(vt.begin(), lower_bound(vt.begin(), vt.end(), ageLimit));

// ageLimit보다 오래되거나 동등한 것들을 모두 없앤다.
vt.erase(vt.begin(), upper_bound(vt.begin(), vt.end(), ageLimit));
    • equal_range
      • 반복자 쌍으로 구성된 pair 객체를 반환한다.
        • 첫째 반복자 : lower_bound와 같다.
        • 둘째 반복자 : upper_bound와 같다.
      • 두 반복자가 같으면 그 범위 안에 아무것도 없다는 뜻이다.
      • vector<Widget> vw;
...
sort(vw.begin(), vw.end());
auto p = equal_range(vw.begin(), vw.end(), w);
if(p.first != p.second) // 같지 않으면 탐색 성공이다.
{
    ...
}
      • 두 반복자 사이의 거리(distance)를 구하면 범위 내의 객체의 갯수가 나온다.
      • auto p = equal_range(vw.begin(), vw.end(), w);
cout << distance(p.first, p.second) << endl; // 갯수 출력
  • upper_bound
    • 정렬된 범위에 객체를 삽입할 때 동등한 값을 가진 것들은 삽입된 순서대로 저장되도록 할 때도 사용할 수 있다.
    • class Person
{
public:
    ...
    const string& name() const;
    ...
};

struct PersonNameLess
{
    bool operator()(const Person& lhs, const Person& rhs) const
    {
        return lhs.name() < rhs.name();
    }
};

list<Person> lp;
...
lp.sort(PersonNameLess()); // PersonNameLess 함수 객체로 정렬

Person newPerson;
...
// newPerson 앞에 오던가 동등한 객체 중 가장 마지막 것의 뒤에 newPerson 삽입
// 다만.. list로 돌리기 때문에 탐색은 선형 시간이다. 비교만 로그 시간에 일어난다.
lp.insert(upper_bound(lp.begin(), lp.end(), newPerson, PersonNameLess()), newPerson);

 

 

 

범위가 아니라 컨테이너를 직접 사용하여 탐색
  • 표준 시퀀스 컨테이너(vector, string, deque, list)
    • 범위와 동일하게 사용하면 된다.(begin, end를 전달한다.)
  • 표쥰 연관 컨테이너(set, multiset, map, multimap)
    • 이들은 알고리즘 외에 탐색용 멤버 함수를 가지고 있다.(항목 44 참조)
    • 즉, 동일한 이름의 멤버 함수를 사용하는 것이 좋다.
    • binary_search는 멤버 함수로 존재하지 않지만... count를 쓰면 되므로 괜찮다.
    • set<Widget> s;
...
Widget w;
...
if(s.count(w))
{
    ...
}
728x90