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

항목 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))
    {
        ...
    }