C++ STL - 알고리즘(algorithm)

알고리즘 라이브러리?

• 컨테이너에 반복자들을 가지고 이런 저런 작업을 쉽게 수행할 수 있도록 도와주는 라이브러리

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

ㄴ 알고리즘을 수행할 반복자의 시작점과 끝점 바로 뒤를 받음

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

ㄴ 반복자는 동일하게 받되, '특정한 조건' 을 추가 인자로 받음.

• 서술자 (Predicate) : '특정한 조건'을 의미하며, 보통 Pred에는 bool을 리턴하는 함수 객체(Functor) 을 전달

정렬 (sort, stable_sort, partial_sort)

• sort
  일반적인 정렬 함수
• stable_sort
  정렬을 하되 원소들 간의 순서를 보존.
  벡터에 [a, b] 순으로 있었는데, a 와 b 가 크기가 같다면 정렬을 [a,b] 혹은 [b,a] 로 할 수 있음. 이 때, sort는 그 순서가 랜덤으로 정해지고 stable_sort는 그 순서를 보존
• partial_sort
  배열의 일부분만 정렬

sort

오름차순 정렬이 기본.
임의접근 반복자(RandomAccessIterator) 타입을 만족해야 하므로, 벡터와 데크에만 sort함수 적용 가능

#include <algorithm>
#include <iostream>
#include <vector>

template <typename Iter>
void print(Iter begin, Iter end) {
  while (begin != end) {
    std::cout << *begin << " ";
    begin++;
  }
  std::cout << std::endl;
}
int main() {
  std::vector<int> vec;
  vec.push_back(5);
  vec.push_back(3);
  vec.push_back(1);
  vec.push_back(6);
  vec.push_back(4);
  vec.push_back(7);
  vec.push_back(2);

  std::cout << "정렬 전 ----" << std::endl;
  print(vec.begin(), vec.end());
  std::sort(vec.begin(), vec.end());

  std::cout << "정렬 후 ----" << std::endl;
  print(vec.begin(), vec.end());
}

만약 내림차순으로 정렬하고 싶다면,
Pred 전달하여 수행

#include <algorithm>
#include <iostream>
#include <vector>

template <typename Iter>
void print(Iter begin, Iter end) {
  while (begin != end) {
    std::cout << *begin << " ";
    begin++;
  }
  std::cout << std::endl;
}

// 함수 객체를 위한 구조체 정의하고,
// 그 안에 operator() 함수를 만들어 줌 
struct int_compare {
  bool operator()(const int& a, const int& b) const { return a > b; }
};


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

  std::cout << "정렬 전 ----" << std::endl;
  print(vec.begin(), vec.end());
  std::sort(vec.begin(), vec.end(), int_compare());

  std::cout << "정렬 후 ----" << std::endl;
  print(vec.begin(), vec.end());
}

+) greater<int> 참고

partial_sort

// 5 3 1 6 4 7 2 
  std::cout << "정렬 전 ----" << std::endl;
  print(vec.begin(), vec.end());

// 1 2 3 6 5 7 4 
  std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
  std::cout << "정렬 후 ----" << std::endl;
  print(vec.begin(), vec.end());

partial_sort 함수는 일부만 정렬하는 함수.
위의 코드에서는 인자를 3개를 받아 정렬

std::partial_sort(start, middle, end)

[stard, end) 전체 원소들 중에서 [start, middle) 까지 원소들이 전체 원소들 중에서 제일 작은애들 순으로 정렬

• 전체 원소의 개수가 N이고, 정렬하려는 부분의 키가 M일 때 복잡도 : O(NlogM)

stable_sort

원소가 삽입되어 있는 순서를 보존하는 정렬 방식

• sort 함수 : 정렬 과정에서 원소들 간의 상대적 위치를 랜덤하게 바꿈 / 최악의 경우에도 O(n log n)
• stable_sort : 그 순서를 처음에 넣었던 상태 그대로 유지 / 최악의 경우 O(n (log n)^2) 으로 조금 더 느림

원소 제거 (remove, remove_if)

원소를 제거하는 함수

remove

remove 함수는 원소의 이동을 수행하지, 실제로 원소를 삭제하는 연산을 수행하지는 X.
따라서, vector에서 실제로 원소를 지우기 위해서는 반드시 erase 함수 호출해야 함.

• 반복자 타입 ForwardIterator
  벡터, 리스트, set, map에서 모두 사용 가능
• 값이 딱 얼마로 정해진 원소 제거

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

remove_if

특정한 조건을 만족하는 원소 제거

