C++ 컨테이너 클래스

목차

• [[#vector|vector]]
• [[#array|array]]
• [[#List|List]]
• [[#Deque|Deque]]
• [[#Set|Set]]
• [[#Map|Map]]
• [[#컨테이너 어댑터|컨테이너 어댑터]]

@주의 : 기본적으로 컨테이너는 객체 로 얇은 복사(shallow copy)

vector

• 동적 배열 사용

• 주요 동작 방식

  • 동적 크기 조정: 벡터의 크기가 증가하면, 현재 배열의 두 배 크기의 새로운 메모리 블록을 할당하고 기존 데이터를 새로운 블록으로 복사합니다. <- 지수적 크기 증가방식 사용
  • 상수 시간 접근: 연속된 메모리 블록을 사용하므로, 임의의 위치에 있는 요소에 대한 접근은 상수 시간($O(1)$)이 소요됩니다.
  • 배열과 유사한 성능: 벡터는 일반 배열처럼 작동하지만, 크기가 동적으로 조정된다는 점에서 배열과 다릅니다.
  • 효율적인 삽입 및 삭제: 벡터의 끝 부분에서 삽입 및 삭제는 평균적으로 상수 시간($O(1)$)이 소요됩니다. 하지만, 중간이나 시작 부분에서의 삽입 및 삭제는 이동 작업이 필요하기 때문에 선형 시간($O(n)$)이 소요됩니다.

• 수동 메모리해제

    vec.clear(); // 벡터의 모든 요소 제거
    vec.shrink_to_fit(); // 벡터의 용량을 현재 크기로 줄임

array

• vector의 생성, 소멸 성능이슈로 만들어진 클래스
• 동적 크기 변경 기능 x
• 정적 크기:
  • 배열 크기는 컴파일 타임에 고정되어야 합니다. 런타임에 크기를 변경할 수 없습니다.
• STL 호환:
  • 범위 기반 for 루프, STL 알고리즘, 이터레이터 등이 지원됩니다.
• 추가 메서드 제공:
  • 배열의 크기 확인(.size()), 요소에 안전하게 접근(.at()), 내부 데이터 접근(.data()) 등을 지원합니다.
• C 스타일 배열과 호환:
  • 기존 C 배열처럼 사용할 수 있으며, .data()를 통해 포인터로 변환 가능합니다.

List

• 이중 연결 리스트:
  • 각 요소는 앞뒤로 연결된 노드를 가지며, 양방향으로 순회가 가능합니다.
  • 삽입과 삭제가 O(1)의 시간 복잡도를 가집니다(특정 위치에서).
• 임의 접근(random access)이 불가능:
  • 인덱스를 통한 접근(list[i])을 지원하지 않으며, 순차적으로 순회해야 합니다.
  • 따라서, O(N)의 시간 복잡도로 특정 위치의 요소를 검색합니다.
• 효율적인 삽입 및 삭제:
  • 배열(vector)처럼 요소를 이동시키지 않고, 포인터만 변경하므로 삽입/삭제가 매우 빠릅니다.
  • 특히, 중간 위치에서의 삽입/삭제가 빈번할 때 적합합니다.

Deque

• 양방향 삽입/삭제:
  • 양쪽 끝(프론트와 백)에서 요소를 삽입하거나 삭제할 수 있습니다.
  • 이는 std::vector와의 주요 차이점 중 하나입니다.
• 연속적 메모리 할당은 아님:
  • std::deque는 내부적으로 연속적 메모리 블록으로 구성되지 않습니다.
  • 대신 여러 개의 고정 크기 메모리 블록을 연결하여 요소를 저장합니다.
  • 따라서 중간에 메모리를 이동시키지 않고도 삽입/삭제가 가능합니다.
• 임의 접근 지원:
  • std::vector와 마찬가지로, [] 연산자 및 .at() 메서드를 사용하여 O(1) 시간 복잡도로 임의 요소에 접근할 수 있습니다.
• 범용성과 성능:
  • std::deque는 양 끝 삽입/삭제가 빈번한 경우에 적합합니다.
  • 하지만 중간에 삽입/삭제가 빈번하다면 std::list가 더 적합할 수 있습니다.

Set

• 내부적으로 이진 검색 트리(BST, 보통 Red-Black Tree)로 구현
• 자동 정렬:
  • 요소는 삽입될 때 자동으로 정렬됩니다(기본적으로 오름차순).
• 중복 방지:
  • 같은 값을 여러 번 삽입하려고 하면 하나의 값만 저장됩니다.
• 탐색:
  • 이진 검색 트리를 기반으로 하여 O(log N)의 시간 복잡도로 탐색할 수 있습니다.
• multiset :
  • 중복 원소 허락
  • equal_range를 통해, 속하는 iterator범위를 얻을 수 있음
• unordered_set :
  • 삽입, 삭제, 검색이 O(1) 수행
    • 해시 함수 사용

Map

• 키-값 쌍(key-value pair)을 저장하는 연관 컨테이너입니다.
• 키는 유일해야 하며, 각 키에 대해 하나의 값이 매핑됩니다.
• 내부적으로 std::set처럼 이진 검색 트리(BST)를 사용합니다.
• 정렬된 저장:
  • std::map의 모든 키는 자동으로 정렬됩니다.
• 키를 통한 빠른 검색:
  • 특정 키를 사용해 O(log N)의 시간 복잡도로 값을 검색할 수 있습니다.
• 중복된 키 금지:
  • 동일한 키를 두 번 삽입하면 덮어쓰기
• multimap :
  • 중복 원소 허락
  • equal_range를 통해, 속하는 iterator범위를 얻을 수 있음
• unordered_map :
  • 삽입, 삭제, 검색이 O(1) 수행
    • 해시 함수 사용
    • 최악의 경우 O(n)

컨테이너 어댑터

• C++ STL에서 제공되는 일련의 템플릿 클래스
• 기존의 순차 컨테이너(vector, list 등)을 기반으로 한 새로운 인터페이스 제공, 특정 자료 구조의 특성 구현 도움
• 대표 컨테이너 어뎁터 : 스택, 큐, 우선 순위 큐

컨테이너 분류 표

분류	컨테이너	설명
순차 컨테이너	vector, deque, list, forward_list, array	- 순서대로 요소를 저장합니다. - 배열이나 연결 리스트 형태로 구현됩니다.
연관 컨테이너	map, multimap, set, multiset	- 키와 값으로 데이터를 저장하거나 정렬된 데이터를 관리합니다. - 요소들이 자동으로 정렬됩니다.
비정렬 연관 컨테이너	unordered_map, unordered_multimap, unordered_set, unordered_multiset	- 정렬되지 않은 데이터를 관리합니다. - 해시 테이블 기반으로 빠른 검색을 지원합니다.
컨테이너 어댑터	stack, queue, priority_queue	- 기존 컨테이너를 기반으로 특수한 동작(스택, 큐, 우선순위 큐 등)을 제공합니다. - 기본적으로 deque가 내부 컨테이너로 사용됩니다.