1. STL 개요

C++ STL의 개념과 역사

STL은 “Standard Template Library”의 약자로, C++ 표준 라이브러리의 일부분이다. STL은 기본적으로 템플릿을 사용한 데이터 구조와 알고리즘을 제공하며, 주로 컨테이너(container), 반복자(iterator), 알고리즘(algorithm), 그리고 함수 객체(function object) 등을 포함한다. STL은 특히 자료 구조와 알고리즘을 제공하여, 프로그래머가 복잡한 기능을 직접 구현하지 않고도 효율적으로 사용할 수 있게 도와준다.

C++의 STL(Standard Template Library)은 1994년 C++의 주요 발전 중 하나로, 데이터 구조와 알고리즘의 효율적인 구현을 제공하기 위해 설계되었다. STL은 템플릿을 기반으로 하여, 다양한 데이터 구조와 알고리즘을 추상화하고 재사용할 수 있게 만든 라이브러리이다. 초기에는 C++의 표준 라이브러리의 일부로 채택되지 않았지만, 이후 C++98 표준에서 공식적으로 채택되어 현재는 C++ 표준 라이브러리의 핵심 부분을 차지하고 있다.

STL의 구성 요소 (컨테이너, 알고리즘, 반복자)

C++ STL은 크게 컨테이너(Container), 알고리즘(Algorithm), 반복자(Iterator)라는 세 가지 주요 구성 요소로 나뉜다. 각 구성 요소는 서로 밀접하게 연관되어 있으며, 이를 통해 C++ 개발자는 복잡한 데이터 처리 작업을 효율적이고 간결하게 수행할 수 있다.

1. 컨테이너 (container)

컨테이너는 데이터를 저장하는 데 사용되는 자료구조이다. STL에서는 다양한 종류의 컨테이너를 제공하며, 각 컨테이너는 데이터를 저장하고 접근하는 방식이 다르다. 주요 컨테이너는 순차적 컨테이너와 연관 컨테이너로 나눌 수 있다. 예를 들어, std::vector, std::list, std::deque는 순차적 컨테이너에 속하며, std::map, std::set, std::unordered_map과 같은 컨테이너는 연관 컨테이너에 속한다. 이들은 각각의 목적에 맞게 데이터를 효율적으로 저장하고 관리할 수 있도록 설계되었다.

2. 알고리즘 (algorithm)

알고리즘은 데이터를 처리하는 데 필요한 일련의 작업을 정의한 함수들이다. STL은 정렬, 검색, 집합 연산 등 다양한 알고리즘을 제공하며, 이러한 알고리즘은 컨테이너의 데이터를 직접 처리하거나, 반복자와 함께 사용하여 데이터를 효율적으로 처리한다. 예를 들어, std::sort, std::find, std::accumulate 등의 알고리즘이 있다. STL 알고리즘은 대부분 템플릿을 사용하여 다양한 데이터 타입에 대해 범용적으로 동작할 수 있도록 설계되었다.

3. 반복자 (iterator)

반복자는 STL에서 컨테이너의 요소에 접근하고, 이를 순차적으로 탐색하는 역할을 한다. 반복자는 포인터와 유사한 동작을 하며, 데이터 구조의 내부를 직접 다루지 않고, 알고리즘과 컨테이너가 상호작용할 수 있도록 돕는다. 반복자는 크게 입력 반복자(input iterator), 출력 반복자(output iterator), 양방향 반복자(bidirectional iterator), 랜덤 접근 반복자(random access iterator) 등으로 분류된다. 이를 통해 STL은 다양한 자료구조에서 일관된 방식으로 데이터를 순차적으로 처리할 수 있게 된다.

2. STL 컨테이너 (Containers)

STL 컨테이너는 데이터를 저장하고 관리하는 핵심적인 자료구조들을 제공한다. 각 컨테이너는 특정 용도와 사용 사례에 맞게 설계되었으며, 그 특성에 따라 데이터를 효율적으로 처리할 수 있도록 도와준다. STL의 컨테이너는 크게 순차적 컨테이너, 연관 컨테이너, 해시 기반 컨테이너, 기타 컨테이너로 나눌 수 있다.

순차적 컨테이너 (Sequence Containers)

순차적 컨테이너는 데이터를 순차적으로 저장하는 컨테이너로, 각 요소는 인덱스를 통해 순서대로 접근할 수 있다. 이들은 주로 삽입과 삭제가 자주 발생하는 경우에 유용하며, 다음과 같은 컨테이너가 포함된다:

  • std::vector
    std::vector는 동적 배열을 구현한 자료구조로, 요소는 연속된 메모리 공간에 저장된다. 이로 인해 인덱스를 사용한 접근이 매우 빠르며, 마지막에 요소를 삽입하는 push_back() 연산은 평균적으로 O(1) 시간 복잡도를 가진다. 그러나 중간에 요소를 삽입하거나 삭제하는 경우에는 O(n)의 시간이 소요된다. 내부적으로 동적 배열을 사용하며, 크기 조정은 자동으로 이루어진다.

    사용방법 
     #include <iostream>
 #include <vector>  // std::vector 라이브러리 포함

 int main() {
    // 1. 선언
    std::vector<int> vec; // 빈 벡터 선언 (int 타입)

    // 2. 정의
    vec.push_back(10); // 벡터 끝에 10 추가
    vec.push_back(20); // 벡터 끝에 20 추가
    vec.push_back(30); // 벡터 끝에 30 추가

    // 3. 주요 함수들
    std::cout << "벡터 크기: " << vec.size() << std::endl;  // 벡터 크기 출력
    std::cout << "벡터 첫 번째 요소: " << vec.front() << std::endl;  // 첫 번째 요소 출력
    std::cout << "벡터 마지막 요소: " << vec.back() << std::endl;  // 마지막 요소 출력

    // 4. 인덱스를 사용하여 접근
    std::cout << "두 번째 요소: " << vec[1] << std::endl;  // 두 번째 요소 출력

    // 5. 벡터 순회
    std::cout << "벡터 요소들: ";
    for (int i = 0; i < vec.size(); ++i) {
       std::cout << vec[i] << " ";  // 벡터의 각 요소 출력
    }
    std::cout << std::endl;

    // 6. 요소 제거
    vec.pop_back();  // 벡터 끝에서 하나의 요소 제거
    std::cout << "요소를 하나 제거한 후 크기: " << vec.size() << std::endl;

    return 0;
 }

  • std::deque
    std::deque는 “double-ended queue”로, 양 끝에서 빠르게 삽입과 삭제가 가능하다. 내부적으로는 두 개의 동적 배열을 사용하여 데이터를 저장하며, 각 배열은 일정 크기씩 증가한다. 중간에 데이터를 삽입하거나 삭제하는 데 드는 시간은 O(n)이다. 양쪽 끝에서의 삽입과 삭제는 O(1)의 시간 복잡도를 가진다.

    사용방법 
     #include <iostream>
 #include <deque>  // std::deque 라이브러리 포함

 int main() {
    // 1. 선언
    std::deque<int> dq; // 빈 덱 선언 (int 타입)

    // 2. 정의
    dq.push_back(10);  // 덱의 뒤쪽에 10 추가
    dq.push_back(20);  // 덱의 뒤쪽에 20 추가
    dq.push_front(5);  // 덱의 앞쪽에 5 추가
    dq.push_front(3);  // 덱의 앞쪽에 3 추가

    // 3. 주요 함수들
    std::cout << "덱 크기: " << dq.size() << std::endl;  // 덱 크기 출력
    std::cout << "덱 첫 번째 요소: " << dq.front() << std::endl;  // 첫 번째 요소 출력
    std::cout << "덱 마지막 요소: " << dq.back() << std::endl;  // 마지막 요소 출력

    // 4. 인덱스를 사용하여 접근
    std::cout << "두 번째 요소: " << dq[1] << std::endl;  // 두 번째 요소 출력

    // 5. 덱 순회
    std::cout << "덱 요소들: ";
    for (int i = 0; i < dq.size(); ++i) {
       std::cout << dq[i] << " ";  // 덱의 각 요소 출력
    }
    std::cout << std::endl;

    // 6. 요소 제거
    dq.pop_back();  // 덱의 뒤쪽에서 하나의 요소 제거
    dq.pop_front(); // 덱의 앞쪽에서 하나의 요소 제거

    std::cout << "요소를 하나씩 제거한 후 크기: " << dq.size() << std::endl;

    return 0;
 }

  • std::list
    std::list는 양방향 연결 리스트로, 각 요소는 이전과 다음 요소를 가리키는 포인터를 가진다. 삽입과 삭제는 O(1)의 시간이 소요되지만, 임의 접근이 불가능하여 인덱스를 통한 탐색은 O(n)이다. 내부 구현은 이중 연결 리스트(Doubly Linked List)를 사용한다.

    사용방법 
     #include <iostream>
 #include <list>  // std::list 라이브러리 포함

 int main() {
    // 1. 선언
    std::list<int> lst;  // 빈 리스트 선언 (int 타입)

    // 2. 정의
    lst.push_back(10);  // 리스트의 뒤쪽에 10 추가
    lst.push_back(20);  // 리스트의 뒤쪽에 20 추가
    lst.push_front(5);  // 리스트의 앞쪽에 5 추가
    lst.push_front(3);  // 리스트의 앞쪽에 3 추가

    // 3. 주요 함수들
    std::cout << "리스트 크기: " << lst.size() << std::endl;  // 리스트 크기 출력
    std::cout << "리스트 첫 번째 요소: " << lst.front() << std::endl;  // 첫 번째 요소 출력
    std::cout << "리스트 마지막 요소: " << lst.back() << std::endl;  // 마지막 요소 출력

    // 4. 리스트 순회
    std::cout << "리스트 요소들: ";
    for (int val : lst) {
       std::cout << val << " ";  // 리스트의 각 요소 출력
    }
    std::cout << std::endl;

    // 5. 요소 제거
    lst.pop_back();  // 리스트의 뒤쪽에서 하나의 요소 제거
    lst.pop_front(); // 리스트의 앞쪽에서 하나의 요소 제거

    std::cout << "요소를 하나씩 제거한 후 크기: " << lst.size() << std::endl;

    return 0;
 }

  • std::array
    std::array는 C++11에서 도입된 고정 크기 배열을 제공하는 컨테이너이다. 크기가 고정되어 있으며, 컴파일 타임에 배열의 크기를 정할 수 있다. 메모리상에서 연속적으로 데이터를 저장하므로, 인덱스를 통한 접근은 O(1)이다.

    사용방법 
     #include <iostream>
 #include <array>  // std::array 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::array<int, 5> arr = {1, 2, 3, 4, 5};  // 크기 5의 배열 선언과 초기화

    // 2. 주요 함수들
    std::cout << "배열 크기: " << arr.size() << std::endl;  // 배열 크기 출력
    std::cout << "배열 첫 번째 요소: " << arr.front() << std::endl;  // 첫 번째 요소 출력
    std::cout << "배열 마지막 요소: " << arr.back() << std::endl;  // 마지막 요소 출력

    // 3. 배열의 인덱스를 사용한 접근
    std::cout << "두 번째 요소: " << arr[1] << std::endl;  // 두 번째 요소 출력

    // 4. 배열 순회
    std::cout << "배열 요소들: ";
    for (int i = 0; i < arr.size(); ++i) {
       std::cout << arr[i] << " ";  // 배열의 각 요소 출력
    }
    std::cout << std::endl;

    // 5. 배열 요소 변경
    arr[2] = 10;  // 세 번째 요소를 10으로 변경
    std::cout << "변경된 배열 요소들: ";
    for (int val : arr) {
       std::cout << val << " ";  // 변경된 배열 출력
    }
    std::cout << std::endl;

    // 6. 배열의 첫 번째와 마지막 요소 변경
    arr.front() = 20;  // 첫 번째 요소를 20으로 변경
    arr.back() = 50;   // 마지막 요소를 50으로 변경

    std::cout << "첫 번째와 마지막 요소 변경 후: ";
    for (int val : arr) {
       std::cout << val << " ";  // 변경된 배열 출력
    }
    std::cout << std::endl;

    return 0;
 }

