Modern C++/Algorithm

[C++] 유용한 <Algorithm> 함수들 (1) (정렬, 파티셔닝, 탐색, 숫자)

dev-ohdam 2024. 11. 25. 17:17

 해당 게시글에선 C++에서 제공하는 Algorithm 함수 중 유용하다가 생각되는 것만 모아서 정리한 것이다.

더 많은 내용을 살펴보려면 cppReference.com을 방문해서 탐색해 보는 것을 추천한다.

 

1. 선수학습 내용

 알고리즘 함수를 다루기 이전엔 반드시 다음 사항을 미리 학습해야 한다.

   1) Iterator 

  Algorithm 함수들의 경우, 컨테이너 내부의 특정 범위의 요소에 대해서 다양한 기능을 제공하기 때문에, 이와 관련된 개념을 숙지해야 할 필요가 있다.

 

   2) Predicate

 Algorithm 함수들의 기능을 제대로 활용하기 위해선 (Ex std::sort의 정렬 기준을 바꾼다.) Predicate를 직접 작성해야 할 필요가 있다. 이와 관련되어 다룬 게시글이 있으니 한 번 읽어보면 좋다. 보편적으로 Lamda Expression을 사용한다.

 

   3) Inserter (Insert Iterator)

 Algorithm 함수의 경우, 어떠한 기능을 수행한 뒤, 목적지(Destination)에 그 결과를 분배하는 기능을 수행하는 경우가 있다.

이때 Inserter 객체들을 자주 넘겨주곤 한다. Inserter는 컨테이너의 종류에 따라 back_inserter, front_inserter 등 여러 형태로 생성할 수 있다. 해당 기능에 관한 자세한 내용은 직접 찾아보는 것이 좋다. 대충 이름에서 유추할 수 있듯이, 컨테이너에 원소를 삽입하는 것을 도와주는 객체들이다.

 

 

2. Algorithm Function Version

1) Algorithm Function - _copy 버전

 일부 알고리즘 함수를 살펴보면 OOO_copy의 형태를 띤 함수들을 볼 수 있다. 이런 경우 Algorithm 함수를 통해 변형된 결과를 다른 목적지에 저장할 수 있는 버전이라고 볼 수 있다. 이는 원본의 값을 유지하되, 변형된 결과를 따로 복사할 때 유용하게

활용한다.

 

 만약 본인이 사용하려고 하는 알고리즘 함수를 타이핑했을 때 _copy가 붙어있는 버전이 있는 경우, 대충 이런 의미구나라고

생각하면 된다. Ex)  std::replace_copy

 

2) Algorithm Function - _if 버전

 일부 알고리즘 함수를 살펴보면 OOO_if의 형태를 띤 함수들을 볼 수 있다. 이런 경우, Predicate를 활용해, 특정 조건에 만족할 때만 함수 기능을 수행하도록 설정할 수 있다.

 

 만약 본인이 사용하려고 하는 알고리즘 함수를 타이핑했을 때 _if가 붙어있는 버전이 있는 경우, 대충 이런 의미구나라고

생각하면 된다. Ex) std::copy_if

 

3) Algorithm Function - _n 버전

 일부 알고리즘 함수를 살펴보면 OOO_n의 형태를 띤 함수들을 볼 수 있다. 이런 경우, 전체가 아닌 임의의 N개만큼의 요소에 관해 조작할 수 있는 함수들이다.  그렇기 때문에 보통 범위를 줄 때, Fisrt만 준다.(First 기준으로 N개만큼 동작을 수행) 그리고 N의 값을 인자로 받는다.

 

 만약 본인이 사용하려고 하는 알고리즘 함수를 타이핑했을 때 _n가 붙어있는 버전이 있는 경우, 대충 이런 의미구나라고

생각하면 된다. Ex) std::search_n, std::generate_n...

3. Algorithm Function vs  Container Member Fucntion

 아마 이 부분에 관련해서 궁금한 학습자도 있을 것이다. Container를 활용하다 보면 알고리즘 함수가 동일한 기능을 제공하는

멤버 함수들이 간혹 존재한다. Ex) unique, find 등등

 그렇다면, 둘 중 어느 것을 사용하는 것이 더 좋은가?, 과연 퍼포먼스적으로 큰 차이점이 있는가? 등의 의문이 들 수 있다.

 

이 부분에 관해 Udemy의 C++ 언어의 강사에게 질문을 해보았다. 그 결과, 다음과 같은 답변을 받았다.

Udemy에서 Modern C++ 를 강의하는 강사 James

 

 

 결론을 말하면 둘 다 충분히 빠르기 때문에 성능 차이가 크지 않다만, list operation(삽입, 삭제, 탐색, 병합, 분할 등)

의 경우에는, 알고리즘 함수보다 더 빠르게 동작하는 컨테이너 멤버 함수를 사용한다고 한다. 

 

 필자의 생각으론, 유의미한 퍼포먼스 차이가 없다면 코드의 가독성을 위해, 모두 알고리즘 함수로 작성하는 것도 나쁘지 않은

선택인 것 같다.

