더북(TheBook)

이외에도 다른 기준을 이용하여 원소를 비교하고 정렬하려면 이항 조건자(binary predicate)를 지정할 수 있습니다. 두 가지 형태의 sort() 함수 모두 선형 로그 시간 복잡도 O(nlogn)을 갖습니다. 다음 예제 코드는 두 형태의 sort() 함수 사용법을 보여줍니다.

std::forward_list<int> list1 = {23, 0, 1, -3, 34, 32};

list1.sort();   // {-3, 0, 1, 23, 32, 34} 순서로 바뀝니다. 

list1.sort(std::greater<int>()); // {34, 32, 23, 1, 0, -3} 순서로 바뀝니다.

앞 예제 코드에서 std::greater<int>는 표준으로 제공되는 비교 함수 객체이며, 결과 리스트에서 확인할 수 있듯이 원소를 내림차순으로 정렬하기 위한 > 연산자에 대한 래퍼입니다.

std::forward_list에서 제공하는 다른 멤버 함수로는 reverse()unique()가 있습니다. reverse() 함수는 저장된 원소의 순서를 역순으로 변경합니다. 이때 걸리는 시간은 리스트 원소 개수에 비례하며 시간 복잡도는 O(n)입니다. unique() 함수는 리스트에서 홀로 나타나는 원소는 놔두고, 인접하여 중복되는 원소에 대해서는 첫 번째만 남겨두고 나머지는 제거합니다. 이 함수는 두 원소가 같은지를 판단하는 방식에 따라 두 가지 형태로 제공됩니다. 하나는 인자가 없는 형태이며, 이때는 원소 타입의 등호 연산자를 사용하여 같은지를 판단합니다. 다른 하나는 bool 값을 반환하는 이항 조건자를 인자로 받으며, 이 조건자는 리스트 원소 타입의 인자를 두 개 받습니다. unique() 함수의 시간 복잡도도 선형 함수로 표현되는데, 이는 unique() 함수가 각각의 원소를 나머지 원소 전체와 비교하는 형태로 동작하는 것이 아님을 암시합니다. 실제로 unique() 함수는 서로 인접한 원소끼리 같은지를 판단하고, 만약 서로 같으면 앞에 있는 원소는 남기고 뒤의 원소는 제거합니다. 그러므로 리스트 전체에서 유일한 원소들만 남게 만들려면 먼저 리스트를 정렬한 후 unique() 함수를 사용해야 합니다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.