C++17 표준 라이브러리에 새로 추가된 알고리즘과 기타 변경 사항 소개

류광, 2017/08/05 18:49
C++17 표준 라이브러리 소개 시리즈의 마지막 글. 새로 추가된 알고리즘과 기타 변경 사항을 소개합니다.

"핵심 C++ 표준 라이브러리" 부록 A 방출 계획의 마지막 글입니다. C++에 새로 추가된 알고리즘들과 자잘한 변경 사항을 간략하게 정리했습니다.

새로 추가된 알고리즘

C++17에서 새로 추가된 알고리즘들을 간략하게만 소개하겠다. 이들은 모두 std 이름공간에 속한다.

  • for_each_n: for_each와 같되 [first, last)가 아니라 [first, first+n)을 입력 범위로 사용하며, first+n을 돌려준다(참고로 for_each의 직렬 버전은 사용자 지정 함수를 돌려주고 병렬 버전은 아무것도 돌려주지 않는다). 필요한 헤더는 <algorithm>이며, 병렬 버전도 있다.
  • sample: 주어진 범위의 요소 n개를 주어진 확률 분포에 따라 무작위로 선택한다. 필요한 헤더는 <algorithm>이다.
  • uninitialized_moveuninitialized_move_n: 주어진 요소들을 초기화되지 않은 메모리 영역으로 이동한다. 필요한 헤더는 <memory>이며, 병렬 버전도 있다.
  • clamp: 주어진 값이 하한보다 작으면 하한을, 상한보다 크면 상한을 돌려준다. 그 외에는 주어진 값을 돌려준다. 비교 함수를 지정할 수 있다. 필요한 헤더는 <algorithm>이다.
  • reduce: 분산 처리나 병렬 처리 관련 프레임워크 또는 언어에서 흔히 볼 수 있는 Map-Reduce(사상-축약) 패턴의 Reduce 단계에 해당하는 알고리즘이다. 필요한 헤더는 <numeric>이며, 병렬 버전도 있다. 참고로 Map에 해당하는 표준 라이브러리 알고리즘은 transform이다. 기존 accumulate 알고리즘에 병렬 버전이 추가되지 않았는데, 대신 reduce의 병렬 버전을 사용하면 된다.
  • transform_reduce: Map-Reduce에 해당하는 알고리즘으로, 요소들을 먼저 변환한 후에 축약한다. 필요한 헤더는 <numeric>이며, 병렬 버전도 있다. 기존 inner_product 알고리즘에 병렬 버전이 추가되지 않았는데, 대신 이 transform_reduce의 병렬 버전을 사용하면 된다.
  • inclusive_scanexclusive_scan: 요소들의 구간 합(prefix sum; 또는 부분합)들을 구한다. inclusive_scani번째 요소를 i번째 부분합에 포함하고, exclusive_scan은 포함하지 않는다. 예를 들어 덧셈과 초기치 0을 사용한다고 할 때 {1, 1, 0, 2, 3}의 inclusive_scan 결과는 {1, 2, 2, 4, 7}이고 exclusive_scan 결과는 {0, 1, 2, 2, 4}이다. 덧셈 이외의 합산 함수를 지정할 수 있으며, 부분합의 초기치도 다르게 지정할 수 있다(기본은 0). 필요한 헤더는 <numeric>이며, 병렬 버전도 있다. 기존 partial_sum 알고리즘에 병렬 버전이 추가되지 않았는데, 대신 inclusive_scan의 병렬 버전을 사용하면 된다.
  • transform_inclusive_scantransform_inclusive_scan: 요소들을 먼저 변환한 후 구간 합을 구한다. 필요한 헤더는 <numeric>이며, 병렬 버전도 있다.

기타 변경 사항