4. Const-Range vs Range

 알고리즘 함수를 사용할 땐 Range(_First, _Last)를 인수값으로 넘겨주는 경우가 많다. 이때 어떤 예시에선 begin(), end()를 사용하는 반면. 어떤 예시에선 cbegin(), cend()와 같은 Const-Range을 넘겨주기도 한다. 이는 무슨 차이일까?

 

 사실 둘 중 어느 값을 주던 큰 차이는 없다. 하지만 일부 Write 작업을 수행하는 기능들은(std::transform...) Const-Range를 인자로 주면 컴파일 에러가 발생한다. 그렇기 때문에, 본인이 활용하고자 하는 알고리즘 함수의 기능을  제대로 숙지해야

한다.

 

또한, 코드의 의미를 좀 더 명확하게 하기 위해서 이 둘을 구분 짓는 것이 학습에 큰 도움이 된다.

Read 작업을 수행하는 경우에는 cbegin(), cend()를 활용하는 것이 더 명확하다. 왜? 해당 범위 내의 원소를 수정할 일이 없기 때문이다.

 

 예를 들어 원본값을 Copy 하는 작업을 수행하는 경우, 원본 값에는 Read 작업만 수행하고, Write 작업이 없기 때문에 cbegin(), cend()를 주어주는 것이 좀 더 적절하다. 아래 주요 알고리즘 함수를 사용한 예시를 살펴볼 때, 이 점을 주목해서 살펴보면 도움이 될 것이다.

 

5. Major Algorithm Function

1) Searching Algorithm

범위 내에서 특정 조건에 맞는 값들을 탐색할 때, 이 알고리즘 함수들은 많은 도움이 된다.

std::find_first_of(Range1 , Range2)

 이름에서도 추측할 수 있듯이 어떠한 조건에 맞는 요소를 탐색할 때, 그 첫 번째 값의 Iterator를 반환해 주는 함수이다. (존재하지 않는다면 end()를 반환한다.)  이때, std::distance 같은 함수를 활용하면, index 또한 구할 수 있다. 여기서 range1는 탐색의 대상이 되는 범위, range2는 탐색하고자 하는 값들의 범위를 나타낸다. 

 

예를 들어, 특정 문장에 영어 모음이 포함되는 것을 탐색하고, 첫 번째 요소의 위치를 반환하는 코드를 작성하면 아래와 같을 것이다.

string dest{"hello my name is dev.oh"};
string vowel{"aeiou"};

auto firstVowelIter = std::find_first_of(cbegin(dest),cend(dest),cbegin(vowel),cend(vowel));

// 이 함수는 탐색을 수행하는 것이기 때문에 , const-range로 인자를 넣었다.
// firstVowelIter 는 'i'이다.

std::cout << "first vowel elements is" << *firstVowelIter << "\n";
std::cout << std::distance(begin(dest),firstVowelIter) << "\n"; // index 구하기

 

std::OOO_of(Range, predicate) 시리즈

  all_of, any_of, none_of 이 세 함수 또한 범위 안에 predicate에 만족하는 값들의 존재여부를 파악할 때 편하다.

 이 함수들은 모두 boolean 값을 반환한다.

 

  • all_of: 모든 원소가 predicate를 만족하면 true 아니면 false
  • any_of: 원소 중 하나라도 predicate를 만족하면 true 아니면 false
  • none_of: 모든 원소가 predicate를 만족하지 않으면 true 아니면 false

 

아래 코드는 range에 속한 요소 중 홀수인 값이 존재하는지 그 여부에 관해 출력하는 예시 코드이다.

	auto is_odd = [](auto n) {return n % 2 == 1; };
	cout << boolalpha << "all of odd: " << all_of(range1.begin(), range1.end(), is_odd) << "\n";
	cout << "any of odd: " << any_of(range1.begin(), range1.end(), is_odd) << "\n";
	cout << "none of odd: " << none_of(range1.begin(), range1.end(), is_odd) << "\n";

 

std::mismatch(Range1, Range2)

 이 함수는 두 범위에 속한 값들을 순차적으로 비교해 나가며, 일치하지 않는 요소를 발견하면 해당 위치를 반환한다.

이때 pair의 형태로 반환되며 first에는 range1의 위치, second에는 range2의 위치가 들어있다.

 

아래 예시는 두 문자열을 비교하며 틀린 위치를 반환받는 코드이다. Bind 개념을 활용해 auto 키워드와 []를 통해 pair 객체를 다음과 같은 형태로도 대입받을 수 있다. 

string str1{"abcde"};
string str2{"abcfed"};

auto [iter1, iter2] = std::mismatch(cbegin(str1),cend(str1), cbegin(str2), cend(str2));

 

std::search(Range1, Range2) & std::search_n(Range1, Count, Value)

 두 함수 모두 한 탐색 범위 안에 서브시퀀스가 존재하는지 파악하는 함수들이다.

 

 std::serach은 range1 안에 range2의 요소가 등장하는 위치를 반환해 주는 함수이다. 이때 range2는 range1에서 탐색하고자

하는 부분 탐색 대상이 된다. Ex range1 ==> "abcde", range2 ==> "ab" 이때 이 함수가 반환하는 곳은 0 번째 위치이다.

string str{"my name is ohsd"};
string substr{"name"};

auto iter = search(cbegin(str), cend(str), cbegin(substr), cend(substr));
cout << distance(begin(str),iter);

// my name is ohsd의 부분 탐색 대상인 name은 4번 인덱스부터 등장한다.

 

std::search_n은 range1 안에 N개의 targetValue가 연속된 위치를 반환해주는 함수이다.

