Chapter7 연관 컨테이너

연관 컨테이너

모든 연관 컨테이너는 노드 기반 컨테이너이며, 균형 이진 트리로 구현되어 있다.

• 모든 연관 컨테이너가 균형 이진트리의 모든 특징을 가진다.
• 모든 연관 컨테이너는 같은 인터페이스를 제공한다.

set 컨테이너

key라 불리는 원소의 집합

주요 특징

• insert(): 원소이자 key인 데이터 삽입 메소드
  • 데이터를 삽입하는 유일한 메소드이다.
  • 삽입되는 원소는 정렬 기준에 따라 자동 정렬된다.
  • 중복 삽입은 허용되지 않는다.
  • 반환값은 pair 객체이다.
    • first는 key의 위치를 가리키는 반복자
    • second는 성공 및 실패 bool 형식
  • insert(iter, data)
    • iter가 가리키는 위치부터 탐색을 시작하여 data를 삽입한다.
    • 삽입 위치가 정렬 순서와 맞다면 바로 삽입한다.
    • 정렬 순서와 다를 경우 log Complexity가 걸린다.
• 정렬 기준은 템플릿 매개변수에 지정이 가능함.
  • 기본 정렬 기준은 less 조건자이다.
• 시퀀스 컨테이너가 제공하는 순서 관련 메소드는 제공하지 않는다.
  • push_back(),push_front(),pop_back(),pop_front(), front(), back()
• 찾기/삽입/삭제 연산에 log Complexity로 수행한다.
• 반복자의 탐색 순서는 inorder 이진 트리 탐색을 사용한다.
• set의 조건자 반환 메소드
  • set은 key == value 이므로, 아래 메소드 타입도 같다.
  • key_comp()
    • 반환-> typedef 내장 멤버형식 key_compare
  • value_comp()
    • 반환-> typedef 내장 멤버형식 value_compare
• count(data): 원소의 개수를 반환하는 메소드
  • set은 중복을 허용하지 않으므로 해당 데이터의 수가 1개 뿐
  • 인터페이스를 맞춤으로 해당 메소드를 지원함
• find(data): 원소를 탐색하여 key를 가리키는 반복자를 반환한다.
  • 원소가 없을 경우 끝 표시 반복자를 반환한다.
  • 원소를 탐색할 때 ==연산을 수행하지 않는다.
    • less일 경우 < 연산을 수행한다.
    • 논리식에 의거 !(a<b)&&!(b<a) 로 데이터가 같음을 이해한다.
  • 순차열 구간
    • lower_bound와 upper_bound
      • lower_bound(): 찾은 원소의 시작 반복자를 반환
      • upper_bound(): 찾은 원소의 다음 원소를 가리키는 반복자
      • 찾은 원소는 [lower_bound(), upper_bound())로 표현 가능하다.
      • 원소를 찾지 못할경우 모두 순차열 끝 표시 반복자를 반환
      • lower_bound()와 upper_bound()가 같다면 원소가 없음을 의미한다.
    • equal_range
      • lower_bound()와 upper_bound()의 반복자 쌍을 pair 객체로 반환한다.

set 특징 정리

• 연관 컨테이너
  • 특정 정렬 기준에 의해 원소가 자동 정렬
• 노드 기반 컨테이너
• 균형 이진 트리로 구현됨
• 앞, 뒤 추가 및 제거 함수와 첫 원소, 마지막 원소 참조는 제공 안함
• 모든 연관 컨테이너의 key는 변경이 불가하다.

multiset 컨테이너

set과 모두 동일하나 중복 원소를 저장할 수 있음이 다름

주요 특징

• insert의 경우
  • 반환 값이 저장된 위치만을 가리키는 반복자를 반환함
• 순차열 구간과 관련된 메소드가 매우 유용하게 사용된다.

map 컨테이너

원소를 key와 value의 쌍(pair)으로 저장하고, key는 중복될 수 없다.

주요 특징

• map은 유일하게 [ ]연산자를 제공한다.
  • [ ]: key에 해당하는 원소의 value에 접근하여 변경 가능
  • key에 해당하는 원소가 있다면 갱신을 수행
  • key에 해당하는 원소가 없다면 추가 연산 수행
• insert(): pair 객체로 저장된다.
  • pair
    • first: key
    • second: value
  • set과 같이 반복자와 성공 여부의 bool 값을 pair 객체로 반환함

set과 인터페이스가 같으므로 해당 정리를 마친다.

multimap 컨테이너

map과 모두 동일하나 중복 key를 저장할 수 있다.
따라서, [ ] 연산자는 제공하지 않는다.

---

Quiz

1. 시퀀스 컨테이너와 연관 컨테이너의 가장 큰 차이점
   • 연관 컨테이너는 시퀀스 컨테이너와 다르게 정렬 기준을 가지고 데이터를 저장한다.

2. 연관 컨테이너의 기본 정렬 기준

   • less<>

3. set에 같은 원소를 저장하면

   • 반환 값으로 pair객체가 나오는데, first에는 원소의 저장 위치 반복자, second에는 실패(false)가 저장되어 있다.

4. multiset에 같은 원소를 저장하면

   • 반환 값으로 해당 저장 위치를 가지는 반복자가 반환됨

5. set과 map의 차이

   • set은 key == value이므로 원소가 곧 key이다.
   • map은 key, value 쌍으로 저장되며, [ ]로 접근이 가능하다.

6. 연관 컨테이너의 lower_bound()와 upper_bound()의 반환값

   • lower_bound(): 찾은 원소의 시작 반복자
   • upper_bound(): 찾은 원소의 다음 반복자
   • 원소를 찾지 못할경우 모두 순차열 끝 표시 반복자를 반환

7. 시퀀스 컨테이너의 insert()와 연관 컨테이너의 insert()의 차이점

   • 시퀀스 컨테이너: 반복자를 통해 원하는 위치에 데이터를 삽입이 가능
   • 연관 컨테이너: 삽입한 데이터가 자동으로 정렬됨

8. 연관 컨테이너의 찾기 관련 함수의 검색 성능

   • 로그 시간