sort()

#include <algorithm>

sort(first, last, /* compare_function */);

기능

• 비교 함수를 기준으로 범위 내 원소를 정렬한다. (기본값은 오름차순)

특징

• 비교 함수는 반환값이 false일 때 원소의 위치를 바꾼다.
• 시간복잡도: O(n log n)
• 일반적으로 Introsort(퀵정렬 + 힙정렬 + 삽입정렬)을 사용한다.
• compare(a, b)에서 a와 b는 비교를 위한 원소일 뿐, a와 b에 어떤 값이 올지는 순서가 보장되지 않는다.

unique()

#include <algorithm>

unique(first, last);

• 기능 : 연속으로 중복된 요소를 제거한다. (그렇기 때문에 꼭 정렬을 먼저 해야 한다.)
• 특징: 컨테이너 내 중복되는 원소들을 뒤로 밀어내 요소들을 실제로 이동시키며, 시간복잡도는 O(n)
• 반환값: 중복되지 않은 원소들만 남겨 새로운 범위의 끝을 가리키는 반복자를 반환한다.

erase()

#include <algorithm>

container.erase(first, last);

• 기능: first부터 last 바로 전까지의 요소를 제거한다.
• 특징: 제거된 요소 뒤의 모든 요소들이 앞으로 이동하며, 시간복잡도는 O(n)
• 반환값: 제거된 마지막 요소의 다음 위치를 가리키는 반복자를 반환한다.

중복 제거

bool compare(int a, int b) {
    return a > b;
}

vector<int> solution(vector<int> container) {
	// sort로 먼저 정렬
    sort(container.begin(), container.end(), compare);

	// unique로 중복 제거한 후의 새로운 위치부터 end까지 제거
    container.erase(unique(container.begin(), container.end()), container.end());
 
    return container;
}