count는 연속된 값의 개수, targetValue는 찾고자 하는 값을 나타낸다. 예를 들어 1,2,2,3,3,3,4,4,5,5,5,5,6의 값이 범위 내에 존재한다고 가정했을 때, targetValue = 5, count = 4로 주어지면, 연속된 4개의 5가 존재한 위치를 반환하는 것이다.

 

std::vector<int> range{1,2,2,3,3,3,4,4,5,5,5,5,6,6};

auto iter = std::search_n(cbegin(range),cend(range),4, 5);
std::cout << std::distance(begin(range),iter); // 8

 

정렬된 범위와 함께 활용하는 함수 std::binary_search(Range, Value) & std::include(Range1, Range2)

std::binary_search와 std::include 모두 정렬된 범위와 함께 활용하는 함수이며 bool 값을 반환한다.

 

 std::binary_search는 우리가 잘 알고 있는 이진 탐색의 기능을 함수의 형태로 제공한다. 당연히 앞에서부터 순차 탐색을 수행하는 std::find보다 훨씬 빠른 속도로 탐색할 수 있다. (logN)

 

 std::include는 std::search와 유사한 느낌이 들지만 사용 목적과 조건이 다르다. std::include는 말 그대로 Range2의 범위가

Range1에 포함되는지를 확인하는 함수로 bool 값을 반환한다. 또한 정렬된 범위를 제공해야 한다는 점에서 std::search와 차이점이 존재한다.

 

std::vector<int> range1 {1,2,3,4,5};
std::vector<int> range2 {2,3,4};

auto retval = std::binary_search(cbegin(range1),cend(range1), 5); // true
auto retval2 = std::include(cbegin(range1),cend(range1),cbegin(range2),cend(range2)); // true

std::cout << std::boolalpha << retval << " " << retval2 << "\n";

 

 

2) Copying Algorithm

한 범위의 값들을 다른 장소로 복사할 때 사용하는 알고리즘 함수이다.

대표적인 함수로 std::copy가 있다. 그리고 해당 함수의 다른 버전인 std::copy_if, std::copy_n이 있다.

 

Copy 시리즈

  • std::copy(Range, Dest)

기본 버전이다. Range의 원소를 Dest에 복사한다.

Dest에는 Range를 충분히 포함할 수 있는 크기의 컨테이너 혹은 Inserter 객체가 들어간다.

  • std::copy_if(Range, Range, Predicate)

std::copy와 동일한 기능을 수행하지만 Predicate에 만족한 요소만 복사한다.

Predicate는 Range의 요소를 인자로 전달받는다.

  • std::copy_n(Range First, Count, Dest-Range)

std::copy와 동일한 기능을 수행하지만 n개의 요소만 복사한다.

std::vector<int> source{1,2,3,4,5};
std::vector<int> dest(source.size());
std::vector<int> empty_dest;


std::copy(cbegin(source),cend(source),dest); // {1,2,3,4,5}

std::copy_if(cbegin(source), cend(source), back_inserter(empty_dest), [](auto n) {
return n % 2 == 1
}); // {1,3,5}

std::copy_n(cbegin(dest), 2, std::back_inserter(empty_dest)); // {1,3,5,1,2}

3) Merge Algorithm

      

 말 그대로 두 범위 내의 요소를 병합할 때, 사용하는 알고리즘 함수이다.

이때 두 범위는 모두 정렬되어 있어야 하며, merge 한 결과물 또한 정렬된 형태를 띤다. 집합 이론을 기반으로 하여 구현된 함수들이다. 대표적으로 std::merge, std::set_intersection, set_union 함수가 있다. predicate에서 비교 연산을 수행하여 정렬 순서를 판단하거나, 동일한 원소인지 판별한다.

 

std::merge(Range1, Range2, Dest, +@ Predicate)

vector<int> range1{1,2,3,4};
vector<int> range2{1,5,6,7};

vector<int> result;
std::merge(cbegin(range1), cend(range1), cbegin(range2), cend(range2),back_inserter(result));

 

 std::merge는 두 범위에 해당하는 요소들을 병합하여 dest에 분포시키는 함수이다. (기본적으로 오름차순 정렬이다.)

dest의 경우 range1과 range2를 모두 담을 수 있는 크기의 컨테이너 혹은 back_inserter를 넘겨준다.

predicate를 통해 조건에 맞는 요소만 병합할 수도 있다. 이때 predicate는 2개의 매개변수를 가진다.

 

해당 코드의 결과는 {1,1,2,3,4,5,6,7}이 된다.

 

아래는 두 범위 내에서 홀수 요소만 병합하는 predicate를 작성한 것이다.

a는 range1의 요소 b는 range2의 요소이다.

std::merge(cbegin(range1), cend(range1), cbegin(range2), cend(range2), back_inserter(result)
[](auto a, auto b) {
	if(is_odd(a) && is_odd(b)) return a < b;
    else if (is_odd(a)) return true;
    else if (is_odd(b)) return false;
});

 

std::set_intersection(Range1, Range2, Dest, +@ Predicate) : 집합 이론(교집합)

std::set_intersection(cbegin(range1),cend(range1), cbegin(range2),cend(range2), std::back_inserter(result));

 

 std::set_intersection은 두 범위에 해당하는 요소 중 양쪽 범위에 모두 속하는 요소(교집합)를 dest에 분포시키는 함수이다.

마찬가지로 predicate를 통해 결괏값을 조정할 수 있다. 매개변수는 merge와 동일하게 2개가 필요하다.

 

