[Mastering C++ Programming] - Associative Containers

• associative container는 sequence container와 달리 정렬된 방식으로 데이터를 저장합니다. 
• 따라서 데이터가 삽입되는 순서는 associative container에 의해 유지되지 않습니다!!. 
• 연관 컨테이너는 O(logn) runtime complexity가 있는 값을 검색하는 데 매우 효율적입니다. 
• 새 값이 컨테이너에 추가될 때마다 컨테이너는 필요한 경우 내부에 저장된 값을 재정렬합니다.

• STL은 다음 유형의 연관 컨테이너를 지원합니다.
  
  • Set
  • Map
  • Multiset 
  • Multimap
  • Unordered set
  • Unordered multiset
  • Unordered map
  • Unordered multimap

 

• associative 데이터를 key-value 쌍으로 구성합니다. 
• 데이터는 random-access를 위해 키를 기준으로 정렬됩니다. 

 

• 연관 컨테이너는 두 가지 유형이 있습니다.
  • Ordered
    
    • 정렬되지 않음
    • 다음 연관 컨테이너는 특정 방식으로 정렬/정렬되므로 정렬된 컨테이너 아래에 있습니다. 정렬된 연관 컨테이너는 일반적으로 BST(Binary Search Tree) 형식을 사용합니다. 일반적으로 레드-블랙 트리는 데이터를 저장하는 데 사용됩니다.
      • set
      • map
      • Multiset
      • Multimap
  • UnOrdered
    • 다음 연관 컨테이너는 특정 방식으로 정렬되지 않고 해시 테이블을 사용하므로 정렬되지 않은 컨테이너에 속합니다.
      • Unordered Set
      • Unordered Map
      • Unordered Multiset
      • Unordered Multimap