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

전자: 알고리즘을 수행할 반복자의 시작점과 끝점 바로 뒤를 받음
후자: 반복자는 동일하게 받되, 특정 조건을 추가 인자로 받음(특정 조건: 서술자-Predicate).

Predicate 자리에는 보통 bool 값을 리턴하는 함수 객체(Functor)가 오게 됨.

정렬(sort, stable_sort, partial_sort)

• sort
• stable_sort
  -> 순서를 지킨 정렬. [a,b]순일 때, a==b인 경우 [a,b]로 순서 지킴
  -> sort보다 느림
• partial_sort
  -> 배열의 일부만 정렬

sort

sort는 기본적으로 오름차순으로 정렬해줌.
내림차순으로 정렬하고 싶으면 아래와 같이 functor를 사용해 비교를 어떻게 수행할 지 알려주면 됨.

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

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

참고: functional 헤더의 greater<int> 참고

partial_sort

100명의 학생 중 상위 10명 학생의 성적순을 보고 싶다
-> partial sort 사용

시간적 복잡도: O(NlogM)

이때 N개의 원소 중 M개만 순서대로 정렬하고 싶을 때, NlogM 만큼의 시간만큼으로 수행됨.
따라서 모두 다 정렬하는 일반 sort(NlogN) > partial_sort(NlogM) 임

stable_sort

stable_sort가 그냥 sort보다 시간이 더 걸림
최악의 경우 O(n(logn)^2)으로 작동함

원소 제거

remove

원소를 제거하는 함수 remove.

remove 함수는 해당 값 v만을 삭제하도록 돕는 함수로,
원소의 이동만을 수행하지 실제로 원소를 삭제하는 연산을 수행하지는 않음.

remove 함수가 끝나면 해당 값 v들을 뒤로 밀어버리고 밀어진 첫 v값 위치를 가리키는 반복자를 리턴함.

// erase 쓰는 방법
Iterator erase(Iterator first, Iterator last);
// remove 사용해서 erase 쓰기
vec.erase(remove(vec.begin(), vec.end(), 3), vec.end());

remove_if

세번째 인자로 조건을 설명할 함수 객체를 전달받음.

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

함수 객체 대신 실제 함수를 전달할 수도 있음 - 아래 참고.

bool odd(const int& i) {
  return i % 2 == 1; 
} 

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;
  vec.erase(std::remove_if(vec.begin(), vec.end(), odd), vec.end()); 
  print(vec.begin(), vec.end());
}

remove_if에 조건 추가하기

C++ 표준에 따르면, 함수 객체 안에 인스턴스 변수를 넣으면 안됨.
<- 해당 함수 객체가 여러번 복사될 수 있기 때문

그렇다면 어떻게 하면 상태가 필요한 조건을 성공적으로 추가할 수 있을까?
-> 외부 변수로 빼면 됨: 포인터!

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

람다 함수

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

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

// 리턴 타입을 생략할 경우
[capture list] ( 받는 인자) {함수 본체}

문제는 람다 함수 외부에서 정의된 변수들 사용 불가
(나름 함수라서 자기 자신만의 스코프를 가지기 때문)

=> 캡쳐 목록을 사용하면 됨

캡처 목록

어떤 변수를 캡쳐할 지 써주면 됨.
람다 함수 내에서 num_erased를 마치 같은 스코프 안에 있는 것처럼 사용할 수 있게 됨.

int main() { 
  std::vector<int> vec; 
  
  std::cout << "처음 vec 상태 ------" << std::endl; 
  print(vec.begin(), vec.end());
  std::cout << "벡터에서 홀수인 원소 2개 삭제---" << 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());
}

캡쳐 목록 사용법

• [this]: 클래스에서 멤버 함수에서는: this를 캡처 리스트로 전달하는 게 가장 이상적
• []: 아무것도 캡처 안함
• [&a, b]: a는 레퍼런스로 캡처, b는 변경 불가한 복사본으로 캡처
• [&]: 외부 모든 변수들을 레퍼런스로 캡처
• [=]: 외부 모든 변수들을 복사본으로 캡처

원소 수정하기(transform)

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

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

주의

값을 저장하는 컨테이너 크기 >= 원래의 컨테이너

그 외 함수들

find, find_if, any_of, all_of