해당 코드의 결과는 {1}이 된다.

 

std::set_union(Range1, Range2, Dest, +@ Predicate) : 집합 이론(합집합)

std::set_union(cbegin(range1), cend(range1), cbegin(range2), cend(range2), back_inserter(result));

 

 std::set_union은 std::merge와 기본적으로 동일한 기능을 수행한다. 다만 std::merge는 중복된 요소도 포함하는

반면, std::set_union은 중복 요소를 제거한다. 마찬가지로 predicate를 통해 결과값을 조정할 수 있다. 매개변수는

merge와 동일하게 2개가 필요하다.

 

해당 코드의 결과는 {1,2,3,4,5,6,7}이 된다.

 

4) Writing - Algorithm

 이 함수들은 특정 범위 내의 요소들을 변환하거나 Write 작업을 수행하는 함수들이다.

컨테이너에 원소를 채우는 것뿐만 아니라, 이미 채워진 요소를 변형하는 작업도 가능하다.

 

당연하게도, 요소를 변형시켜야 하기 때문에, 보편적으로 const-Iterator가 아닌 Iterator를 사용한다.

 

std::fill(Range, Value) & std::fill_n(Range (or Inserter), Count, Value)

 std::fill과 std::fill_n은 컨테이너에 동일한 값을 채워 넣을 때 활용하는 함수이다. std::vector같은 경우 생성자에 매개변수 값을 주어 std::fill과 동일한 기능을 수행할 수 있다. std::fill의 특수 버전인 std::fill_n의 경우 채우고자 하는 요소의 갯수를 지정할 수  있다. 값을 채워넣을 Range와 Value값을 인자로 받는다.

 

  해당 함수의 결과로는 마지막 원소의 Iterator를 반환한다.

(Inserter를 Range로 주었다면, Inserter를 반환한다.) 

std::vector<int> vec1(10, 42); // 42값으로 채워넣기

for(auto i : vec1) cout << i << " ";
cout << "\n";

std::vector<int> vec2(10);
auto iter = std::fill(begin(vec2),end(vec2),42); // 동일한 결과
auto bInserter = std::fill_n(back_inserter(vec2), 5, 100) // 이후 5개의 값을 100으로 추가하기

for(auto i : vec2) cout << i << " ";
cout << "\n"

 

std::generate(Range, Predicate) & std::genreate_n(Dest-Range, Count, Predicate)

 std::fill이 value를 통해 값을 채워 넣는다고 하면, std::generate의 경우 predicate를 활용해 내가 원하는 연산을 적용하여

채워 넣을 수 있다. 이때, 좀 더 다채로운 조작을 위해 mutable과  capture를 활용하면 좋다.

 

 std::generate_n은 앞서 설명한 OOO_n 함수와 마찬가지로, std::generate와 동일한 기능을 하면서 일정 개수만큼 원소를 채워 넣을 수 있다. 아래 코드는 원소를 2n과 n^2 형태로 채워 넣는 예시를 작성한 것이다.

vector<int> genVec1(5);
auto n = 0;

std::generate(begin(genVec2),end(genVec2),[n]() mutable { 
++n;
return n + n;
}); // 2, 4, 6, 7, 10



vector<int> genVec2;
std::generate_n(back_inserter(genVec2),5,[n]() mutable { 
++n;
return n * n;
}); // 1 4 9 25 36

 

Replace 시리즈

 std::replace는 꽤 많은 버전을 가지고 있다. 하지만 어려워할 필요 없다. 앞서 언급했던 _copy, _if 버전의 의미를 잘 기억하고 있다면 아주 쉽게 해석할 수 있다. 우리는 std::replace의 핵심 기능만 이해하면 그만이다.

 

 Replace 함수는 이름에서도 유추할 수 있듯이 특정 원소를 다른 새로운 값으로 대체하는 상황에서 사용하는

알고리즘 함수이다. 보통 문자열과 함께 사용한다. 

 

  • std::replace(Range, TargetValue, NewValue)

  Range에 속한 값들 중 TargetValue에 해당하는 값들을 모두 NewValue로 대체한다.

당연히 범위 안의 값에 Write 동작을 수행하기 때문에 const-Range를 주어선 안된다.

 

  • std::replace_copy(Range, TargetValue, NewValue, Dest)

 _copy는 어떤 버전이다? 해당 함수를 적용한 결과를 다른 곳에 채우는 버전이라고 언급했다.

당연하게도 마지막 매개변수에 Dest가 추가된 것을 볼 수 있다.

 

  • std::replace_if(Range, NewValue, Predicate)

 _if 버전이니 굳이 설명하지 않더라도 알 수 있을 것이라고 생각된다. 

Predicate에 부합하는 원소를 새로운 값으로 대체하는 기능을 수행한다.

 

  • std::replace_copy_if(Range, NewValue, Dest, Predicate)

_copy 버전과 _if 버전을 합친 것이다. 아마 설명하지 않더라도 충분히 알 수 있다고 생각한다.

 

std::string str {"banana"};

cout << "Original String: " << str << "\n";
std::replace(begin(str),end(str),'a','x'); 
// bxaxnx
std::replace_if(begin(str), end(str),'z' ,[](auto c) { return c == 'n';}) 
// bxaxzx
cout << "After Replace: " << str << "\n";