그 외에 C++17 표준 라이브러리의 변경 사항을 정리하자면 다음과 같다.

  • random_shuffle, auto_ptr, result_of, bind1st, unxepected 등 이전 표준들이 폐기 예정으로 분류한 구성요소들이 실제로 폐기되었다(표 A.3).
  • 활성 예외 객체 검출 함수 uncaught_exception이 폐기 예정으로 분류되고, 이를 대신하는 uncaught_exceptions가 추가되었다. 전자는 현재 스레드에 활성 예외 객체(던져졌지만 아직 해당 catch 절에 도달하지 않은 예외 객체)가 있는지의 여부(bool)를 돌려주지만, 후자는 현재 스레드의 활성 예외 객체 개수(int)를 돌려준다(<exception> 헤더).
  • mapunordered_maptry_emplaceinsert_or_assign이라는 새로운 멤버 함수가 추가되었다. 이들은 주어진 키가 컨테이너에 없는 경우에만 새 요소를 생성 또는 삽입한다.
  • 컨테이너 멤버 함수 size, empty, data의 비멤버 함수 버전인 std::size, std::empty, std::data가 추가되었다(<iterator> 헤더).
  • 메모리를 구성하는 바이트byte의 개념을 좀 더 명시적으로 표현하기 위해 std::byte라는 형식이 추가되었다. 내부적으로 std::byte는 하나의 열거형 클래스(enum class)인데, 바탕 자료 형식은 unsigned char이다. unsigned char와는 달리 std::byte는 문자 형식으로도, 수치(산술) 형식으로도 간주되지 않는다. 개념적으로 std::byte는 단지 비트들의 집합일 뿐이며, 산술 연산자들은 지원하지 않고 비트별 논리 연산자들과 자리이동(shift) 연산자들만 지원한다. 임의의 정수 n을 std::byte 객체로 변환하려면 std::byte{n} 형태의 표현식을 사용하고(C++17부터는 이런 식으로 열거형 객체를 생성할 수 있게 되었다), 그 반대의 변환은 std::to_integer 함수(역시 C++17에서 추가되었다)를 사용하면 된다.
  • 컴파일 시점에서 형식 특질들의 논리합, 논리곱, 부정을 산출하는 메타 함수 conjunction, disjunction, negation이 추가되었으며, is_aggregate, is_invocable, is_swappable 등 다양한 컴파일 시점 형식 판정 함수가 추가되었다(<type_traits> 헤더).
  • 최대공약수와 최소공배수를 돌려주는 수학 함수 gcdlcm이 추가되었으며(<numeric> 헤더), 타원적분, 베셀 함수, 르장드르 함수, 노이만 함수, 리만 제타 함수 등 다양한 특수 함수가 추가되었다(<cmath> 헤더). 표 A.4에 특수 함수들이 나열되어 있다.

표 A.3 폐기된 구성요소들

auto_ptr, const_mem_fun_t, pointer_to_binary_function, binary_function, get_unexpected, pointer_to_unary_function, bind1st, mem_fun1_ref_t, ptr_fun, bind2nd, mem_fun1_t, random_shuffle, binder1st, mem_fun_ref_t, set_unexpected, binder2nd, mem_fun_ref, unary_function, const_mem_fun1_ref_t, mem_fun_t, unexpected, const_mem_fun1_t, mem_fun, unexpected_handler, const_mem_fun_ref_t

표 A.4 특수 수학 함수

assoc_laguerre, comp_ellint_3f, ellint_1l, legendre, assoc_laguerref, comp_ellint_3l, ellint_2, legendref, assoc_laguerrel, cyl_bessel_i, ellint_2f, legendrel, assoc_legendre, cyl_bessel_if, ellint_2l, riemann_zeta, assoc_legendref, cyl_bessel_il, ellint_3, riemann_zetaf, assoc_legendrel, cyl_bessel_j, ellint_3f, riemann_zetal, beta, cyl_bessel_jf, ellint_3l, sph_bessel, betaf, cyl_bessel_jl, expint, sph_besself, betal, cyl_bessel_k, expintf, sph_bessell, comp_ellint_1, cyl_bessel_kf, expintl, sph_legendre, comp_ellint_1f, cyl_bessel_kl, hermite, sph_legendref, comp_ellint_1l, cyl_neumann, hermitef, sph_legendrel, comp_ellint_2, cyl_neumannf, hermitel, sph_neumann, comp_ellint_2f, cyl_neumannl, laguerre, sph_neumannf, comp_ellint_2l, ellint_1, laguerref, sph_neumannl, comp_ellint_3, ellint_1f, laguerrel