연관 컨테이너 (Associative Containers)

연관 컨테이너는 키를 기반으로 데이터를 저장하는 자료구조로, 각 데이터 요소는 키-값 쌍(key-value pair)으로 저장된다. 연관 컨테이너는 트리 기반이나 맵핑 기반 구조를 사용하여 데이터를 관리하며, 이를 통해 데이터를 효율적으로 검색하고 정렬할 수 있다.

  • std::set
    std::set은 이진 탐색 트리를 기반으로 구현된 자료구조이다. 요소들은 중복 없이 저장되며, 자동으로 오름차순으로 정렬된다. 삽입, 삭제, 검색 모두 평균적으로 O(log n) 시간 복잡도를 가진다. 내부 구현은 레드-블랙 트리(Red-Black Tree) 또는 AVL 트리 같은 균형 이진 탐색 트리를 사용한다.

    사용방법 
     #include <iostream>
 #include <set>  // std::set 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::set<int> s;  // int 타입의 빈 set 선언

    // 2. 주요 함수들
    s.insert(10);  // set에 10 삽입
    s.insert(20);  // set에 20 삽입
    s.insert(5);   // set에 5 삽입
    s.insert(5);   // 중복된 값 삽입 시 무시됨

    // 3. 요소 출력
    std::cout << "set의 요소들: ";
    for (int val : s) {
       std::cout << val << " ";  // set의 각 요소 출력
    }
    std::cout << std::endl;

    // 4. 요소 검색
    if (s.find(20) != s.end()) {  // 20이 set에 존재하는지 확인
       std::cout << "20이 set에 존재합니다." << std::endl;
    } else {
       std::cout << "20이 set에 존재하지 않습니다." << std::endl;
    }

    // 5. 요소 삭제
    s.erase(10);  // 10 삭제
    std::cout << "10을 삭제한 후 set의 요소들: ";
    for (int val : s) {
       std::cout << val << " ";  // 삭제 후 set 출력
    }
    std::cout << std::endl;

    // 6. set의 크기
    std::cout << "set의 크기: " << s.size() << std::endl;

    return 0;
 }

  • std::map
    std::map은 std::set과 유사하지만, 키-값 쌍(key-value pair)을 저장한다. 내부적으로 레드-블랙 트리를 사용하여 키를 기준으로 자동 정렬되며, 중복된 키는 허용하지 않는다. 삽입, 삭제, 검색은 O(log n) 시간 복잡도를 가진다.

    사용방법 
     #include <iostream>
 #include <map>  // std::map 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::map<int, std::string> m;  // int를 키로, string을 값으로 갖는 map 선언

    // 2. 주요 함수들
    m[1] = "사과";  // 키 1에 "사과"라는 값을 삽입
    m[2] = "바나나";  // 키 2에 "바나나"라는 값을 삽입
    m[3] = "체리";    // 키 3에 "체리"라는 값을 삽입

    // 3. map 요소 출력
    std::cout << "map의 요소들: " << std::endl;
    for (const auto& pair : m) {  // map은 키-값 쌍으로 구성
       std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    // 4. 요소 검색
    auto it = m.find(2);  // 키 2를 찾아서 반복자 반환
    if (it != m.end()) {
       std::cout << "키 2에 대한 값: " << it->second << std::endl;
    } else {
       std::cout << "키 2는 존재하지 않습니다." << std::endl;
    }

    // 5. 요소 삭제
    m.erase(1);  // 키 1을 삭제
    std::cout << "키 1 삭제 후 map의 요소들: " << std::endl;
    for (const auto& pair : m) {
       std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    // 6. map의 크기
    std::cout << "map의 크기: " << m.size() << std::endl;

    return 0;
 }

  • std::multiset
    std::multiset은 std::set과 유사하지만, 중복된 값을 허용한다. 내부 구현은 std::set과 동일하게 레드-블랙 트리를 사용하여 데이터를 정렬한다. 중복된 값은 여러 번 삽입할 수 있으며, 검색은 O(log n) 시간 복잡도를 가진다.

    사용방법 
     #include <iostream>
 #include <set>  // std::multiset 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::multiset<int> ms;  // int 타입의 multiset 선언

    // 2. 주요 함수들
    ms.insert(10);  // multiset에 10 삽입
    ms.insert(20);  // multiset에 20 삽입
    ms.insert(10);  // 중복된 10 삽입 가능
    ms.insert(5);   // multiset에 5 삽입
    ms.insert(5);   // 중복된 5 삽입 가능

    // 3. multiset 요소 출력
    std::cout << "multiset의 요소들: ";
    for (int val : ms) {
       std::cout << val << " ";  // multiset의 각 요소 출력
    }
    std::cout << std::endl;

    // 4. 요소 검색
    auto it = ms.find(10);  // 10을 검색
    if (it != ms.end()) {
       std::cout << "10이 multiset에 존재합니다." << std::endl;
    } else {
       std::cout << "10이 multiset에 존재하지 않습니다." << std::endl;
    }

    // 5. 요소 삭제
    ms.erase(10);  // 10을 삭제
    std::cout << "10 삭제 후 multiset의 요소들: ";
    for (int val : ms) {
       std::cout << val << " ";  // 삭제 후 multiset 출력
    }
    std::cout << std::endl;

    // 6. multiset의 크기
    std::cout << "multiset의 크기: " << ms.size() << std::endl;

    return 0;
 }

  • std::multimap
    std::multimap은 std::map과 유사하지만, 하나의 키에 여러 값을 저장할 수 있다. 내부적으로 레드-블랙 트리를 사용하여 자동으로 키를 정렬한다. 하나의 키에 여러 값을 저장할 수 있기 때문에 중복 키를 허용한다. 삽입, 삭제, 검색은 O(log n) 시간 복잡도를 가진다.

    사용방법 
     #include <iostream>
 #include <map>  // std::multimap 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::multimap<int, std::string> mm;  // int를 키로, string을 값으로 갖는 multimap 선언

    // 2. 주요 함수들
    mm.insert({1, "사과"});  // 키 1에 "사과" 값을 삽입
    mm.insert({2, "바나나"});  // 키 2에 "바나나" 값을 삽입
    mm.insert({1, "체리"});  // 키 1에 "체리" 값을 삽입 (중복 키 허용)
    mm.insert({3, "딸기"});  // 키 3에 "딸기" 값을 삽입
    mm.insert({2, "포도"});  // 키 2에 "포도" 값을 삽입 (중복 키 허용)

    // 3. multimap 요소 출력
    std::cout << "multimap의 요소들: " << std::endl;
    for (const auto& pair : mm) {
       std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    // 4. 요소 검색
    auto range = mm.equal_range(2);  // 키 2에 해당하는 값들의 범위 반환
    std::cout << "키 2에 대한 값들: ";
    for (auto it = range.first; it != range.second; ++it) {
       std::cout << it->second << " ";  // 키 2에 해당하는 값 출력
    }
    std::cout << std::endl;

    // 5. 요소 삭제
    mm.erase(1);  // 키 1에 해당하는 모든 값 삭제
    std::cout << "키 1 삭제 후 multimap의 요소들: " << std::endl;
    for (const auto& pair : mm) {
       std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    // 6. multimap의 크기
    std::cout << "multimap의 크기: " << mm.size() << std::endl;

    return 0;
 }

해시 기반 컨테이너 (Unordered Containers)

해시 기반 컨테이너는 데이터를 해시 테이블을 사용하여 관리한다. 이 구조는 평균적으로 매우 빠른 삽입, 삭제, 검색 성능을 제공하지만, 요소들이 자동으로 정렬되지 않으며, 순서가 보장되지 않는다.

  • std::unordered_set
    std::unordered_set은 해시 테이블을 사용하여 데이터를 저장하며, 중복된 값은 허용하지 않는다. 검색, 삽입, 삭제 모두 평균적으로 O(1) 시간 복잡도를 가진다. 요소들은 정렬되지 않으며, 해시 충돌을 해결하기 위해 체이닝 기법을 사용한다.

    사용방법 
     #include <iostream>
 #include <unordered_set>  // std::unordered_set 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::unordered_set<int> uset;  // int 타입의 unordered_set 선언

    // 2. 주요 함수들
    uset.insert(10);  // unordered_set에 10 삽입
    uset.insert(20);  // unordered_set에 20 삽입
    uset.insert(30);  // unordered_set에 30 삽입
    uset.insert(10);  // 중복된 10 삽입 (허용되지 않음)

    // 3. unordered_set 요소 출력
    std::cout << "unordered_set의 요소들: ";
    for (int val : uset) {
       std::cout << val << " ";  // unordered_set의 각 요소 출력
    }
    std::cout << std::endl;

    // 4. 요소 검색
    if (uset.find(20) != uset.end()) {
       std::cout << "20이 unordered_set에 존재합니다." << std::endl;
    } else {
       std::cout << "20이 unordered_set에 존재하지 않습니다." << std::endl;
    }

    // 5. 요소 삭제
    uset.erase(10);  // 10 삭제
    std::cout << "10 삭제 후 unordered_set의 요소들: ";
    for (int val : uset) {
       std::cout << val << " ";  // 삭제 후 unordered_set 출력
    }
    std::cout << std::endl;

    // 6. unordered_set의 크기
    std::cout << "unordered_set의 크기: " << uset.size() << std::endl;

    return 0;
 }

  • std::unordered_map
    std::unordered_map은 std::unordered_set과 유사하지만, 키-값 쌍을 저장한다. 내부적으로 해시 테이블을 사용하여 데이터를 빠르게 관리하며, 삽입, 삭제, 검색이 평균적으로 O(1) 시간 복잡도를 가진다. 중복된 키를 허용하지 않으며, 해시 충돌 해결을 위해 체이닝 기법을 사용한다.

    사용방법 
     #include <iostream>
 #include <unordered_map>  // std::unordered_map 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::unordered_map<int, std::string> umap;  // int를 키로, string을 값으로 갖는 unordered_map 선언

    // 2. 주요 함수들
    umap[1] = "사과";  // 키 1에 "사과" 값을 삽입
    umap[2] = "바나나";  // 키 2에 "바나나" 값을 삽입
    umap[3] = "체리";  // 키 3에 "체리" 값을 삽입
    umap[1] = "딸기";  // 키 1의 값을 "딸기"로 업데이트 (기존 값 덮어쓰기)

    // 3. unordered_map 요소 출력
    std::cout << "unordered_map의 요소들: " << std::endl;
    for (const auto& pair : umap) {
       std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    // 4. 요소 검색
    if (umap.find(2) != umap.end()) {
       std::cout << "키 2에 해당하는 값: " << umap[2] << std::endl;
    } else {
       std::cout << "키 2에 해당하는 값이 존재하지 않습니다." << std::endl;
    }

    // 5. 요소 삭제
    umap.erase(1);  // 키 1에 해당하는 요소 삭제
    std::cout << "키 1 삭제 후 unordered_map의 요소들: " << std::endl;
    for (const auto& pair : umap) {
       std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    // 6. unordered_map의 크기
    std::cout << "unordered_map의 크기: " << umap.size() << std::endl;

    return 0;
 }

  • std::unordered_multiset
    std::unordered_multiset은 std::unordered_set과 비슷하지만, 중복된 값을 허용한다. 해시 테이블을 사용하여 데이터를 저장하며, 요소들의 순서는 보장되지 않는다.

    사용방법 
     #include <iostream>
 #include <unordered_set>  // std::unordered_multiset 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::unordered_multiset<int> umset;  // int 타입의 unordered_multiset 선언

    // 2. 주요 함수들
    umset.insert(10);  // unordered_multiset에 10 삽입
    umset.insert(20);  // unordered_multiset에 20 삽입
    umset.insert(30);  // unordered_multiset에 30 삽입
    umset.insert(10);  // 중복된 10 삽입 (허용됨)
    umset.insert(20);  // 중복된 20 삽입 (허용됨)

    // 3. unordered_multiset 요소 출력
    std::cout << "unordered_multiset의 요소들: ";
    for (int val : umset) {
       std::cout << val << " ";  // unordered_multiset의 각 요소 출력
    }
    std::cout << std::endl;

    // 4. 특정 요소의 개수 확인
    std::cout << "10의 개수: " << umset.count(10) << std::endl;  // 10의 개수를 반환

    // 5. 요소 삭제
    umset.erase(10);  // 모든 10 삭제
    std::cout << "10 삭제 후 unordered_multiset의 요소들: ";
    for (int val : umset) {
       std::cout << val << " ";  // 삭제 후 unordered_multiset 출력
    }
    std::cout << std::endl;

    // 6. unordered_multiset의 크기
    std::cout << "unordered_multiset의 크기: " << umset.size() << std::endl;

    return 0;
 }

  • std::unordered_multimap
    std::unordered_multimap은 std::unordered_map과 유사하지만, 하나의 키에 여러 개의 값을 저장할 수 있다. 해시 테이블을 사용하여 데이터를 빠르게 검색하고 관리한다. 키의 순서는 보장되지 않으며, 중복된 키를 허용한다.

    사용방법 
     #include <iostream>
 #include <unordered_map>  // std::unordered_multimap 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::unordered_multimap<int, std::string> ummap;  // int를 키로, string을 값으로 갖는 unordered_multimap 선언

    // 2. 주요 함수들
    ummap.insert({1, "사과"});  // 키 1에 "사과" 삽입
    ummap.insert({2, "바나나"});  // 키 2에 "바나나" 삽입
    ummap.insert({3, "체리"});  // 키 3에 "체리" 삽입
    ummap.insert({1, "딸기"});  // 키 1에 중복된 값 "딸기" 삽입
    ummap.insert({2, "파인애플"});  // 키 2에 중복된 값 "파인애플" 삽입

    // 3. unordered_multimap 요소 출력
    std::cout << "unordered_multimap의 요소들: " << std::endl;
    for (const auto& pair : ummap) {
       std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    // 4. 특정 키에 대한 값들 출력
    std::cout << "키 1에 해당하는 값들: ";
    auto range = ummap.equal_range(1);  // 키 1에 해당하는 값들의 범위 반환
    for (auto it = range.first; it != range.second; ++it) {
       std::cout << it->second << " ";  // 키 1에 해당하는 값 출력
    }
    std::cout << std::endl;

    // 5. 특정 키 삭제
    ummap.erase(1);  // 키 1에 해당하는 모든 요소 삭제
    std::cout << "키 1 삭제 후 unordered_multimap의 요소들: " << std::endl;
    for (const auto& pair : ummap) {
       std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    // 6. unordered_multimap의 크기
    std::cout << "unordered_multimap의 크기: " << ummap.size() << std::endl;

    return 0;
 }

기타 컨테이너

기타 컨테이너는 특별한 용도를 위해 설계된 컨테이너들로, 주로 특정 상황에서 유용하게 사용된다.

  • std::stack
    std::stack은 LIFO(Last In, First Out) 구조를 제공하는 컨테이너로, 주로 함수 호출 스택이나 후입선출 방식의 알고리즘에 사용된다. 내부적으로는 std::deque나 std::vector가 사용될 수 있으며, 두 컨테이너 모두 O(1) 시간 복잡도를 가진다.

    사용방법 
     #include <iostream>
 #include <stack>  // std::stack 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::stack<int> stk;  // int 타입의 스택 선언

    // 2. 주요 함수들
    stk.push(10);  // 스택에 10 삽입
    stk.push(20);  // 스택에 20 삽입
    stk.push(30);  // 스택에 30 삽입

    // 3. 스택의 요소 출력
    std::cout << "스택의 최상위 요소: " << stk.top() << std::endl;  // 최상위 요소 출력

    // 4. 스택에서 요소 제거
    stk.pop();  // 스택의 최상위 요소 제거
    std::cout << "pop 후 최상위 요소: " << stk.top() << std::endl;  // 제거 후 최상위 요소 출력

    // 5. 스택의 크기 확인
    std::cout << "스택의 크기: " << stk.size() << std::endl;  // 스택의 요소 개수

    // 6. 스택이 비어있는지 확인
    std::cout << "스택이 비어있는지: " << (stk.empty() ? "Yes" : "No") << std::endl;  // 비어있는지 확인

    // 7. 스택이 비어있을 때 pop 시도
    stk.pop();  // 20을 pop
    stk.pop();  // 10을 pop
    std::cout << "스택이 비어있는지: " << (stk.empty() ? "Yes" : "No") << std::endl;  // 이제 비어있는지 확인

    return 0;
 }

  • std::queue
    std::queue는 FIFO(First In, First Out) 구조를 제공하는 컨테이너이다. 큐는 요소를 한쪽 끝에서 삽입하고, 다른 쪽 끝에서 삭제하는 방식으로 동작한다. 내부 구현은 보통 std::deque를 사용하며, 삽입과 삭제는 O(1) 시간 복잡도를 가진다.

    사용방법 
     #include <iostream>
 #include <queue>  // std::queue 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::queue<int> q;  // int 타입의 큐 선언

    // 2. 주요 함수들
    q.push(10);  // 큐에 10 삽입
    q.push(20);  // 큐에 20 삽입
    q.push(30);  // 큐에 30 삽입

    // 3. 큐의 최상위 요소 출력
    std::cout << "큐의 최상위 요소: " << q.front() << std::endl;  // 큐의 가장 앞 요소 출력

    // 4. 큐에서 요소 제거
    q.pop();  // 큐의 가장 앞 요소 제거
    std::cout << "pop 후 큐의 최상위 요소: " << q.front() << std::endl;  // 제거 후 최상위 요소 출력

    // 5. 큐의 크기 확인
    std::cout << "큐의 크기: " << q.size() << std::endl;  // 큐의 요소 개수

    // 6. 큐가 비어있는지 확인
    std::cout << "큐가 비어있는지: " << (q.empty() ? "Yes" : "No") << std::endl;  // 큐가 비어있는지 확인

    // 7. 큐가 비어있을 때 pop 시도
    q.pop();  // 20을 pop
    q.pop();  // 30을 pop
    std::cout << "큐가 비어있는지: " << (q.empty() ? "Yes" : "No") << std::endl;  // 이제 비어있는지 확인

    return 0;
 }

  • std::priority_queue
    std::priority_queue는 힙(heap) 구조를 기반으로 하는 우선순위 큐이다. 우선순위 큐는 큐에서 가장 높은 우선순위를 가진 요소가 먼저 처리된다. 내부적으로는 이진 힙을 사용하여 O(log n)의 시간 복잡도로 삽입 및 삭제가 이루어진다.

    사용방법 
     #include <iostream>
 #include <queue>  // std::priority_queue 라이브러리 포함

 int main() {
    // 1. 선언 및 정의
    std::priority_queue<int> pq;  // int 타입의 최댓값 우선순위 큐 선언

    // 2. 주요 함수들
    pq.push(10);  // 우선순위 큐에 10 삽입
    pq.push(30);  // 우선순위 큐에 30 삽입
    pq.push(20);  // 우선순위 큐에 20 삽입

    // 3. 우선순위 큐의 최상위 요소 출력
    std::cout << "우선순위 큐의 최상위 요소: " << pq.top() << std::endl;  // 큐의 가장 큰 요소 출력

    // 4. 우선순위 큐에서 요소 제거
    pq.pop();  // 우선순위 큐에서 가장 큰 요소 제거
    std::cout << "pop 후 우선순위 큐의 최상위 요소: " << pq.top() << std::endl;  // 제거 후 최상위 요소 출력

    // 5. 우선순위 큐의 크기 확인
    std::cout << "우선순위 큐의 크기: " << pq.size() << std::endl;  // 우선순위 큐의 요소 개수

    // 6. 우선순위 큐가 비어있는지 확인
    std::cout << "우선순위 큐가 비어있는지: " << (pq.empty() ? "Yes" : "No") << std::endl;  // 큐가 비어있는지 확인

    return 0;
 }

 // 사용자 정의 비교 함수 클래스
 class Compare {
 public:
    bool operator()(int a, int b) {
       // a가 b보다 우선순위가 낮을 경우 true 반환
       return a > b; // 오름차순 (작은 값이 우선순위 높음)
    }
 };

 int main() {
    // 1. 기본 우선순위 큐 (최댓값 우선)
    std::priority_queue<int> pq; // 기본적으로 최대 힙

    // 2. 사용자 정의 우선순위 큐 (최솟값 우선)
    std::priority_queue<int, std::vector<int>, Compare> minHeap;

    // 기본 우선순위 큐 사용 예제
    pq.push(10);
    pq.push(30);
    pq.push(20);

    std::cout << "기본 우선순위 큐의 최상위 요소: " << pq.top() << std::endl;
    pq.pop();
    std::cout << "pop 후 기본 우선순위 큐의 최상위 요소: " << pq.top() << std::endl;

    // 사용자 정의 우선순위 큐 사용 예제
    minHeap.push(10);
    minHeap.push(30);
    minHeap.push(20);

    std::cout << "\n사용자 정의 우선순위 큐의 최상위 요소: " << minHeap.top() << std::endl;
    minHeap.pop();
    std::cout << "pop 후 사용자 정의 우선순위 큐의 최상위 요소: " << minHeap.top() << std::endl;

    return 0;
 }

