STL Algorithm

Date: 2024.05.01 Updated: 2024.05.01

카테고리: Cpp

모두의 코드 씹어먹는 c++ 자료를 보고 정리한 내용입니다.

template <typename Iter>
void do_something(Iter begin, Iter end);

template <typename Iter, typename Pred>
void do_something(Iter begin, Iter end, Pred pred);

c++ 표준 라이브러리의 알고리즘은 크게 위 두개의 형태를 가지고 있다. 전자의 경우, 알고리즘을 수행할 반복자의 시작점과 끝점 바로 뒤를 받는다. 후자의 경우, 반복자는 동일하게 받되, ‘특정한 조건’을 추가 인자로 받게 된다. 이러한 ‘특정한 조건’을 Predicate (서술자)라 부르며 보통 bool을 리턴하는 Functor(함수 객체) 를 전달한다.

Lambda Function

Lambda Function은 c++ 11에서 처음 도입되었다. 람다 함수를 통해 익명의 함수 객체를 매우 편리하게 만들 수 있다. 람다 함수의 예시와 일반적인 꼴은 다음과 같다.

[] (int i) -> bool { return i % 2 == 1; }

[!summary] [capture list] (받는 인자) → 리턴 타입 { 함수 본체 } (리턴 타입은 생략 가능)

[](int i) { return i % 2 == 1; }(3);  // true

auto func = [](int i) { return i % 2 == 1; };
func(4);  // false;

바로 호출할 수도 있고
람다 함수로 함수 객체를 생성한 후에 호출할 수도 있음

한 가지 중요한 점은 람다 함수 역시 함수이기 때문에 자기 자신만의 스코프를 가진다는 것이다. 이때 외부 변수가 필요한 경우 사용하는 것이 바로 캡쳐 목록(capture list) 이다. 일반적인 경우 필요한 변수에 레퍼런스를 받아오면 되는데, 문제는 클래스의 멤버 함수 안에서 람다를 사용할 때 멤버 변수를 참조하는 경우이다. 이런 경우 일반 변수가 아니라 객체에 종속되어 있는 멤버 변수이기 때문에 레퍼런스를 받아오려 하면 컴파일 에러가 발생한다. 이런 경우 보통 직접적으로 멤버 변수를 전달하지 않고 this를 통해 객체를 전달해주어야 한다(참고로 this는 레퍼런스로 전달할 수 없다).

주의) this 전달하면 편하긴 한데, nullptr 예외처리가 안된다고 함. 루키스는 귀찮더라도 변수마다 지정하라고 함

위 경우 말고도 캡쳐 리스트의 일반적인 사용 방법은 아래와 같다.

[ ] : 아무것도 캡쳐 안함
[&a, b] : a는 레퍼런스로 캡쳐하고, b는 const 복사본으로 캡쳐
[&] : 외부의 모든 변수들을 레퍼런스로 캡쳐
[=] : 외부의 모든 변수들을 const 복사본으로 캡쳐

Sort

sort : 일반적인 정렬
stable_sort : 크기가 같은 원소의 경우 기존의 순서를 유지하면서 정렬 (sort보다 조금 더 느림)
partial_sort : 배열의 일부만 정렬

sort(vec.begin(), vec.end());

참고로 sort에 들어가는 반복자의 경우 반드시 RandomAccessIterator 타입을 만족해야 한다. 우리가 봐왔던 컨테이너들 중에선 vector와 deque만 가능하고 나머지 컨테이너들은 sort 함수를 적용할 수 없다.

std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());

5 3 1 6 4 7 2 → 1 2 3 6 5 7 4

std::partial_sort(start, middle, end) **[start, end )원소들 중에서 [ start, middle )까지 전체에서 가장 작은 순으로 저장하고 나머지 위치는 알빠노

Remove

vec.erase(remove(vec.begin(), vec.end(), 3), vec.end());

remove 함수는 주어진 값을 컨테이너 내에서 제거하고 마지막 인덱스 + 1 (end) 반복자를 반환한다. 이때 중요한 점은 실제 컨테이너의 크기가 줄어드는 것이 아니라, 삭제되어야 할 원소들의 위치에 유지될 원소들의 값을 덮어 씌운다는 것이다. 즉, 아래 그림과 같이 컨테이너 뒤 쪽에 지운 셈 치는 데이터나 남아있다. 따라서 실제 원소를 지우기 위해서는 반드시 erase 함수를 호출해야 한다.