std::string orignal{"original"};
std::string copied;
cout << "Original String: " << original << "\n";
std::replace_copy(cbegin(str),cend(str), 'i','c', back_inserter(copied)); 
// copy 버전은 원본값을 read만 수행하고 변형된 결과를 다른 저장소에 복사하기 때문에 
// Range를 const-Range로 주어도 무방

cout << "After Replace Copy Original: " << original << "\n" // original
cout << "Copied String: " << copied << "\n"; // orcgcnal

std::transform(Range1, +@Range2, Dest, Predicate)

 std::transform도 많이 사용하는 Write Algorithm 함수이다. 이름에서 알 수 있듯이 Range에 속한 원소를 Predicate를 사용해 변환하여 Dest에 채우는 기능을 수행한다. Dest는 내가 해당 결과를 저장하고자 하는 새로운 컨테이너가 될 수도 있고 원본이 될 수도 있다. 

 

 std::transform의 경우 동일한 길이의 Range를 여러 개 받을 수도 있다. 이 경우, Predicate에 매개변수가 하나 더

추가된다.  이를 활용하면 내적(Inner Product) 계산을 구현할 수도 있다.

 

vector<int> nums {1,2,3,4,5};
vector<int> square;

std::transform(cbegin(nums),cend(nums), back_inserter(square), [](auto n) {
return n * n;
});

for(auto i : square) cout << i << " "; // 1, 4, 9, 16, 25


// inner product
vector<float> xmf3 {1.0, 2.0, 3.0};
vector<float> xmf3_2 {0.1, 0.1, 0.1};
vector<float> dest;

float result = 0.f;

std::transform(cbegin(xmf3),cend(xmf3), cbegin(xmf3_2), cend(xmf3_2), back_inserter(dest), [](auto a, auto b){
 return a * b;
});

result = std::accumulate(cbegin(dest), cend(dest));  // a1b1 + a2b2 + a3b3;

 

5) Sorting Algorithm

 명칭에서도 알 수 있듯이 특정 범위 내 요소를 정렬할 때 사용하는 알고리즘 함수들이다.

 

 대표적인 정렬 알고리즘 함수인 std::sort는 내가 정렬에 대한 개념이 부족할 때도 사용했던 함수다. 그만큼 유명한 함수라는 것이다. std::sort는 혼합 정렬 알고리즘으로 삽입정렬와 힙정렬를 혼합하여 구현했다. 그 덕분에 평균 시간복잡도가

O(NlogN)이라는 어마무시한 성능을 자랑한다.

 

std::sort(Range, +@ Predicate)

 하지만 std::sort는 불완전한 정렬을 띤다. 불완전 정렬? 완전 정렬? 이게 도대체 무엇인가?

라고 하면, 동일한 값에 관해 정렬을 수행할 때, 기존의 입력 순서가 보장되지 않을 수 있음을 의미한다.

 

다소 이해하기 어려운 표현인데, 예시를 한번 들도록 하겠다.

Key-Value로 이루어진 구조체가 있다고 가정하자. Key는 정렬 기준이되는 정수, 그리고 Value는 입력 순서값을 담고 있다.

 

 Input -> {1,0}, {2,1}, {1,2} 가 존재할 때, 우리가 생각하는 완전한 정렬은 {1,0}, {1,2}, {2,1} 일 것이다. 

하지만 std::sort를 통해 정렬하면 {1,2}, {1,0}, {2,3} 의 형태로 정렬될 수가 있다.

다만 모든 상황에서 그렇게 적용되는 것은 아니고, 그럴 가능성이 있다는 것이다.

 

아마 적은 수의 예시로는 크게 확인할 수 없을 것이다.

노란색: 정렬 전 / 파란색: stable_sort / 초록색: sort

 

std::stable_sort(Range, +@ Predicate)

 그래서 이를 보완한 함수인 std::stable_sort가 추가적으로 제공되는데, 당연하게도 추가적인 기능이 들어간 만큼,

퍼포먼스는 좀 더 안좋은 편이다.

 

 위 두 함수는 매개변수는 비교적 간단하다. 정렬하고자 하는 범위와 그 정렬 기준을 추가적으로 제시해주면 된다.

기본적으로는 오름차순 정렬이기 때문에, 따로 Predicate를 구현하거나, greater<type> 과 같은 C++ Libarary에서 제공하는 Functor 객체를 이용하면 된다. Predicate는 보통 < 연산자를 활용해 구현한다. 

 

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

std::sort(begin(v1),end(v1),less<int>{});    // 오름차순 생략 가능
std::sort(begin(v1),end(v1),greater<int>{}); // 내림차순


// key: 정렬 기준
// value: 기존 index
std::vector<std::pair<int,int>> v2 {{1,0},{2,1},{1,2},{3,3}};

std::sort(begin(v2), end(v2),less<int>{});
for(auto &[key, value] : v2 ) cout << key << " : " << value << "\n"; 

std::stable_sort(begin(v2), end(v2),less<int>{});
for(auto &[key, value] : v2 ) cout << key << " : " << value << "\n";

 

std::partial_sort(Range-First, Pivot , Range-End) 

 std::sort가 모든 원소를 정렬한다면, 일부분만 정렬하는 부분 정렬 함수도 존재한다. 당연히 모든 원소를 정렬하는 것이

아니기 때문에 퍼포먼스가 훨씬 좋다! O(NlogK) (K가 정렬할 원소의 개수)

 

 std::partial_sort는 std::sort와 다르게 Pivot을 인자로 받는다.

