전문가를 위한 C++/ C++ 표준 라이브러리 둘러보기

Contents

(전체가 아니라 C#과 차이가 있는 부분을 중심으로 요약 정리)

C++ 프로그래머에게 가장 중요한 라이브러리는 C++ 표준 라이브러리(Standard Library)이다. C++ 표준 라이브러리 중에서 가장 핵심은 제네릭 컨테이너와 제네릭 알고리즘이다. 이 라이브러리는 원래 표준 템플릿 라이브러리(Standard Template Library, STL)라는 이름의 서드파티 라이브러리였다. 그래서 아직도 표준 라이브러리는 STL이라 부르는 사람이 많은데 이는 표준 용어가 아니다.

(이하 내용 생략)

코드 작성법

표준 라이브러리는 C++의 템플릿과 연산자 오버로딩 기능을 상당히 많이 사용한다.

템플릿 활용

템플릿을 활용하면 제네릭 프로그래밍을 할 수 있다. 

(이하 설명 생략)

연산자 오버로딩 활용

(내용 생략)

C++ 표준 라이브러리 둘러보기

스트링

C++은 string이란 클래스를 기본으로 제공한다. C++에서 C 스타일의 문자 배열로 스트링을 표현해도 되지만 C++의 string을 활용하는 것이 여러모로 유리하다. 메모리를 관리해 줄 뿐만 아니라 인덱스 경계 검사, 대입과 비교 기능, 스트링 결합 , 스트링 추출, 부분 스트링 만들기, 문자 치환 등과 같은 다양한 기능도 제공한다.

Note) 엄밀히 말하면 std::string은 std::basic_string 템플릿을 char 타입 매개변수로 인스턴스화한 것의 타입 앨리어스이지만 이런 세부사항은 알 필요 없고 일반 클래스처럼 사용해도 된다.

표준 라이브러리는 string_view 클래스도 제공한다. string_view는 스트링을 읽기 전용으로 표현한다. 또한 const string& 자리에 그대로 넣을 수 있고 오버헤드도 발생하지 않는다. 스트링을 복제하지 않기 때문이다.

정규표현식

정규표현식을 활용하면 패턴 매칭을 쉽게 구현할 수 있다. 정규 표현식은 19장에서 설명한다.

I/O 스트림

C++이 제공하는 입력과 출력에 대한 모델.

스마트 포인터

C++은 unique_ptr, shared_ptr, weak_ptr와 같은 스마트 포인터를 제공한다. shared_ptr과 weak_ptr은 스레드에 안전하다.

C++ 11버전 이전에는 unique_ptr에 대한 기능을 auto_ptr 타입으로 처리했지만 C++ 17부터 auto_ptr이 없어졌기 때문에 이제는 이렇게 사용하지 않는 것이 좋다.

익셉션

C++는 익셉션 메커니즘을 제공한다. C++ 표준 라이브러리는 익셉션에 대해 정의된 상속 계층을 제공하는데, 적절한 타입의 익셉션을 코드에서 곧바로 사용하거나 그중에서 원하는 익셉션을 커스터마이즈 할 수도 있다.

수학 관련 유틸리티

C++ 표준라이브러리는 수학 연산에 관련된 다양한 클래스와 함수도 제공한다.

C++ 17부터는 르장드르 다항식, 베타 함수, 타원 적분, 베셀 함수, 원기둥 함수인 노이만 함수와 같은 특수한 수학 함수도 추가됐다.

또한 complex란 이름의 복소수 클래스도 제공한다.

컴파일 시간 유리수 연산 라이브러리는 ratio 클래스 템플릿을 제공한다.

표준 라이브러리는 valarray란 클래스도 제공하는데 이 클래스는 vector와 비슷하지만 고성능 수치 연산용으로 최적화한 것이다. 이 라이브러리는 벡터 슬라이스(vector slice)를 표현하는 클래스를 다양하게 제공한다. 이런 기본 요소로 행렬 연산을 수행하는 클래스를 정의할 수 있다. 표준 라이브러리는 행렬을 직접 다루는 클래스는 제공하지 않지만 부스트 같은 서드파티 라이브러리는 행렬 연산에 관련된 클래스를 제공한다.

시간 관련 유틸리티

C++은 시간에 관련된 chrono 라이브러리도 제공한다.

무작위수

C++은 예전부터 srand()와 rand() 함수를 통해 의사 무작위수 생성기능을 제공했다. 하지만 이 함수는 굉장히 기초적인 수준으로만 무작위수를 생성할 수 있다.

C++ 11부터 이보다 훨씬 강력한 무작위수 라이브러리가 표준에 추가됐다. 이 라이브러리는 <random> 헤더 파일에 정의돼 있으며 무작위수 엔진, 무작위수 엔진 어댑터, 무작위수 분포 등도 제공한다. 이 기능을 활용하면 정규 분포, 역지수 분포 등에 보다 적합한 무작위수를 생성할 수 있다.

이니셜라이즈 리스트

이니셜라이즈 리스트는 인수의 개수가 다양한 함수를 쉽게 작성할 수 있다.

pair와 tuple

<utility> 헤더 파일에서는 서로 다른 타입의 두 원소를 하나로 묶어서 저장하는 pair 템플릿을 정의하고 있다. 이런 저장 방식을 이종(heterogeneous) 원소 저장이라 부른다. 이 장에서 소개하는 표준 라이브러리 컨테이너는 모두 동종(homogeneous) 원소 저장 방식을 따른다. 즉 컨테이너에 담긴 원소의 타입은 모두 같다. pair 템플릿을 이용하면 서로 타입이 다른 두 원소를 객체 하나에 담을 수 있다.

<tuple> 헤더에 정의된 tuple은 pair를 일반화한 것이다. 고정된 크기의 수열로서 서로 타입이 다른 원소를 저장할 수 있다. tuple에 담긴 원소 개수와 타입은 tuple 인스턴스를 생성하는 컴파일 시간에 결정된다. 튜플은 20장에서 자세히 설명한다.

optional, variant, any

C++ 17부터 다음의 클래스가 새로 추가됐다.

  • optional
    • 특정한 타입의 값을 저장하거나 값을 가지지 않을 수 있다. 값이 없을 수도 있는 함수의 매개변수나 리턴 타입으로 사용할 수 있다.
  • variant
    • 지정한 타입 집합 중 하나의 값을 가지거나 값을 가지지 않을 수 있다.
  • any
    • 모든 타입의 값을 단 하나만 가진다.

이 세 가지 클래스는 20장에서 설명한다.

함수 객체

함수 호출 연산자를 구현하는 클래스를 함수 객체(function object), 펑터(functor)라 부른다. 함수 객체는 특정한 표준 라이브러리 알고리즘에 대한 조건식(predicate) 등에 활용된다.

함수 객체는 18장에서 자세히 소개한다.

파일시스템

C++ 17부터 파일시스템을 지원하는 라이브러리가 추가됐다. 그래서 파일시스템을 다루는 코드를 이식(포팅)하기 쉽게 만들 수 있다. 파일시스템 지원 라이브러리는 20장에서 자세히 설명한다.

멀티스레딩

표준 라이브러리는 멀티스레딩을 지원하는데 필요한 다양한 기본 기능을 제공한다. <thread> 헤더 파일에 정의된 thread 클래스를 이용하면 스레드를 하나씩 생성할 수 있다.

멀티스레드 코드를 작성할 때는 여러 스레드가 같은 데이터를 동시에 읽고 쓰지 않도록 조심해야 한다. 이때 <atomic> 헤더 팡리에 정의된 atomic을 사용하면 데이터를 스레드에 안전하고 아토믹하게 (여러 스레드가 동시에 접근하지 않게) 만들 수 있다. <condition_variable>과 <mutex> 헤더 파일에서도 다양한 스레드 동기화 메커니즘을 제공한다.

여러 스레드로 뭔가 계산해서 적절한 예외 처리 방식을 통해 결과를 받기만 한다면 async와 future를 활용한다. 둘 다 <future> 헤더 파일에 정의돼 있으며 thread 클래스를 직접 다룰 때보다 훨씬 사용하기 쉽다.

타입 트레이드

타입 트레이트(type traits, 타입 특성/속성) 기능은 컴파일 시간에 타입 정보를 조회할 수 있다. 이 기능은 고급 템플릿을 작성할 때 유용하며 22장에서 자세히 설명한다.