STL 컨테이너별 CRUD 시간 복잡도

컨테이너 삽입 (Insert) 삭제 (Delete) 접근 (Access) 검색 (Search)
std::vector O(1) O(n) O(1) O(n)
std::deque O(1) O(n) O(1) O(n)
std::list O(1) O(1) O(n) O(n)
std::array O(1) O(1) O(1) O(n)
std::set O(log n) O(log n) O(log n) O(log n)
std::map O(log n) O(log n) O(log n) O(log n)
std::multiset O(log n) O(log n) O(log n) O(log n)
std::unordered_set O(1) O(1) O(1) O(1)
std::unordered_map O(1) O(1) O(1) O(1)
std::unordered_multiset O(1) O(1) O(1) O(1)
std::unordered_multimap O(1) O(1) O(1) O(1)
std::stack O(1) O(1) N/A N/A
std::queue O(1) O(1) N/A N/A
std::priority_queue O(log n) O(log n) N/A O(log n)

3. STL 알고리즘 (Algorithms)

STL 알고리즘은 데이터를 처리하고 변형하는데 유용한 여러 함수들을 제공합니다. STL 알고리즘은 다양한 종류로 나눠지며, 데이터의 순서와 집합 연산, 변형 등을 효율적으로 처리할 수 있도록 돕습니다. 다음은 STL 알고리즘의 주요 카테고리와 각 알고리즘의 설명이다.

