해시 맵과 순서 순회

Question

저는 C++의 처음부터 완전한 기능을 갖춘 추상 데이터 형식으로 해시 맵을 구현하려고합니다. 특히, 식별 키의 오름차순으로 모든 레코드를 트래버스 할 수있는이 데이터 컨테이너에 대한 반복자를 제공하려고합니다. 그리고이 부분은 나를 혼란스럽게 만들고 어떻게해야할지 모르겠습니다. Btw, 해싱 기능에 의해 나는 단방향 목록과 별도의 연결을 사용하기로 결정했습니다. 한 가지 해결책은 모든 요소를 ​​적절한 순서로 바인딩하는 목록을 만드는 것입니다.이 목록은 삽입 프로세스 자체에서 보호됩니다. 그러나 적어도 삽입에 관해서는 해싱의 이점을 많이 손상시킬 것입니다. 특히 ADT의 목적을 살펴보면 트래버스 기능은 상대적으로 거의 사용되지 않습니다. 간단히 말해, 어떤 종류의 솔루션을 제공해야합니까? 전문 라이브러리는 사용할 수 없습니다.

참고 :

나는 해시 맵이 무엇인지 알고 있다는 그것의 격식을 중요시하는 정의에 의해 본질적으로 정렬되지 않은 것입니다. 어쩌면 내가 다르게 넣어야했는데, 기본적으로 해시 맵과 iterator 기능을 제공하는 추가 라이트 웨이트 모듈로 구성된 ADT를 구축하여 ADT 사용자가 키의 오름차순으로 레코드를 타임 아웃 할 수 있습니다.

Answer 1

해시 맵은 본질적으로 순서가 지정되지 않습니다. 그래서 C++에서는 일반적으로 unordered_map이라는 이름이 붙습니다. 해시 맵의 반복자는 각 멤버를 한 번 방문하지만 정의되지 않은 순서로 방문합니다.

실제로 해시 맵을 사용하지 않고 빨강 - 검정 트리와 같은 다른 연관 맵 컨테이너를 사용합니다. 또는 업데이트가 거의없는 경우 병렬 정렬 인덱스를 유지 관리합니다. 또는 업데이트가 빈번하지만 순회가 거의 발생하지 않는 경우 주문형 정렬 식 색인을 생성하십시오.

Answer 2

해시 맵은 본질적으로 정렬되지 않습니다. 전체 지점은 값을 저장할 위치를 알기 위해 해시를 사용하기 때문입니다.

내가 볼 수있는 유일한 방법은 해시가 항상 증가한다는 것을 보장하면 이 일 수 있습니다 (성능 및 실제 사용 편의성에서 약간의 비용이 발생할 수 있음). 즉, 해시는 삽입 순서의 함수이며 순서가 지정된 해시를 제공합니다. 이것은 충돌하는 해시를 처리합니다. 당신은 여전히 ​​아마이 그냥 생각

그렇지 않을 경우, 유일의 작동하지 않습니다 올바른 순서 양동이에서 목록을 통과해야하는, 그래서 그냥 목록을 유지하기위한 삽입 시간

에 분류 다른 방법은 모든 값을 정렬 친화적 인 구조에 저장하고 거기에서 반복하는 것입니다. hashmap 클래스에서이 작업을 수행하면 해시 맵을 반복 처리하는 것처럼 보이지만 실제로는 그렇지 않습니다. 순회 그냥 어떤 순서로 테이블을 복사, 매우 자주 발생하지 않을 경우

우리가 어떻게되는지 알려,이 기괴한 요구 사항