표준 정수 타입

<cstdint> 헤더 파일에서는 다양한 표준 정수 타입을 정의하고 이싿. 또한 이러한 타입의 최댓값과 최솟값을 지정하는 매크로도 제공한다. 이런 정수 타입에 대한 자세한 사항은 30장에서 다룬다.

컨테이너

표준 라이브러리는 연결 리스트(linked list)나 큐(queue)와 같이 흔히 사용되는 데이터 구조를 제공한다. C++로 프로그래밍할 때는 이러한 데이터 구조를 직접 구현할 필요 없다. 이러한 데이터 구조는 정보를 원소(element) 단위로 저장하는 컨테이너(container) 개념에 따라 구현했으며, 연결 리스트나 큐와 같은 구쳊거인 데이터의 구조의 특성에 맞게 다양하게 구현했다.

표준 라이브러리에서 제공하는 컨테이너는 모두 클래스 템플릿이다. 그래서 int나 double 같은 기본 타입 뿐만 아니라 사용자가 정의한 클래스에 이르기까지 모든 타입의 데이터를 담을 수 있다. 컨테이너 인스턴스마다 단 한가지 타입의 객체만 저장할 수 있다. 다시 말해 동형(homogeneous) 컬렉션이다.

크기가 고정되지 않은 동형 컬렉션이 필요하다면 각각의 원소를 std::any 인스턴스로 만들어서 컨테이너에 저장한다. 아니면 std::variant 인스턴스로 저장해도 된다. 지원할 타입의 범위가 작고 컴파일 시간에 결정할 수 있다면 variant로 만든다.

C++ 17 이전 버전에서 이형(heeterogeneous) 컬렉션이 필요하다면 각 타입에 맞는 파생 클래스로 구성된 클래스를 새로 정의한다.

(이하 개별 컬렉션 설명 생략)

기본 설명

컨테이너 클래스 이름 컨테이너 타입 사용 시기
vector 순차 컨테이너 기본 컨테이너로 사용한다. 프로파일러로 분석한 결과 이보다 낫다고 판단될 때만 다른 컨테이너를 사용한다.
list 순차 사용할 일이 거의 없다. 프로파일러로 분석한 결과 list가 vector 보다 낫다고 판단되지 않으면 웬만하면 vector를 쓴다.
forward_list 순차 사용할 일이 거의 없다. 프로파일러로 분석한 결과 forward_list가 vector 보다 낫다고 판단되지 않으면 웬만하면 vector를 쓴다.
deque 순차 사용할 일이 많지 않다. 주로 vector를 쓴다.
array 순차 표준 C 스타일 배열 대신 고정 크기 배열이 필요할 때
queue 컨테이너 어댑터 FIFO 구조가 필요할 떄
priority_queue 컨테이너 어댑터 우선순위가 있는 queue를 구현하고 싶을 때
stack 컨테이너 어댑터 FILO이나 LIFO 구조를 구현하고 싶을 때
set
multiset
정렬 연관 원소를 정렬된 묶음에 담고, 조회/추가/삭제 성능도 모두 같게 만들고 싶을 때. 원소의 중복을 허용하지 않으려면 set을 이용한다.
map
multimap
정렬 연관 원소를 키와 값이 연관된 순서쌍으로 키 값에 대해 정렬된 상태, 즉 연관 배열로 저장하면서 조회/추가/삭제 성능도 모두 같게 만들고 싶을 때
unodered_map
unordered_multimap
비정렬 연관  키와 값을 묶어서 저장하고 조회, 추가, 삭제 성능이 모두 같게 만들고 싶으면서 원소를 정렬하지 않아도 될 때. 일반 map 보다 성능이 좋지만 원소의 종류에 따라 달라질 수 있다.
unorderd_set
unorderd_multiset 
비정렬 연관 조회, 추가, 삭제 성능이 모두 같게 만들고 싶으면서 우너소를 정렬하지 않아도 될 때, 일반 set보다 성능이 좋지만 원소의 종류에 따라 달라질 수 있다.
bitset 특수 플래그 묶음을 표현하고 싶을 때

성능

컨테이너 클래스 이름 추가 연산 성능 삭제 연산 성능 조회 연산 성능
vector 끝에서는 분할 상환 성능이 O(1), 나머지는 O(N) 끝에서는 O(1), 나머지는 O(N) O(1)
list 시작과 끝점 그리고 추가할 위치가 정확히 결정된 상태에는 O(1) 시작과 끝점 그리고 추가할 위치가 정확히 결정된 상태에는 O(1) 첫 번째와 마지막 원소를 조회할 때는 O(1), 나머지는 O(N)
forward_list 추가할 지점이 시작점이거나 정확한 위치를 안다면 O(1) 삭제할 지점이 시작점이거나 정확한 위치를 안다면 O(1) 첫 번째 원소를 조회할 때는 O(1), 나머지는 O(N)
deque 시작과 끝에서는 O(1), 나머지는 O(N) 시작과 끝에서는 O(1), 나머지는 O(N) O(1)
array N/A N/A N/A
queue 내부 컨테이너의 종류에 따라 다르다. list나 deque로 구현할 때는 O(1) 내부 컨테이너의 종류에 따라 다르다. list나 deque로 구현할 때는 O(1) N/A
priority_queue 내부 컨테이너에 따라 다르다 vector를 사용할 때는 분할 상환 성능이 O(log(N))이고 deque를 사용할 때는 O(log(N))이다. 내부 컨테이너에 따라 다르다. vector나 deque를 사용할 때는 O(log(N)) N/A
stack 내부 컨테이너에 따라 다르다. list나 deque를 사용하면 O(1), vector를 사용하면 분할 상환 성능으로 O(1) 내부 컨테이너에 따라 다르다. list, vector, deque일 때 O(1), N/A
set
multiset
O(log(N)) O(log(N)) O(log(N))
map
multimap
O(log(N)) O(log(N)) O(log(N))
unodered_map
unordered_multimap
평균 O(1),
최악 O(N)
평균 O(1),
최악 O(N)
평균 O(1),
최악 O(N)
unorderd_set
unorderd_multiset 
평균 O(1),
최악 O(N)
평균 O(1),
최악 O(N)
평균 O(1),
최악 O(N)
bitset N/A N/A N/A

Note) 반드시 vector를 기본 컨테이너로 사용하기 바란다. 실전에서 list나 forward_list를 사용하는 것보다 vector로 구현하는 것이 추가나 삭제 연산이 훨씬 빠르다. 그 이유는 최신 CPU에서 메모리와 캐시를 처리하는 방식 때문이기도 하고, list, forward_list를 사용할 때는 추가나 삭제할 지점까지 탐색하는 오버헤드가 있기 때문이다. list나 foward_list는 메모리 공간에 연속적으로 저장되지 않을 수 있다. 그래서 vector보다 반복문의 성능이 떨어질 수 있다.

알고리즘

표준 라이브러리는 컨테이너 뿐만 다양한 제네릭 알고리즘도 제공한다. 표준 라이브러리에서 제공하는 알고리즘은 함수 템플릿으로 구현되어 있어서 다양한 타입의 컨테이너에 적용할 수 있다. 참고로 알고리즘은 컨테이너에 속하지 않는다는 점을 주의한다.

표준 라이브러리는 데이터(컨테이너)와 기능(알고리즘)을 엄격히 구분한다. 얼핏 생각하면 객체지향 프로그래밍 정신에 어긋나 보이지만 표준 라이브러리의 범용성을 유지하기 위해서는 중요한 원칙이다. 이렇나 직교성 원칙에 따라 컨테이너와 알고리즘을 서로 독립적으로 관리한다. 그래서 거의 모든 종류의 알고리즘과 컨테이너를 조합해서 사용할 수 있다.

Note) 알고리즘과 컨테이너가 이론상 구분돼 있지만, 어떤 컨테이너는 클래스 메서드 형태로 알고리즘을 제공하기도 한다. 컨테이너의 성격에 따라 제네릭 알고리즘으로 처리하면 성능이 떨어지기 때문이다. 예컨대 set에서 제공하는 find() 메서드에 제공된 알고리즘은 제네릭 버전의 find() 보다 더 빠르다.

