Java의 priority queue은 put (삽입)에 대해 O(log n) 복잡도, min (최소 요소 검색 및 제거)에 대해 O(log n) 인 데이터 구조입니다.Java 우선 순위 큐
C++ STL의 multimap은 min 요소 (시작 및 지우기)를 검색하고 제거하기 위해 동일한 기능을하지만 O(1) 복잡도를 가지고 있습니다. Java에 상응하는 것이 있습니까?
Google Collections은 Multimap 구현을 제공합니다. 특히 TreeMultimap은 비교자를 사용하여 키, 값 또는 둘 모두를 기반으로 정렬 할 수 있습니다.
Google 멀티 맵은 키 주문을 지원하지 않습니다. C++ 용으로 암시 된 것입니까? –
TreeMultimap – Mark
Apache Commons Collections을 시도해보십시오.
MultiHashMap 및 MultiValueMap (해당 페이지에서 링크 됨)이 실제로 인터페이스를 구현합니다.
실제적으로 Priority Queue도 있지만, buffer package에 찬성하여 가치가 하락합니다.
std:multimap은 추가 및 제거가 모두 O (log n)가되는 트리 구조입니다.
추가 및 제거를 참조하도록 내 대답을 업데이트했습니다 O (1) amortized 있습니다. –
해시 구조의 경우 O (1)입니다. 하지만 나무 때문에? –
먼저, C++의 멀티 맵이 실제로 에 대해 O (1)을 지정했는지 확인합니다. 최소 요소를 제거합니다. 소트 된 맵/우선 순위 큐의 가장 일반적인 구조는 쿼리 요소의 최소 요소가 O (1) 복잡성이지만 을 제거하는 트리 구조입니다.은 O (log n)입니다. 말했다
, 나는 (자바의 ConcurrentSkipListMap과에 의해 구현 된) 스킵 목록 당신은 O (1) 최소의 요소의 제거를 위해 줄 수 있다는 생각하지만, 나는 절대적으로 확실하지 않다. ConcurrentSkipListMap의 성능을 평가할 때의 문제점 중 하나는 탐색 연산이 이전의 삭제에 의해 남겨진 마커를 "정돈"한다는 것입니다. 따라서 작업의 복잡성은 실제로 이전 작업이 무엇인지에 달려 있습니다. (다른 한편으로, 어느 정도는 어떤 알고리즘이라도 사실입니다 : 어떤 데이터가 CPU 캐시에 있는지 여부는 이전 작업이 거기에 놓여 있는지 여부에 달려 있습니다 ...)P.S. 말하는 것을 잊어 버렸습니다 : ConcurrentSkipListMap.pollFirstEntry()에서보세요.
멀티 맵의 지우기 (iterator x)는 상수로 상각되므로, 그렇습니다. priority_queue의 pop은 O (log N)입니다. –
그렉 - 그들이 어떤 구조를 사용하는지 알고 있습니까? –
대기열이 멀티 맵일 수있는 방법을 설명해 주시겠습니까? 첫 번째 매개 변수에는 하나의 유형 매개 변수가 있고 두 번째 매개 변수에는 두 개의 매개 변수가 있습니다. –
두 번째 유형 매개 변수로 Void를 사용 하시겠습니까? –
priority_queue를 사용하는 경우 유형에 사용자 정의 연산자 <를 사용해야합니다. 보세요. http://www.google.com/codesearch/p?hl=ko#GBlGDoDYBC4/Maude-2.2/src/ObjectSystem/pseudoThread.hh&q=priority_queue –