stl 컨테이너 선택 기준

• vector
  • 랜덤 access
  • 현재 할당 사이즈를 넘을 경우 마다 복사 비용 발생
  • 중간 element 의 삭제,추가 시 비용 발생
  • reserve 사용 을 고려
  • iterator 가 삽입,삭제 중 정상유지 될수 없어 for 문 사용시 iterator 사용때 주의
• list
  • 연결리스트
  • 삽입
    • 굳이 중간에 넣어야 한다면 vector 보다 낫다
  • 조회
    • vector 가 낫다
• iterator 컨테이너의 삽입 삭제 동작 전후로도 항상 유지된다는 장점
• set
  • 정렬
  • 중복 불가능
  • unique element 관리에 사용
• map
  • 정렬
  • key, value
  • key 값은 바꿀 수 없다 당연히
  • 이진 트리
  • O(logn)
  • 비교적 빠른 검색
  • 비슷한 양상의 데이터가 순차 삽입 될 경우 비용 발생
    • 트리 재정렬이 필요해짐 (리밸런싱)
• unordered_map
  • hash table 기반
  • O(1) 검색
  • 빠른 검색
  • 삽입/검색 시 마다 해쉬 함수를 돌려야 하는 비용 발생
  • 많은 양의 element 일 경우 맵보다 해쉬 함수 비용보다 검색 비용이 좋아진다

• multi_xx
  • 동일 키에 element 중복가능

고정 사이즈로 사용되고 삽입이나 검색이슈가 없을 경우 일반 배열을 사용하는것도 나쁘지 않다.
– stack 에 할당되며 런타임 비용이 없기 때문