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

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

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

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

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

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

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

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

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> 헤더 파일에 정의돼 있으며 무작위수 엔진, 무작위수 엔진 어댑터, 무작위수 분포 등도 제공한다. 이 기능을 활용하면 정규 분포, 역지수 분포 등에 보다 적합한 무작위수를 생성할 수 있다.

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

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

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

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

이 세 가지 클래스는 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) 컬렉션이 필요하다면 각 타입에 맞는 파생 클래스로 구성된 클래스를 새로 정의한다.

기본 설명

성능

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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> 헤더 파일에 정의돼 있으며 무작위수 엔진, 무작위수 엔진 어댑터, 무작위수 분포 등도 제공한다. 이 기능을 활용하면 정규 분포, 역지수 분포 등에 보다 적합한 무작위수를 생성할 수 있다.

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

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

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

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

이 세 가지 클래스는 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) 컬렉션이 필요하다면 각 타입에 맞는 파생 클래스로 구성된 클래스를 새로 정의한다.

기본 설명

성능

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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