여기서 제네릭 알고리즘을 곧바로 컨테이너에 적용할 수 없다는 점에 주의한다. 대부분 반복자(iterator)라 부르는 중간 매체를 거친다. 표준 라이브러리에서 제공하는 컨테이너는 대부분 그 컨테이너에 담긴 원소를 순차적으로 탐색하도록 반복자를 제공한다. 컨테이너마다 반복자의 동작은 다르지만, 모두 표준 인터페이스를 따르기 때문에 내부적으로 구현된 컨테이너의 종류에 관계 없이 반복자를 구현하는 코드의 형태는 모두 같다. <iterator> 헤더 파일은 다음과 같이 컨테이너에 맞는 반복자를 리턴하는 헬퍼 함수를 제공하고 있다.

함수 이름 설명
begin()
end()
첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 non-const 반복자를 리턴한다.
cbegin()
cend()
첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 const 반복자를 리턴한다.
rbegin()
rend()
마지막 원소부터 첫 번째 항목의 바로 전 원소까지 순차적으로(역방향으로) 탐색하는 non-const 반복자를 리턴한다.
crbegin()
crend()
마지막 원소부터 첫 번째 항목의 바로 전 원소까지 순차적으로(역방향으로) 탐색하는 const 반복자를 리턴한다.

Note) 반복자는 알고리즘과 컨테이너를 연결한다. 컨테이너에 담긴 원소를 순차적으로 탐색하기 위한 표준 인터페이스를 제공하기 때문에 알고리즘과 컨테이너의 종류에 관계 없이 똑같은 방식으로 코드를 작성할 수 있다.

Note) 알고리즘을 훑어볼 때 표준 라이브러리는 범용성(일반화)에 주안점을 두고 디자인했다는 사실을 명심하기 바란다. 얼핏 쓸데없어 보이지만 범용성을 위해 반드시 필요한 기능과 구조가 반영돼 있다.

불변형 순차 알고리즘

불변형 순차 알고리즘(non-modifying sequence algorithm)이란 원소를 순차적으로 조회하여 각 원소에 대한 정보를 리턴하는 알고리즘을 말한다. ‘불변형’ 이란 표현에서 눈치챌 수 있듯이 원소의 값이나 순서를 변경하지 않는다. 여기에 속한 알고리즘을 크게 세 가지로 구분할 수 있다.  여기 나온 알고리즘을 사용하면 원소를 순차적으로 탐색할 때 for 문을 작성할 일이 거의 없다.

탐색 알고리즘

탐색 알고리즘(search algorithm)은 원소가 정렬돼 있지 않아도 사용할 수 있다. 여기서 N은 탐색할 대상의 크기를 의미하고 M은 탐색할 패턴의 크기를 의미한다.

알고리즘 이름 설명 복잡도
adjacent_find() 조건으로 입력한 값과 같거나 조건식에 대입한 결과가 같은 연속된 두 원소 중 처음 나온 것을 찾는다. O(N)
find()
find_if()
조건으로 입력한 값과 같거나 조건식의 결과가 true인 원소 중 첫 번째 원소를 찾는다. O(N)
find_first_of() find()와 비슷하지만 여러 원소를 동시에 찾는다. O(NM)
find_if_not() 조건식의 결과가 false인 원소 중 첫 번째 원소를 찾는다. O(N)
find_end() 입력한 시퀀스나 조건식에 맞는 시퀀스 중에서 마지막 부분을 찾는다. O(M*(N-M))
search() 입력된 시퀀스와 일치하거나 입력한 조건식을 기준으로 같다고 판단되는 시퀀스 중에서 첫 번째 항목을 찾는다. O(NM)*
search_n() 입력한 값과 같거나 입력한 조건식을 기준으로 같다고 판단되는 원소 중 n번 연속해서 일치하는 결과 중 첫 번째 결과를 찾는다. O(N)
비교 알고리즘

여기 나온 알고리즘은 입력값이 정렬되지 않아도 사용할 수 있다. 모두 최악의 경우 선형 복잡도를 갖는다.

알고리즘 이름 설명
equal() 입력한 두 시퀀스가 서로 같거나, 입력한 조건식을 모두 만족하는지 검사한다.
mismatch() 입력한 시퀀스와 일치하지 않는 지점의 첫 번째 원소를 리턴한다.
lexicographical_compare() 입력한 두 시퀀스를 사전 나열 순서대로 비교한다. 이 알고리즘은 첫 번째 인수와 두 번째 인수로 입력한 시퀀스의 모든 항목을 하나씩 비교한다. 각 원소를 비교할 때마다 어느 하나가 사전 순으로 더 작다고 판단되면 그 시퀀스가 먼저다. 두 원소가 같으면 그 다음 번째의 원소를 비교한다.
집계 알고리즘
알고리즘 이름 설명
all_of() 입력 시퀀스에 있는 모든 원소에 대해 조건식이 true를 리턴하거나 입력 시퀀스가 공백이면 true를 리턴한다. 나머지는 false를 리턴한다.
any_of() 입력 시퀀스에 있는 원소 중 최소 하나에 대해 조건식이 true를 리턴하면 true를 리턴한다. 나머지는 false를 리턴한다.
none_of() 입력 시퀀스에 있는 모든 원소에 대해 조건식이 false를 리턴하거나 입력 시퀀스가 공백이면 true를 리턴한다. 나머지는 false를 리턴한다.
count()
count_if()
입력한 값과 일치하는 원소나 입력한 조건식의 결과가 true가 되는 원소 수를 센다.

가변형 순차 알고리즘

가변형 순차 알고리즘(modifying sequence algorithm)이란 시퀀스의 모든 원소나 일부 원소를 수정하는 알고리즘이다. 어떤 알고리즘은 원소가 있는 자리에서 바로 수정하기 때문에 순서가 바뀔 수 있다. 또 어떤 알고리즘은 결과를 별도의 시퀀스로 복사하기 때문에 원래 순서가 그대로 유지된다. 두 가지 알고리즘 모두 최악의 경우 선형 복잡도의 성능을 낸다.

알고리즘 이름 설명
copy()
copy_backward()
원본 시퀀스를 대상 시퀀스로 복제한다.
copy_if() 원본 시퀀스에서 조건식이 true를 리턴하는 원소를 대상 시퀀스로 복제한다.
copy_n() 원본 시퀀스에서 n개 원소를 대상 시퀀스로 복제한다.
fill() 시퀀스의 원소를 모두 새 값으로 설정한다.
fill_n() 시퀀스에서 n개 원소를 새 값으로 설정한다.
generate() 지정한 함수를 호출해서 시퀀스의 원소에 채울 새 값을 생성한다.
generate_n() 지정한 함수를 호출해서 시퀀스의 앞부터 n개 원소에 채울 새 값을 생성한다.
move()
move_backward()
원본 시퀀스의 원소를 대상 시퀀스로 옮긴다. 효율적으로 옮기도록 이동 의미론을 적용한다.

revmove()
remove_if()
remove_copy()
remove_copy_if()

지정한 값과 일치하거나 지정한 조건식이 true가 되는 원소를 바로 그 자리에서 삭제하거나 다른 시퀀스로 복제해서 삭제한다.
replace()
replace_if()
replace_copy()
replace_copy_if()
지정한 값과 일치하거나 지정한 조건시기 true가 되는 원소를 모두 그 자리에서 새 원소로 교체하거나 다른 시퀀스로 복제해서 교체한다
reverse()
reverse_copy()
원본 시퀀스에 나열된 원소의 순서를 그 자리에서 반대로 바꾸거나 다른 시퀀스에 복제해서 바꾼다.
rotate()
rotate_copy()
주어진 시퀀스를 두 개로 나눠서 앞부분과 뒷부분의 위치를 그 자리에서 바꾸거나 결과를 다른 시퀀스에 복제한다. 이때 두 시퀀스의 길이는 서로 달라도 된다.
sample() 주어진 시퀀스에서 n개 원소를 무작위로 선택한다.
shuffle()
random_shuffle()
주어진 시퀀스에 담긴 원소의 순서를 무작위로 바꾼다. 이때 사용할 무작위수 생성기를 직접 지정할 수 있다. 
random_shuffle()은 C++ 14부터 폐기 됐고, C++ 17부터 완전히 삭제됐다.
transform() 주어진 시퀀스의 각 우너소에 대해 단항 함수를 호출하거나 두 시퀀스에서 위치가 같은 원소에 대해 이항 함수를 호출한다. 변환은 그 자리에서 수행한다.
unique()
unique_copy()
주어진 시퀀스에서 연속적으로 중복되는 항목을 그 자리에서 제거하거나 다른 시퀀스로 복제해서 제거한다.