top
트랙백 0 : 의견 # + 0

C++17 표준 라이브러리의 알고리즘 병렬화 소개

류광, 2017/07/29 14:43
C++17 표준 라이브러리의 알고리즘 병렬화를 소개합니다

"핵심 C++ 표준 라이브러리" 부록 A 중 C++17의 알고리즘 병렬화에 관한 글입니다. "순서 대로"와 "순차적으로"의 차이는 제 능력으로는 간단하게 설명하기가 좀 어렵네요. 언제 좀 더 풀어서 설명하는 글을 한 번 써보겠습니다.

알고리즘의 병렬화

C++17은 표준 라이브러리의 여러 알고리즘에 ‘병렬 실행’을 지원하는 중복적재 버전을 추가하며, 병렬 실행을 지원하는 새 알고리즘도 여럿 추가한다. 예를 들어 기존 알고리즘인 std::transform에는 다음과 같은 중복적재 버전들이 추가되었다.

FwdIt2 transform( ExePolicy&& policy, FwdItIt1 first1, FwdItIt1 last1,
                    FwdIt2 d_first, UnFunc func);
FwdIt3 transform( ExePolicy&& policy, FwdIt1 first1, FwdIt1 last1,
                    FwdIt2 first2, FwdIt3 d_first, BiFunc func );

모든 병렬 버전에서 템플릿 매개변수 ExePolicy는 실행 방침(execution policy)을 뜻하는 어떤 클래스로, 주된 용도는 중복적재 해소 과정에서 알고리즘의 병렬 버전이 선택되게 하는 것이다. C++17 표준 라이브러리의 std::execution 이름공간에는 다음과 같은 세 가지 구체적 실행 방침 클래스가 정의되어 있다(필요한 헤더는 <execution>).

  • sequenced_policy 클래스
  • parallel_policy 클래스
  • parallel_unsequenced_policy 클래스

또한, 편의를 위해 std::execution::seq, std::execution::par, std::execution::par_unseq라는 인스턴스들(각각 sequenced_policy, parallel_policy, paralllel_unsequenced_policy의 인스턴스)이 미리 생성되어 있으므로, 특별한 이유가 없는 한 따로 객체를 생성할 필요 없이 이들을 바로 사용하면 된다(마치 cout을 사용할 때처럼).

병렬 알고리즘을 호출할 때 첫 인수로 seq를 지정하면 병렬 실행이 금지된다. 즉, 구현은 요소들을 반드시 현재 스레드(알고리즘을 호출한 스레드)에서 처리해야 한다. 이 방침에서 요소들이 반드시 원래 순서대로(in order) 처리된다는 보장은 없지만, 요소들이 순차적으로 처리된다(sequenced)는 보장은 있다. 다른 말로 하면, 한 스레드에서 어떤 한 요소의 처리가 끝나기 전에 다른 요소의 처리가 시작되는 일은 없다.

par를 지정하면 병렬 실행이 허용된다. 즉, 병렬 알고리즘 구현은 현재 스레드 이외의 스레드를 따로 생성해서 요소들을 처리할 수 있다. 이 경우에도 각 스레드는 요소들을 반드시 순차적으로 처리한다. 이 방침에서는 다중 스레드 상황이 벌어지므로 경쟁 조건이나 교착 상태가 발생할 수 있는데, 사용자가 지정한 호출 가능 단위로 요소에 접근하는 알고리즘의 경우 적절한 동기화로 그런 문제를 방지하는 것은 프로그래머의 몫이다. 예를 들어 다음은 C++17 표준 명세서 초안에 나오는 예로, 공유 변수 x에 대한 접근을 뮤텍스로 보호한다.

int x = 0;
std::mutex m;
int a[] = {1,2};
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int) {
  std::lock_guard<mutex> guard(m);
  ++x;
});

