안녕하세요? 김백일입니다.

STL에서의 검색(탐색)은 정말 자주 쓰이는 작업이지만, 가능한 방법이 다양하기 때문에 초보자에게는 혼동스럽습니다.

이를 잘 정리한 표가 있어 다음에 소개합니다.

다음은 'Effective STL'의 Item 45에 나오는 표입니다.

 

질문 (해야 할 작업들)	사용할 알고리듬		사용할 멤버 함수
	정렬되지 않은 범위	정렬된 범위	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

다음은 정렬된 시퀀스(벡터와 배열)에 대해 이진 탐색을 하는 예제 코드입니다.

// Illustrating the generic binary search algorithms
int main()
{
  vector<int> v(5);
  bool found;

  // Initialize:
  iota(v.begin(), v.end(), 0);

  // Search for each of the integers 0, 1, 2, 3, 4:
  for (int i = 0; i < 5; ++i) {
    found = binary_search(v.begin(), v.end(), i);
    assert (found == true);
  }

  // Try searching for a value that's not present:
  found = binary_search (v.begin(), v.end(), 9);
  assert (found == false);
  int a[5] = {0, 7, 7, 7, 8};

  // Apply upper_bound, lower_bound and equal_range on v:
  int *k = lower_bound(&a[0], &a[5], 7);
  assert (k == &a[0] + 1 && *k == 7);
  k = upper_bound(&a[0], &a[5], 7);
  assert (k == &a[5] - 1 && *k == 8);

  pair pi = equal_range(&a[0], &a[5], 7);
  assert (pi.first == &a[0] + 1);
  assert (pi.second == &a[5] - 1);

  return 0;
}