작업 알고리즘

작업 알고리즘(operational algorithm)은 시퀀스의 원소마다 함수를 실행한다. 표준 라이브러리에서 제공하는 작업 알고리즘은 두 가지가 있으며 둘 다 선형 복잡도를 갖고 원본 시퀀스를 정렬하지 않아도 사용할 수 있다.

알고리즘 이름 설명
for_each() 주어진 시퀀스에 담긴 원소마다 함수를 실행한다. 시퀀스는 시작 반복자와 끝 반복자로 지정한다.
for_each_n() for_each()와 비슷하지만 주어진 시퀀스에서 첫 n개 원소만 처리한다. 시퀀스는 시작 반복자와 원소 수(n)로 지정한다.

교환 알고리즘

알고리즘 이름 설명
iter_swap()
swap_ranges()
두 원소 또는 시퀀스를 맞바꾼다.
swap() 두 값을 맞바꾼다.
exchage() 지정한 값을 새 값으로 교체하고 기존 값을 리턴한다.

분할 알고리즘

주어진 조건식(predicate)에 시퀀스를 적용했을 때 true를 리턴하는 원소가 false를 리턴하는 원소보다 앞에 있으면 그 시퀀스를 분할(partition)한다. 시퀀스에서 조건식을 만족하지 않는 첫 원소를 분할 지점(partition point, 파티션 포인트)이라 부른다.

알고리즘 이름 설명 복잡도
is_partitioned() 조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있으면 true를 리턴한다. 선형
partition() 조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있도록 시퀀스를 정렬한다. 각 파티션의 원소는 원본 순서를 유지하지 않는다. 선형
stable_partition() 조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있도록 시퀀스를 정렬한다. 각 파티션의 원소는 원본 순서를 유지한다. 선형 로그
partition_copy() 원본 시퀀스에 있는 원소를 서로 다른 두 시퀀스로 복제한다. 대상 시퀀스는 조건식의 결과가 true인지 false인지에 따라 결정한다. 선형
partition_point() 반복자 앞에 나온 원소가 모두 조건식에 대해 true가 되고 반복자 뒤에 나온 원소가 모두 조건식에 대해 false가 되는 반복자를 리턴한다. 로그

정렬 알고리즘

알고리즘 이름 설명 복잡도
is_sorted()
is_sorted_until()
시퀀스 또는 부분 시퀀스가 정렬된 상태인지 검사한다. 선형
nth_element() 시퀀스를 정렬했을 때 인수로 지정한 원소가 n번째 원소가 되도록 위치를 이동하고, 그 앞에 나온 원소가 모두 n번째 원소보다 작고, 그 뒤에 나온 원소가 n번째 원소보다 크도록 정렬한다. 선형
partial_sort()
partial_sort_copy()
시퀀스의 일부분, 즉 첫 n개 원소만 정렬한다(지정한 반복자를 기준으로) 나머지는 그대로 둔다. 그 자리에서 곧바로 정렬하거나 새 시퀀스에 복제해서 정렬한다. 선형 로그
sort()
stable_sort()
원소를 그 자리에서 곧바로 정렬한다. 중복된 원소는 순서가 바뀔수도 있고(sort()), 유지될 수도 있다(stable_sort()) 선형 로그

이진 탐색 알고리즘

여기서 소개할 이진 탐색 알고리즘(binary search algorithm)은 주로 정렬된 시퀀스에 적용한다. 구체적으로 설명하면 대상 시퀀스가 최소한 탐색할 원소를 기준으로 분할된 상태여야 한다. 대상 시퀀스는 std::partition() 등으로 분할 할 수 있다. 정렬된 시퀀스도 마찬가지로 이 조건을 만족해야 한다. 여기 소개하는 알고리즘의 복잡도는 모두 로그다.

알고리즘 이름 설명
lower_bound() 주어진 값보다 작지 않은(크거나 같은) 첫 번째 원소를 시퀀스에서 찾는다.
upper_bound() 주어진 값보다 큰 첫 번째 원소를 시퀀스에서 찾는다.
equal_range() lower_bound()와 upper_bound()의 결과를 모두 담은 pair를 리턴한다.
binary_search() 지정한 값이 시퀀스에 있으면 true, 아니면 false를 리턴한다.

집합 알고리즘

집합 알고리즘(set algorithm)은 시퀀스에 대해 집합 연산을 수행하는 특수한 형태의 가변 알고리즘(modifying algorithm)이다. set 컨테이너에 있는 시퀀스에 가장 적합하지만 다른 컨테이너의 정렬된 시퀀스에도 대부분 적용할 수 있다.

(전체가 아니라 C#과 차이가 있는 부분을 중심으로 요약 정리)

C++ 프로그래머에게 가장 중요한 라이브러리는 C++ 표준 라이브러리(Standard Library)이다. C++ 표준 라이브러리 중에서 가장 핵심은 제네릭 컨테이너와 제네릭 알고리즘이다. 이 라이브러리는 원래 표준 템플릿 라이브러리(Standard Template Library, STL)라는 이름의 서드파티 라이브러리였다. 그래서 아직도 표준 라이브러리는 STL이라 부르는 사람이 많은데 이는 표준 용어가 아니다.

(이하 내용 생략)

코드 작성법

표준 라이브러리는 C++의 템플릿과 연산자 오버로딩 기능을 상당히 많이 사용한다.

템플릿 활용

템플릿을 활용하면 제네릭 프로그래밍을 할 수 있다. 

(이하 설명 생략)

연산자 오버로딩 활용

(내용 생략)

C++ 표준 라이브러리 둘러보기

스트링

C++은 string이란 클래스를 기본으로 제공한다. C++에서 C 스타일의 문자 배열로 스트링을 표현해도 되지만 C++의 string을 활용하는 것이 여러모로 유리하다. 메모리를 관리해 줄 뿐만 아니라 인덱스 경계 검사, 대입과 비교 기능, 스트링 결합 , 스트링 추출, 부분 스트링 만들기, 문자 치환 등과 같은 다양한 기능도 제공한다.

Note) 엄밀히 말하면 std::string은 std::basic_string 템플릿을 char 타입 매개변수로 인스턴스화한 것의 타입 앨리어스이지만 이런 세부사항은 알 필요 없고 일반 클래스처럼 사용해도 된다.

표준 라이브러리는 string_view 클래스도 제공한다. string_view는 스트링을 읽기 전용으로 표현한다. 또한 const string& 자리에 그대로 넣을 수 있고 오버헤드도 발생하지 않는다. 스트링을 복제하지 않기 때문이다.

정규표현식

정규표현식을 활용하면 패턴 매칭을 쉽게 구현할 수 있다. 정규 표현식은 19장에서 설명한다.

I/O 스트림

C++이 제공하는 입력과 출력에 대한 모델.

스마트 포인터

C++은 unique_ptr, shared_ptr, weak_ptr와 같은 스마트 포인터를 제공한다. shared_ptr과 weak_ptr은 스레드에 안전하다.

C++ 11버전 이전에는 unique_ptr에 대한 기능을 auto_ptr 타입으로 처리했지만 C++ 17부터 auto_ptr이 없어졌기 때문에 이제는 이렇게 사용하지 않는 것이 좋다.

익셉션

C++는 익셉션 메커니즘을 제공한다. C++ 표준 라이브러리는 익셉션에 대해 정의된 상속 계층을 제공하는데, 적절한 타입의 익셉션을 코드에서 곧바로 사용하거나 그중에서 원하는 익셉션을 커스터마이즈 할 수도 있다.

수학 관련 유틸리티

C++ 표준라이브러리는 수학 연산에 관련된 다양한 클래스와 함수도 제공한다.

C++ 17부터는 르장드르 다항식, 베타 함수, 타원 적분, 베셀 함수, 원기둥 함수인 노이만 함수와 같은 특수한 수학 함수도 추가됐다.

또한 complex란 이름의 복소수 클래스도 제공한다.

컴파일 시간 유리수 연산 라이브러리는 ratio 클래스 템플릿을 제공한다.