기본 알고리즘

기본 알고리즘은 데이터의 순차적 탐색, 계산 및 변형을 위한 가장 기본적인 함수들을 포함한다. 이들은 주로 컨테이너의 요소에 대해 반복 작업을 수행하는 데 유용하다.

  • std::sort
    std::sort는 주어진 범위의 데이터를 오름차순 또는 내림차순으로 정렬하는 알고리즘이다. 평균적으로 O(n log n) 시간 복잡도를 가지며, 가장 널리 사용되는 정렬 알고리즘 중 하나이다. 기본적으로 힙 정렬이나 퀵 정렬을 사용하여 구현된다.

    사용방법 
     #include <iostream>
 #include <vector>   // std::vector 라이브러리 포함
 #include <algorithm> // std::sort 라이브러리 포함

 // 사용자 정의 비교 함수
 bool compare(int a, int b) {
    return a < b;  // 오름차순 정렬
 }

 int main() {
    // 1. 벡터 선언 및 초기화
    std::vector<int> vec = {10, 30, 20, 50, 40};

    // 2. 기본 정렬 (오름차순)
    std::sort(vec.begin(), vec.end());  // 벡터를 오름차순으로 정렬

    // 3. 정렬된 벡터 출력
    std::cout << "오름차순 정렬 결과: ";
    for (int num : vec) {
       std::cout << num << " ";
    }
    std::cout << std::endl;

    // 4. 내림차순 정렬
    std::sort(vec.begin(), vec.end(), std::greater<int>());  // 내림차순으로 정렬

    // 5. 내림차순 정렬된 벡터 출력
    std::cout << "내림차순 정렬 결과: ";
    for (int num : vec) {
       std::cout << num << " ";
    }
    std::cout << std::endl;

    // 사용자 정의 비교 함수로 정렬
    std::sort(vec.begin(), vec.end(), compare);
    std::cout << "사용자 정의 비교 함수로 정렬 결과: ";
    for (int num : vec) {
       std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
 }

  • std::reverse
    std::reverse는 주어진 범위의 요소들을 역순으로 뒤집는 알고리즘이다. 시간 복잡도는 O(n)으로, 모든 요소를 한 번씩만 뒤집으면 된다.

    사용방법 
     #include <iostream>
 #include <vector>    // std::vector 라이브러리 포함
 #include <algorithm> // std::reverse 라이브러리 포함

 int main() {
    // 1. 벡터 선언 및 초기화
    std::vector<int> vec = {10, 20, 30, 40, 50};

    // 2. 원본 벡터 출력
    std::cout << "원본 벡터: ";
    for (int num : vec) {
       std::cout << num << " ";
    }
    std::cout << std::endl;

    // 3. 벡터 순서 뒤집기
    std::reverse(vec.begin(), vec.end());  // 벡터의 순서를 뒤집음

    // 4. 뒤집힌 벡터 출력
    std::cout << "뒤집힌 벡터: ";
    for (int num : vec) {
       std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
 }

  • std::find
    std::find는 주어진 범위 내에서 특정 값을 찾아 해당 요소의 반복자를 반환하는 알고리즘이다. 최악의 경우 O(n)의 시간 복잡도를 가지며, 요소를 찾을 때까지 범위를 순차적으로 탐색한다.

    사용방법 
     #include <iostream>
 #include <vector>     // std::vector 라이브러리 포함
 #include <algorithm>  // std::find 라이브러리 포함

 int main() {
    // 1. 벡터 선언 및 초기화
    std::vector<int> vec = {10, 20, 30, 40, 50};

    // 2. 값을 찾기 (30을 찾음)
    auto it = std::find(vec.begin(), vec.end(), 30); // 30을 찾기

    // 3. 찾은 값 출력
    if (it != vec.end()) {
       std::cout << "찾은 값: " << *it << std::endl; // 찾은 값 출력
       std::cout << "위치: " << std::distance(vec.begin(), it) << std::endl; // 찾은 값의 위치 출력
    } else {
       std::cout << "값을 찾을 수 없습니다." << std::endl;
    }

    return 0;
 }

  • std::count
    std::count는 주어진 범위에서 특정 값이 등장하는 횟수를 반환하는 알고리즘이다. 이 역시 O(n)의 시간 복잡도를 가지며, 데이터를 처음부터 끝까지 순차적으로 확인한다.

    사용방법

  • std::accumulate
    std::accumulate는 범위 내의 요소들을 특정 이진 연산으로 누적하는 알고리즘이다. 기본적으로 덧셈을 사용하며, O(n)의 시간 복잡도를 가진다. 예를 들어, 주어진 벡터의 모든 값을 더할 때 유용하다.

    사용방법 
     #include <iostream>
 #include <vector>     // std::vector 라이브러리 포함
 #include <numeric>    // std::accumulate 라이브러리 포함

 // 사용자 정의 연산자: 곱셈
 int multiply(int a, int b) {
    return a * b;
 }

 int main() {
    // 1. 벡터 선언 및 초기화
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 2. 모든 요소의 합을 계산
    int sum = std::accumulate(vec.begin(), vec.end(), 0); // 초기값은 0

    // 3. 합 출력
    std::cout << "벡터의 합: " << sum << std::endl;

    // 3. (사용자 정의 함수 적용) 모든 요소의 곱을 계산
    int product = std::accumulate(vec.begin(), vec.end(), 1, multiply); // 초기값은 1, 연산자는 multiply

    // 4 곱셈 결과 출력
    std::cout << "벡터의 곱: " << product << std::endl;

    return 0;
 }

  • std::for_each
    std::for_each는 범위 내의 각 요소에 대해 주어진 함수 또는 연산을 적용하는 알고리즘이다. 이는 각 요소에 대해 임의의 함수를 적용할 때 유용하며, O(n)의 시간 복잡도를 가진다.

    사용방법 
     #include <iostream>
 #include <vector>     // std::vector 라이브러리 포함
 #include <algorithm>  // std::for_each 라이브러리 포함

 // 출력하는 함수 객체
 void print(int n) {
    std::cout << n << " ";
 }

 int main() {
    // 1. 벡터 선언 및 초기화
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 2. for_each를 사용하여 벡터의 모든 요소에 대해 출력 함수 적용
    std::for_each(vec.begin(), vec.end(), print);

    std::cout << std::endl;

    return 0;
 }

변형 알고리즘

변형 알고리즘은 데이터를 변형하거나 특정 조건에 맞게 수정하는 데 사용된다. 이들은 기존 데이터를 다른 형태로 바꾸거나 변환하는 데 유용하다.

  • std::transform
    std::transform은 범위 내의 각 요소에 대해 지정된 변환 함수를 적용하여 새로운 값을 생성하는 알고리즘이다. O(n)의 시간 복잡도를 가지며, 원본 데이터를 변형한 후 결과를 다른 컨테이너에 저장할 수 있다.

    사용방법 
     #include <iostream>
 #include <vector>     // std::vector 라이브러리 포함
 #include <algorithm>  // std::transform 라이브러리 포함

 // 제곱을 계산하는 함수
 int square(int n) {
    return n * n;
 }

 int main() {
    // 1. 벡터 선언 및 초기화
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::vector<int> result(5);  // 결과를 저장할 벡터

    // 2. transform을 사용하여 vec의 각 요소에 square 함수 적용
    std::transform(vec.begin(), vec.end(), result.begin(), square);

    // 3. 결과 출력
    for (int n : result) {
       std::cout << n << " ";  // 1 4 9 16 25
    }
    std::cout << std::endl;

    return 0;
 }

  • std::fill
    std::fill은 주어진 범위 내의 모든 요소를 특정 값으로 채우는 알고리즘이다. 이 알고리즘은 O(n)의 시간 복잡도를 가지며, 데이터가 이미 할당된 상태에서 값의 초기화를 할 때 유용하다.

    사용방법 
     #include <iostream>
 #include <vector>     // std::vector 라이브러리 포함
 #include <algorithm>  // std::fill 라이브러리 포함

 int main() {
    // 1. 벡터 선언 및 초기화
    std::vector<int> vec(5);  // 크기 5인 벡터

    // 2. std::fill을 사용하여 vec의 모든 요소를 10으로 채움
    std::fill(vec.begin(), vec.end(), 10);

    // 3. 결과 출력
    for (int n : vec) {
       std::cout << n << " ";  // 10 10 10 10 10
    }
    std::cout << std::endl;

    return 0;
 }

  • std::replace
    std::replace는 범위 내에서 특정 값을 다른 값으로 대체하는 알고리즘이다. O(n)의 시간 복잡도를 가지며, 일괄적인 값 교체가 필요한 경우에 유용하다.

    사용방법 
     #include <iostream>
 #include <vector>     // std::vector 라이브러리 포함
 #include <algorithm>  // std::replace 라이브러리 포함

 int main() {
    // 1. 벡터 선언 및 초기화
    std::vector<int> vec = {1, 2, 3, 4, 5, 3, 6};

    // 2. std::replace를 사용하여 벡터 내의 3을 99로 교체
    std::replace(vec.begin(), vec.end(), 3, 99);

    // 3. 결과 출력
    for (int n : vec) {
       std::cout << n << " ";  // 1 2 99 4 5 99 6
    }
    std::cout << std::endl;


    // 4. 배열 선언
    int arr[5] = {1, 2, 3, 4, 3};

    // 5. std::replace를 사용하여 배열의 모든 3을 99로 교체
    std::replace(std::begin(arr), std::end(arr), 3, 99);

    // 6. 결과 출력
    for (int n : arr) {
       std::cout << n << " ";  // 1 2 99 4 99
    }
    std::cout << std::endl;

    return 0;
 }

정렬 알고리즘

정렬 알고리즘은 데이터를 오름차순 또는 내림차순으로 정렬하는 데 사용된다. STL에서는 여러 가지 정렬 방법을 제공하여 다양한 상황에서 최적의 성능을 발휘한다.

  • std::sort
    std::sort는 범위 내의 데이터를 정렬하는 알고리즘으로, 기본적으로 O(n log n)의 시간 복잡도를 가진다. 기본적인 정렬 알고리즘으로, 빠르고 효율적으로 사용될 수 있다.

    사용방법 
     #include <iostream>
 #include <vector>
 #include <algorithm>  // std::sort 라이브러리 포함

 int main() {
    // 1. 벡터 선언 및 초기화
    std::vector<int> vec = {5, 3, 8, 1, 2};

    // 2. std::sort를 사용하여 벡터를 내림차순으로 정렬 (람다 함수 사용)
    std::sort(vec.begin(), vec.end(), [](int a, int b) {
       return a > b;  // 내림차순 정렬 조건
    });

    // 3. 결과 출력
    for (int n : vec) {
       std::cout << n << " ";  // 8 5 3 2 1
    }
    std::cout << std::endl;

    return 0;
 }

  • std::partial_sort
    std::partial_sort는 범위 내의 데이터 중 일부만 정렬하는 알고리즘이다. 예를 들어, 상위 n개의 요소만 정렬할 때 유용하다. 최악의 경우에도 O(n log n) 시간 복잡도를 가지며, 전체 정렬이 아니라 부분적으로 정렬된 결과를 얻을 수 있다.

    사용방법 
     #include <iostream>
 #include <vector>
 #include <algorithm> // std::partial_sort 포함

 int main() {
    // 1. 벡터 선언 및 초기화
    std::vector<int> vec = {8, 3, 5, 1, 9, 4, 2, 7, 6};

    // 2. std::partial_sort를 사용하여 상위 3개 요소를 정렬
    std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
    /*
    std::partial_sort(begin, middle, end)

    begin: 정렬할 범위의 시작 반복자.
    middle: 이 위치까지 오름차순으로 정렬됩니다.
    end: 범위의 끝 반복자 (전체 컨테이너).
    결과적으로 begin부터 middle까지는 정렬된 상태가 되고, 나머지는 정렬되지 않는다.
    */

    // 3. 결과 출력 (처음 3개의 요소만 오름차순으로 정렬됨)
    for (int n : vec) {
       std::cout << n << " ";
    }
    // 예상 출력: 1 2 3 8 9 4 5 7 6

    return 0;
 }

  • std::stable_sort
    std::stable_sort는 std::sort와 유사하지만, 동일한 값들에 대해 원래의 순서를 유지하는 정렬 알고리즘이다. 이는 비교적 느린 정렬이지만, 안정적인 정렬이 필요할 때 유용하다. 내부적으로 병합 정렬(Merge Sort)을 사용하여 O(n log n)의 시간 복잡도를 가진다.

    사용방법 
     #include <iostream>
 #include <vector>
 #include <algorithm> // std::stable_sort 포함

 struct Person {
    std::string name;
    int age;
 };

 int main() {
    // 1. 벡터 선언 및 초기화
    std::vector<Person> people = {
       {"Alice", 30}, {"Bob", 25}, {"Charlie", 25}, {"David", 35}
    };

    // 2. 나이를 기준으로 안정 정렬 (오름차순)
    std::stable_sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
       return a.age < b.age; // 나이가 적은 순서대로 정렬
    });

    // 3. 결과 출력 (동일 나이에서는 원래 순서 유지)
    for (const auto& person : people) {
       std::cout << person.name << " (" << person.age << ")\n";
    }
    // 예상 출력:
    // Bob (25)
    // Charlie (25)
    // Alice (30)
    // David (35)

    return 0;
 }