Pivot은 보통 Range-First + N(정렬하려는 원소의 개수 ) 로 표현된다.

_copy 버전도 존재하기 때문에,(std::partial_sort_copy) 원본값을 유지하면서 정렬된 결과를 다른 곳에 복사할 수도 있다.

 

 아래 예시 코드를 보면 이해하기 쉬울 것이다.

std::vector<int> nums {3,1,2,4,5,6,9,7};
std::partial_sort(begin(nums), begin(nums) + 5,end(nums)); // 5 인덱스 까지 정렬한다.

for(auto i : nums) std::cout << i << " ";
cout << "\n";

std::string str{"qwertyuiopasdfghjklzxcvbnm"};
std::partial_sort(begin(nums), begin(nums) + 10,end(nums)); // 10 인덱스까지 정렬한다.

std::cout << str.substr(0,10); // abcdefghijk

 

std::nth_element(Range-First, Nth Rank, Range-End, +@ Predicate) 

 std::nth_element는 원리를 이해하는데 좀 오래 걸렸다. std::nth_element는 std::partial_sort와 마찬가지로 부분 정렬

알고리즘(퀵셀렉트)을 적용한 함수이다. Predicate에는 std::sort와 마찬가지로 정렬 기준을 나타내는 Functor가 들어간다.

 

 그냥 std::sort를 호출한 후에 n번째 인덱스로 접근하면 안되는 것인가? 라고 생각할 수 있다.

하지만 해당 범위의 N번째 값을 알아낼 때, 굳이 모든 요소에 대해서 정렬을 수행할 필요가 있을까?

전혀 그럴 필요가 없다. 해당 N번째 값이 제대로 위치할 때까지만 정렬하면 그만이다.

 

 이러한 특성 때문에 std::nth_element는 해당 Nth Rank에 적절한 값이 들어간 이후에는 정렬을 수행하지 않는다.

그리고 부분 정렬 알고리즘을 활용하기 때문에 Range의 범위가 꼭 전체가 아니더라도 부분 범위 내에서도 Nth Rank값을 구하는 것이 가능하다. Nth Rank의 경우 Range-First + N 의 형태로 표현된다. 

 

 아마 말로 설명하면 잘 와닿지 않을테니 직접 예시를 들어주도록 하겠다.

std::vector<int> num {30, 20, 60, 50, 70, 10, 80, 40};
std::nth_element(std::begin(num), std::begin(num) + 1, std::begin(num) + 3);
for(auto i = 0; i < 4; ++i) std::cout << num[i] << " ";

 

 해당 코드에서 std::nth_element에 주어진 인자를 잘 살펴보면 0번 인덱스부터 3번 인덱스까지의 범위를 주어진 것을 알 수 있다.

그리고 Nth-Rank에는 begin(num) + 1이 들어가 있으므로 해당 범위에서 2번째로 작은 값이 정렬될 때까지만 정렬을 수행하게 될 것이다.

 

 주어진 범위에 해당하는 값은 30, 20, 60 ,50 이다.

이 범위 안에서 1번 인덱스에 들어와야할 적절한 값은 30이다. (30,20,60,50 중 두 번째로 작은 값이 30이기 때문.)

 

 그리고 정렬을 수행하고 나면 위 그림과 같이 될 것이다. 60과 50은 이미 N번째 값을 적절하게 배치했기 때문에 정렬할

필요가 없다. 다음은 출력 결과이다. 위에 그림과 동일한 결과가 나왔음을 알 수 있다.

출력 결과

 

  별로 어려워보이지 않는 이 함수를 필자가 해당 함수를 이해하는데 다소 시간이 걸린 이유는 다음과 같다.

의도된 결과인진 모르겠으나, 전체 범위를 주어줬을 땐, 모든 원소가 정렬되는 현상이 있었다. 이는 퀵셀렉트 방식 외에 내부적으로 어떤 추가적인 정렬이 수행되는지 잘 모르기 때문에 정확한 원인을 파악하진 못했다. 이를 알게됐을 경우 추후에 갱신하도록 하겠다.

 

6) Numeric Algorithm

 Numeric(숫자) 알고리즘 함수들은 어떤 최댓값, 최솟값, 혹은 누적값 등 숫자와 관련된 다양한 연산을 수행할 때 사용되는 함수들이다. <algorithm> 헤더 외에도 <cmath> 나 <numeric> 헤더에서도 다양한 기능을 제공하기 때문에 필자가 소개한 함수 외에도 직접 찾아보는 것을 추천한다.

 

std::accumulate(Range, StartValue) , std::reduce(Parallel Policy, Range, StartValue)

 std::accumulate와 std::reduce는 동일한 동작을 수행한다. 바로 주어진 범위의 누적합을 반환한다는 것이다.

이는 위의 예시코드에서도 활용했었던 함수로, 내적 계산을 구현하기 위해서 std::transform과 std::accumulate를 활용했다.

 

 이때, std::reduce는 C++17에서 새로 추가된 함수로 병렬 처리를 제공한다는 점에서 더 고급기능을 지원한다.

그렇기 때문에, 첫 번째 인자에 병렬 정책이라는 flag 값을 추가적으로 넘겨준다. 보편적으로 std::execution::par을 사용한다.

 

