[C++/STL] Algorithm Library

STL Algorithm Library

• 주로 컨테이너 반복자(배열 주소 값)로 다양한 작업을 수행하도록 도와준다.
• 반복자 없이 값으로만 수행되는 함수도 있다.
• function을 인자로 설정해주기도 한다.
• range는 항상 [first, last)이다. (last 미포함)
• 함수의 형태는 대부분 아래와 같다.

함수 형태	대상
func(iterator first, iterator last, T value)	find, count, lower_bound, upper_bound
func(iterator first, iterator last)	sort, max_element, min_element
func(iterator first, iterator last, function f)	for_each, find_if, count_if, sort
func(T a, T b)	swap, max, min
func({ initializer list })	max, min

 

 

function 설정 방법

1. naive function
2. function object (functor)
3. lamda

 

예시

vector를 절대값 기준으로 오름차순 정렬하는 경우

1) naive function

bool comp (int am int b) {
    return abs(a) < abs(b);
}

2) function object

struct Compare {
    bool operator()(const int a, const int b) const {
        return abs(a) < abs(b);
    }
} comp;

3) lamda

    auto comp = [](int a, int b) { return abs(a) < abs(b) };

 

 

Algorithm library 주요 함수

• sort, partial_sort
• nth_element
• find, find_if
• swap
• max, min, minmax
• lower_bound, upper_bound
• max_element, min_element, minmax_element
• for_each
• count, count_if
• remove, remove_if

 

sort()

template<class RandomIt>
void sort(RandomIt first, RandomIt last);

template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

• [first, last) 구간을 comp 기준에 맞게 정렬
• comp를 명시하지 않으면 operator< 기준에 맞게 정렬

예시

vector<int> arr { 5, 3, -2, 1, -4};
sort(arr.begin(), arr.end());                   // -4, -2, 1, 3, 5
sort(arr.begin(), arr.end(), greater<int>{});   // 5, 3, 1, -2, -4

 

partial_sort()

template<class RandomIt>
void partial_sort(RandomIt first, RandomIt middle, RandomIt last);

template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp);

• [first, last) 구간에서 우선순위 기준으로 [fist, middle)만 정렬
• heap sort 기반
• default 값과 compare 설정은 sort와 동일
• O( (last - first) log (middle - first) )

예시

vector<int> arr { 5, 3, -2, 1, -4 };
partial_sort(arr.begin(), arr.begin() + 2, arr.end()); // [-4, -2], 5, 3, 1

 

nth_element()

template<class RandomIt>
void nth_element(RandomIt first, RandomIt nth, RandomIt last);

template<class RandomIt, class Compare>
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);

• [first, last) 구간에서 comp 기준(default : <)으로 nth 위치의 값을 선택하여 왼쪽, 오른쪽에 comp 기준에 맞게 값들을 배치
• < 기준으로 nth위치 값의 왼쪽에는 nth보다 작거나 같은 값, 오른쪽에는 nth보다 크거나 같은 값이 들어감
• 값들이 정렬되어 있지는 않음
• comp 기준은 sort와 동일
• introSelect 기반, average O(n)

예시

vector<int> v;
nth_element(v.begin(), v.begin() + 3, v.end()); // x x x o y y y y y y y

 

find(), find_if()

find()

template<class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value);

• [first, last) 구간에서 값이 value인 첫번째 element의 iterator 반환

예시

auto it = find(arr,begin(), arr.end(), 1);

 

find_if()

template<class InputIt, class UnaryPredicate>
InputIt find_if(InputIt first, InputIt last, UnaryPredicate p);

• [first, last) 구간에서 f의 결과가 true인 첫번째 element의 iterator 반환
• UnaryPredicate : bool p(T a)

예시

auto it = find_if(arr.begin(), arr.end(), [](auto x) { return x < 10; });

 

swap(), max(), min()

void swap(T a, T b) : a, b의 값을 바꿈
T max(T a, T b) : operator< 기준 큰 값
T min(T a, T b) : operator < 기준 작은 값
pair<T, T> minmax(T a, T b) : operator< 기준 first 작은 값, second 큰 값