시퀀스 컨테이너

: 데이터가 선형적으로 저장되는 컨테이너

1. 벡터(Vector)

• 동적 배열 구조로, 런타임에 크기를 임의로 변경할 수 있다.

• 메모리에 데이터가 연속적으로 위치한다.

• 벡터는 포인터 세 개로 구현되어 있다.

  • 할당된 배열의 시작 주소를 가리키는 포인터
  • 다음에 데이터가 삽입될 위치를 가리키는 포인터
  • 할당된 배열의 끝 주소를 가리키는 포인터
    

• 데이터를 삽입하면 빨간 포인터가 가리키는 부분에 삽입되고, 빨간 포인터가 1 증가한다.

• 벡터의 메모리 할당 방식은 size(실제 사용 메모리 크기)와 capacity(여유분 포함 메모리 크기)로 이루어진다. (항상 size <= capacity)

  • 벡터에 데이터를 삽입할 때, 할당된 공간이 전부 차면 배열을 통째로 복사해 새로운 벡터에 할당하는 방식으로 메모리 크기를 늘린다. 때문에 벡터의 메모리를 적게 할당하고 계속 데이터를 늘릴 경우 복사 비용이 지속적으로 들어 비효율적이게 된다. 따라서 가급적 벡터의 size를 충분히 확보한 상태에서 사용하는 것이 좋다.

• 맨 끝이 아닌 중간 부분에서의 데이터 삽입 및 삭제는 비효율적이다. (삽입이나 삭제 위치 뒤의 모든 데이터를 한 칸씩 뒤로 밀거나 앞으로 당겨야 하기 때문)

• 특정 원소를 인덱스로 임의 접근(Random Access)이 가능.

2. 배열(Array)

• 벡터와 마찬가지로 메모리에 데이터가 연속적으로 위치한다.

• 배열은 연속된 메모리들의 첫 주소를 담는 포인터이다.

• 크기가 고정이기 때문에 처음 설정한 데이터의 크기를 넘어서 데이터를 저장할 수 없으므로 원소의 추가나 삭제가 불가능하다.

• 특정 원소를 인덱스로 임의 접근(Random Access)이 가능.

3. 리스트(List)

• 노드 기반 컨테이너이다.

• 이중 연결 리스트(Double Linked List)와 같은 형식으로 구현되어 있다.

  • 각 노드는 데이터 필드, 이전 노드와 다음 노드를 가리키는 링크 필드 2개로 구성된다.
    각각의 링크 필드는 다른 노드를 가리키는 포인터이다.

• 데이터가 메모리 상에 비연속적으로 저장된다.

• 임의 접근(Random Access)가 불가능하다.

• 중간 부분에서의 데이터 삭제가 벡터보다 효율적이다. (모든 데이터를 하나씩 밀거나 당길 필요 없이 링크 필드만 변경해주면 되기 때문)

연관 컨테이너

: Key - Value 구조를 가지는 컨테이너, 특정 기준에 따라 원소를 자동 정렬하는 컨테이너

1. 맵(Map)

• 각 노드가 key와 value의 쌍으로 이루어진 트리.

• 중복을 허용하지 않는다.

• map의 각 원소들은 pair 객체로 저장되는데, first가 key, second가 value로 저장된다.

• Red-Black Tree(자가 균형 이진 탐색 트리)로 구현되어 있다.

  • 이진 탐색 트리이기 때문에 (부모 노드의 왼쪽 < 부모 노드 < 부모노드의 오른쪽)

• 자료를 저장할 때 자동으로 key 값을 기준으로 오름차순 정렬한다.

  • 내림차순 정렬하려면 map<type1, type2, greater<type1>> 과 같이 선언
  • 자동 정렬하기 때문에 원소의 삽입이나 삭제가 빈번할 경우 성능 저하

• key를 통해 value에 접근

map<int, string> m;

m[1] = "ABC";
cout << m[1];

실행 결과 : ABC

2. unordered_map

• map과 다르게 값이 정렬되지 않고 랜덤하게 저장된다.

  • 자동으로 정렬하지 않기 때문에 정렬이 필요 없는 경우 사용하면 성능 향상이 가능하다.

• map과 다르게 Hash Table로 구현되어 있다.

  • 어떤 원소가 삽입될 때, 원소 값을 해시 함수에 넣어 1 ~ N(==해시 테이블의 크기) 중 특정 해시값을 반환해 삽입된 원소가 저장될 해시 테이블의 인덱스로 삼게 된다.
    • 1이라는 원소를 넣을 때 hashFunc(1) = 2 라면 Hash Table의 2번 인덱스에 저장된다.
    • 같은 원소를 해시 함수에 전달한다면 같은 해시값을 리턴하므로 원소의 탐색을 빠르게 수행할 수 있다.
  • 해시 함수는 해시값 계산을 상수 시간에 처리하기 때문에 unordered_map은 탐색을 상수 시간 0(1)에 처리할 수 있다.
    • 다만 해시 테이블의 크기가 원소 개수보다 적기 때문에 다른 원소이지만 같은 해시값을 가져 같은 해시 테이블에 저장되는 경우가 발생할 수 있다. (== 해시 충돌)
    • 위와 같은 경우 같은 상자 내에서 한 번 더 탐색을 거쳐야 한다. 운이 매우 나쁘다면 해시값이 겹치는 경우가 많이 발생해 O(N)의 탐색 시간이 걸릴 수도 있다.

• 많은 자료를 저장하고, 검색 속도가 빨라야 하는 경우에 사용하면 좋다. (자료양이 적을 때는 메모리 낭비 발생)

• 나머지는 map과 동일한 특징을 가진다.