반면, std::accumulate는 오래된 함수(C++98)로, 해당 연산을 순차적으로 처리한다. (1, (1 + 2), (1 + 2) + 3 ....)

 

 이 두 함수의 퍼포먼스를 시간을 통해 비교해보는 것도 좋은 학습 방법일 것같다. 직접 짜기 귀찮다면, cppReference에서 이를 제공하니 한번 살펴보는 것도 좋다.

 

또한 추가적으로 std::reduce와 관련된 함수 중 std::transform_reduce가 존재하는데, 이도 마찬가지로 병렬처리를 지원하면서, std::transform보다 더 유연하게 동작한다. 이 함수에 관한 설명은 아래에서 좀 더 자세하게 언급하겠다.

std::vector<int> v{1,2,3,4,5};
auto acc = std::accumulate(cbegin(v),cend(v),0);
auto par_acc = std::reduce(std::execution::par, cbegin(v),cend(v),0);

std::cout << acc << " " << par_acc << "\n" // 둘 다 똑같이 15를 반환한다.

 

std::inner_product(Range1, Range2, StartValue, +@ Predicate1, +@ Predicate2)  &

std::transform_reduce(Parallel Policy, Range1, Range2, StartValue, Predicate1, Predicate2)

 

 std::inner_product는 이름에서도 알 수 있듯이 내적값을 구할 때 유용하게 활용되는 알고리즘 함수로 C++98부터 제공된 오래된 함수이다. std::transform_reduce는 C++17부터 등장한 함수로, std::inner_product보다 좀 더 유연하게 동작하며, 병렬 처리 기능까지 제공하는 상위호환 함수라고 볼 수 있다.

 

 두 함수 모두 두 범위를 인자로 받는다. 이때 주의해야할 점은 이 두 함수는 Predicate에서 Range1과 Range2의 원소를 1:1 대응하여 연산을 수행하기 때문에 두 범위의 길이는 동일해야한다.

 

 그리고 총 2개의 Predicate를 받는데, 각각의 Predicate의 목적은 아래와 같다.

  • Predicate1 : Accumulate
  • Predicate2 : Transform

 

 Predicate1는 Predicate2에 의해 변형된 결과값을 어떤 방식으로 합산할 것인가에 관한 함수 객체이다.

std::inner_product의 경우, 디폴트값은 std::plus<> 이다.

 

 Predicate2는 두 범위에 해당하는 요소를 어떤 식으로 연산할 것인가에 관한 함수 객체이다.

std::inner_product의 경우, 디폴트값은 std::multiplies<> 이다.

 

 두 함수를 모두 활용해서 내적 연산을 수행하는 코드를 작성해보겠다.

std::vector<int> xmi3_a{1,2,3};
std::vector<int> xmi3_b{4,5,6};

auto retval = std::inner_product(std::cbegin(xmi3_a),std::cend(xmi3_a),std::cbegin(xmi3_b), 0);

auto retval2 = std::transform_reduce(std::cbegin(xmi3_a),std::cend(xmi3_a),std::cbegin(xmi3_b), 0
,std::plus<int>{},std::multiplies<int>{});


auto retval3 = std::transform_reduce(std::cbegin(xmi3_a),std::cend(xmi3_a),std::cbegin(xmi3_b), 0
[](auto sum, auto next) {return sum + next;}, [](auto a, auto b) { return a * b;});

 retval, retval2, retval3 모두 동일한 값을 가지며, 그 동작 방식도 모두 동일하다.

retval3는 std::plus<>와 std::multiplies<> Functor를 람다로 표현한 것이다.

 

 그렇다면 둘 중 어느 것을 사용해야하는가? 라고하면, 간단한 내적 계산을 수행하는거면 std::inner_product를

사용하는 것이 좀 더 명확할 것 같고, 추가적인 연산이나 계산이 필요하거나, 병렬 처리 기능이 요구되는 경우, std::transform_reduce를 활용하는 것이 더 명확할 것 같다.

 

 std::inner_product도 Predicate를 커스터마이징해서 어느정도 유연성을 보장하지만, 함수 명칭 자체가 내적을 의미하기 때문에, 적절하진 않다고 생각한다.

 

 그 외에도 std::min, std::max, std::max_element, std::min_element, std::minmax_element 등 다양한 숫자 알고리즘 함수들이 존재한다. 이들은 굳이 필자가 설명할 정도로 어려운 함수들이 아니기 때문에, 따로 찾아보는 것을 추천한다.

 +@ std::partial_sum, std::adjcent_difference

7) Partitioning Algorithm ***

 분할 작업과 관련된 알고리즘 함수들이다.

이 함수를 다루기 전에는 분할 작업이 어떤 것인지에 관해 먼저 이해하고 가는 것이 중요하다.

 

Partitioning(파티셔닝)이란?

 특정 범위 혹은 컨테이너 안의 원소에 관해, 특정 프로퍼티(Property)에 맞게 분류하는 것을 의미한다.

프로퍼티는 해당 용어의 의미 그대로 분류 목적이라고 해석하면 된다. 예를 들면 홀수값인지 아닌지? 등이

프로퍼티가 될 수 있다.

 

 다소 어려운 표현처럼 보이지만 일상 생활에서 자주 보이는 어플리케이션의 기능에 대입해보면 쉽게 이해할 수 있다.

  • 핸드폰의 메시지 어플의 경우, 가장 최근에 메시지가 온 항목이 리스트의 맨 위로 고정된다.
  • 게임 클라이언트의 경우, 선택된 아이템을 맨 앞쪽에 디스플레이하고 그 외의 아이템은 후열에 디스플레이한다.

 

 정렬과 비슷하다라고 느낄 수 있지만, 파티셔닝은 정렬과 다르게 프로퍼티에 맞게 원소를 재배치하는 것만 수행하고,

