KoreanFoodie's Study

C++ 기초 개념 10-3 : STL 알고리즘 (STL algorithm) 본문

Tutorials/C++ : Beginner

C++ 기초 개념 10-3 : STL 알고리즘 (STL algorithm)

GoldGiver 2022. 4. 18. 15:15

모두의 코드를 참고하여 핵심 내용을 간추리고 있습니다. 자세한 내용은 모두의 코드의 씹어먹는 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; });

 

Comments