목록과 멀티 세트의 차이점은 무엇입니까?

Question

필자의 이해에서,리스트와 다중 세트는 값이 여러 번 발생할 수있는 정렬 된 값의 집합입니다. 어떤 차이가 있습니까?

Answer 1

아니요, 목록 및 다중 세트가 다릅니다. 목록에서 중요한 사항을 주문하고 멀티 세트에는 포함되지 않습니다.

(list 1 2 3 2) != (list 2 1 3 2) 
(multiset 1 2 2 3) == (multiset 1 3 2 2) 

Answer 2

주문 외에도 각 컨테이너에는 고유 한 사용 가능한 방법 세트와 그 복잡성이 있습니다. 예를 들어 목록에서 검색하는 경우 o(n)입니다 (검색 할 때까지 모든 요소를 ​​확인해야합니다). multiset에있는 검색은 o(log(n))입니다. 이 요구 사항을 충족시키기 위해 일반적으로 빨강 - 검정 나무로 구현됩니다.