3
즉, unordered_map 또는 unordered_set 두 개를 채우는 경우 정확히 동일한 내용과 동일한 해싱 함수를 가진 객체는 반복되는 키/값 쌍 시퀀스를 제공합니까?두 개의 동일한 unordered_maps의 순서가 동일합니까?
그렇다면이 조건을 유지하는 조건 (예 : 동일한 해시 함수, 동일한 키, 반드시 동일한 값이 아님)은 무엇입니까?
A
답변
5
번호 일반적입니다. 사실, 일반적으로 액세스 할 수있는 유일한 정보는 해시 값이기 때문에 순서가 지정되지 않은지도는이 작업을 수행하는 것이 불가능합니다.
+1
동일한 키를 가진 항목을 동일한 순서로 같은 크기의 컨테이너에 추가하면 (즉, '예약'또는 그 밖의 다른 항목을 사용하지 않는 경우), 어떻게 다르게 주문할 수 있습니까? –
+0
그래, 그래서 .. 그게 내가 물어 보는거야. 실제로 지정되지 않았지만 실제로는 실제로 지정되어 있습니다. :) – pms
+3
@SethCarnegie : 우선, OP는 그들이 같은 순서로 추가 될 것이라고 말하지 않았다. 둘째, 무엇이든지 다르게 명령을 내릴 수 있습니다. 필요에 따라 구현을 무작위로 배열하거나 가장 자주 액세스하는 객체를 먼저 해시 체인에 배치 할 수 있습니다. –
3
이 경우의 동작은 정의되지 않습니다. 그래서 어떤 상황에서는 그 순서가 동일 할 것이고, 다른 경우에는 다를 것입니다. 당신은 아무것도 확신 할 수 없습니다. 귀하가 언급 한 유형의 이름은 이며, 우연이 아닌입니다. 그것들을 주문한 것들로 사용하는 것은 매우 위험하고 매우 위험한 스타일입니다.
컴파일러는 사용하려는 특별한 방법으로 작동합니다. 그러나 당신은 확신 할 수 없습니다. 당신은 확실하지 않아야합니다! 당신은 어떤 조건이 컴파일러의 그러한 행동을 일으키는 지 모른다. 컴파일러 버전을 변경해도 필요한 동작이 변경되지 않는다는 것을 확신 할 수 없습니다.
C/C++에서 다른 언어로 단순히 금지 된 것은 지정되지 않습니다. 그러나 당신도 그것을 금지 된 것으로 받아 들여야합니다.
봐 c-faq about the problem of undefined behavior이 개념은 어떤 요구 사항이 동일한 해시를 가진 객체가 특정 순서로 배치하는 것이, 예를 들어,이 없습니다 모든 C/C++
+0
그래 ..하지만 내가 읽을 수있는 [여기] (http://stackoverflow.com/questions/3176621/c-is-the-unordered-map-really-unordered) 그것은 가능한 것 같습니다 ... – pms
+3
일어날 수 있습니다. 그러나 그렇게하지 않는 것이 가능합니다. C/C++에서 다른 언어로 단순히 금지 된 것은 지정되지 않습니다. 그러나 당신도 그것을 금지 된 것으로 받아 들여야합니다. – Gangnus
+1
@pms : "정렬되지 않은"이란 의미는 "신뢰할 수없는 순서"입니다. 이는 * C++ 사양 *이 주문을 정의하지 않음을 의미합니다. 'std :: unordered_ * '의 구현은 실제로 일관된 순서를 가질 수 있습니다. 그러나 사양은 이것을 시행하지 않습니다. 반면에 그것은'std :: map'에 특정한 순서를 적용합니다. 따라서 코드를 이식 가능하게 만들려면 주문에 의존 할 수 없습니다. –
2
음 제 I은 MSDN 인용한다 :
제어 시퀀스의 요소의 실제 순서는 해시 기능, 비교 기능, 삽입의 순서, 최대 하중 인자 및 현재 번호에 따라버킷의. 일반적으로 제어 된 순서로 요소의 순서를 예측할 수는 없습니다. 그러나 동일한 순서가있는 요소의 하위 집합은 제어 된 순서로 인접 해 있음을 항상 확신 할 수 있습니다.
위의 인용
는unordered_map 및
unordered_set에 대해 동일하고 이름으로하지만, 그들이 해당하는 키가 인접 언급 않는 순서가 지정되어 있지 않은 것을 의미한다.
+1
그게 MS의 구현을위한 것 같아요? 아니면 표준의 요구 사항입니까? 그것은 충돌을 위해 선형 프로빙을 사용하도록 구현을 강제 할 것입니다 (또는 간접 동적 배열의 각 요소를 저장하는 것). –
+1
@SethCarnegie : 필수 항목 인 것 같습니다. [여기]에 대한 토론을 찾았습니다 (https://groups.google.com/group/comp.std.c++/tree/browse_frm/month/2006-11/19fc7cb847e9127b?rnum). = 1 & _done =/group/comp.std.c % 2B % 2B/browse_frm/month/2006-11? & hl = pt) (체크 포스트 6). –
0
보증 된 주문이 필요하면 이 아니며 데이터 구조가입니다. 사실, 주로 반복 작업을 수행하려는 경우 unordered_map/set이 데이터 구조체가 아닙니다.
반복의 경우 한 노드에서 다음 노드까지의 gonig가 알고리즘 적으로 덜 복잡하기 때문에 std::map이 더 나은 데이터 구조로 나타납니다. std::map에있는 객체의 반복 순서는 사양에 의해 보장되는이며 실제로 구조 자체의 정의 속성입니다. (이것은 분명히 동일한 비교 연산자를 사용한다고 가정합니다.) std::map에는 해싱이 없습니다.
당신이 틀린 나무를 여기에서 짖고있는 것처럼 그것은 말하기 충분하다. unordered_map은 일반적으로 O (1) 조회와 같은 이점을 위해 사용되어야하며 오브젝트 목록을 저장하지 않고 반복해야합니다. 그것은 가장 확실하게은 반복의 결정 론적 순서를 얻으려는 경우 사용하지 말아야합니다.
당신이 생각하고있는 해시 함수는 실제로 사용되는 최종 해시 함수가 아닙니다. 버킷 크기는 동적으로 변경 될 수 있으며 실제 해시 함수는 해시 함수에서 파생됩니다 (아마도 일부 모듈러 산술 방식으로). –