2025/04/06 ch.16 C++ 표준 라이브러리 둘러보기

C++표준 라이브러리 중에서도 가장 핵심은 제네릭 컨테이너와 제네릭 알고리즘

원래 표준 템플릿 라이브러리(STL) 이라는 서드 파티 라이브러리였다

이제는 표준 라이브러리 이므로 STL은 사실 잘못된 용어

 

표준 라이브러리에서 제공하는 대다수의 알고리즘과 컨테이너가 상호 호환되고 컨테이너에 담긴 데이터 타입의 종류에 무관하게 작동하는 범용성

프로그래머가 직접 정의한 것보다 더 빠른 컨테이너와 알고리즘을 제공

 

템플릿 활용

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

모든 종류의 객체를 다룰 수 있을 뿐만 아니라 코드 작성 시점에는 모르던 객체도 처리할 수 있게 만들 수 있음

템플릿 코드를 만드는 프로그래머

- 객체 생성에 필요한 클래스 요구사항을 명시해야 함

- 비교 연산자나 복제 생성자 등과 같은 해당 템플릿을 사용하는 데 필요한 기능을 명시해야 함

- 템플릿 코드를 사용할 때 이러한 필수 기능만 사용하도록 함

- 템플릿에서 요구하는 연산자나 메서드를 구현함

 

연산자 오버로딩도 C++ 표준 라이브러리에서 상당히 많이 사용함

 

16.2.1 스트링

<string>

메모리를 관리해주고

인덱스 경계 검사

대입과 비교

스트링 결합

스트링 추출

부분 스트링 만들기

문자 치환

등과 같은 다양한 기능 제공

 

# string은 basic_string 템플릿을  char 타입에 대해 인스턴스화 한 것의 타입 앨리어스임

 

<string_view>

스트링을 읽기 전용으로 표현

const string& 대신 사용할 수 있고 오버헤드 발생 x. 스트링을 복제하지 않음

 

유니코드와 현지화도 지원 <locale>

 

16.2.2 정규 표현식

<regex>

스트링을 다룰 때 흔히 사용하는 패턴 매칭을 쉽게 구현할 수 있음

패턴 매칭 - 스트링에서 특정한 패턴을 찾거나 새 패턴으로 교체하는 데 사용됨

 

16.2.3 I/O 스트림

기본 타입 데이터를 파일이나 키보드, 콘솔, 스트링에 읽고 쓰는 루틴을 제공함

자신이 직접 정의한 객체를 읽고 쓰는 루틴도 직접 정의하는 기능도 제공

 

16.2.4 스마트 포인터

객체를 삭제하는 시점의 모호함에 의해 발생하는 다양한 문제

대표적으로 메모리 누수가 있다

댕글링 포인터, 이중 해제

이런 문제를 해결하기 위해 스마트 포인터를 제공함

 

16.2.5 익셉션

예외 메커니즘

 

C++20

# 부호 있는 값과 부호 없는 값 사이의 비교 연산의 주의할 점

부호 있는 값 -1과 부호 없는 값 0을 비교 하면 -1은 부호 없는 정수로 변환되어 매우 큰수가 되어버릴 수 있음

C++20에서 추가된 비교 함수는 이러한 예외를 처리해준다

 

 

16.2.9 초기자 리스트

<initializer_list>

인수의 개수를 다양하게 받는 함수를 쉽게 작성할 수 있다

 

16.2.10 페어, 튜플

<utility>

pair 클래스 템플릿은 타입이 서로 다른 두 원소를 하나로 묶어서 저장함

대부분의 표준 라이브러리 컨테이너는 모두 동형 원소를 저장하지만 pair는 이형 원소를 저장할 수 있음

<tuple>

pair를 일반화 한 것

크기가 고정된 수열. 서로 타입이 다른 원소를 저장할 수 있음

 

16.2.11 어휘 타입

optional: 특정한 타입의 값을 갖거나 그렇지 않을 수 있음

variant: 지정한 타입 집합 중 하나로 된 값을 담음

any: 모든 타입의 값을 단 하나만 가짐

 

16.2.12 함수 객체

함수 호출 연산자를 구현하는 클래스

표준 라이브러리 알고리즘에서 조건식을 구현하는데 활용됨

 

16.2.13 파일 시스템

<filesystem> 

파일 시스템을 다루는 코드를 이식하기 쉬운 형태로 만들 수 있음

 

16.2.14 멀티스레딩

멀티코어 cpu를 최대한 활용하게 하려면 여러 스레드를 사용하도록 작성해야 함

 

16.2.15 타입 트레이트

컴파일 시간에 타입 정보를 조회할 수 있다

 

16.2.20 컨테이너

흔히 사용되는 데이터 구조를 제공함

