알고리즘(Algorithms) (1)

항목 30 : 알고리즘의 데이터 기록 범위는 충분히 크게 잡자

int transmogrify(int x);

std::vector<int> values;
...
std::vector<int> results;
std::transform(values.begin(), values.end(), results.end(), transmogrify);

위의 코드의 의도는 함수의 반환값을 results.end부터 삽입하라는 의미이다.

하지만 동작하지 않는다. 왜냐면 results.end()는 객체가 존재하지 않기 때문이다.

 

std::transform(values.begin(), values.end(), std::back_inserter(results), transmogrify);

대신 삽입 반복자를 사용한다. back_inserter는 push_back을 호출하도록 되어있기 때문에 push_back을 지원하는 컨테이너에만 사용할 수 있다.

back_inserter 말고도 front_inserter(앞에서 추가), inserter(임의 위치부터 추가)도 존재한다.

 

if (results.size() < values.size()) results.resize(values.size());

std::transform(values.begin(), values.end(), results.begin(), transmogrify);

만약 결과값을 기존 컨테이너에 덮어씌우고 싶다면 resize를 통해서 최소한의 크기는 확보하는게 안전하다.

혹은 results를 clear한 이후 삽입 반복자를 호출하면 된다.

 

결론적으로 목적지 범위를 지정하여 수행하는 알고리즘은 범위의 크기를 미리 확보하거나 자동으로 증가되도록 만들어야 한다.

 

 

항목 31 : 정렬시의 선택 사항들을 제대로 파악해 놓자

전체 정렬이 필요한 경우 sort, 전체 정렬을 하되 순서 유지성이 필요하면 stable_sort, 부분 정렬이 필요한 경우 partial_sort, 상위 값이 필요하되 정렬여부는 관계 없다면 nth_element를 사용하면 된다.

 

// 전체 정렬
std::sort(widget.begin(), widget.end(), qualityCompare);

// 전체 정렬 (순서 유지)
std::stable_sort(widget.begin(), widget.end(), qualityCompare);

// 부분 정렬 (상위 20개)
std::partial_sort(widget.begin(), widget.begin() + 20, widget.end(), qualityCompare);

// 상위 값 추출 (단, 지정된 반복자만 정렬 순서 보장. 이경우 widget.begin() + 20)
std::nth_element(widget.begin(), widget.begin() + 20, widget.end(), qualityCompare);

 

partial_sort, nth_element는 값이 동등관계인 경우 아무거나 골라낸다.

nth_element는 상위 n개의 요소를 찾아내는 것 외에 범위 내의 중앙값을 찾거나 특정한 백분위 위치에 있는 값을 찾아내는 데에도 사용할 수 있다.

 

다만 위의 알고리즘들은 임의 접근 반복자를 지원해주는 컨테이너에만(vector, deque) 사용이 가능하다. (list는 사용불가)

 

한가지 알고리즘이 더 있다. 컨테이너의 요소를 특정 조건을 기준으로 좌우로 분할한다.

 

bool hasAcceptableQuality(const Widget& w)
{
    // Widget 객체의 등급이 2등급 이상인지 판별
}

auto goodEnd = std::partition(widget.begin(), widget.end(), hasAcceptableQuality);

어떤 조건을 기준으로 조건을 만족한 값은 begin~goodEnd 사이에, 만족하지 못한 값은 goodEnd~end 사이에 위치하게 된다.

partition은 위의 알고리즘과 다르게 양방향 반복자 이상이면 사용할 수 있으므로 표준 시퀀스 컨테이너 모두에 대해 동작한다.

 

◾ 전체 정렬 (sort, stable_sort) : vector, string, deque, 배열

◾ 부분 정렬 (partial_sort) : vector, string, deque, 배열

◾ 상위 N개 요소 (nth_element) : vector, string, deque, 배열

◾ 기준에 따른 요소 구분 (partition, stable_partition) : 표준 시퀀스 컨테이너

 

partition -> stable_partition -> nth_element -> partial_sort -> sort -> stable_sort 순으로 성능이 점점 나빠진다.

 

 

항목 32 : 요소를 정말로 제거하고자 한다면 remove 류의 알고리즘에는 꼭 erase를 붙여 사용하자

remove는 이름과 달리 범위 내의 요소를 재배치할 뿐이다. 다만 삭제하기 원치 않은 요소들을 앞으로 당겨오며 덮어쓸 뿐이다.

대신 remove가 이루어지고 나면 새로운 end 반복자를 반환해주기 때문에 여기서부터 본래 반복자의 end까지를 erase 시켜주면 실제 의도한대로 삭제가 이루어진다.

 

v.erase(std::remove(v.begin(), v.end(), 99), v.end());

remove_if나 unique 역시 동일하게 동작하기 때문에 erase를 같이 써주어야한다.

 

예외적으로 list의 멤버 함수로 제공되는 remove, unique는 실제로 삭제가 이루어진다.

 

 

항목 33 : remove와 비슷한 알고리즘을 포인터의 컨테이너에 적용할 때에는 각별히 조심하자

동적 할당된 포인터를 별도의 해제 없이 erase-remove하게 된다면 remove에서 요소가 앞으로 당겨지며 덮어씌워질 때, 메모리 누수가 발생한다. 덮어 씌워진 포인터는 찾을 방법이 아예 없어진다.

대신 partition으로 나누고 뒷부분에 대해서 delete를 실행해준 뒤 erase를 하면 문제가 없을 것이다.

 

더 좋은 방법으로는 스마트 포인터를 사용하는 것이다. 딱히 고려할것도 없이 바로 erase-remove를 수행해도 된다.