검색 알고리즘

검색 알고리즘은 데이터 집합 내에서 특정 요소를 찾는 데 사용된다. 정렬된 데이터에 대해서는 이진 탐색 알고리즘을 사용할 수 있으며, 이는 매우 효율적인 검색 방법이다.

  • std::binary_search
    std::binary_search는 정렬된 범위 내에서 특정 값이 존재하는지 확인하는 알고리즘이다. O(log n)의 시간 복잡도를 가지며, 이진 탐색을 사용하여 데이터를 효율적으로 검색한다.

    사용방법 
     #include <iostream>
 #include <vector>
 #include <algorithm> // std::binary_search 포함

 int main() {
    // 1. 정렬된 벡터 초기화
    std::vector<int> vec = {1, 3, 5, 7, 9};

    // 2. 특정 값 탐색
    int target = 5;
    if (std::binary_search(vec.begin(), vec.end(), target)) {
       std::cout << target << " is found in the vector.\n";
    } else {
       std::cout << target << " is not found in the vector.\n";
    }

    // 3. 없는 값 탐색
    target = 6;
    if (std::binary_search(vec.begin(), vec.end(), target)) {
       std::cout << target << " is found in the vector.\n";
    } else {
       std::cout << target << " is not found in the vector.\n";
    }

    //4. 사용자 정의함수 사용가능
    std::binary_search(vec.begin(), vec.end(), 7, std::greater<int>())

    return 0;
 }

  • std::lower_bound
    std::lower_bound는 정렬된 범위 내에서 특정 값보다 크거나 같은 첫 번째 요소의 반복자를 반환하는 알고리즘이다. 이 역시 O(log n)의 시간 복잡도를 가지며, 정렬된 데이터를 다룰 때 매우 유용하다.

    사용방법 
     #include <iostream>
 #include <vector>
 #include <algorithm> // std::lower_bound 포함

 int main() {
    // 1. 정렬된 벡터 초기화
    std::vector<int> vec = {10, 20, 20, 30, 40};

    // 2. 값 찾기
    int target = 20;
    auto it = std::lower_bound(vec.begin(), vec.end(), target);

    // 3. 반복자가 끝이 아니고 값을 찾은 경우
    if (it != vec.end()) {
       std::cout << "The first element >= " << target << " is " << *it << ".\n";
    } else {
       std::cout << "No element >= " << target << " found.\n";
    }

    // 4. 없는 값 찾기
    target = 25;
    it = std::lower_bound(vec.begin(), vec.end(), target);
    if (it != vec.end()) {
       std::cout << "The first element >= " << target << " is " << *it << ".\n";
    } else {
       std::cout << "No element >= " << target << " found.\n";
    }

    return 0;
 }

  • std::upper_bound
    std::upper_bound는 정렬된 범위 내에서 특정 값보다 큰 첫 번째 요소의 반복자를 반환하는 알고리즘이다. std::lower_bound와 유사하지만, 비교하는 값보다 큰 첫 번째 요소를 찾는 데 사용된다.

    사용방법 
     #include <iostream>
 #include <vector>
 #include <algorithm> // std::lower_bound 포함

 int main() {
    // 1. 정렬된 벡터 초기화
    std::vector<int> vec = {10, 20, 20, 30, 40};

    // 2. 값 찾기
    int target = 20;
    auto it = std::lower_bound(vec.begin(), vec.end(), target);

    // 3. 반복자가 끝이 아니고 값을 찾은 경우
    if (it != vec.end()) {
       std::cout << "The first element >= " << target << " is " << *it << ".\n";
    } else {
       std::cout << "No element >= " << target << " found.\n";
    }

    // 4. 없는 값 찾기
    target = 25;
    it = std::lower_bound(vec.begin(), vec.end(), target);
    if (it != vec.end()) {
       std::cout << "The first element >= " << target << " is " << *it << ".\n";
    } else {
       std::cout << "No element >= " << target << " found.\n";
    }

    return 0;
 }

