C++ STL: 6장 - STL 컨테이너 성능 비교와 활용 사례

6.1 STL 컨테이너 성능 비교

STL에서 제공하는 다양한 컨테이너는 각기 다른 데이터 구조와 알고리즘에 기반을 두고 설계되었기 때문에, 성능이 작업 유형과 데이터의 크기에 따라 크게 달라질 수 있습니다. 이 장에서는 주요 STL 컨테이너 간의 성능 차이를 이해하고, 각각의 컨테이너가 적합한 상황을 설명합니다.

---

6.1.1 순차 컨테이너 성능 비교

컨테이너	삽입/삭제 (중간)	삽입/삭제 (끝)	검색	임의 접근
std::vector	느림 (O(n))	평균 O(1), 최악 O(n)	느림 (O(n))	빠름 (O(1))
std::deque	느림 (O(n))	빠름 (O(1))	느림 (O(n))	빠름 (O(1))
std::list	빠름 (O(1))	빠름 (O(1))	느림 (O(n))	불가능
std::array	고정 크기	고정 크기	느림 (O(n))	빠름 (O(1))

자세한 설명:

1. std::vector:
   • 요소가 연속된 메모리 블록에 저장되므로 끝에서의 삽입/삭제는 빠르지만(O(1)), 중간 삽입/삭제는 이후 요소를 이동해야 하므로 느립니다(O(n)).
   • 정렬되지 않은 상태에서는 검색이 O(n)이며, 정렬된 상태에서는 std::binary_search를 사용하여 O(log n)으로 성능을 향상시킬 수 있습니다.
2. std::deque:
   • 양쪽 끝에서 삽입과 삭제가 O(1)로 빠릅니다.
   • 중간 삽입/삭제는 느리며(O(n)), 따라서 양쪽 끝에서 삽입/삭제가 빈번한 작업에 적합합니다.
   • 임의 접근이 가능하며, O(1)입니다.
3. std::list:
   • 이중 연결 리스트 구조로, 중간 삽입/삭제와 양쪽 끝에서의 삽입/삭제가 모두 O(1)로 빠릅니다.
   • 하지만 임의 접근이 불가능하며, 특정 위치로 이동하는 데 O(n)이 소요됩니다.
4. std::array:
   • 고정 크기의 배열로, 컴파일 시간에 크기가 정해집니다.
   • 끝이나 중간 삽입/삭제는 지원하지 않으며, 검색은 선형 검색(O(n))입니다.

6.1.2 연관 컨테이너 성능 비교

컨테이너	삽입/삭제	검색	정렬
std::set	O(log n)	O(log n)	자동 정렬
std::map	O(log n)	O(log n)	자동 정렬
std::unordered_set	O(1) 평균, O(n) 최악	O(1) 평균, O(n) 최악	정렬 없음
std::unordered_map	O(1) 평균, O(n) 최악	O(1) 평균, O(n) 최악	정렬 없음

자세한 설명:

1. std::set과 std::map:
   • 내부적으로 Red-Black Tree를 사용하여 요소를 자동으로 정렬합니다.
   • 삽입/삭제/검색 모두 O(log n)의 성능을 가집니다.
2. std::unordered_set과 std::unordered_map:
   • 해시 테이블 기반으로 평균적으로 O(1)의 성능을 제공합니다.
   • 하지만 해시 충돌이 발생하면 최악의 경우 O(n)의 성능을 보일 수 있습니다.
   • 데이터가 정렬되지 않습니다.

6.1.3 컨테이너 어댑터 성능

컨테이너 어댑터는 기본 컨테이너에 따라 성능이 좌우됩니다. 예를 들어, std::stack과 std::queue는 일반적으로 std::deque를 기반으로 구현됩니다.

어댑터	삽입/삭제 (끝)	검색
std::stack	빠름 (O(1))	느림
std::queue	빠름 (O(1))	느림
std::priority_queue	효율적 (O(log n))	느림

자세한 설명:

1. std::priority_queue:
   • 내부적으로 최대 힙 또는 최소 힙을 사용하여 구현됩니다.
   • 삽입과 삭제는 O(log n)의 성능을 가지며, 이는 힙의 균형을 유지하기 위한 연산 때문입니다.
   • 상대적으로 효율적인 성능을 제공합니다.

---

6.2 컨테이너 선택 가이드

6.2.1 작업 유형별 추천 컨테이너

1. 삽입과 삭제가 빈번한 경우:
   • 추천: std::list, std::deque
   • 이유: std::list는 중간 삽입/삭제와 양쪽 끝 삽입/삭제가 모두 효율적이고, std::deque는 양쪽 끝에서의 삽입/삭제가 매우 효율적입니다.
2. 랜덤 액세스가 중요한 경우:
   • 추천: std::vector, std::array
   • 이유: 연속된 메모리 블록을 사용하므로 임의 접근 속도가 빠릅니다.
3. 자동 정렬된 데이터가 필요한 경우:
   • 추천: std::set, std::map
   • 이유: 삽입 시 자동으로 정렬되며, 검색 효율이 높습니다.
4. 빠른 키-값 검색이 필요한 경우:
   • 추천: std::unordered_map, std::unordered_set
   • 이유: 해시 기반 데이터 구조로 평균적으로 O(1)의 시간 복잡도를 가집니다.
5. 고정 크기의 데이터를 다루는 경우:
   • 추천: std::array
   • 이유: 크기가 고정되어 메모리 관리가 간단하며 빠릅니다.

---

6.3 활용 사례

6.3.1 정렬된 데이터 관리

• 상황: 정렬된 데이터에서 중복 없이 요소를 저장하고 검색.
• 컨테이너: std::set

예제:

#include <iostream>
#include <set>

int main() {
    std::set<int> s = {3, 1, 4, 1, 5};

    for (const auto& elem : s) {
        std::cout << elem << " "; // 1 3 4 5
    }

    return 0;
}

6.3.2 키-값 데이터 저장

• 상황: 사용자 이름과 나이를 저장하고 검색.
• 컨테이너: std::unordered_map

예제:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> age_map = {
        {"Alice", 25},
        {"Bob", 30}
    };

    age_map["Charlie"] = 20;

    for (const auto& [key, value] : age_map) {
        std::cout << key << ": " << value << "\n";
    }

    return 0;
}

6.3.3 대규모 데이터 처리

• 상황: 데이터 스트림에서 고속 처리가 필요.
• 컨테이너: std::vector

예제:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {5, 1, 4, 2, 3};

    std::sort(vec.begin(), vec.end());

    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }

    return 0;
}

---

6.4 컨테이너 성능 최적화 팁

1. 메모리 예약: std::vector와 같은 컨테이너는 reserve를 사용해 불필요한 재할당을 줄일 수 있습니다.
2. 필요한 컨테이너 선택: 작업 유형에 맞는 컨테이너를 선택하여 시간 복잡도를 최소화하세요.
3. 컨테이너 복사 최소화: 큰 데이터를 다룰 때 복사를 피하기 위해 std::move를 활용하세요.
4. shrink_to_fit 사용: 사용 후 남은 여유 공간을 줄여 메모리를 효율적으로 관리하세요.

---

결론

STL 컨테이너는 각각의 특성과 성능을 이해하고 적절히 활용할 때 가장 강력한 도구가 됩니다. 다양한 작업 유형에 맞는 컨테이너를 선택하고 성능 최적화 팁을 적용하면 효율적인 프로그램을 작성할 수 있습니다.