STL의 검색(탐색) 방법 정리
안녕하세요? 김백일입니다.
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;
}
|