vec.erase(remove_if(vec.begin(), vec.end(), is_odd()), vec.end());

세 번째 인자 = 조건을 설명할 함수 객체

template <typename Iter, typename Pred>
remove_if(Iter first, Iter last, Pred pred)

위와 같이 함수 객체로 실제 함수를 전달할 수 있으며, 이 경우 Pred가 함수 포인터 타입

remove_if에 조건 추가하기

C++ 표준에 따르면, remove_if에 전달되는 함수 객체의 경우 이전의 호출에 의해 내부 상태가 달라지면 안됨 = 함수 객체 안에 인스턴스 변수를 넣는 것 불가능

why?
해당 함수 객체가 여러번 복사될 수 있기 때문!

따라서, 인스턴스 변수(num_delete)를 객체 내부 변수가 아니라 외부 변수로 빼내어 이를 해결할 수 있음.

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

template <typename Iter>
void print(Iter begin, Iter end) {
  while (begin != end) {
    std::cout << "[" << *begin << "] ";
    begin++;
  }
  std::cout << std::endl;
}

struct is_odd {
  // num_delete를 포인터로 !
  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;
  }
};

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;
  int num_delete = 0;
  vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd(&num_delete)),
            vec.end());
  print(vec.begin(), vec.end());
}

람다 함수(lambda function)

람다함수 : 이름이 없는 함수 객체

[capture list] (받는 인자) -> 리턴 타입 { 함수 본체 }
[capture list] ( 받는 인자) {함수 본체} // return type 생략

일반적으로 위와 같은 형태를 가짐.

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

int i를 받고, bool 을 리턴하는 람다 함수를 정의한 것 !
리턴 타입을 생략한다면, 컴파일러가 알아서 함수 본체에서 return 문을 보고 리턴 타입을 추측

캡쳐 목록 (capture list)

캡쳐목록 사용 시, 람다 함수가 외부에서 정의된 변수를 사용할 수 있음
(본래 람다 함수도 함수이기 때문에 자신만의 scope를 가져 접근 불가)

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

template <typename Iter>
void print(Iter begin, Iter end) {
  while (begin != end) {
    std::cout << "[" << *begin << "] ";
    begin++;
  }
  std::cout << std::endl;
}
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 << "벡터에서 홀수인 원소 ---" << std::endl;
  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 : num_erased의 레퍼런스를 캡쳐함으로써 num_erased의 값을 수정 가능
• num_erased : num_erased의 복사본을 얻기 때문에, 형태는 const. 값 수정 불가능

클래스의 멤버 함수 내에서의 람다

class SomeClass {
  std::vector<int> vec;

  int num_erased;

 public:
  SomeClass() {
    vec.push_back(5);
    vec.push_back(3);
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(4);

    num_erased = 1;

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

위의 경우 num_erased는 일반 변수가 아니라, 객체에 종속되어 있는 멤버 변수이기 때문에 컴파일 불가능. 이를 해결하기 위해서 this 전달

캡쳐 리스트 사용 방법

• [this] : 클래스 멤버 함수에서는 this로 전달하여 멤버 변수 참조
• [] : 아무것도 캡쳐 안함
• [&a, b] : a 는 레퍼런스로 캡쳐하고 b 는 (변경 불가능한) 복사본으로 캡쳐
• [&] : 외부의 모든 변수들을 레퍼런스로 캡쳐
• [=] : 외부의 모든 변수들을 복사본으로 캡쳐

원소 수정하기 (transform)

원소를 수정하는 함수
특히, container 전체 혹은 일부를 순회하며 값을 수정하는 작업을 할 때 많이 사용

transform (시작 반복자, 끝 반복자, 결과를 저장할 컨테이너의 시작 반복자, Pred)

일반적으로 위와 같은 형태를 가짐.

transform(vec.begin(), vec.end(), vec.begin(), [](int i) { return i + 1; });

vec의 시작부터 끝까지 각 원소에 [] (int i) {return i + 1} 함수를 적용시킨 결과를 vec.begin() 부터 저장

+) 주의 : 값을 저장하는 컨테이너의 크기가 원래의 컨테이너보다 최소한 같거나 커야 함

원소를 탐색하는 함수(find, find_if, any_of, all_of 등등)

find_if

find 함수가 단순한 값을 받았다면 find_if 함수의 경우 함수 객체를 인자로 받아서 그 결과가 참인 원소들을 찾음

any_of

인자로 받은 범위안의 모든 원소들 중에서 조건을 하나라도 충족하는 것이 있다면 true 를 리턴

all_of

모든 원소들이 전부 조건을 충족해야 true 를 리턴