광고


[C++17] Standard Libarary Algorithms : C++17에서의 변화/추가 #1 TR1/C++11/C++14/C++17


0. 서문

이 길은 VC Blog의 "Standard Library Algorithms : Changes and Additions in C++ 17"을 거의 그대로 해석한 글이다.
내용 정리가 꽤 깔끔하게 잘 되어 있어서 개인적 첨언은 최대한 자제하였으며, 당장은 관심없는 "Gneralized sum algorithms"와 "Parallel algorithms" 챕터는 작성하지 않았다.
(이 글의 제목에 #1이 붙은 이유이기도 하지만, #2를 언제 작성할지는 모르겠다)


1. New algorithm


1-1. sample


주어진 범위 내([first, last))의 요소중 n개를 랜덤하게 뽑아내어 output iterator에 담아 돌려주는 함수.
아래는 1~20의 숫자를 담는 벡터에서 5개의 랜덤요소를 sampling하는 예제이다.

  1. #include <algorithm>
  2.  
  3. std::vector<int> data(20);
  4. iota(begin(data), end(data)1);
  5. // 출력 결과
  6. // 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
  7. std::copy(cbegin(data), cend(data), ostream_iterator<int>(cout" "));
  8. std::cout << '\n';
  9.  
  10. // 선언 및 초기화 : Random-Seed / Random-Engine
  11. random_device seeder;
  12. const auto seed = seeder.entropy() ? seeder() : time(nullptr);
  13. default_random_engine generator(static_cast<default_random_engine::result_type>(seed));
  14.  
  15. // 결과를 담을 벡터
  16. vector<int> sampledData(numberOfSamples);
  17.  
  18. std::sample(
  19.     cbegin(data),         // [first] of Input
  20.     cend(data),           // [last] of Input
  21.     begin(sampledData)// Iterator of Output
  22.     numberOfSamples,   // number of sampling
  23.     generator              // Random generator
  24. );
  25.  
  26. // 출력 결과
  27. // 2 3 4 5 20
  28. std::copy(cbegin(sampledData), cend(sampledData), ostream_iterator<int>(cout" "));
  29. std::cout << '\n';


1-2. Iterating


기존의 for_each 함수는 [first, last)의 iterator 형식으로 범위를 지정할 수 있었지만,
C++17에서 새로이 추가된 for_each_n 함수는 [first, first + N)의 개념으로 시작 iterator와 개수(N)의 형식으로 범위를 지정한다.

아래는 1~20의 숫자를 담는 벡터의 [1,2,3,4,5]를 출력하는 예제이다.

  1. #include <algorithm>
  2.  
  3. std::vector<int> data(20);
  4. iota(begin(data), end(data)1);
  5.  
  6. // [first, first + n]의 범위 요소들에 대해 funcObj 실행/적용
  7. std::for_each_n(
  8.     begin(data),             // [first] of Input
  9.     5,                        // number of elements to apply the function to
  10.     [](const auto& value) // function object
  11.     {
  12.         std::cout << value << '\n';
  13.     }
  14. );


1-3. Searching

C++17에서 다음 3개의 특수화된 searcher들을 추가하였으며, 이들은 <functional> 헤더에서 찾아볼 수 있다.
Boyer-Moore searcher들은 큰 텍스트 블록에서 특정 단어를 찾을 때 종종 사용되며, 이들은 default searcher보다 대부분 더 효율적이다. 실제로 2개의 Boyer-Moore searcher들은 모든 개별 글자를 비교하는 대신 특정 글자들을 스킵할 수 있으며, 이로 인해 선형 복잡도를 가지는 default searcher 보다 빠를 수 있는 것이다. 검색패턴이 길면 길수록 알고리즘 수행 속도는 더 빨라진다.

물론 세상에 공짜없다고 default_searcher보다 더 나은 성능을 제공하기 위해 boyer_moore 함수들은 더 많은 메모리를 차지한다.

코드를 엄밀히 분석하지 않았기에 boyer_moore_searcher와 boyer_moore_horspool_searcher와의 정확한 차이점은 모르겠으나, boyer_moore_horspool_searcher의 경우 최상의 경우엔 boyer_moore_searcher보다 나을 수 있으나, 최악의 경우엔 boyer_moore_searcher보다 훨씬 큰 성능 저하가 발생한다고 한다.

Boyer-Moore 알고리즘 자체의 자세한 내용은 아래 링크를 참고하기 바란다.

이들은 단독으론 사용할 수 없고, 객체 생성 후 std::search 함수의 파라미터로 넘기는 방식으로 사용된다.
우선 개략적인 용례를 보기 위해 아래 예제를 살펴보자.

  1. #include <functional>
  2.  
  3. const std::string input =
  4.     "Lorem ipsum dolor sit amet, consectetur adipiscing elit,"
  5.     " sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.";
  6. // 찾을 대상
  7. const std::string needle = "consectetur";
  8.  
  9. // std::search([first, last), BinaryPredicate);
  10. auto result = std::search(
  11.                 input.begin(),
  12.                 input.end(),
  13.                 // default_searcher(needle.begin(), needle.end())
  14.                 boyer_moore_searcher(needle.begin(), needle.end())
  15.                 // boyer_moore_horspool_searcher(needle.begin(), needle.end())
  16. );
  17.  
  18. if (result != input.end())
  19.     std::cout << "Found it\n";
  20. else
  21.     std::cout << "Not found\n";

위 예제에서는 searcher 객체를 1회성으로 사용하였지만, 찾을려는 패턴이 동일하다면(예제에서의 needle이 동일하다면) 하나의 searcher 객체를 여러번 std::search 함수의 파라미터로 넘길 수 있다는 점을 참고하기 바란다.


2. Utility functions

알고리즘은 아니지만, 간편하지만 유용한 함수들도 추가되었기에 소개한다.

1-1. clamp

드디어 정식 C++에 clamp 함수가 도입되었다. 그동안 얼마나 많은 사제 MathLib에서 Clamp 함수를 직접 만들어 썼던가!!!
clamp를 모르는 사람이 있을까봐 간단히 설명하면...
  • 주어진 값 < min => min 반환
  • 주어진 값 > max => max 반환
  • 둘 다가 아니면 주어진 값 반환

즉, 주어진 값을 [min, max] 사이로 가두고 싶을 때 사용하는 함수이다.

  1. #include <algorithm>
  2.  
  3. const int low = -32768;
  4. const int high = 32767;
  5.  
  6. // 12000은 [low, high] 범위에 포함되므로, 12000 출력
  7. cout << std::clamp(12000, low, high) << '\n';
  8. // -36000은 low보다 작으므로, min인 -32768 출력
  9. cout << std::clamp(-36000, low, high) << '\n';
  10. // 40000은 max보다 크므로, max인 32767 출력
  11. cout << std::clamp(40000, low, high) << '\n';


1-2. gcd(최대공약수) / lcm(최소공배수)

설마 최대공약수(Greatest Common Divider)와 최소공배수(Least Common Multiple)를 모르는 사람은 없을거라 믿고, 바로 예제로 넘어간다.

  1. #include <numeric>
  2.  
  3. // 24와 44의 최대공약수는 4
  4. std::cout << std::gcd(2444) << '\n';
  5. // 24와 44의 최소공배수는 264
  6. std::cout << std::lcm(2444) << '\n';


3. Removed algorithms

C++17에서 random_shuffle 함수가 삭제되고 shuffle 함수로 대체되었으며, 자세한 내용은 아래 참고를 살펴보기 바란다.


1 2 3 4 5 6 7 8 9 10 다음