표준 라이브러리는 valarray란 클래스도 제공하는데 이 클래스는 vector와 비슷하지만 고성능 수치 연산용으로 최적화한 것이다. 이 라이브러리는 벡터 슬라이스(vector slice)를 표현하는 클래스를 다양하게 제공한다. 이런 기본 요소로 행렬 연산을 수행하는 클래스를 정의할 수 있다. 표준 라이브러리는 행렬을 직접 다루는 클래스는 제공하지 않지만 부스트 같은 서드파티 라이브러리는 행렬 연산에 관련된 클래스를 제공한다.

시간 관련 유틸리티

C++은 시간에 관련된 chrono 라이브러리도 제공한다.

무작위수

C++은 예전부터 srand()와 rand() 함수를 통해 의사 무작위수 생성기능을 제공했다. 하지만 이 함수는 굉장히 기초적인 수준으로만 무작위수를 생성할 수 있다.

C++ 11부터 이보다 훨씬 강력한 무작위수 라이브러리가 표준에 추가됐다. 이 라이브러리는 <random> 헤더 파일에 정의돼 있으며 무작위수 엔진, 무작위수 엔진 어댑터, 무작위수 분포 등도 제공한다. 이 기능을 활용하면 정규 분포, 역지수 분포 등에 보다 적합한 무작위수를 생성할 수 있다.

이니셜라이즈 리스트

이니셜라이즈 리스트는 인수의 개수가 다양한 함수를 쉽게 작성할 수 있다.

pair와 tuple

<utility> 헤더 파일에서는 서로 다른 타입의 두 원소를 하나로 묶어서 저장하는 pair 템플릿을 정의하고 있다. 이런 저장 방식을 이종(heterogeneous) 원소 저장이라 부른다. 이 장에서 소개하는 표준 라이브러리 컨테이너는 모두 동종(homogeneous) 원소 저장 방식을 따른다. 즉 컨테이너에 담긴 원소의 타입은 모두 같다. pair 템플릿을 이용하면 서로 타입이 다른 두 원소를 객체 하나에 담을 수 있다.

<tuple> 헤더에 정의된 tuple은 pair를 일반화한 것이다. 고정된 크기의 수열로서 서로 타입이 다른 원소를 저장할 수 있다. tuple에 담긴 원소 개수와 타입은 tuple 인스턴스를 생성하는 컴파일 시간에 결정된다. 튜플은 20장에서 자세히 설명한다.

optional, variant, any

C++ 17부터 다음의 클래스가 새로 추가됐다.

  • optional
    • 특정한 타입의 값을 저장하거나 값을 가지지 않을 수 있다. 값이 없을 수도 있는 함수의 매개변수나 리턴 타입으로 사용할 수 있다.
  • variant
    • 지정한 타입 집합 중 하나의 값을 가지거나 값을 가지지 않을 수 있다.
  • any
    • 모든 타입의 값을 단 하나만 가진다.

이 세 가지 클래스는 20장에서 설명한다.

함수 객체

함수 호출 연산자를 구현하는 클래스를 함수 객체(function object), 펑터(functor)라 부른다. 함수 객체는 특정한 표준 라이브러리 알고리즘에 대한 조건식(predicate) 등에 활용된다.

함수 객체는 18장에서 자세히 소개한다.

파일시스템

C++ 17부터 파일시스템을 지원하는 라이브러리가 추가됐다. 그래서 파일시스템을 다루는 코드를 이식(포팅)하기 쉽게 만들 수 있다. 파일시스템 지원 라이브러리는 20장에서 자세히 설명한다.

멀티스레딩

표준 라이브러리는 멀티스레딩을 지원하는데 필요한 다양한 기본 기능을 제공한다. <thread> 헤더 파일에 정의된 thread 클래스를 이용하면 스레드를 하나씩 생성할 수 있다.

멀티스레드 코드를 작성할 때는 여러 스레드가 같은 데이터를 동시에 읽고 쓰지 않도록 조심해야 한다. 이때 <atomic> 헤더 팡리에 정의된 atomic을 사용하면 데이터를 스레드에 안전하고 아토믹하게 (여러 스레드가 동시에 접근하지 않게) 만들 수 있다. <condition_variable>과 <mutex> 헤더 파일에서도 다양한 스레드 동기화 메커니즘을 제공한다.

여러 스레드로 뭔가 계산해서 적절한 예외 처리 방식을 통해 결과를 받기만 한다면 async와 future를 활용한다. 둘 다 <future> 헤더 파일에 정의돼 있으며 thread 클래스를 직접 다룰 때보다 훨씬 사용하기 쉽다.

타입 트레이드

타입 트레이트(type traits, 타입 특성/속성) 기능은 컴파일 시간에 타입 정보를 조회할 수 있다. 이 기능은 고급 템플릿을 작성할 때 유용하며 22장에서 자세히 설명한다.

표준 정수 타입

<cstdint> 헤더 파일에서는 다양한 표준 정수 타입을 정의하고 이싿. 또한 이러한 타입의 최댓값과 최솟값을 지정하는 매크로도 제공한다. 이런 정수 타입에 대한 자세한 사항은 30장에서 다룬다.

컨테이너

표준 라이브러리는 연결 리스트(linked list)나 큐(queue)와 같이 흔히 사용되는 데이터 구조를 제공한다. C++로 프로그래밍할 때는 이러한 데이터 구조를 직접 구현할 필요 없다. 이러한 데이터 구조는 정보를 원소(element) 단위로 저장하는 컨테이너(container) 개념에 따라 구현했으며, 연결 리스트나 큐와 같은 구쳊거인 데이터의 구조의 특성에 맞게 다양하게 구현했다.

표준 라이브러리에서 제공하는 컨테이너는 모두 클래스 템플릿이다. 그래서 int나 double 같은 기본 타입 뿐만 아니라 사용자가 정의한 클래스에 이르기까지 모든 타입의 데이터를 담을 수 있다. 컨테이너 인스턴스마다 단 한가지 타입의 객체만 저장할 수 있다. 다시 말해 동형(homogeneous) 컬렉션이다.

크기가 고정되지 않은 동형 컬렉션이 필요하다면 각각의 원소를 std::any 인스턴스로 만들어서 컨테이너에 저장한다. 아니면 std::variant 인스턴스로 저장해도 된다. 지원할 타입의 범위가 작고 컴파일 시간에 결정할 수 있다면 variant로 만든다.

C++ 17 이전 버전에서 이형(heeterogeneous) 컬렉션이 필요하다면 각 타입에 맞는 파생 클래스로 구성된 클래스를 새로 정의한다.

(이하 개별 컬렉션 설명 생략)

기본 설명

컨테이너 클래스 이름 컨테이너 타입 사용 시기
vector 순차 컨테이너 기본 컨테이너로 사용한다. 프로파일러로 분석한 결과 이보다 낫다고 판단될 때만 다른 컨테이너를 사용한다.
list 순차 사용할 일이 거의 없다. 프로파일러로 분석한 결과 list가 vector 보다 낫다고 판단되지 않으면 웬만하면 vector를 쓴다.
forward_list 순차 사용할 일이 거의 없다. 프로파일러로 분석한 결과 forward_list가 vector 보다 낫다고 판단되지 않으면 웬만하면 vector를 쓴다.
deque 순차 사용할 일이 많지 않다. 주로 vector를 쓴다.
array 순차 표준 C 스타일 배열 대신 고정 크기 배열이 필요할 때
queue 컨테이너 어댑터 FIFO 구조가 필요할 떄
priority_queue 컨테이너 어댑터 우선순위가 있는 queue를 구현하고 싶을 때
stack 컨테이너 어댑터 FILO이나 LIFO 구조를 구현하고 싶을 때
set
multiset
정렬 연관 원소를 정렬된 묶음에 담고, 조회/추가/삭제 성능도 모두 같게 만들고 싶을 때. 원소의 중복을 허용하지 않으려면 set을 이용한다.
map
multimap
정렬 연관 원소를 키와 값이 연관된 순서쌍으로 키 값에 대해 정렬된 상태, 즉 연관 배열로 저장하면서 조회/추가/삭제 성능도 모두 같게 만들고 싶을 때
unodered_map
unordered_multimap
비정렬 연관  키와 값을 묶어서 저장하고 조회, 추가, 삭제 성능이 모두 같게 만들고 싶으면서 원소를 정렬하지 않아도 될 때. 일반 map 보다 성능이 좋지만 원소의 종류에 따라 달라질 수 있다.
unorderd_set
unorderd_multiset 
비정렬 연관 조회, 추가, 삭제 성능이 모두 같게 만들고 싶으면서 우너소를 정렬하지 않아도 될 때, 일반 set보다 성능이 좋지만 원소의 종류에 따라 달라질 수 있다.
bitset 특수 플래그 묶음을 표현하고 싶을 때