Pasted image 20240402025751

Remove_if

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;
  }
};

int main() {
  std::vector<int> vec;
  vec.push_back(5);
  vec.push_back(3);
  vec.push_back(1);
  vec.push_back(2);
  vec.push_back(3);
  vec.push_back(4);

  std::cout << "처음 vec 상태 ------" << std::endl;
  print(vec.begin(), vec.end());

  std::cout << "벡터에서 홀수인 원소 앞의 2개 제거 ---" << std::endl;
  vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd()), vec.end());
  print(vec.begin(), vec.end());
}

[!result] 처음 vec 상태 —- 5 3 1 2 3 4 벡터에서 홀수인 원소 앞의 2개 제거 — 2 3 4

위 코드와 같이 remove_if 함수에 조건을 추가하여 홀수인 원소들을 삭제하되 처음 2개만 삭제한다고 해보자. 실행 결과를 보면 홀수 원소 2개가 아니라 3개가 삭제되었다. 왜 이런 일이 일어났을까?

사실 c++ 표준에 따르면 remove_if에 전달되는 함수 객체는 이전 호출에 의해 내부 상태가 달라지면 안된다. 다시 말해, 위 코드 처럼 함수 객체 안에 인스턴스 변수(num_delete) 를 넣는 것은 원칙상 안되다는 것이다.

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;
}

remove_if의 코드를 살펴보자. 참고로 find_if 함수의 경우 인자로 전달된 조건pred가 참인 첫 번째 원소를 리턴한다. 그런데 문제는 pred의 레퍼런스를 받는 것이 아니라, 복사 생성된 버전을 받는다는 점이다. 따라서, find_if 호출 후에 아래 반복문에서 이미 한 개의 원소를 지웠다는 정보가 소멸되게 된다. 즉 후에 호출되는 pred는 이미 num_delete가 1이 된지 모른 채 다시 0부터 시작하게 된다.

[!danger] 함수 객체에는 절대로 특정 상태를 저장해서 이에 따라 결과가 달라지는 루틴을 짜면 안된다. ( 전역 변수를 조건으로 쓰는 위와 같은 경우를 말하는듯.. )

위 문제를 해결하는 방법은 num_delete를 내부 변수가 아니라 외부 변수로 빼고, 람다 함수를 이용하면 된다.

Transform

컨테이너 전체 혹은 일부를 순회하며 값들을 수정하는 작업이 필요한 경우가 있다. 예를 들어 벡터의 모든 원소에 1을 더한다던가 하는 작업들을 말하는데, 이런 작업을 도와주는 함수가 transform 이다.

  std::cout << "벡터 전체에 1 을 더한다" << std::endl;
  std::transform(vec.begin(), vec.end(), vec.begin(), [](int i) { return i + 1; });

[!summary] trasform (시작 반복자, 끝 반복자, 결과를 저장할 컨테이너의 시작 반복자, Pred)

Find

template <class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value)
{
	// ...
}

auto result = std::find(vec.begin(), vec.end(), 3);

find 함수는 단순히 first 부터 last 까지 하나씩 순회하면서 value와 같은 원소가 있는지 확인하고, 있으면 이를 가리키는 반복자를 리턴한다. 반복자에 따라서 forward_iterator이면 앞에서 부터 찾고, reverse_iterator이면 뒤에서 부터 거꾸로 찾는다. 물론 컨테이너에 중복되는 값이 있으면 가장 먼저 찾은 것을 리턴한다. 만약 벡터에서 값이 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 계열의 함수를 사용할 때 중요한 점은, 만약 컨테이너에서 제공하는 기본적인 find 함수가 있다면 이를 사용하는 것이 훨씬 빠르다는 것이다. 왜냐하면 알고리즘 라이브러리의 find는 컨테이너 자료 구조의 특성을 생각하지 않고 하나하나 무식하게 비교하기 때문이다. 예를 들어 set의 경우 find 함수는 O(log N) 으로 매우 빠르게 수행된다.

맨 위로 이동하기

등딱지빌런