표준 라이브러리에서 제공하는 컨테이너는 모두 클래스 템플릿

기본타입, 사용자 정의 클래스 데이터도 담을 수 있다

컨테이너 인스턴스마다 단 한가지 타입의 객체만 저장할 수 있다

크기가 고정되지 않은 동형 컬렉션이 필요하다면 각각의 원소를 any  인스턴스로 만들어서 컨테이너에 저장함

variant 인스턴스도 가능

 

vector
일련의 원소를 저장하고 각 원소를 임의로 접근할 수 있음

원소를 추가할 때마다 크기가 동적으로 증가

경곗값 검사 기능도 제공하는 배열

배열처럼 원소를 메모리 공간에 연달아 저장

 

마지막 항목을 추가하거나 삭제하는 연산을 매우 빠르게 처리함

연산이 분할 상환 상수 시간에 처리됨 - 연산을 수행하는 데 걸리는 시간이 대체로 상수 시간인 O(1) 이란 뜻

원소가 추가될 때마다 크기도 늘어나야 함으로 공간 복잡도는 O(1)

하지만 vector의 끝이 아닌 다른 지점에 원소를 추가하거나 삭제하는 연산은 그보다 느린 선형 시간이 걸림

새 원소를 추가하거나 삭제하려면 공간을 확보하거나 채우기 위해 모든 원소를 한 칸씩 이동해야 하기 때문

 

이런 단점에도 불구하고 일단 vector를 기본으로 사용하는게 좋음

vector는 연속된 메모리 공간에 데이터를 저장. 컴퓨터는 연속된 공간에 저장된 데이터를 굉장히 효율적으로 처리함

 

vector<bool>은 조금 특수함

부울 타입 원소에 대한 공간 할당 작업에 최적화 되어있다

그런데 어떻게 최적화 하는지는 표준에 명시되어있지 않으므로 주의

 

list

2중연결 리스트

원소를 연달아 저장하지만 실제 메모리 공간은 떨어져 있을 수 있다

 

forward_list

단일연결 리스트

정방향 반복만 지원. list 보다 메모리를 적게 씀

랜덤액세스 기능 지원하지 않음

 

deque

양방향 쿠

원소 접근 속도가 상수시간, 양 끝에 원소를 추가하거나 삭제하는 연산도 상수 시간

중간에 추가하거나 삭제하는 연산은 선형시간

메모리 공간에 연달아 저장되지 않음

양 끝에 원소를 추가하거나 삭제하는 연산, 원소를 조회하는 연산을 모두 빠르게 처리하고 싶다면  deque 사용

하지만 어지간하면 vector가 더 빠름

 

array

표준 c 스타일 배열을 단순히 래핑한 것

주어진 컨테이너에 담긴 원소의 개수를 정확히 알고 있고 공간을 동적으로 사용할 필요가 없을때 사용

크기도 항상 정해져 있고 포인터로 자동으로 캐스팅 하지 않음. 항상 크기가 일정해서 스택에 할당도 가능

 

queue

선입선출

항상 한쪽 끝에서만 원소를 추가, 다른 쪽 끝에서는 꺼내기만 함

추가 삭제 모두 분할 상환 상수 시간

 

priority_queue 

원소마다 우선순위를 정할 수 있음

원소를 제거할 때 우선순위에 따라 처리함

우선순위가 같은 원소끼리는 어느것이 먼제 제거될지 모름

우선순위에 따라 원소를 정렬해야 하기 때문에 일반 queue 보다는 느김

 

stack

후입선출

가장 늦게 추가한 원소부터 제거

 

set, multiset

set - 원소로 구성된 집합을 표현하는 클래스 템플릿

원소가 중복될 수 없고 원소의 인스턴스가 최소한 한 개 이상 있어야 함

원소에 순서가 정해져 있다

원소를 추가하거나 삭제하거나 조회하는 연산은 로그 시간에 처리

원소에 순서를 유지해야 하고, 추가/삭제/조회 연산을 골고루 사용하고, 각 연산의 성능도 서로 비슷한 수준으로 최적화 하고 싶을때 사용

set은 원소의 중복을 허용하지 않음

multiset은 원소의 중복을 허용하는 set

 

map, multimap

연관 배열을 표현한 클래스 템플릿

인덱스를 원하는 타입으로 지정할 수 있는 배열

원소를 키/값 쌍으로 저장하고 키를 기준으로 정렬한 상태를 유지

operator[]를 지원. 나머지 속성은 set과 같음

multimap은 키의 중복을 허용하는 map

 

 

비정렬 연결 컨테이너와 해시 테이블

unordered_map

unordered_multimap

unordered_set

unordered_multi_set

 

해시 테이블 컨테이너이지만 hash_가 아니라 unordered인 이유는 c++11에서 표준 라이브러리에 추가되었기 때문에 이미 hash 이름을 가진 서드파티 라이브러리가 많아서 다른 이름을 사용했음

 