성능

컨테이너 클래스 이름 추가 연산 성능 삭제 연산 성능 조회 연산 성능
vector 끝에서는 분할 상환 성능이 O(1), 나머지는 O(N) 끝에서는 O(1), 나머지는 O(N) O(1)
list 시작과 끝점 그리고 추가할 위치가 정확히 결정된 상태에는 O(1) 시작과 끝점 그리고 추가할 위치가 정확히 결정된 상태에는 O(1) 첫 번째와 마지막 원소를 조회할 때는 O(1), 나머지는 O(N)
forward_list 추가할 지점이 시작점이거나 정확한 위치를 안다면 O(1) 삭제할 지점이 시작점이거나 정확한 위치를 안다면 O(1) 첫 번째 원소를 조회할 때는 O(1), 나머지는 O(N)
deque 시작과 끝에서는 O(1), 나머지는 O(N) 시작과 끝에서는 O(1), 나머지는 O(N) O(1)
array N/A N/A N/A
queue 내부 컨테이너의 종류에 따라 다르다. list나 deque로 구현할 때는 O(1) 내부 컨테이너의 종류에 따라 다르다. list나 deque로 구현할 때는 O(1) N/A
priority_queue 내부 컨테이너에 따라 다르다 vector를 사용할 때는 분할 상환 성능이 O(log(N))이고 deque를 사용할 때는 O(log(N))이다. 내부 컨테이너에 따라 다르다. vector나 deque를 사용할 때는 O(log(N)) N/A
stack 내부 컨테이너에 따라 다르다. list나 deque를 사용하면 O(1), vector를 사용하면 분할 상환 성능으로 O(1) 내부 컨테이너에 따라 다르다. list, vector, deque일 때 O(1), N/A
set
multiset
O(log(N)) O(log(N)) O(log(N))
map
multimap
O(log(N)) O(log(N)) O(log(N))
unodered_map
unordered_multimap
평균 O(1),
최악 O(N)
평균 O(1),
최악 O(N)
평균 O(1),
최악 O(N)
unorderd_set
unorderd_multiset 
평균 O(1),
최악 O(N)
평균 O(1),
최악 O(N)
평균 O(1),
최악 O(N)
bitset N/A N/A N/A

Note) 반드시 vector를 기본 컨테이너로 사용하기 바란다. 실전에서 list나 forward_list를 사용하는 것보다 vector로 구현하는 것이 추가나 삭제 연산이 훨씬 빠르다. 그 이유는 최신 CPU에서 메모리와 캐시를 처리하는 방식 때문이기도 하고, list, forward_list를 사용할 때는 추가나 삭제할 지점까지 탐색하는 오버헤드가 있기 때문이다. list나 foward_list는 메모리 공간에 연속적으로 저장되지 않을 수 있다. 그래서 vector보다 반복문의 성능이 떨어질 수 있다.

알고리즘

표준 라이브러리는 컨테이너 뿐만 다양한 제네릭 알고리즘도 제공한다. 표준 라이브러리에서 제공하는 알고리즘은 함수 템플릿으로 구현되어 있어서 다양한 타입의 컨테이너에 적용할 수 있다. 참고로 알고리즘은 컨테이너에 속하지 않는다는 점을 주의한다.

표준 라이브러리는 데이터(컨테이너)와 기능(알고리즘)을 엄격히 구분한다. 얼핏 생각하면 객체지향 프로그래밍 정신에 어긋나 보이지만 표준 라이브러리의 범용성을 유지하기 위해서는 중요한 원칙이다. 이렇나 직교성 원칙에 따라 컨테이너와 알고리즘을 서로 독립적으로 관리한다. 그래서 거의 모든 종류의 알고리즘과 컨테이너를 조합해서 사용할 수 있다.

Note) 알고리즘과 컨테이너가 이론상 구분돼 있지만, 어떤 컨테이너는 클래스 메서드 형태로 알고리즘을 제공하기도 한다. 컨테이너의 성격에 따라 제네릭 알고리즘으로 처리하면 성능이 떨어지기 때문이다. 예컨대 set에서 제공하는 find() 메서드에 제공된 알고리즘은 제네릭 버전의 find() 보다 더 빠르다.

여기서 제네릭 알고리즘을 곧바로 컨테이너에 적용할 수 없다는 점에 주의한다. 대부분 반복자(iterator)라 부르는 중간 매체를 거친다. 표준 라이브러리에서 제공하는 컨테이너는 대부분 그 컨테이너에 담긴 원소를 순차적으로 탐색하도록 반복자를 제공한다. 컨테이너마다 반복자의 동작은 다르지만, 모두 표준 인터페이스를 따르기 때문에 내부적으로 구현된 컨테이너의 종류에 관계 없이 반복자를 구현하는 코드의 형태는 모두 같다. <iterator> 헤더 파일은 다음과 같이 컨테이너에 맞는 반복자를 리턴하는 헬퍼 함수를 제공하고 있다.

함수 이름 설명
begin()
end()
첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 non-const 반복자를 리턴한다.
cbegin()
cend()
첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 const 반복자를 리턴한다.
rbegin()
rend()
마지막 원소부터 첫 번째 항목의 바로 전 원소까지 순차적으로(역방향으로) 탐색하는 non-const 반복자를 리턴한다.
crbegin()
crend()
마지막 원소부터 첫 번째 항목의 바로 전 원소까지 순차적으로(역방향으로) 탐색하는 const 반복자를 리턴한다.

Note) 반복자는 알고리즘과 컨테이너를 연결한다. 컨테이너에 담긴 원소를 순차적으로 탐색하기 위한 표준 인터페이스를 제공하기 때문에 알고리즘과 컨테이너의 종류에 관계 없이 똑같은 방식으로 코드를 작성할 수 있다.

Note) 알고리즘을 훑어볼 때 표준 라이브러리는 범용성(일반화)에 주안점을 두고 디자인했다는 사실을 명심하기 바란다. 얼핏 쓸데없어 보이지만 범용성을 위해 반드시 필요한 기능과 구조가 반영돼 있다.

불변형 순차 알고리즘

불변형 순차 알고리즘(non-modifying sequence algorithm)이란 원소를 순차적으로 조회하여 각 원소에 대한 정보를 리턴하는 알고리즘을 말한다. ‘불변형’ 이란 표현에서 눈치챌 수 있듯이 원소의 값이나 순서를 변경하지 않는다. 여기에 속한 알고리즘을 크게 세 가지로 구분할 수 있다.  여기 나온 알고리즘을 사용하면 원소를 순차적으로 탐색할 때 for 문을 작성할 일이 거의 없다.

탐색 알고리즘

탐색 알고리즘(search algorithm)은 원소가 정렬돼 있지 않아도 사용할 수 있다. 여기서 N은 탐색할 대상의 크기를 의미하고 M은 탐색할 패턴의 크기를 의미한다.

알고리즘 이름 설명 복잡도
adjacent_find() 조건으로 입력한 값과 같거나 조건식에 대입한 결과가 같은 연속된 두 원소 중 처음 나온 것을 찾는다. O(N)
find()
find_if()
조건으로 입력한 값과 같거나 조건식의 결과가 true인 원소 중 첫 번째 원소를 찾는다. O(N)
find_first_of() find()와 비슷하지만 여러 원소를 동시에 찾는다. O(NM)
find_if_not() 조건식의 결과가 false인 원소 중 첫 번째 원소를 찾는다. O(N)
find_end() 입력한 시퀀스나 조건식에 맞는 시퀀스 중에서 마지막 부분을 찾는다. O(M*(N-M))
search() 입력된 시퀀스와 일치하거나 입력한 조건식을 기준으로 같다고 판단되는 시퀀스 중에서 첫 번째 항목을 찾는다. O(NM)*
search_n() 입력한 값과 같거나 입력한 조건식을 기준으로 같다고 판단되는 원소 중 n번 연속해서 일치하는 결과 중 첫 번째 결과를 찾는다. O(N)
비교 알고리즘