집합 연산 알고리즘

집합 연산 알고리즘은 두 집합 간의 교집합, 합집합, 차집합 등의 연산을 수행하는 데 사용된다. 이는 데이터 집합을 조합하거나 비교할 때 유용하다.

  • std::set_intersection
    std::set_intersection은 두 개의 정렬된 범위 간의 교집합을 구하는 알고리즘이다. 결과는 두 집합에 공통된 요소만 포함하며, O(n + m)의 시간 복잡도를 가진다. n과 m은 두 집합의 크기이다.

    사용방법 
     #include <iostream>
 #include <vector>
 #include <algorithm> // std::set_intersection 포함

 int main() {
    // 1. 정렬된 두 벡터
    std::vector<int> vec1 = {10, 20, 30, 40, 50};
    std::vector<int> vec2 = {30, 40, 50, 60, 70};

    // 2. 교집합을 저장할 벡터 (최대 크기는 vec1 또는 vec2 중 작은 크기)
    std::vector<int> result(std::min(vec1.size(), vec2.size()));

    // 3. set_intersection 수행
    auto it = std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

    // 4. 결과 저장 후 크기를 조정
    result.resize(it - result.begin());

    // 5. 결과 출력
    std::cout << "Intersection: ";
    for (int num : result) {
       std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
 }

  • std::set_union
    std::set_union은 두 개의 정렬된 범위 간의 합집합을 구하는 알고리즘이다. 두 집합의 모든 요소를 포함하며, 중복 요소는 한 번만 포함된다. O(n + m)의 시간 복잡도를 가진다.

    사용방법 
     #include <iostream>
 #include <vector>
 #include <algorithm> // std::set_union 포함

 int main() {
    // 1. 정렬된 두 벡터
    std::vector<int> vec1 = {10, 20, 30, 40, 50};
    std::vector<int> vec2 = {30, 40, 50, 60, 70};

    // 2. 합집합을 저장할 벡터
    std::vector<int> result(vec1.size() + vec2.size()); // 크기는 두 범위 합보다 크거나 같아야 함

    // 3. set_union 실행
    auto it = std::set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

    // 4. 결과 저장 후 크기를 조정
    result.resize(it - result.begin());

    // 5. 결과 출력
    std::cout << "Union: ";
    for (int num : result) {
       std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
 }

  • std::set_difference
    std::set_difference는 두 개의 정렬된 범위 간의 차집합을 구하는 알고리즘이다. 첫 번째 범위에는 포함되지만 두 번째 범위에는 포함되지 않은 요소를 반환한다. O(n + m)의 시간 복잡도를 가진다.

    사용방법 
     #include <iostream>
 #include <vector>
 #include <algorithm> // std::set_difference 포함

 int main() {
    // 1. 정렬된 두 벡터
    std::vector<int> vec1 = {10, 20, 30, 40, 50};
    std::vector<int> vec2 = {30, 40, 50, 60, 70};

    // 2. 차집합을 저장할 벡터
    std::vector<int> result(vec1.size()); // 결과 벡터는 첫 번째 범위 크기 이상이어야 함

    // 3. set_difference 실행
    auto it = std::set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

    // 4. 결과 저장 후 크기를 조정
    result.resize(it - result.begin());

    // 5. 결과 출력
    std::cout << "Difference: ";
    for (int num : result) {
       std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
 }

4. 반복자 (Iterators)

반복자의 종류

C++에서 반복자는 컨테이너 내의 요소들에 순차적으로 접근할 수 있도록 도와주는 객체이다. 반복자는 기본적으로 포인터와 유사한 역할을 하며, 다양한 종류의 반복자가 제공되어 각기 다른 용도에 맞게 사용할 수 있다. 반복자는 크게 6가지로 분류할 수 있다.

  1. std::iterator
    std::iterator는 모든 반복자의 기본 클래스로, 다양한 반복자 타입을 정의할 때 기초가 되는 클래스로 사용된다. 이 클래스는 반복자가 구현해야 하는 최소한의 연산들을 제공하며, 일반적으로 새로운 반복자를 정의할 때 이를 상속받아 사용한다.

  2. std::input_iterator
    std::input_iterator는 데이터를 한 번 읽는 데 적합한 반복자이다. 이 반복자는 순차적으로 컨테이너에서 데이터를 읽기만 할 수 있으며, 한 번 읽은 요소를 다시 읽을 수 없기 때문에 주로 입력 스트림과 관련된 컨테이너에서 사용된다. 이 반복자는 읽기 전용이며, 전진만 가능하다.

  3. std::output_iterator
    std::output_iterator는 데이터를 컨테이너에 기록하는 데 사용되는 반복자이다. 이 반복자는 단방향으로만 작동하며, 주로 출력 스트림이나 데이터 저장에 사용된다. 이 반복자는 데이터를 기록하기만 할 수 있으며, 읽는 연산은 지원하지 않는다.

  4. std::forward_iterator
    std::forward_iterator는 std::input_iterator의 기능을 확장한 것으로, 순차적으로 데이터를 읽을 수 있으며, 한 번에 하나씩만 순회할 수 있다. 또한, 반복자 자체가 증가하는 연산이 가능하여, 일반적인 순차 데이터에 대한 처리에 적합하다.

  5. std::bidirectional_iterator
    std::bidirectional_iterator는 std::forward_iterator의 특성을 확장하여, 양방향으로 순회할 수 있는 반복자이다. 이 반복자는 데이터를 순차적으로 읽고 쓸 수 있을 뿐만 아니라, 이전 요소로 되돌아갈 수 있는 기능도 제공하여 이중 연결 리스트와 같은 구조에서 유용하게 사용된다.

  6. std::random_access_iterator
    std::random_access_iterator는 가장 고급의 반복자로, 임의의 위치로 즉시 접근할 수 있는 특성을 가진다. 이 반복자는 배열처럼 인덱스를 사용하여 빠르게 접근할 수 있으며, std::vector, std::deque와 같은 연속된 메모리 블록을 사용하는 컨테이너에서 사용된다. 이 반복자는 덧셈, 뺄셈, 비교 등 다양한 연산을 지원한다.

반복자 사용법

반복자는 일반적으로 다음과 같은 방식으로 사용된다. 먼저, 반복자는 컨테이너의 begin() 함수나 end() 함수를 통해 얻을 수 있다. begin()은 첫 번째 요소를 가리키는 반복자를 반환하며, end()는 마지막 요소의 다음 위치를 가리키는 반복자를 반환한다. 반복자는 * 연산자를 사용하여 해당 위치의 요소에 접근할 수 있으며, ++ 연산자를 사용하여 반복자를 한 단계씩 전진시킬 수 있다.

std::vector<int> vec = {1, 2, 3, 4, 5};
for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

위의 코드에서는 std::vector<int> 컨테이너의 반복자를 사용하여 벡터의 모든 요소를 순차적으로 출력한다. it은 벡터의 시작 위치인 begin()에서 시작하여, end()에 도달할 때까지 한 단계씩 전진하면서 각 요소를 출력한다.

반복자는 std::for_each와 같은 알고리즘에서 인자로 사용될 수도 있으며, 이는 컨테이너의 각 요소에 대해 동일한 연산을 적용하는 데 유용하다.

std::for_each(vec.begin(), vec.end(), [](int n) {
    std::cout << n * 2 << " ";
});

이 코드에서는 std::for_each 알고리즘을 사용하여 벡터의 각 요소에 대해 두 배로 곱한 값을 출력한다. 이와 같이 반복자는 알고리즘과 결합되어 매우 효율적인 코드 작성을 가능하게 한다.

4. STL 이외의 유용한 라이브러리

C++에서 STL이 아닌 유용한 라이브러리에는 여러 가지가 있다. 다음은 C++에서 자주 사용되는 주요 라이브러리들이다.

1. <cmath>

  • <cmath>는 수학적 연산을 위한 함수들이 포함된 라이브러리이다. 예를 들어, sqrt, pow, sin, cos, log, exp, abs 등의 수학 함수들을 제공한다. 이는 STL에는 포함되지 않지만, C++ 표준 라이브러리의 일환이다.

1. abs()

  • 절댓값을 반환한다. 입력 값이 음수일 경우 양수로 변환된다.
  • 예: abs(-5)는 5를 반환한다.

2. acos()

  • 아크코사인 값을 계산한다. 입력 값은 -1과 1 사이여야 한다. 반환 값은 라디안 단위로 반환된다.
  • 예: acos(1)은 0을 반환한다.

3. asin()

  • 아크사인 값을 계산한다. 입력 값은 -1과 1 사이여야 한다. 반환 값은 라디안 단위로 반환된다.
  • 예: asin(0)은 0을 반환한다.

4. atan()

  • 아크탄젠트 값을 계산한다. 반환 값은 라디안 단위로 반환된다.
  • 예: atan(1)은 0.785398을 반환한다.

5. atan2()

  • 두 점의 좌표를 이용하여 아크탄젠트 값을 계산한다. 첫 번째 매개변수는 y, 두 번째 매개변수는 x이다. 반환 값은 라디안 단위로 반환된다.
  • 예: atan2(1, 1)은 0.785398을 반환한다.

6. ceil()

  • 주어진 값을 초과하지 않는 가장 작은 정수로 반올림한다.
  • 예: ceil(3.14)는 4를 반환한다.

7. cos()

  • 주어진 각도의 코사인 값을 계산한다. 입력 값은 라디안 단위로 제공된다.
  • 예: cos(0)은 1을 반환한다.

8. cosh()

  • 하이퍼볼릭 코사인 값을 계산한다.
  • 예: cosh(0)은 1을 반환한다.

9. exp()

  • 자연 상수 e를 밑으로 하는 지수 함수 값을 계산한다.
  • 예: exp(1)은 2.718281828459045를 반환한다.

10. fabs()

  • 부동소수점 수의 절댓값을 반환한다.
  • 예: fabs(-3.14)는 3.14를 반환한다.

11. floor()

  • 주어진 값을 초과하지 않는 가장 큰 정수로 내림한다.
  • 예: floor(3.14)는 3을 반환한다.

12. fmod()

  • 두 수를 나눈 나머지를 반환한다. 부동소수점 수에 대해 연산을 수행한다.
  • 예: fmod(5.3, 2)는 1.3을 반환한다.

13. hypot()

  • 피타고라스의 정리를 사용하여 두 값의 제곱합의 제곱근을 계산한다. 두 값의 길이를 이용해 대각선 길이를 구할 수 있다.
  • 예: hypot(3, 4)는 5를 반환한다.

14. log()

  • 자연 로그 (밑이 e인 로그)를 계산한다.
  • 예: log(2.718281828459045)는 1을 반환한다.

15. log10()

  • 밑이 10인 로그를 계산한다.
  • 예: log10(100)은 2를 반환한다.

16. modf()

  • 실수 값을 분리하여 소수점 이하와 정수 부분을 반환한다. 반환값은 소수점 이하 부분과 정수 부분이다.
  • 예: modf(3.14, &intpart)는 0.14와 3을 반환한다.

17. pow()

  • 첫 번째 매개변수를 밑으로, 두 번째 매개변수를 지수로 하는 거듭제곱 값을 계산한다.
  • 예: pow(2, 3)은 8을 반환한다.

18. sin()

  • 주어진 각도의 사인 값을 계산한다. 입력 값은 라디안 단위로 제공된다.
  • 예: sin(0)은 0을 반환한다.

19. sinh()

  • 하이퍼볼릭 사인 값을 계산한다.
  • 예: sinh(0)은 0을 반환한다.

20. sqrt()

  • 주어진 값의 제곱근을 계산한다.
  • 예: sqrt(9)는 3을 반환한다.

21. tan()

  • 주어진 각도의 탄젠트 값을 계산한다. 입력 값은 라디안 단위로 제공된다.
  • 예: tan(0)은 0을 반환한다.

22. tanh()

  • 하이퍼볼릭 탄젠트 값을 계산한다.
  • 예: tanh(0)은 0을 반환한다.

23. trunc()

  • 실수 값을 내림하여 정수 부분만 반환한다. 소수점 이하 자리는 버린다.
  • 예: trunc(3.14)는 3을 반환한다.

2. Boost

  • Boost는 C++에서 매우 널리 사용되는 고급 라이브러리이다. STL에서 제공하지 않는 다양한 기능을 보완해 준다. 예를 들어, Boost.Asio는 네트워크 프로그래밍을 위한 라이브러리이며, Boost.Filesystem은 파일 시스템 작업을 단순화한다. 또한, Boost.Thread는 멀티스레딩을 지원하고, Boost.SmartPtr은 스마트 포인터를 제공한다.

3. <regex>

  • <regex>는 정규 표현식을 다루기 위한 라이브러리이다. std::regex를 통해 문자열을 효율적으로 검색하고, 패턴을 검사하는 기능을 제공한다. STL에는 정규 표현식 처리 기능이 없기 때문에, 이 라이브러리가 매우 유용하다.

4. Eigen

  • Eigen은 고성능 수치 연산을 위한 C++ 라이브러리이다. 주로 벡터, 행렬, 선형 대수학 연산에 사용된다. STL은 행렬 연산을 위한 기능을 제공하지 않기 때문에, 이러한 연산을 처리할 수 있는 Eigen과 같은 라이브러리가 필요하다.

5. <thread>와 <mutex>

  • C++11 이상에서 제공되는 스레딩과 동기화를 위한 라이브러리이다. 멀티스레딩을 활용한 병렬 처리와 동기화를 구현할 수 있게 해준다. std::thread, std::mutex, std::lock_guard 등을 사용하여 멀티스레딩 작업을 쉽게 처리할 수 있다.

6. Cereal

  • Cereal은 직렬화(serialization) 라이브러리이다. C++ 객체를 파일이나 네트워크 스트림으로 변환하는 기능을 제공한다. 이 라이브러리는 복잡한 C++ 객체를 직렬화하고 역직렬화하는 데 유용하다.

7. JSON for Modern C++ (nlohmann/json)

  • nlohmann/json은 C++에서 JSON 데이터를 간편하게 처리할 수 있는 라이브러리이다. JSON 객체를 다루는 직관적인 API를 제공하며, C++의 표준 라이브러리에는 JSON 처리 기능이 없기 때문에 매우 유용하다.

8. Google’s Protocol Buffers (protobuf)

  • Protocol Buffers는 Google에서 개발한 데이터 직렬화 라이브러리이다. 데이터의 직렬화와 역직렬화에 유용하며, 데이터 형식이 명확하고 빠르다. 다양한 언어를 지원하는 장점이 있다.

9. OpenCV

  • OpenCV는 이미지 처리 및 컴퓨터 비전 작업을 위한 라이브러리이다. 고성능의 이미지 처리 기능을 제공하며, 비디오 캡처, 얼굴 인식, 물체 추적 등의 다양한 기능을 포함하고 있다.

10. Qt

  • Qt는 C++ 기반의 GUI 애플리케이션을 개발할 수 있게 해주는 라이브러리이다. 이 라이브러리는 복잡한 GUI를 효율적으로 만들 수 있도록 도와주며, 네트워크, 스레딩, 데이터베이스, OpenGL과 같은 다양한 기능도 제공한다.

11. Poco

  • Poco는 C++에서 네트워킹, 파일 시스템 작업, 데이터베이스 연동, XML 처리 등 다양한 기능을 제공하는 크로스 플랫폼 라이브러리이다.

12. GLM

  • GLM은 OpenGL을 위한 수학 라이브러리이다. 벡터와 행렬 연산을 위한 함수들을 제공하며, 3D 그래픽스를 다룰 때 매우 유용하다.

13. spdlog

  • spdlog는 빠르고 효율적인 C++ 로깅 라이브러리이다. 스레드 안전하며, 다양한 출력 형식과 로그 레벨을 지원한다.

14. TBB (Threading Building Blocks)

  • TBB는 Intel에서 개발한 멀티스레딩 라이브러리이다. 고성능 병렬 프로그래밍을 지원하며, 스레드 관리와 병렬화 작업을 쉽게 처리할 수 있다.

15. SQLite

  • SQLite는 가벼운 임베디드 데이터베이스 엔진이다. 서버 없이 사용할 수 있는 데이터베이스로, C++ 애플리케이션에서 로컬 데이터베이스를 쉽게 다룰 수 있다.

이와 같은 라이브러리들은 C++의 표준 라이브러리에는 포함되지 않지만, C++ 개발에서 매우 유용하게 사용되는 중요한 외부 라이브러리들이다. 이러한 라이브러리들을 활용하면 C++에서 복잡한 작업을 더 쉽고 효율적으로 처리할 수 있다

Boost 라이브러리와 STL의 차이점

Boost 라이브러리와 STL은 모두 C++의 중요한 라이브러리로 널리 사용되지만, 몇 가지 중요한 차이점이 존재한다. 첫 번째 차이점은 기능의 범위이다. STL은 주로 기본적인 데이터 구조(예: vector, list, map, set 등)와 알고리즘(예: sort, find, accumulate)을 제공하는 반면, Boost는 더 넓은 범위의 기능을 제공한다. Boost는 정규 표현식, 스마트 포인터, 스레딩, 파일 시스템 등 다양한 추가 기능을 포함하고 있으며, 이를 통해 C++에서 직접 구현하기 어려운 고급 기능을 손쉽게 사용할 수 있다.

두 번째 차이점은 호환성이다. STL은 C++ 표준 라이브러리의 일부분으로, 모든 C++ 컴파일러에서 기본적으로 제공된다. 반면, Boost는 표준 라이브러리가 아니므로 별도로 설치해야 하며, 일부 기능은 특정 컴파일러에서 지원되지 않을 수 있다. 그러나 Boost는 C++ 표준 라이브러리에 포함되지 않은 기능을 제공하고, C++ 표준화 위원회에서 일부 기능이 C++ 표준에 포함되기도 했다. 예를 들어, std::shared_ptr와 std::unique_ptr는 원래 Boost의 Boost Smart Pointers 라이브러리에서 유래한 것이다.

또한, 템플릿 메타프로그래밍에서 Boost는 STL보다 더 많은 고급 기능을 제공한다. Boost의 Boost.MPL(Metaprogramming Library)과 Boost.Hana는 템플릿 메타프로그래밍을 통해 컴파일 시간에 효율적인 연산을 수행할 수 있도록 돕는다. STL은 기본적으로 템플릿을 사용하지만, Boost는 더 복잡하고 강력한 메타프로그래밍 기능을 제공하여 컴파일 타임 계산을 최적화하고, C++ 코드의 재사용성을 높이는 데 기여한다.

STL과 C++17 이상의 표준 라이브러리의 차이점

C++17 이상의 표준 라이브러리는 STL의 기존 기능에 비해 많은 향상된 기능을 제공한다. C++17에서는 병렬 알고리즘을 지원하는 새로운 기능들이 추가되었다. 이를 통해 std::sort, std::for_each 등 기존의 알고리즘들을 멀티스레딩 환경에서 병렬로 실행할 수 있어, 대규모 데이터 처리에서 성능을 크게 향상시킬 수 있다. 예를 들어, C++17에서는 std::execution::par 옵션을 통해 병렬 처리를 명시적으로 지시할 수 있다.

또한, C++17에서는 파일 시스템 라이브러리가 표준으로 추가되었다. 이 라이브러리는 Boost의 Boost.Filesystem 라이브러리와 비슷한 기능을 제공하지만, 이제는 추가적인 외부 라이브러리 없이 C++ 표준 라이브러리에서 직접 파일 시스템 관련 기능을 사용할 수 있게 되었다. 파일 경로 처리, 디렉토리 탐색, 파일 입출력 등의 기능을 손쉽게 구현할 수 있다.

C++20에서는 또 다른 큰 변화로 코루틴(coroutine)이 도입되었다. 코루틴은 비동기 프로그래밍을 더욱 직관적으로 작성할 수 있도록 도와주며, 특히 입출력 처리나 네트워크 프로그래밍 등에서 큰 성과를 낼 수 있다. 코루틴을 사용하면 비동기 작업을 마치 동기적인 코드처럼 작성할 수 있어, 코드의 가독성과 유지보수성을 크게 향상시킬 수 있다.

또한, C++20에서는 모듈(Modules) 기능이 도입되었다. 모듈은 C++의 전통적인 헤더 파일 기반의 컴파일 방식을 대체할 수 있는 기능으로, 컴파일 시간을 크게 단축시킬 수 있다. 모듈을 사용하면 소스 코드 파일 간의 의존성을 명확하게 정의하고, 컴파일러가 필요한 부분만 컴파일하도록 하여 최적화할 수 있다.

결론적으로, STL은 C++의 기본적인 자료 구조와 알고리즘을 제공하는 데 중점을 두고 있으며, C++17 이상에서는 STL에 비해 더 많은 고급 기능을 제공하는 표준 라이브러리가 도입되었다. Boost는 표준 라이브러리와 STL이 제공하지 않는 다양한 기능을 보충하며, C++에서의 개발 효율성을 높이는 데 중요한 역할을 한다.

참조