Chapter6. 알고리즘 Part.3
1. 검색 알고리즘
STL 컨테이너의 항목열을 대상으로 특정 항목을 찾는 함수들 이다. 모든 알고리즘은 operator == 또는 operator <의 디폴트 연산자를 사용하는데, 필요하다면 비교 콜백 함수를 직접 전달 할 수 있도록 오버로딩 되어있다.
1) find(), find_if()
주어진 값과 같거나, 주어진 조건이 true가 되는 첫 번째 항목을 찾아주며 선형 시간 복잡도를 갖는다.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
auto ptr = find(arr, arr + 10, 7); //반복자 대신 배열의 항목을 가리키는 포인터도 가능
cout << *ptr << endl; //prt은 int*
vector<int> v {-1, -4, 6, 2};
auto vIter = find_if(v.begin(), v.end(), [](int a) {
return a > 10;
}); //람다를 통한 비교 콜백 함수 작성
cout << boolalpha << (vIter == v.end()) << endl;
//조건에 맞는 항목을 찾지 못하면 end 반복자 반환
}2) min_element(), max_element(), minmax_element()
각각 취솟값, 최댓값, 최솟값과 최대값의 쌍을 찾아준다. 선형시간 복잡도를 갖는다.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
vector<int> v {-1, -4, 6, 2};
auto minIter = min_element(v.begin(), v.end());
auto maxIter = max_element(v.begin(), v.end());
auto minMaxIter = minmax_element(v.begin(), v.end());
cout << '<' << *minMaxIter.first << ',' << *minMaxIter.second << '>' << endl;
}3) binary_search(), lower_bound(), upper_bound(), equal_range()
이 함수들은 이미 정렬된 항목열을 대상으로 한다. 자체적으로 정렬 상태를 유지하고 있는 컨테이너들은 메서드로서 이러한 알고리즘들이 제공되므로 제외하고 항목들 간의 순서가 무의미한 컨테이너들을 제외하고 나면 현실적으로 이 알고리즘 함수들이 유용하게 사용될 수 있는 대상은 vector, deque, array, 배열정도 이다. 이들 컨테이너의 항목열을 대상으로 이 함수들을 사용하면 로그 시간 복잡도로 대상을 찾아준다. list에도 사용할 수 있지만 랜덤 액세스 반복자를 지원하지 않기 때문에 선형 시간 복잡도로 성능이 떨어진다.
binary_search는 주어진 항목열에 특정 값이 있는지 없는지 여부만 bool 타입으로 반환해준다. lower_bound, upper_bound, equal_range는 특정 값을 기준으로 항목을 찾아 반복자를 반환해준다.
lower_bound는 주어진 값보다 작지 않은 첫 번째 항목을 가리키는 반복자를 반환해준다. 예를 들어 {1,2,2,3,5}와 같은 항목열에서 2를 찾는다면 두 번째 항목을 가리키는 반복자를 반환해주고, 4를 찾는다면 마지막 항목을 가리키는 반복자를 반환해준다. 주어진 값이 마지막 항목보다 크다면 end 반복자를 반환해준다.
upper_bound는 주어진 값보다 큰 첫 번째 항목을 가리키는 반복자를 반환해준다. 동일한 예로 {1,2,2,3,5}의 항목열에서 2를 찾는다면 네 번째 항목을 가리키는 반복자를 반환해준다. 4를 찾는다면 마지막 항목을 가리키는 반복자를 반환해주고, 5 이상의 값을 찾는다면 end 반복자를 반환해준다.
equal_range는 앞서 설명한 lower_bound와 upper_bound의 결과를 pair로 묶어 같이 반환해준다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <random>
using namespace std;
constexpr int RANDOM_S = 10, RANDOM_E = 100, RANDOM_CNT = 1000;
int main()
{
random_device rd; //난수생성기
vector<int> v;
v.reserve(RANDOM_CNT);
int mod = RANDOM_E - RANDOM_S;
for (int i = 0; i < RANDOM_CNT; ++i)
v.push_back(RANDOM_S + rd() % mod);
sort(v.begin(), v.end());
cout << "There is 77 : " << boolalpha << binary_search(v.begin(), v.end(), 77) << endl;
auto range = equal_range(v.begin(), v.end(), 77);
for (auto iter = range.first; iter != range.second; ++iter)
cout << *iter << ' ';
}2. 유틸리티 알고리즘
유틸리티 알고리즘에는 min, max, minmax 등이 있다. 이들은 다른 STL 알고리즘 함수들과 달리 반복자를 사용하지 않는다.
#include <algorithm>
using namespace std;
int x = 4, y = 5;
cout << "x is " << x << " and y is " << y << end;
cout << "Max is " << max(x, y) << endl;
cout << "Min is " << min(x, y) << endl;
//C++11버전 이후에서는 여러 값들 중 최소 또는 최대를 찾거나,
//최소값과 최대값을 함께 찾을 수 있음
int x1 = 2, x2 = 9, x3 = 3, x4 = 12;
cout << "Max of 4 elements is " << max({x1, x2, x3, x4}) << endl;
cout << "Min of 4 elements is " << min({x1, x2, x3, x4}) << endl;
auto mnx = minmax({x1, x2, x4, x4});
cout << "Minmax of 4 elements is <" << mnx.first << ',' << mnx.second << '>' << endl;