KoreanFoodie's Study
C++ 기초 개념 10-3 : STL 알고리즘 (STL algorithm) 본문
모두의 코드를 참고하여 핵심 내용을 간추리고 있습니다. 자세한 내용은 모두의 코드의 씹어먹는 C++ 강좌를 참고해 주세요!
STL algorithm
STL algorithm 라이브러리는 STL 자료구조를 다루는 데 필요한 편리한 메소드들을 제공하고 있다. STL 알고리즘 라이브러리에 있는 함수들은 대체로 다음과 같은 두 가지 형태를 띄고 있다.
template <typename Iter>
void do_something(Iter begin, Iter end);
template <typename Iter, typename Pred>
void do_something(Iter begin, Iter end, Pred pred);두 번째의 Pred 는 일반적으로 bool 을 리턴하는 함수 객체(Funtor) 가 전달된다.
정렬 (sort, stable_sort, partial_sort
정렬은 크게 세 가지로 나뉜다.
- sort : 일반적인 정렬
- stable_sort : 정렬을 하되, 원소들 간의 순서를 보존 (예 : 같은 값인 a 와 b 가 a, b ... 순으로 정렬되어 있었다면, 정렬 후에도 a 가 b 보다 먼저 나옴). sort 보다 조금 느리다.
- partial_sort : 배열의 일부분만 정렬
먼저 sort 의 예시들을 보자. stable_sort 는 sort 와 사용법이 같으므로 생략한다. (시간 복잡도는 O(n * logn)^2) 이다)
// sort 는 vector 와 deque 만 가능
sort(vec.begin(), vec.end());
// list 는 임의접근 반복자 (RandomAccessIterator) 타입이 없으므로 적용불가!
list<int> l;
sort(l.begin(), l.end());
sort 함수는 원소들을 기본적으로 오름차순으로 정렬하는데, Functor 를 넣어 우리가 원하는 대로 정렬 방식을 바꿀 수도 있다.
struct int_compare
{
bool operator()(const int& a, const int& b) const { return a > b; }
};
...
// 내림차순 정렬
std::sort(vec.begin(), vec.end(), int_compare());
// functional 헤더를 사용하면 더욱 간편하다!
std::sort(vec.begin(), vec.end(), greater<int>());
이제 partial_sort 의 예시를 보자.
// 정렬 전 :
// 5 3 1 6 4 7 2
std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
// 정렬 후 :
// 1 2 3 6 5 7 4위처럼, partial_sort 는 첫번째 인자에서 두번째 인자까지 원소들이 전체 원소들 중에서 제일 작은 애들 순으로 정렬시킨후, 나머지 위치는 건드리지 않고 리턴한다. 즉, 위의 예시에서는 가장 작은 3 개의 원소 1, 2, 3 이 정렬된 것이다.
따라서 전체 원소의 개수가 N 개이고, 정렬 하려는 부분의 크기가 M 이라면, 시간 복잡도는 O(N * logM) 이 된다. 왤까? M 개의 원소를 이용한 MaxHeap 을 만든다고 해 보자. 그럼 이 힙에 원소를 넣고 빼는 시간은 logM 이 될 것이고, 이것을 전체 원소에 대해 행해야 하기 때문에, N * logM 이라는 값이 나오게 된다.
만약 100명의 학생 중 상위 10명의 점수만 보고싶다면, sort 대신 partial_sort 가 더 빠를 것이다!
원소 제거 (remove, remove_if)
벡터 등에서 원소를 제거할때는 일반적으로 erase 를 사용한다. 하지만, 다음과 같은 경우, 원소를 제거할 때마다 기존에 제거하였던 반복자들이 초기화되므로, 해당 위치를 가리키는 반복자를 다시 가져와야 한다.
std::vector<int>::iterator itr = vec.begin();
for (; itr != vec.end(); ++itr) {
if (*itr == 3) {
vec.erase(itr);
itr = vec.begin();
}
}
위의 문제는 remove 를 사용하면 간단히 해결할 수 있다.
std::cout << "벡터에서 값이 3 인 원소 제거 ---" << std::endl;
vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end());이때 remove 함수는 원소를 실제로 지우는 것이 아니라, 조건에 해당하는 원소들을 반복자끝 부분으로 shift 한다. 따라서 remove 가 끝나면 3 이 제외된 원소들 벡터의 마지막을 가리키는 반복자를 리턴한다.
erase 는 remove 에서 전달한 반복자 위치를 받아, vec.end( ) 까지의 원소를 '실질적으로' 지우는 것이다! 참고로 erase 의 동작은 다음 두 가지로 나뉜다.
// pos 에 해당하는 원소 삭제
Iterator erase(Iterator pos);
// first 부터 last 까지의 원소들 삭제
Iterator erase(Iterator first, Iterator last);
참고로 remove 함수의 경우 반복자의 타입이 ForwardIterator 이므로, 리스트, 셋, 맵에도 모두 사용할 수 있다!
만약 특정한 조건을 만족하는 원소들을 제거하고 싶을 때는 remove_if 를 사용한다.
struct is_odd {
bool operator()(const int& i) { return i % 2 == 1; }
};
...
std::cout << "벡터에서 홀수 인 원소 제거 ---" << std::endl;
vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd()), vec.end());remove_if 의 경우, 세번째 인자로 우리가 설정한 Functor 를 전달해 주면 된다.
그런데 만약 홀수를 삭제하되 처음 2개만 삭제하고 싶다면 어떻게 구현해야 할까? 다음과 같이 Functor 를 수정해보자.
struct is_odd {
int num_delete;
is_odd() : num_delete(0) {}
bool operator()(const int& i) {
if (num_delete >= 2) return false;
if (i % 2 == 1) {
num_delete++;
return true;
}
return false;
}
};위의 Functor 를 집어넣으면 2개가 아니라 3개의 홀수를 삭제해 버린다. 사실 C++ 표준에 따르면 remove_if 에 전달되는 함수 객체의 경우 이전의 호출에 의해 내부 상태가 달라지면 안된다. 다시 말해, 위처럼 함수 객체 안에 인스턴스 변수 (num_delete) 를 넣는 것이 원칙상 안 된다는 것이다.
그 이유는 remove_if 를 실제로 구현했을 때, 해당 함수 객체가 여러 번 복사될 수 있기 때문이다. 물론 이는 버전마다 다르다. 아래 버전을 한 번 보자.
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
UnaryPredicate pred) {
ForwardIterator result = first;
while (first != last) {
if (!pred(*first)) { // <-- 함수 객체 pred 를 실행하는 부분
*result = std::move(*first);
++result;
}
++first;
}
return result;
}위에서는 인자로 전달된 함수 객체 pred 가 복사되지 않고 계속 호출되므로, 우리가 위에서 num_delete 를 사용한 is_odd Functor 가 의도대로 작동했을 것이다. 하지만 다른 버전은 어떨까?
template <class ForwardIt, class UnaryPredicate>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate pred) {
first = std::find_if(first, last, pred); // <- pred 한 번 복사됨
if (first != last)
// 아래 for 문은 first + 1 부터 시작한다고 봐도 된다 (++i != last)
for (ForwardIt i = first; ++i != last;)
if (!pred(*i)) // <-- pred 호출 하는 부분
*first++ = std::move(*i);
return first;
}위와 같은 버전의 경우, find_if 함수의 인자로 전달된 조건 pred 는 레퍼런스로 전달되지 않고 복사 생성되어 전달된다. 따라서, find_if 호출 후에 아래 for 문에서 이미 한 개 원소를 지웠다는 정보가 소멸되게 된다. 후에 호출되는 pred 들은 num_delete 가 1 인지 모른 채 0 부터 다시 시작하게 된다.
그러므로, 함수 객체에는 절대로 특정 상태를 저장해서 이에 따라 결과가 달라지는 루틴을 짜면 안된다. 위와 같이 이해하기 힘든 오류가 발생할 수도 있기 때문이다!
그렇다면 위의 문제를 어떻게 해결할까? 한 가지 방법은 num_delete 를 객체의 외부 변수로 빼는 방법이다.
struct is_odd {
int* num_delete;
is_odd(int* num_delete) : num_delete(num_delete) {}
bool operator()(const int& i) {
if (*num_delete >= 2) return false;
if (i % 2 == 1) {
(*num_delete)++;
return true;
}
return false;
}
};
...
std::cout << "벡터에서 홀수인 원소 앞의 2개 제거 ---" << std::endl;
int num_delete = 0;
vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd(&num_delete)),
vec.end());하지만 이 방법은 num_delete 를 새롭게 정의해야 하므로 바람직하지 않다. 대신, C++ 는 새로운 해결책을 도입하는데...
람다 함수 (lambda function)
람다 함수를 사용하면 위의 is_odd Functor 를 간단히 대체할 수 있다.
std::cout << "벡터에서 홀수인 원소 제거 ---" << std::endl;
vec.erase(std::remove_if(vec.begin(), vec.end(),
[](int i) -> bool {return i % 2 == 1;}),람다 함수는 다음과 같은 꼴로 정의된다 :
[ capture list ] ( 받는 인자 ) -> 리턴 타입 { 함수 본체 }
혹은 -> 을 생략할 수도 있다.
람다 함수의 capture list 를 활용하면 외부 변수에 접근할 수 있다.
int num_erased = 0;
vec.erase(std::remove_if(vec.begin(), vec.end(),
[&num_erased](int i) {
if (num_erased >= 2)
return false;
else if (i % 2 == 1) {
num_erased++;
return true;
}
return false;
}),
vec.end());
print(vec.begin(), vec.end());캡쳐 목록에는 어떤 변수를 캡쳐할 지 써주면 된다. 위에서는 num_erased 를 레퍼런스로 받았는데, 만약 & 를 써주지 않으면 num_erased 의 복사본을 const 로 받게 된다. 클래스 내부의 멤버 변수를 받을 때는 this 를 써주면 된다.
캡쳐 리스트 정리 :
- [ ] : 아무것도 캡쳐 안함
- [ &a, b ] : a 는 레퍼런스로 캡쳐하고 b 는 (변경 불가능한) 복사본으로 캡쳐
- [ & ] : 외부의 모든 변수들을 레퍼런스로 캡쳐
- [ = ] : 외부의 모든 변수들을 복사본으로 캡쳐
원소 수정하기 (transform)
transform 함수는 컨테이너의 전체 혹은 일부를 순회하며 값들을 수정하는 작업들을 도와주는 함수이다.
std::cout << "벡터 전체에 1 을 더한다" << std::endl;
std::transform(vec.begin(), vec.end(), vec.begin(),
[](int i) { return i + 1; });
// vec 에 1 씩 더한 결과값을 vec2 에 저장
std::transform(vec.begin(), vec.end(), vec2.begin(),
[](int i) { return i + 1; });transform 함수는 다음과 같은 꼴로 생겼다.
transform (시작 반복자, 끝 반복자, 결과를 저장할 컨테이너의 시작 반복자, Pred)우리가 사용한 예는 vec 의 begin 부터 end 까지의 원소에 1 을 더해준 결과를 begin 부터 덮어 씌우는 동작을 수행한다. 한 가지 주의할 점은 값을 저장하는 컨테이너의 크기가 원래의 컨테이너보다 최소한 같거나 커야 한다는 것이다. 다음의 예시를 보자.
transform(vec.begin(), vec.end(), vec.begin() + 1, [](int i) {return i + 1;});위의 코드는 저장하는 쪽의 공간이 하나 부족하므로 out of range 오류를 발생시키게 된다.
원소를 탐색하는 함수 (find, find_if, any_of, all_of) 등
find 함수는 다음과 같이 생겼으며, 결과값은 찾는 값을 가리키는 반복자를 리턴한다. (없으면 end)
template <class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value) {...}
...
auto result = find(vec.begin(), vec.end(), 3);
만약 해당 값을 가진 위치를 전부 찾고 싶다면, 다음과 같이 쓰면 된다.
auto current = vec.begin();
while (true) {
current = std::find(current, vec.end(), 3);
if (current == vec.end()) break;
std::cout << "3 은 " << std::distance(vec.begin(), current) + 1
<< " 번째 원소" << std::endl;
current++;
}find 함수들을 사용할때, 알고리즘 라이브러리에서는 해당 컨테이너에 대한 정보가 없으므로 평범한 O(n) 으로 처리된다. 하지만 set 의 경우 find 가 O(logn) 으로 수행될 수 있으며, unordered_set 의 경우 O(1) 으로 수행될수도 있다. 따라서 벡터와 같이 기본적으로 find 함수를 지원하지 않는 컨테이너에 사용하는 것이 좋다.
find_if 의 사용법도 find 와 비슷하다.
auto current = vec.begin();
while (true) {
current =
std::find_if(current, vec.end(), [](int i) { return i % 3 == 2; });
if (current == vec.end()) break;
std::cout << "3 으로 나눈 나머지가 2 인 원소는 : " << *current << " 이다 "
<< std::endl;
current++;
}차이점은 세 번째 인자로 값이 아닌 조건문(Functor 나 Lambda 함수) 를 넣는다는 것이다.
마지막으로 any_of 와 all_of 를 보자. any_of 는 인자로 받은 범위 안의 모든 원소들 중 조건을 충족하는 것이 하나라도 있으면 true 를 리턴하고, all_of 는 모든 원소들이 전부 조건을 충족해야 true 를 리턴한다.
// 파티원 모두가 15 레벨 이상이여야지 던전 입장 가능
bool can_join_dungeon() {
return std::all_of(users.begin(), users.end(),
[](User& user) { return user.level >= 15; });
}
// 파티원 중 한명 이라도 19렙 이상이면 특별 아이템 사용 가능
bool can_use_special_item() {
return std::any_of(users.begin(), users.end(),
[](User& user) { return user.level >= 19; });
'Tutorials > C++ : Beginner' 카테고리의 다른 글
| C++ 기초 개념 11 : 예외처리 (0) | 2022.04.19 |
|---|---|
| C++ 기초 개념 10-4 : C++ 문자열의 모든 것 (string과 string_view) (0) | 2022.04.18 |
| C++ 기초 개념 10-2 : 맵(map), 셋(set), unordered_map, unordered-set (0) | 2022.03.18 |
| C++ 기초 개념 10-1 : 벡터(vector), 리스트(list), 덱(deque) (0) | 2022.03.18 |
| C++ 기초 개념 9-4 : 템플릿 메타 프로그래밍 2 (의존 타입, auto) (0) | 2022.03.18 |
