erase-remove idiom

remove

  • 지정한 값과 일치하지 않는 요소를 앞으로 이동시킴
  • 컨테이너 크기는 그대로 유지됨

erase

  • 컨테이너의 멤버 함수
  • 실제 컨테이너의 크기를 줄임

erase-remove idiom

  • 제거 대상 요소들을 remove로 뒤로 몰고, erase로 제거
  • vector처럼 연속된 메모리를 갖는 컨테이너에 가장 적합
  v.erase(std::remove(v.begin(), v.end(), 3), v.end());

ranges::remove (C++20)

  • 반환값은 반복자가 아닌, 삭제된 영역을 가리키는 범위 쌍
  std::vector v1{1, 3, 1, 3, 1, 3, 10, 3, 9, 3};
auto ret1 = std::remove(v1.begin(), std::next(v1.begin(), 7), 3);
v1.erase(ret1, std::next(v1.begin(), 7));

std::vector v2{1, 3, 1, 3, 1, 3, 10, 3, 9, 3};
auto ret2 = std::ranges::remove(v2.begin(), std::next(v2.begin(), 7), 3);
v2.erase(ret2.begin(), ret2.end());

algorithm vs member function

list에서 erase-remove idiom 비효율적 이유

  • remove 호출 시 직접 요소를 제거하는 멤버 함수가 더 효율적

원칙

  • 컨테이너에 동일한 이름의 멤버 함수가 있다면 그것을 사용

멤버 함수 존재 이유

  1. 반복자 요구 조건이 안 맞는 경우 (예: sort는 introsort(quick + heap)을 사용하는데, random access iterator가 없는 list는 다른 방식의 sort 필요)
  2. 멤버 함수가 내부 구조에 최적화되어 있어 더 효율적임

erase/erase_if (C++20)

erase를 할 때 vector와 list가 다른 불편함 해결

  std::vector v{1, 2, 3, 1, 2, 3};
std::list s{1, 2, 3, 1, 2, 3};

// v.erase(std::remove(v.begin(), v.end(), 3), v.end());
// s.erase(std::remove(s.begin(), s.end(), 3), s.end());
// s.remove(3);
auto cnt1 = std::erase(v, 3);
auto cnt2 = std::erase(s, 3);
  • erase-remove idiom을 대체함

transform 알고리즘 

  std::vector v1{1, 2, 3, 4, 5};
std::vector<int> v2;
std::vector<int> v3;

std::ranges::transform(v1, std::back_inserter(v2), square); // v2 : 1, 4, 9, 16, 25
std::ranges::transform(v1, v2, std::back_inserter(v3), add); // v3 : 2, 6, 12, 20, 30
std::ranges::for_each(v3, print);

알고리즘에 전달하는 함수

  • 일반 함수
  • 함수 객체
  • 람다 표현식 (지역 변수 캡처 가능)
  • 지역 변수 캡처의 장점때문에 함수 객체 / 람다 표현식 사용 권장
  sort(v, std::greater<int>{});
sort(v, std::greater{}); // ~C++ 17
sort(v, {});

Predicate (조건자)

  • bool 또는 bool로 변환 가능한 값을 반환하는 함수
  • find_if, remove_if 등에서 조건자로 사용
  find_if(v, [] (int n) { return n % 3 == 0; });
  • sort와 달리 find가 아닌 find_if인 이유: C++98에서는 같은 함수 이름으로 여러 템플릿 만들 수 없었음

Projection (C++20)

상황

Point 객체를 갖는 컨테이너에서 y가 3인 요소를 찾는 경우

방법

  1. find_if
  2. projection

Projection

알고리즘에서 요소 자체가 아닌 요소의 특정 멤버나 속성만을 기준으로 동작하도록 만드는 기능 대부분의 c++20 ranges에서지원

  std::ranges::algorithm(container, comparator, projection);

기존과 비교 

  1. std::sort(v.begin(), v.end(), [](const Point& a, const Point& b) {
    return a.y < b.y;
});

2. std::ranges::sort(v, std::less{}, &Point::y);

find 예시시 

  auto ret1 = std::ranges::find(v, 3, &Point::y);
auto ret2 = std::ranges::find(v, 3, &Point::get_y);