remove_if & erase-remove idiom

핵심 오해: remove_if는 erase가 아니다

remove_if가 실제로 하는 일

• remove_if는 요소를 지우지 않고, 남길 요소를 앞쪽으로 재배치합니다.
• 반환값은 new_end(유효 구간의 새 끝) 이터레이터입니다.
• 컨테이너 size()는 그대로입니다.

auto newEnd = std::remove_if(v.begin(), v.end(), IsOdd());
// 여기까지는 size 변화 없음

구간 의미

• [begin, newEnd) : 유효 데이터
• [newEnd, end) : 값은 남아 있을 수 있지만 논리적으로 제거 대상 구간

이 뒤 구간은 "사용하지 않는 구간"으로 보고, 보통 곧바로 erase로 잘라냅니다.

내부 동작 요약

• 스캔 포인터(next)가 앞으로 이동하며 "남길 요소"를 찾음
• 쓰기 포인터(first) 위치로 이동/대입하고 first++
• 결과적으로 "남길 요소의 상대 순서"는 유지됩니다(안정적)

remove_if 내부 동작 다이어그램

---

vector/deque/string: erase-remove idiom

필수 패턴

v.erase(std::remove_if(v.begin(), v.end(), IsOdd()), v.end());

• remove_if + erase는 세트로 기억합니다.
• 이 패턴을 빼먹으면 size가 줄지 않아 버그가 납니다.

람다 버전

v.erase(
    std::remove_if(v.begin(), v.end(), [](int n) { return n % 2 != 0; }),
    v.end()
);

복잡도 감각

• remove_if: O(N)
• erase(꼬리 구간 제거): 컨테이너 특성에 따라 추가 비용
• 전체적으로 보통 선형 시간에 가까운 패턴으로 동작

---

list는 멤버 remove_if를 우선 고려

std::list는 멤버 함수 remove_if가 있어 노드를 직접 제거할 수 있습니다.

std::list<int> lst{1, 4, 3, 5, 8, 2};
lst.remove_if([](int n) { return n % 2 != 0; }); // 실제 삭제

• list에서는 이 방식이 더 자연스럽고 의도가 명확합니다.
• 반면 vector는 멤버 remove_if가 없어서 erase-remove idiom을 사용합니다.

---

map / unordered_map은 별도 방식

• 연관 컨테이너(map, unordered_map)에는 erase-remove idiom을 그대로 적용하지 않습니다.
• C++20부터는 std::erase_if를 사용하면 깔끔합니다.

std::erase_if(mp, [](const auto& kv) {
    return kv.second <= 0; // 값이 0 이하인 항목 제거
});

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
remove_if만 호출하고 끝냄	size 미감소, 제거된 줄 알았던 요소가 남음
newEnd 이후 구간을 정상 데이터로 사용	논리 오류/중복 처리 버그
모든 컨테이너에 erase-remove 패턴을 동일 적용	list, map 계열에서 비권장/오해
Predicate에서 부작용 많은 로직 수행	디버깅 어려움, 의도 파악 저하

체크 질문 (스스로 답해보기)

• remove_if 반환값 newEnd는 무엇을 의미하는가?
• 왜 vector에서는 erase(remove_if(...), end())가 필요할까?
• list에서 보통 멤버 remove_if를 쓰는 이유는?
• map에서 조건 삭제를 깔끔히 처리하는 방법은?

---