여기 나온 알고리즘은 입력값이 정렬되지 않아도 사용할 수 있다. 모두 최악의 경우 선형 복잡도를 갖는다.

알고리즘 이름 설명
equal() 입력한 두 시퀀스가 서로 같거나, 입력한 조건식을 모두 만족하는지 검사한다.
mismatch() 입력한 시퀀스와 일치하지 않는 지점의 첫 번째 원소를 리턴한다.
lexicographical_compare() 입력한 두 시퀀스를 사전 나열 순서대로 비교한다. 이 알고리즘은 첫 번째 인수와 두 번째 인수로 입력한 시퀀스의 모든 항목을 하나씩 비교한다. 각 원소를 비교할 때마다 어느 하나가 사전 순으로 더 작다고 판단되면 그 시퀀스가 먼저다. 두 원소가 같으면 그 다음 번째의 원소를 비교한다.
집계 알고리즘
알고리즘 이름 설명
all_of() 입력 시퀀스에 있는 모든 원소에 대해 조건식이 true를 리턴하거나 입력 시퀀스가 공백이면 true를 리턴한다. 나머지는 false를 리턴한다.
any_of() 입력 시퀀스에 있는 원소 중 최소 하나에 대해 조건식이 true를 리턴하면 true를 리턴한다. 나머지는 false를 리턴한다.
none_of() 입력 시퀀스에 있는 모든 원소에 대해 조건식이 false를 리턴하거나 입력 시퀀스가 공백이면 true를 리턴한다. 나머지는 false를 리턴한다.
count()
count_if()
입력한 값과 일치하는 원소나 입력한 조건식의 결과가 true가 되는 원소 수를 센다.

가변형 순차 알고리즘

가변형 순차 알고리즘(modifying sequence algorithm)이란 시퀀스의 모든 원소나 일부 원소를 수정하는 알고리즘이다. 어떤 알고리즘은 원소가 있는 자리에서 바로 수정하기 때문에 순서가 바뀔 수 있다. 또 어떤 알고리즘은 결과를 별도의 시퀀스로 복사하기 때문에 원래 순서가 그대로 유지된다. 두 가지 알고리즘 모두 최악의 경우 선형 복잡도의 성능을 낸다.

알고리즘 이름 설명
copy()
copy_backward()
원본 시퀀스를 대상 시퀀스로 복제한다.
copy_if() 원본 시퀀스에서 조건식이 true를 리턴하는 원소를 대상 시퀀스로 복제한다.
copy_n() 원본 시퀀스에서 n개 원소를 대상 시퀀스로 복제한다.
fill() 시퀀스의 원소를 모두 새 값으로 설정한다.
fill_n() 시퀀스에서 n개 원소를 새 값으로 설정한다.
generate() 지정한 함수를 호출해서 시퀀스의 원소에 채울 새 값을 생성한다.
generate_n() 지정한 함수를 호출해서 시퀀스의 앞부터 n개 원소에 채울 새 값을 생성한다.
move()
move_backward()
원본 시퀀스의 원소를 대상 시퀀스로 옮긴다. 효율적으로 옮기도록 이동 의미론을 적용한다.

revmove()
remove_if()
remove_copy()
remove_copy_if()

지정한 값과 일치하거나 지정한 조건식이 true가 되는 원소를 바로 그 자리에서 삭제하거나 다른 시퀀스로 복제해서 삭제한다.
replace()
replace_if()
replace_copy()
replace_copy_if()
지정한 값과 일치하거나 지정한 조건시기 true가 되는 원소를 모두 그 자리에서 새 원소로 교체하거나 다른 시퀀스로 복제해서 교체한다
reverse()
reverse_copy()
원본 시퀀스에 나열된 원소의 순서를 그 자리에서 반대로 바꾸거나 다른 시퀀스에 복제해서 바꾼다.
rotate()
rotate_copy()
주어진 시퀀스를 두 개로 나눠서 앞부분과 뒷부분의 위치를 그 자리에서 바꾸거나 결과를 다른 시퀀스에 복제한다. 이때 두 시퀀스의 길이는 서로 달라도 된다.
sample() 주어진 시퀀스에서 n개 원소를 무작위로 선택한다.
shuffle()
random_shuffle()
주어진 시퀀스에 담긴 원소의 순서를 무작위로 바꾼다. 이때 사용할 무작위수 생성기를 직접 지정할 수 있다. 
random_shuffle()은 C++ 14부터 폐기 됐고, C++ 17부터 완전히 삭제됐다.
transform() 주어진 시퀀스의 각 우너소에 대해 단항 함수를 호출하거나 두 시퀀스에서 위치가 같은 원소에 대해 이항 함수를 호출한다. 변환은 그 자리에서 수행한다.
unique()
unique_copy()
주어진 시퀀스에서 연속적으로 중복되는 항목을 그 자리에서 제거하거나 다른 시퀀스로 복제해서 제거한다.

작업 알고리즘

작업 알고리즘(operational algorithm)은 시퀀스의 원소마다 함수를 실행한다. 표준 라이브러리에서 제공하는 작업 알고리즘은 두 가지가 있으며 둘 다 선형 복잡도를 갖고 원본 시퀀스를 정렬하지 않아도 사용할 수 있다.

알고리즘 이름 설명
for_each() 주어진 시퀀스에 담긴 원소마다 함수를 실행한다. 시퀀스는 시작 반복자와 끝 반복자로 지정한다.
for_each_n() for_each()와 비슷하지만 주어진 시퀀스에서 첫 n개 원소만 처리한다. 시퀀스는 시작 반복자와 원소 수(n)로 지정한다.

교환 알고리즘

알고리즘 이름 설명
iter_swap()
swap_ranges()
두 원소 또는 시퀀스를 맞바꾼다.
swap() 두 값을 맞바꾼다.
exchage() 지정한 값을 새 값으로 교체하고 기존 값을 리턴한다.

분할 알고리즘

주어진 조건식(predicate)에 시퀀스를 적용했을 때 true를 리턴하는 원소가 false를 리턴하는 원소보다 앞에 있으면 그 시퀀스를 분할(partition)한다. 시퀀스에서 조건식을 만족하지 않는 첫 원소를 분할 지점(partition point, 파티션 포인트)이라 부른다.

알고리즘 이름 설명 복잡도
is_partitioned() 조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있으면 true를 리턴한다. 선형
partition() 조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있도록 시퀀스를 정렬한다. 각 파티션의 원소는 원본 순서를 유지하지 않는다. 선형
stable_partition() 조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있도록 시퀀스를 정렬한다. 각 파티션의 원소는 원본 순서를 유지한다. 선형 로그
partition_copy() 원본 시퀀스에 있는 원소를 서로 다른 두 시퀀스로 복제한다. 대상 시퀀스는 조건식의 결과가 true인지 false인지에 따라 결정한다. 선형
partition_point() 반복자 앞에 나온 원소가 모두 조건식에 대해 true가 되고 반복자 뒤에 나온 원소가 모두 조건식에 대해 false가 되는 반복자를 리턴한다. 로그

정렬 알고리즘

알고리즘 이름 설명 복잡도
is_sorted()
is_sorted_until()
시퀀스 또는 부분 시퀀스가 정렬된 상태인지 검사한다. 선형
nth_element() 시퀀스를 정렬했을 때 인수로 지정한 원소가 n번째 원소가 되도록 위치를 이동하고 그 앞에 나온 원소가 모두 n번째 원소보다 작고, 그 뒤에 나온 원소가 n번째 원소보다 크도록 정렬한다. 선형
partial_sort()
partial_sort_copy()
시퀀스의 일부분, 즉 첫 n개 원소만 정렬한다(지정한 반복자를 기준으로) 나머지는 그대로 둔다. 그 자리에서 곧바로 정렬하거나 새 시퀀스에 복제해서 정렬한다. 선형 로그
sort()
stable_sort()
원소를 그 자리에서 곧바로 정렬한다. 중복된 원소는 순서가 바뀔수도 있고(sort()), 유지될 수도 있다(stable_sort()) 선형 로그

이진 탐색 알고리즘

