[C++] 컨테이너(container)

C++의 컨테이너(container)는 데이터를 저장하고 관리하는 클래스 템플릿입니다. 다양한 유형의 데이터를 효율적으로 저장하고 조작할 수 있도록 도와주며, C++ 표준 라이브러리에서 제공하는 주요 컨테이너는 크게 순차 컨테이너, 연관 컨테이너, 해시 기반 컨테이너, 그리고 어댑터로 나눌 수 있습니다.

주요 컨테이너

1. 순차 컨테이너 (Sequence Containers)

• std::vector: 동적 배열로, 요소를 끝에 추가할 수 있고 크기를 자동으로 조절합니다. 임의 접근이 빠르며, 메모리 효율성이 뛰어납니다.
• std::deque: 양쪽 끝에서 삽입 및 삭제가 가능한 이중 끝 큐로, 앞뒤 모두에서 빠른 접근과 수정이 가능합니다.
• std::list: 이중 연결 리스트로, 요소의 삽입과 삭제가 빠르지만, 임의 접근 속도가 느립니다.
• std::forward_list: 단일 연결 리스트로, 메모리 사용이 효율적이지만, 양방향 접근이 불가능합니다.
• std::array: 고정 크기 배열로, 크기가 컴파일 타임에 정해지며, 메모리를 스택에 할당합니다.

2. 연관 컨테이너 (Associative Containers)

• std::set: 중복되지 않는 요소의 집합으로, 자동으로 정렬됩니다. 요소 검색이 빠릅니다.
• std::map: 키-값 쌍을 저장하는 연관 배열로, 키에 대해 자동으로 정렬됩니다. 각 키는 고유해야 합니다.
• std::multiset: 중복된 요소를 허용하는 집합입니다.
• std::multimap: 중복된 키를 허용하는 연관 배열입니다.

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

• std::unordered_set: 해시 테이블을 사용하여 요소를 저장하며, 중복되지 않는 요소의 집합입니다. 정렬되지 않습니다.
• std::unordered_map: 해시 테이블 기반의 키-값 쌍을 저장하는 연관 배열입니다.
• std::unordered_multiset: 중복 요소를 허용하는 해시 기반 집합입니다.
• std::unordered_multimap: 중복 키를 허용하는 해시 기반 연관 배열입니다.

4. 어댑터 (Adapters)

• std::stack: LIFO(Last In, First Out) 방식으로 작동하는 스택입니다.
• std::queue: FIFO(First In, First Out) 방식으로 작동하는 큐입니다.
• std::priority_queue: 우선순위 큐로, 가장 높은 우선순위를 가진 요소가 먼저 나옵니다.

컨테이너 선택 기준

각 컨테이너는 데이터 저장 방식과 접근 방식이 다르므로, 특정 상황에 맞는 컨테이너를 선택하는 것이 중요합니다. 예를 들어:

• 빠른 임의 접근이 필요할 때는 std::vector나 std::array를 사용하는 것이 적합합니다.
• 빈번한 삽입/삭제 작업이 필요할 경우 std::list나 std::deque가 적합합니다.
• 검색 작업이 많고 중복 요소가 없어야 할 경우 std::set을 사용하는 것이 효율적입니다.

컨테이너의 시간 복잡도

각 컨테이너의 삽입, 삭제, 검색 연산에 대한 시간 복잡도를 이해하면 성능 측면에서 올바른 컨테이너를 선택할 수 있습니다.

• std::vector: 끝에서 삽입/삭제 O(1), 임의 접근 O(1), 중간에서 삽입/삭제 O(n)
• std::deque: 양쪽 끝에서 삽입/삭제 O(1), 임의 접근 O(1)
• std::list: 임의 접근 O(n), 삽입/삭제 O(1)
• std::set, std::map: 삽입/삭제/검색 O(log n) (트리 구조)
• std::unordered_set, std::unordered_map: 삽입/삭제/검색 평균 O(1) (해시 테이블 기반)

메모리 관리 및 최적화

• std::vector는 동적 메모리 할당을 사용하여 자동으로 크기를 조정하지만, 사용자가 크기를 예측할 수 있다면 reserve() 함수를 사용해 성능을 최적화할 수 있습니다.
• std::list는 연결 리스트 구조로, 각 요소가 다음/이전 요소를 가리키는 포인터를 포함하므로 메모리 오버헤드가 발생할 수 있습니다.

STL 알고리즘과의 통합

C++의 STL(Standard Template Library) 알고리즘은 컨테이너와 잘 통합되어 있어, 다양한 알고리즘을 컨테이너와 함께 사용할 수 있습니다.

[C++] STL(표준 템플릿 라이브러리) 알고리즘이란?

[C++] STL(표준 템플릿 라이브러리) 알고리즘이란?

 

예시로, std::vector와 std::sort를 사용하는 방법은 다음과 같습니다

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

int main() {
    std::vector<int> numbers = {30, 10, 20};
    
    std::sort(numbers.begin(), numbers.end()); // 오름차순 정렬
    
    for (int num : numbers) {
        std::cout << num << " ";
    }

    return 0;
}

 

이 예시에서는 std::sort 알고리즘을 사용해 numbers 벡터를 오름차순으로 정렬합니다. STL 알고리즘은 다양한 컨테이너에서 사용할 수 있으며, 이를 통해 코드의 가독성과 성능을 향상시킬 수 있습니다.

멀티스레드 환경에서의 주의점

대부분의 C++ 표준 컨테이너는 스레드 안전성을 제공하지 않으므로, 멀티스레드 환경에서 사용할 때는 외부에서 적절한 동기화가 필요합니다. 예를 들어, std::mutex와 같은 동기화 메커니즘을 사용하여 경쟁 조건을 방지해야 합니다.

결론

C++의 컨테이너는 데이터를 효율적으로 저장하고 관리할 수 있는 다양한 방법을 제공합니다. 각 컨테이너는 고유한 특성과 장단점을 가지고 있으며, 데이터 구조, 접근 방식, 성능 요구 사항에 따라 적절한 컨테이너를 선택하는 것이 중요합니다. 또한, STL 알고리즘과 결합하여 더 강력한 데이터 처리 기능을 구현할 수 있습니다.