정렬은 이루지 않는다. 앞서 언급한 정렬 알고리즘 함수 중, std::nth_element도 이와 유사하다.(목적만 달성하면 더 이상 정렬하지 X)

 

 해당 범위 내 원소들을 홀수값인지에 따라 분류한다고 가정해보자. 그림으로 표현하면 아래와 같다.

Partitioning by Odd Number

 1, 2, 3, 4의 값이 프로퍼티에 의해 2번 인덱스를 기준으로 재배치 된 모습이다.

Property에 만족하는 원소는 Front에 만족하지 못하는 원소는 Back에 배치된다.

 

 이러한 특성을 가진 파티셔닝 알고리즘 함수들은 Predicate로 Property가 들어가며, 당연히 True, False를 반환하는

형태로 구현된다.

std::partition(Range, Predicate(Property))

 이 함수가 위의 기능을 수행하는 알고리즘 함수이다. (_copy버전도 존재.)

예시의 그림에 맞는 기능을 코드로 작성하면 다음과 같다.

std::vector<int> nums {1,2,3,4};
std::partition(std::begin(nums),std::end(nums), [](auto n) { return n % 2 == 1;});

for(auto i : nums) cout << i << " ";

 

 사용법도 아주 간단하다. 하지만 여기서 의문점을 하나 발견할 수 있다. 바로 도대체 배치되는 과정이 어떻게 되는

것인가? 어떤 순서를 유지하며 교환이 이루어지는가?이다. std::partition의 경우 불완전한 배치를 수행하며, std::sort와 마찬가지로 stable한 버전인 std::stable_partition 함수가 존재한다. 즉, std::partition은 입력 순서를 유지한 채로 교환이 이루어지지 않는다는 것이다.

 

 std::partition은 양방향 순회를 지원한다. 그리고 파티셔닝 과정에서 두개의 Iterator를 사용한다. 

하나는 정방향 순회를 수행하는 Front-Iterator 나머지 하나는 역방향 순회를 수행하는 Back-Iterator이다.

(두 명칭은 필자가 임의로 붙인 것이다.) 

 

  1. Front-Iterator는 Property에 만족하지 않은 요소가 나올 때 까지 이동한다. (Last-First / 2 까지)
  2. Back-Iterator는 Property에 만족하는 요소가 나올 때까지 이동한다. (Last-First / 2 까지)
  3. 1,2 과정을 수행하다 두 Iterator가 이동을 멈췄다면, 두 요소를 swap한다.

 

 {1, 2, 3, 4}를 원소로 가지고 있고, 홀수값에 따라 분류한다고 가정하자,

 

  1. Front-Iterator는 0번 인덱스부터 1번 인덱스까지 이동한다.
  2. Back-Iterator는 3번 인덱스부터 2번 인덱스까지 이동한다
  3. 두 Iterator 값을 Swap한다
  4. 결과는 1, 3, 2, 4가 된다.

 

해당 예시는, 운이 좋게도 stable한 배치를 만족하는 결과가 나온다.

 (참고: 앞서 보여준 그림에서는 설명의 목적으로 작성했기 때문에, 이 부분을 고려하지 않고 표현했다.)

 

std::stable_partition(Range, Predicate(Property))

 std::partition의 stable한 버전이다. 기존 입력 순서를 유지한 채, 교환을 수행한다. 교환 방식은 어렵지 않다.

 

  1. 두 개의 컨테이너 A, B를 마련한다.
  2. 앞에서부터 순서대로 순회하며, Property에 만족한 원소는 컨테이너 A에, 아닌 원소는 컨테이너 B에 추가한다.
  3. 순회가 끝나면 두 컨테이너를 합친다. A의 원소는 Front로 B의 원소는 Back으로 이동한다. (A + B)

이번에는 좀 더 복잡한 예시를 가져와, std::partition과 어떤 결과 차이를 보여주는지 비교해보겠다.

std::vector<int> v{3,1,4,1,5,9,2,8,1,6};

std::partition(begin(v), end(v), [](auto n) { 
		return n % 2 == 1; 
		});
        
        
std::vector<int> v2{3,1,4,1,5,9,2,8,1,6};

std::partition(begin(v2), end(v2), [](auto n) { 
		return n % 2 == 1; 
});

// .... print v1 & v2

Output

Stable 함수에 관한 동작 방식을 그림으로 표현하자면 다음과 같다.

 

std::stable_partition

std::partition_point(Range, Predicate)

 해당 함수는 이름에서도 유추할 수 있듯이, 프로퍼티에 맞게 분류된 두 지점의 경계점을 Iterator로 반환하는 함수이다.

다만 분류되지 않은 범위를 주어줄 수 도 있는데, 그 경우, 프로퍼티에 만족하지 않는 그 첫 번째 지점을 반환한다.

std::vector<int> partitioned{1,3,2,4};
auto pp = std::partition_point(begin(partitioned), end(partitioned), [](auto n){
  return n % 2 == 1;
});

std::cout << *pp << "\n"; // 2;

 

 

분량 조절을 위해, 이번 게시글에선 여기까지 다루고, Ordering Algorithm과 Remove Algorithm은 다음 게시글을 통해 다뤄보도록 하겠다.