No Raw Loops! Yes STL Algorithms!

  • Sat, Sep 18, 2021
  • 읽는 시간 5분

unsplash



What are raw loops (↔ algorithms)?

  • for loop
  • while loop
  • do while loop
// Raw loop
for (size_t i=0; i < my_vector.size();i++)
{
  // do something including erase, push, insert and break;
}

for (auto& x : my_vector){
  // do something
}

// Algorithms
auto it_found = std::find_if(cbegin(my_vector), cend(my_vector), 
                             find_function);
auto it_remove = std::remove_if(cbegin(my_vector), cend(my_vector),
                                remove_function);
auto it_fill = std::fill_n(my_vector.begin(), count, value);



Why you should not use raw loops?

  • raw loop 는 한눈에 loop 의 목적을 파악하기가 어렵다.
    • raw loop 는 loop 안의 body를 확인해야 한다.
  • 종료조건을 확인하기 어렵다.
  • loop 의 time complexity 를 숨긴다
    • 시스템의 성능 저하를 야기할 수 있다.
  • STL algorithms 을 적용하면 의도를 확인하기 쉬운 추상화된 코드로 작성이 가능하다.
    • 가독성, 유지관리의 용이성 증가



STL algorithms every programmer must know.

upper_bound, lower_bound

template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, 
                       Compare comp );

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, 
                       Compare comp );

// * C++20 에서는 constexpr 버전이 추가되었다.

  • upper_bound

    • 용도 : 찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
    • 범위 [first, last) 안의 원소들 중, value 보다 큰 첫 번째 원소를 리턴한다. 만일 그런 원소가 없다면 last 를 리턴한다. 이름 그대로 어떠한 값의 상한선 을 의미한다.

  • lower_bound

    • 용도 : 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
    • 범위 [first, last) 안의 원소들 중, value 보다 작지 않은 (크거나 같은) 첫 번째 원소를 리턴한다. 만일 그런 원소가 없다면 last 를 리턴한다. 이름 그대로 어떠한 값의 하한선 을 의미한다.

  • Condition: 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 함

  • Time Complexity: O(log(N))

  • Example:

    #include <algorithm>
#include <iostream>
#include <vector>

int main() {

  int gfg[] = { 5, 6, 7, 7, 6, 5, 5, 6 };

  std::vector<int> v(gfg, gfg + 8); // 5 6 7 7 6 5 5 6

  std::sort(v.begin(), v.end()); // 5 5 5 6 6 6 7 7

  auto lower = lower_bound(v.begin(), v.end(), 6);
  auto upper = upper_bound(v.begin(), v.end(), 6);

  std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
  return 0;
}

/* output
6 6 6
*/

rotate

template< class ForwardIt >
ForwardIt rotate( ForwardIt first, ForwardIt n_first, ForwardIt last );

// * C++20 에서는 constexpr, ExecutionPolicy 버전이 추가되었다.

  • rotate

    • [first, last) 구간에서 n_first 만큼 회전시킨다. first 위치는 n_first 위치로 이동하게 된다.
    • 왼쪽으로 이동하며, 오른쪽으로 회전시키려면 reverse iterator 를 이용한다.
    • first 가 이동한 위치를 리턴한다.

  • Time Complexity: O(N)

  • Example:

    #include <vector>
#include <iostream>
#include <algorithm>

auto print = [](auto const& remark, auto const& v) {
    std::cout << remark;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
};

int main()
{
    std::vector<int> v{2, 4, 2, 0, 5, 9, 7, 3, 7, 1};

    print("before sort:\t\t", v);

    // insertion sort
    for (auto i = v.begin(); i != v.end(); ++i) {
        std::rotate(std::upper_bound(v.begin(), i, *i), i, i+1);
    }

    print("after sort:\t\t", v);

    // simple rotation to the left
    std::rotate(v.begin(), v.begin() + 1, v.end());

    print("simple rotate left:\t", v);

    // simple rotation to the right
    std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());

    print("simple rotate right:\t", v);

    // rotate partially
    std::rotate(v.begin()+2, v.begin() + 4, v.begin() + 7);

    print("rotate partially:\t", v);
}

/* output
before sort:         2 4 2 0 5 9 7 3 7 1 
after sort:          0 1 2 2 3 4 5 7 7 9 
simple rotate left:  1 2 2 3 4 5 7 7 9 0 
simple rotate right: 0 1 2 2 3 4 5 7 7 9 
rotate partially:    0 1 3 4 5 2 2 7 7 9
*/

partition

template< class ForwardIt, class UnaryPredicate >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

// * C++20 에서는 constexpr, ExecutionPolicy 버전이 추가되었다.

  • partition

    • [first, last) 구간에서 UnaryPredicate p 를 만족하는 값은 앞쪽 그룹, 만족하지 않는 값은 뒤쪽 그룹으로 나누고 두번째 그룹의 시작점을 리턴한다.
    • **stable_partition** 함수는 partition 과 동일하게 동작하나 원래 값의 순서를 보장해 준다.

  • Time Complexity:

    • Given N = [std::distance](http://en.cppreference.com/w/cpp/iterator/distance)(first,last)

      1) Exactly N applications of the predicate. At most N/2 swaps if ForwardIt meets the requirements of LegacyBidirectionalIterator, and at most N swaps otherwise.

      2) O(N log N) swaps and O(N) applications of the predicate.

  • Example:

    #include <iostream>
#include <algorithm>

int main()
{
    std::vector<int> v = {1, 2, 4, 5, 3, 6, 8, 5, 7, 9};

    std::cout << "partition (odd first): ";
    std::partition(v.begin(), v.end(), 
                                   [](auto n){return n%2 == 1;});
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    std::cout << "stable partition (even first): ";
    auto p = std::stable_partition(v.begin(), v.end(), 
                                   [](auto n){return n%2 == 0;});
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
    std::cout << "position: " << p - v.begin() + 1<< "\n";
    return 0;
}

/* output
partition (odd first): 1 9 7 5 3 5 8 6 4 2 
stable partition (even first): 8 6 4 2 1 9 7 5 3 5 
position: 5
*/

unsplash



그래도 raw loop 를 써야한다면?

  • range-based loop 를 사용
  • loop의 body 를 최대한 간결하게 사용
for (const auto& e : r) f(e);
for (auto&  e : r) e = f(e);
for (const auto& e : r) { f(e); g(e); }



Reference



이 시리즈의 게시물

C++STL알고리즘 (algorithm)

댓글