마지막으로, par_unseq를 지정한다는 것은 병렬 실행을 허용할 뿐만 아니라 순차 처리도 강제하지 않는다는 뜻이다. 순차 처리가 필수가 아니면 구현이 벡터화(vectorization)를 이용해서 좀 더 빠른 코드를 생성할 여지가 생긴다. 사용자가 지정한 호출 가능 단위로 요소에 접근하는 알고리즘의 경우, 벡터화에 따른 위험(교착 상태 등)은 프로그래머가 방지해야 한다. 다음은 앞의 예에서 parpar_unseq로 대체한 코드로, 역시 C++17 초안에 나온 것이다.

int x = 0;
std::mutex m;
int a[] = {1,2};
std::for_each(std::execution::par_unseq, std::begin(a), std::end(a),
  [&](int) {
    std::lock_guard<mutex> guard(m); // 올바르지 않음: lock_guard 생성자는
                                     // m.lock()을 호출함.
    ++x;
});

구현이 for_each 루프를 하나의 스레드로 실행하기로 해도(parpar_unseq는 병렬 실행을 허용하는 것일 뿐 강제하는 것은 아니므로, 필요하다면 구현은 그냥 하나의 스레드에서 알고리즘을 실행할 수 있다), 앞의 par 예제에서는 의해 순차 처리가 요구되므로 루프가 m.lock(); ++x; m.unlock(); m.lock(); ++x; m.unlock(); 형태로 실행된다. 따라서 교착 상태는 벌어지지 않는다. 그러나 이번 예제의 par_unseq 방침 하에서는 순차 처리가 필수가 아니므로 구현이 m.lock(); m.lock(); ++x; ++x; m.unlock(); m.unlock(); 형태의 코드를 생성할 수 있다. 그러면 한 스레드에서 같은 뮤텍스를 연달아 잠그려 해서 교착 상태가 발생한다.

표 A.2는 병렬 버전이 추가된 알고리즘들이다. 알고리즘 자체가 C++17에서 새롭게 추가된 경우는 굵은 글씨로 표시했다.

표 A.2 병렬 실행을 지원하는 표준 알고리즘

adjacent_difference, adjacent_find, all_of, any_of, copy, copy_if, copy_n, count, count_if, equal, exclusive_scan, fill, fill_n, find, find_end, find_first_of, find_if, find_if_not, for_each, for_each_n, generate, generate_n, includes, inclusive_scan, inner_product, inplace_merge, , is_heap, is_heap_until, is_partitioned, is_sorted, is_sorted_until, lexicographical_compare, max_element, merge, min_element, minmax_element, mismatch, move, none_of, nth_element, partial_sort, partial_sort_copy, partition, partition_copy, reduce, remove, , remove_copy, remove_copy_if, remove_if, replace, replace_copy, replace_copy_if, replace_if, reverse, reverse_copy, rotate, rotate_copy, search, search_n, set_difference, set_intersection, set_symmetric_difference, set_union, sort, stable_partition, stable_sort, swap_ranges, transform, transform_exclusive_scan, transform_inclusive_scan, transform_reduce, uninitialized_copy, uninitialized_copy_n, uninitialized_fill, uninitialized_fill_n, unique, unique_copy

병렬화의 이득을 볼 만한 기존 알고리즘 accumulate, inner_product, partial_sum에 병렬 버전이 추가되지 않은 점을 의아하게 생각하는 독자도 있을 텐데, 이 세 알고리즘의 병렬화는 다음 절[1]에 나오는 reduce, transform_reduce, inclusive_scan의 병렬 버전으로 대신할 수 있다.


[1] '다음 절'은 핵심 C++ 표준 라이브러리 부록 A의 '새로 추가된 알고리즘' 단원을 말하는데, 조만간 이 블로그에도 올리겠습니다.

top
트랙백 0 : 의견 # + 0

C++17 표준 라이브러리의 파일 시스템 라이브러리 소개

류광, 2017/07/22 13:20
이어지는 핵심 C++ 표준 라이브러리" 부록 공개. 이번에는 C++17에 추가된 파일 시스템 라이브러리를 소개합니다.

"핵심 C++ 표준 라이브러리" 부록 A 중 C++17에 추가된 파일 시스템 라이브러리를 소개하는 글입니다.

파일 시스템 라이브러리

