[Basic C++] #32-2_STL 탐색 알고리즘

 

[Basic C++] #32-2_STL 탐색 알고리즘

 

C++ 개발에서 표준 라이브러리(STL)에 대해 알아보겠습니다.

"전문가를 위한 C"의 15 항목, "C++ 표준 라이브러리 살펴보기"에 해당하는 내용입니다.

 

---

 

Overview

 

1. 탐색 알고리즘
2. adjacent_find
3. find

 

#0. 탐색 알고리즘

1. 개념

• 이번 항목에서 다룰 내용은 "탐색" 알고리즘입니다.
• 탐색 알고리즘은 컨테이너가 저장하고 있는 항목들의 정보를 리턴하거나, 항목마다 특정 함수를 호출합니다. 
• STL 탐색 알고리즘 - adjacent_find, find, 그리고 search에 대해 알아보겠습니다.

 

#1. adjacent_find

1. 예제

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> myVector;
    
    myVector.push_back(20);
    myVector.push_back(20);
    myVector.push_back(30);
    myVector.push_back(40);
    
    // adjacent_find(begin(), end()) : 순차열 [b,e)의 원소 중 *p == *(p+1)인 "첫" 원소의 "반복자"를 리턴합니다.
    auto iter = adjacent_find(myVector.begin(), myVector.end());
    
    if(iter != myVector.end()) cout << *iter << endl;
    
    return;
}

 

Details

 

• 위 코드를 살펴보면, "myVector"는 vector 타입의 컨테이너로 4개의 항목을 담고 있습니다.
• 서로 인접한 항목 중 같은 값을 갖는 원소는 "20"으로 "0" 번째 원소와 "1" 번째 원소가 되겠죠.
• 따라서, "adjacent_find" 알고리즘은 0번째 원소의 반복자를 리턴합니다.

 

2. Predicate 활용 예제

// 이항 조건자
bool Condition(int a, int b)
{
    returun abs(a-b) <= 3;
}

int main()
{
    vector<int> v;
    
    v.push_back(10);
    v.push_back(13);
    v.push_back(20);
    v.push_back(50);
    
    // 조건자를 포함한 adjacent_find 함수 호출, 세 번째  매개 변수는 함수 포인터입니다. 
    auto iter = adjacent_find(v.begin(), v.end(), Condition);
    
    if(iter != v.end()) cout << *iter << endl;
    
    return;
}

 

• STL에서 제공하는 제네릭 알고리즘은 "디폴트 버전"과 "조건자 버전"이 존재합니다.
• 디폴트 버전의 경우 STL이 제공하는 기본 조건을 따르는 버전이며, 조건자 버전의 경우 사용자 정의 조건을 적용할 수 있는 버전입니다.
• 위 코드의 경우, 오차 범위 3 이내의 인접한 원소들 중 첫 번째 원소를 반환하도록 작성되었습니다.
• 따라서, "0" 번째 원소의 반복자를 반환합니다. 

 

#2. find

1. 예제

int main()
{
    vector<int> v;
    
    v.push_back(20);
    v.push_back(30);
    
    // find(begin(), end(), TARGET) : 순차열 [b,e)의 원소 중 TARGET과 같은 첫 원소의 반복자를 리턴합니다.
    auto iter = find(v.begin(), v.end(), 20);
    
    if(iter != v.end()) cout << *iter << endl;
    
    return;
}

 

Details

 

• "find(begin(), end(), TARGET)" 알고리즘은 TARGET과 같은 첫 원소의 반복자를 반환합니다. 간단하죠.
• "adjacent_find" 알고리즘과 동일하게 "find" 알고리즘도 조건자 버전으로 "find_if"를 갖고 있습니다.

 

#3. search

1. 예제

/*

	search(a.begin(), a.end(), b.begin(), b.end())
   	 : a의 항목중 b의 순차열과 동일한 순차열이 있다면, 그 중 첫 번째 순차열의 첫 원소의 반복자를 반환합니다.
     
*/

int main()
{
    vector<int> v;
    
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);
    v.push_back(7);
    v.push_back(1);
    v.push_back(1);
    v.push_back(1);
    
    /**********************************************************/
    // 5, 7 의 순차열과 동일한 순차열이 있는지 찾습니다.
    
    vector <int> v2 = {5, 7};
    
    auto it = search(v.begin(), v.end(), v2.begin(), v2.end());
    
    if(it != v.end())
    	cout << it-v.begin() << endl;
    else
    	cout << "No Result" << endl;
    
    /**********************************************************/
    // 5, 6, 7의 순차열과 동일한 순차열이 있는지 찾습니다.
    
    vector<int> v3 = {5, 6, 7};
    
    auto it = search(v.begin(), v.end(), v2.begin(), v2.end());
    
    if(it != end())
    	cout << it-v.begin() << endl;
    else
    	cout << "No Result" << endl;
}

 

Details

 

• "search" 알고리즘의 경우 앞서 살펴본 "adjacent_find"와 "find"와는 다르게 일치하는 "순차열"을 찾기 위한 알고리즘입니다.
• 따라서, "search" 알고리즘은 두 개의 동일한 데이터 타입을 담는 컨테이너가 필요합니다.