여기서 소개할 이진 탐색 알고리즘(binary search algorithm)은 주로 정렬된 시퀀스에 적용한다. 구체적으로 설명하면 대상 시퀀스가 최소한 탐색할 원소를 기준으로 분할된 상태여야 한다. 대상 시퀀스는 std::partition() 등으로 분할할 수 있다. 정렬된 시퀀스도 마찬가지로 이 조건을 만족해야 한다. 여기서 소개하는 알고리즘의 복잡도는 모두 로그다.

알고리즘 이름 설명
lower_bound() 주어진 값보다 작지 않은(크거나 같은) 첫 번째 원소를 시퀀스에서 찾는다.
upper_bound() 주어진 값보다 큰 첫 번째 원소를 시퀀스에서 찾는다.
equal_range() lower_bound()와 upper_bound()의 결과를 모두 담은 pair를 리턴한다.
binary_search() 지정한 값이 시퀀스에 있으면 true, 아니면 false를 리턴한다.

집합 알고리즘

집합 알고리즘(set algorithm)은 시퀀스에 대해 집합 연산을 수행하는 특수한 형태의 가변 알고리즘(modifying algorithm)이다. set 컨테이너에 있는 시퀀스에 가장 적합하지만 다른 컨테이너의 정렬된 시퀀스에도 대부분 적용할 수 있다.

알고리즘 이름 설명 복잡도
inplace_merge() 정렬된 시퀀스 두 개를 그 자리에서 병합한다. 선형 로그
merge() 정렬된 시퀀스 두 개를 새 시퀀스에 복제해서 병합한다. 선형
includes() 어떤 정렬된 시퀀스가 다른 정렬된 시퀀스에 완전히 포함되는지 검사한다. 선형
set_union()
set_intersection()
set_difference()
set_symmetric_difference()
정렬된 시퀀스 두 개에 대해 합집합, 교집합, 차집합, 대칭 차집합 연산을 수행해서 제 3의 정렬된 시퀀스로 복제한다. 선형

힙 알고리즘

힙은 최상단(top)에 있는 원소를 빨리 찾도록 적절히 정렬된 상태를 유지하는 배열이나 시퀀스에 대한 데이터 구조다. 대표적인 예로 priority_queue를 구현할 때 힙을 사용한다.

알고리즘 이름 설명 복잡도
is_heap() 주어진 범위의 원소가 힙을 만족하는지 검사한다. 선형
is_heap_until() 주어진 범위의 원소에서 힙을 만족하는 최대 범위를 찾는다. 선형
make_heap() 주어진 범위의 원소에서 힙을 생성한다. 선형
push_heap()
pop_heap()
힙에 원소를 추가하거나 힙에서 원소를 삭제한다. 로그
sort_heap() 힙을 오름차순으로 정렬된 시퀀스로 변환한다. 선형 로그

최대/최소 알고리즘

알고리즘 이름 설명
clamp() 주어진 값 v가 최솟값(lo)과 최댓값(hi) 사이에 있는지 확인한다. v < lo면 lo에 대한 레퍼런스를 리턴하고, v > hi면 hi에 대한 레퍼런스를 리턴하고, 둘 다 아니면 v에 대한 레퍼런스를 리턴한다.
min()
max()
주어진 두 개 이상의 값 중에서 최댓값 또는 최솟값을 리턴한다.
minmax() 주어진 두 개 이상의 값 중에서 최댓값과 최솟값을 pair로 묶어서 리턴한다.
min_element()
max_element()
주어진 시퀀스에서 최대 원소 또는 최소 원소를 리턴한다.
minmax_element() 주어진 시퀀스에서 최대 원소와 최소 원소를 pair로 묶어서 리턴한다.

수치 연산 알고리즘

다음의 수치 연산 알고리즘(numerical processing algorithm)은 모두 정렬되지 않은 시퀀스에 대해 적용할 수 있으며 선형 복잡도의 성능을 낸다.

알고리즘 이름 설명
iota() 시퀀스를 주어진 값에서 싲가해서 연속적으로 증가하는 값으로 채운다.
gcd() 주어진 두 정수의 최대 공약수를 리턴한다.
lcm() 주어진 두 정수의 최소 공배수를 리턴한다.
adjacent_difference() 주어진 시퀀스에서 인접한 두 원소를 골라서 뒤쪽 원소에서 앞쪽 원소를 뺀(또는 다른 바이너리 연산을 적용한) 결과가 원소가 되는 시퀀스를 생성한다. 
(ex a0, a1, … -> a0, a1-a0, a2-a1, …)
partial_sum() 주어진 시퀀스의 각 원소를 그 앞에 나온 모든 원소와 더한 (또는 다른 바이너리 연산을 적용한) 결과가 원소가 되는 시퀀스를 생성한다. 
(ex a0, a1, … -> a0, a0+a1, a0+a1+a2, …)
exclusive_scan()
inclusive_scan()
기본 기능은 partial_sum()과 같지만 inclusive_scan()은 주어진 합 연산이 결합법칙을 만족할 때만 partial_sum()과 같다. 그런데 inclusive_sum()을 더하는 순서는 일정하지 않은 반면 partial_sum은 항상 왼쪽에서 오른쪽 순서로 더한다. 따라서 결합법칙을 만족하지 않는 합 연산을 적용하면 결과가 일정하지 않다. exclusive_scan() 알고리즘도 합 연산의 순서가 일정하지 않다. 
inclusive_scan()을 수행할 때 i번째 원소는 i번째 합에 포함된다. 이는 partial_sum()과 같다. 반면 exclusive_scan()에서는 i번째 원소가 i번째 합에 포함되지 않는다.
transform_exclusive_scan()
transform_inclusive_scan()
주어진 시퀀스의 각 원소마다 변환을 적용한 다음 exclusive_scan() 또는 inclusive_scan()을 적용한다.
accumulate() 주어진 시퀀스의 모든 원솟값을 누적한다. 기본적으로 원소의 합을 구하지만 얼마든지 다른 이항 함수를 지정할 수 있다.
inner_product() accumulate()와 비슷하지만 두 개의 시퀀스에 대해 적용한다. 이 알고리즘은 두 시퀀스에서 위치가 같은 원소를 이항 함수(디폴트 함수는 곱셈)에 적용한 뒤 그 결과를 다른 이항 함수(디폴트 함수는 덧셈)에 적용해서 결과를 누적한다. 주어진 시퀀스가 수학의 벡터라면 두 벡터의 내적을 구한다.
reduce() accumulate()와 비슷하지만 병렬 실행을 지원한다. reduce() 연산의 실행 순서는 일정하지 않지만 accumulate()는 항상 왼쪽에서 오른쪽 순으로 처리한다. 따라서 reduce()에 주어진 이항 함수가 결합법칙이나 교환법칙을 만족하지 않으면 결과가 일정하지 않다.
transform_reduce() 주어진 시퀀스에 있는 각 원소를 변환한 다음 reduce()를 수행한다.

순열 알고리즘

순열(permutation)이란 시퀀스에 담긴 원소를 다양한 순서로 나열하는 것이다.

알고리즘 이름 설명 복잡도
is_Permutation() 두 시퀀스 중 하나가 다른 시퀀스의 순열이면 true를 리턴한다. 제곱(quadratic)
next_permutation()
prev_permutation()
주어진 시퀀스를 사전 순으로 다음 또는 이전에 나오는 순열로 변환한다. 어느 하나에 대해 연속적으로 호출하면 모든 경우의 순열을 구할 수 있다. 단, 제대로 정렬된 시퀀스로 호출하기 싲가해야 한다. 더는 나올 수 있는 순열이 없으면 false를 리턴한다. 선형

표준 라이브러리에서 제공하지 않는 기능

다음과 같은 기능은 표준 라이브러리에 없다.

  • 여러 스레드가 컨테이너에 동시에 접근할 때 스레드 안전성을 보장하지 않는다.
  • 표준 라이브러리는 제네릭 트리나 그래프 구조를 제공하지 않는다. map과 set이 균형 이진트리(balanced binary tree)로 구현돼 있지만, 이를 직접 사용하도록 인터페이스를 제공하지 않는다. 파서 등을 구현하기 위해 트리나 그래프 구조가 필요하다면 직접 만들거나 다른 라이브러리를 활용한다.

[ssba]

The author

지성을 추구하는 사람/ suyeongpark@abyne.com

댓글 남기기

이 사이트는 스팸을 줄이는 아키스밋을 사용합니다. 댓글이 어떻게 처리되는지 알아보십시오.