원소를 정렬하지 않는다는 점을 제외하면 동작은 똑같음

원소 추가, 삭제 조회하는 연산의 속도는 대체로 상수 시간, 최악이여도 선형

원소를 조회하는 속도는 일반 map이나 set보다 훨씬 빠름. 담긴 원소가 많을수록 더욱

 

bitset

비트 플래그를 이용할때 보통 int나 long에 저장해서 비트 연산자를 사용하는데 이를 bitset 컨테이너로 지원함

일반적인 컨테이너와 달리 원소를 추가하거나 삭제할 수 있는 데이터 구조도 아니고 반복자도 지원하지 않음

다만 원소의 타입에 크기 제한이 없다. bitset<N>으로 N 비트 만큼의 공간을 할당한다

 

# 대부분의 경우에서 vector 가 빠르므로 반드시 기본적으로 vector를 사용합시다

 

 

16.2.21 알고리즘

함수 템플릿으로 구현되어 있어 다양한 타입의 컨테이너에 적용 가능

다만 알고리즘은 컨테이너에 속하지 않는다. 표준 라이브러리는 데이터(컨테이너)와 기능(알고리즘)을 엄격히 구분함

직교성 원칙 - 표준 라이브러리의 범용성을 유지하기 위함

 

# 알고리즘과 컨테이너가 구분되어있기는 하지만 어떤 컨테이너들은 특성상 범용 알고리즘보다 해당 구조에 맞는 알고리즘을 사용하는것이 더 빠를때가 있다. 대부분 해당 컨테이너에서 그 컨테이너에 맞는 알고리즘을 사용한 함수를 제공한다

 

불변형 순차 알고리즘

원소를 순차적으로 조회하여 각 원소에 대한 정보를 리턴하는 알고리즘

원소의 값이나 순서를 변경하지 않는다

 

1. 탐색 알고리즘

원소가 정렬되어 있지 않아도 사용 가능

 

2. 비교 알고리즘

입력값이 정렬되지 않아도 사용가능. 모두 최악의 경우에 선형 복잡도를 갖는다

 

 

가변형 순차 알고리즘

시퀀스의 모든 원소나 일부 원소를 수정하는 알고리즘

어떤 알고리즘은 원소가 있는 자리에서 바로 수정하기 대문에 순서가 바뀔 수 있고, 어떤 알고리즘은 결과를 별도의 시퀀스로 복사하기 때문에 원래 순서가 그대로 유지됨

최악의 경우 선형 복잡도의 성능을 냄

 

 

작업 알고리즘

시퀀스의 원소마다 함수를 실행한다

선형 복잡도를 가지며 원본 시퀀스를 정렬하지 않아도 사용 가능

 

교환 알고리즘

 

분할 알고리즘

주어진 조건식에 시퀀스를 적용했을 때 true를 리턴하는 원소가 false를 리턴하는 우너소보다 앞에 있으면 그 시퀀스를 분할 함.

시퀀스에서 조건식을 만족하지 않는 첫 원소를 분할 지점이라 부름

 

정렬 알고리즘

 

이진탐색 알고리즘

정렬된 시퀀스에 적용함

대상 시퀀스가 최소한 탐색할 원소를 기준으로 분할된 상태여야 함

복잡도는 모두 로그

 

집합 알고리즘

시퀀스에 대해 집합 연산을 수행하는 특수한 형태의 가변 알고리즘

set 컨테이너에 있는 시퀀스에 가장 적합하지만 다른 컨테이너의 정렬된 시퀀스에도 대부분 적용 가능

 

힙 알고리즘

힙 - 최상단에 있는 원소를 빨리 찾도록 적절히 정렬된 상태를 유지하는 배열이나 시퀀스에 대한 데이터 구조

 

최대/최소 알고리즘

가장 작거나 큰 원소를 찾는 알고리즘

 

수치 처리 알고리즘

정렬되지 않은 시퀀스에 대해 적용가능, 선형 복잡도

 

순열 알고리즘

시퀀스에 담긴 원소를 다양한 순서로 나열

 

 

c++20 

반복자 대신 범위를 사용할 수 있게 되었다

반복자보다 보기 좋고 이해하기 쉬울 뿐만 아니라 시작과 끝 반복자가 맞지 않을 가능성을 줄여줌

 

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

- 여러 스레드가 컨테이너에 동시에 접근할 때 스레드 안정성을 보장하지 않음

- 범용 트리나 그래프 구조를 제공하지 않음

map, set이 균형 이진트리지만 이를 직접 사용하도록 인터페이스를 제공하지 않음

직접 만들거나 다른 라이브러리를 사용해야 함

 

856p