C++14까지 C++ 표준 라이브러리에는 파일 입출력을 위한 수단은 있었지만 파일 시스템을 위한 수단은 없었다. C++17에서 드디어 C++도 파일 시스템 라이브러리를 가지게 되었다. 이 파일 시스템 라이브러리는 원래 boost.filesystem으로 출발해서 TS(Technical Specification) 단계를 거쳐서 표준 라이브러리에까지 들어오게 된 것이다. C++ 파일 시스템 라이브러리의 모든 형식과 함수는 std::filesystem 이름공간에 속하며, 필요한 헤더는 <filesystem>이다.

파일 시스템 라이브러리에는 파일의 경로를 나타내는 path와 디렉터리의 한 항목(보통의 파일뿐만 아니라 하위 디렉터리, 기호 링크, 소켓, 파이프 등도 포함)을 나타내는 directory_entry, 파일의 종류와 상태를 나타내는 file_status, 가용 디스크 용량을 위한 space_info, 파일 시간을 위한 file_time_type 등 다양한 클래스가 있으며, 디렉터리 반복(운행)을 위한 두 반복자 클래스 directory_iteratorrecursive_directory_iterator도 제공한다. 또한, 파일 접근 권한, 파일 종류, 복사 옵션, 디렉터리 반복 운행) 옵션을 위한 열거형들(perms, file_type 등)도 갖추어져 있다.

이러한 형식들 외에, 실질적인 파일 시스템 연산들을 수행하는 다양한 비멤버 함수들이 있다. 예를 들어 directory_entry 클래스에는 디렉터리를 생성하거나 파일을 복사하는 멤버 함수가 없다. 디렉터리 생성은 비멤버 함수 create_directorycreate_directories가, 복사는 비멤버 함수 copycopy_file이 담당한다. 그 밖에 rename, resize_file, current_path, exits 등 경로와 파일, 디렉터리를 다루는 데 필요한 다양한 함수가 있다. 또한, is_directory, is_empty, is_regular_file 등 주어진 디렉터리 항목의 종류를 판정하는 술어 함수들도 있다. 표 A.1은 파일 시스템 라이브러리의 구성요소들을 나열한 것이다.

void h()
{
    namespace fs = std::filesystem;
    fs::create_directory("foo");

    // create_directories는 경로 중간의 디렉터리들까지 생성해준다.
    fs::create_directories("foo/bar/abc/123")

    // 보통의 파일을 생성하려면 파일 입출력 라이브러리가 필요하다.
    std::ofstream("foo/bar/abc/file.txt");

    // 반복자를 이용해서 foo 디렉터리와 그 하위 디렉터리의
    // 모든 항목을 훑는다.
    for(auto&& x: fs::recursive_directory_iterator('foo')) {
        cout << x.path() << endl;
    }
}

표 A.1 파일 시스템 라이브러리의 구성

		형식
path			recursive_directory_iterator	perms
filesystem_error	file_status			copy_options
directory_entry		space_info			directory_options
directory_iterator	file_type			file_time_type
		함수
absolute		create_directories		permissions
system_complete		create_hard_link		read_symlink
canonical		create_symlink			remove
weakly_canonical	create_directory_symlink	remove_all
relative		current_path			rename
proximate		exists				resize_file
copy			equivalent			space
copy_file		file_size			status
copy_symlink		hard_link_count			symlink_status
create_directory	last_write_time			temp_directory_path
		파일 종류 및 상태 판정 술어
is_block_file		status_known			is_regular_file
is_character_file	is_fifo				is_socket
is_directory		is_other			is_symlink
is_empty
top
트랙백 0 : 의견 # + 0

C++17 표준 라이브러리의 std::variant 소개

류광, 2017/07/15 18:35
C++17 표준 라이브러리에 추가된 std::variant를 소개합니다.

본문 열기

top
트랙백 0 : 의견 # + 0

C++17 표준 라이브러리의 std::any 소개

류광, 2017/07/08 19:58
C++17 표준 라이브러리에 추가된 std::any를 소개합니다.

본문 열기

top
트랙백 0 : 의견 # + 0

◀ PREV : [1] : [2] : [3] : [4] : [5] : ... [60] : NEXT ▶