Does std::unordered_map equality depend on insertion order
Clash Royale CLAN TAG#URR8PPP
up vote
23
down vote
favorite
If you create two std::unordered_map
containers using the same set of (non equal) key-value pairs, but inserted in a different order (so the containers hold equal elements, but potentially in different orders), are the containers guaranteed to be equal, according to the equality operator (operator==
). I'm assuming that the hash-code and equality operators of the container elements satisfy all the required constraints on their implementation.
c++ unordered-map
 |Â
show 1 more comment
up vote
23
down vote
favorite
If you create two std::unordered_map
containers using the same set of (non equal) key-value pairs, but inserted in a different order (so the containers hold equal elements, but potentially in different orders), are the containers guaranteed to be equal, according to the equality operator (operator==
). I'm assuming that the hash-code and equality operators of the container elements satisfy all the required constraints on their implementation.
c++ unordered-map
Have you tried it? Also, that guarantee would follow from the according ISO standard, so that indirectly contain the answer.
â Ulrich Eckhardt
yesterday
@UlrichEckhardt I've tried, and the answer seems to be "yes, it depends on insertion order", but I'm not sure whether that is because I've made a mistake.
â Raedwald
yesterday
No. (This space intentionally left blank)
â n.m.
yesterday
Sample code showing equality of all permutations of insertion sequences for a map of 4 pairs<char, string>
â KarlM
yesterday
1
@UlrichEckhardt "Have you tried it" can't tell you whether "it doesn't depend on insertion order" is a feature of this implementation, or is guaranteed for all C++ implementations. (I suppose it can tell you that "it does depend on insertion order" - but all the answers below show that that would be a bug in the implementation.)
â Martin Bonner
19 hours ago
 |Â
show 1 more comment
up vote
23
down vote
favorite
up vote
23
down vote
favorite
If you create two std::unordered_map
containers using the same set of (non equal) key-value pairs, but inserted in a different order (so the containers hold equal elements, but potentially in different orders), are the containers guaranteed to be equal, according to the equality operator (operator==
). I'm assuming that the hash-code and equality operators of the container elements satisfy all the required constraints on their implementation.
c++ unordered-map
If you create two std::unordered_map
containers using the same set of (non equal) key-value pairs, but inserted in a different order (so the containers hold equal elements, but potentially in different orders), are the containers guaranteed to be equal, according to the equality operator (operator==
). I'm assuming that the hash-code and equality operators of the container elements satisfy all the required constraints on their implementation.
c++ unordered-map
edited yesterday
Baum mit Augen
39.1k12109141
39.1k12109141
asked yesterday
Raedwald
24.4k2188146
24.4k2188146
Have you tried it? Also, that guarantee would follow from the according ISO standard, so that indirectly contain the answer.
â Ulrich Eckhardt
yesterday
@UlrichEckhardt I've tried, and the answer seems to be "yes, it depends on insertion order", but I'm not sure whether that is because I've made a mistake.
â Raedwald
yesterday
No. (This space intentionally left blank)
â n.m.
yesterday
Sample code showing equality of all permutations of insertion sequences for a map of 4 pairs<char, string>
â KarlM
yesterday
1
@UlrichEckhardt "Have you tried it" can't tell you whether "it doesn't depend on insertion order" is a feature of this implementation, or is guaranteed for all C++ implementations. (I suppose it can tell you that "it does depend on insertion order" - but all the answers below show that that would be a bug in the implementation.)
â Martin Bonner
19 hours ago
 |Â
show 1 more comment
Have you tried it? Also, that guarantee would follow from the according ISO standard, so that indirectly contain the answer.
â Ulrich Eckhardt
yesterday
@UlrichEckhardt I've tried, and the answer seems to be "yes, it depends on insertion order", but I'm not sure whether that is because I've made a mistake.
â Raedwald
yesterday
No. (This space intentionally left blank)
â n.m.
yesterday
Sample code showing equality of all permutations of insertion sequences for a map of 4 pairs<char, string>
â KarlM
yesterday
1
@UlrichEckhardt "Have you tried it" can't tell you whether "it doesn't depend on insertion order" is a feature of this implementation, or is guaranteed for all C++ implementations. (I suppose it can tell you that "it does depend on insertion order" - but all the answers below show that that would be a bug in the implementation.)
â Martin Bonner
19 hours ago
Have you tried it? Also, that guarantee would follow from the according ISO standard, so that indirectly contain the answer.
â Ulrich Eckhardt
yesterday
Have you tried it? Also, that guarantee would follow from the according ISO standard, so that indirectly contain the answer.
â Ulrich Eckhardt
yesterday
@UlrichEckhardt I've tried, and the answer seems to be "yes, it depends on insertion order", but I'm not sure whether that is because I've made a mistake.
â Raedwald
yesterday
@UlrichEckhardt I've tried, and the answer seems to be "yes, it depends on insertion order", but I'm not sure whether that is because I've made a mistake.
â Raedwald
yesterday
No. (This space intentionally left blank)
â n.m.
yesterday
No. (This space intentionally left blank)
â n.m.
yesterday
Sample code showing equality of all permutations of insertion sequences for a map of 4 pairs<char, string>
â KarlM
yesterday
Sample code showing equality of all permutations of insertion sequences for a map of 4 pairs<char, string>
â KarlM
yesterday
1
1
@UlrichEckhardt "Have you tried it" can't tell you whether "it doesn't depend on insertion order" is a feature of this implementation, or is guaranteed for all C++ implementations. (I suppose it can tell you that "it does depend on insertion order" - but all the answers below show that that would be a bug in the implementation.)
â Martin Bonner
19 hours ago
@UlrichEckhardt "Have you tried it" can't tell you whether "it doesn't depend on insertion order" is a feature of this implementation, or is guaranteed for all C++ implementations. (I suppose it can tell you that "it does depend on insertion order" - but all the answers below show that that would be a bug in the implementation.)
â Martin Bonner
19 hours ago
 |Â
show 1 more comment
3 Answers
3
active
oldest
votes
up vote
26
down vote
accepted
Yes, they're guaranteed to return equal in this case. The specific wording (from N4659, ç[unord.req]/12) is:
Two unordered containers
a
andb
compare equal ifa.size() == b.size()
and, for every equivalent-key group[Ea1, Ea2)
obtained froma.equal_range(Ea1)
, there exists an equivalent-key group[Eb1, Eb2)
obtained fromb.equal_range(Ea1)
, such thatis_permutation(Ea1, Ea2, Eb1, Eb2)
returnstrue
.
So, as long as the keys in one are the same as the other (but possibly in a differently-permuted order), it will compare equal.
Nice. Any idea how it is implemented? I can see a pure hash table implementing this is in O(n log n), (i.e. collect the keys, sort them by their hash, check the values) but maybe there's better
â Ant
17 hours ago
@Ant Normally it is implemented as a balanced binary search tree, like red-black tree.
â hgminh
17 hours ago
@hgminh I meant, how is the equality comparison algorithm implemented (granted, it most likely depends on the underlying structure)
â Ant
16 hours ago
1
@hgm -- Red black tree? This question concerns unordered maps, not (ordered) maps.
â David Hammen
13 hours ago
1
@Ant: Unordered containers are hash tables, so they start out with all they keys that hashed to the same value in the same bucket. I'd expect they'd actually usestd::is_permutation
to check for keys in the same bucket. That can be O(n).
â Jerry Coffin
13 hours ago
 |Â
show 3 more comments
up vote
13
down vote
From [unord.red]/12
Two unordered containers
a
andb
compare equal ifa.size() == b.size()
and, for every equivalent-key group[Ea1, Ea2)
obtained froma.equal_ÃÂrange(Ea1)
, there exists an equivalent-key group[Eb1, Eb2)
obtained fromb.equal_ÃÂrange(Ea1)
, such thatis_ÃÂpermutation(Ea1, Ea2, Eb1, Eb2)
returnstrue
. [...]
So, as long as the keys are the same and the size is the same the containers will compare equal no matter what order the keys are in.
add a comment |Â
up vote
3
down vote
Below are quotes from cppreference.com about the std:unordered_map, operator==,!=(std::unordered_map):
The contents of two unordered containers lhs and rhs are equal if the following conditions hold:
- lhs.size() == rhs.size()
- each group of equivalent elements [lhs_eq1, lhs_eq2) obtained from lhs.equal_range(lhs_eq1) has a corresponding group of equivalent elements in the other container [rhs_eq1, rhs_eq2) obtained from rhs.equal_range(rhs_eq1), that has the following properties:
- std::distance(lhs_eq1, lhs_eq2) == std::distance(rhs_eq1, rhs_eq2).
- std::is_permutation(lhs_eq1, lhs_eq2, rhs_eq1) == true.
Note that:
The behavior is undefined if Key or T are not EqualityComparable.
The behavior is also undefined if Hash and KeyEqual do (until C++20)KeyEqual does (since C++20) not have the same behavior on lhs and rhs or if operator== for Key is not a refinement of the partition into equivalent-key groups introduced by KeyEqual (that is, if two elements that compare equal using operator== fall into different partitions)
Finally, to consider is the complexity:
Proportional to N calls to operator== on value_type, calls to the predicate returned by key_eq, and calls to the hasher returned by hash_function, in the average case, proportional to N2 in the worst case where N is the size of the container.
Therefore, if both unordered maps have the same size, and each key in one of the containers is looked for in the other plus, if it happens to be found then their values are compared then they are the considered the same.
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
26
down vote
accepted
Yes, they're guaranteed to return equal in this case. The specific wording (from N4659, ç[unord.req]/12) is:
Two unordered containers
a
andb
compare equal ifa.size() == b.size()
and, for every equivalent-key group[Ea1, Ea2)
obtained froma.equal_range(Ea1)
, there exists an equivalent-key group[Eb1, Eb2)
obtained fromb.equal_range(Ea1)
, such thatis_permutation(Ea1, Ea2, Eb1, Eb2)
returnstrue
.
So, as long as the keys in one are the same as the other (but possibly in a differently-permuted order), it will compare equal.
Nice. Any idea how it is implemented? I can see a pure hash table implementing this is in O(n log n), (i.e. collect the keys, sort them by their hash, check the values) but maybe there's better
â Ant
17 hours ago
@Ant Normally it is implemented as a balanced binary search tree, like red-black tree.
â hgminh
17 hours ago
@hgminh I meant, how is the equality comparison algorithm implemented (granted, it most likely depends on the underlying structure)
â Ant
16 hours ago
1
@hgm -- Red black tree? This question concerns unordered maps, not (ordered) maps.
â David Hammen
13 hours ago
1
@Ant: Unordered containers are hash tables, so they start out with all they keys that hashed to the same value in the same bucket. I'd expect they'd actually usestd::is_permutation
to check for keys in the same bucket. That can be O(n).
â Jerry Coffin
13 hours ago
 |Â
show 3 more comments
up vote
26
down vote
accepted
Yes, they're guaranteed to return equal in this case. The specific wording (from N4659, ç[unord.req]/12) is:
Two unordered containers
a
andb
compare equal ifa.size() == b.size()
and, for every equivalent-key group[Ea1, Ea2)
obtained froma.equal_range(Ea1)
, there exists an equivalent-key group[Eb1, Eb2)
obtained fromb.equal_range(Ea1)
, such thatis_permutation(Ea1, Ea2, Eb1, Eb2)
returnstrue
.
So, as long as the keys in one are the same as the other (but possibly in a differently-permuted order), it will compare equal.
Nice. Any idea how it is implemented? I can see a pure hash table implementing this is in O(n log n), (i.e. collect the keys, sort them by their hash, check the values) but maybe there's better
â Ant
17 hours ago
@Ant Normally it is implemented as a balanced binary search tree, like red-black tree.
â hgminh
17 hours ago
@hgminh I meant, how is the equality comparison algorithm implemented (granted, it most likely depends on the underlying structure)
â Ant
16 hours ago
1
@hgm -- Red black tree? This question concerns unordered maps, not (ordered) maps.
â David Hammen
13 hours ago
1
@Ant: Unordered containers are hash tables, so they start out with all they keys that hashed to the same value in the same bucket. I'd expect they'd actually usestd::is_permutation
to check for keys in the same bucket. That can be O(n).
â Jerry Coffin
13 hours ago
 |Â
show 3 more comments
up vote
26
down vote
accepted
up vote
26
down vote
accepted
Yes, they're guaranteed to return equal in this case. The specific wording (from N4659, ç[unord.req]/12) is:
Two unordered containers
a
andb
compare equal ifa.size() == b.size()
and, for every equivalent-key group[Ea1, Ea2)
obtained froma.equal_range(Ea1)
, there exists an equivalent-key group[Eb1, Eb2)
obtained fromb.equal_range(Ea1)
, such thatis_permutation(Ea1, Ea2, Eb1, Eb2)
returnstrue
.
So, as long as the keys in one are the same as the other (but possibly in a differently-permuted order), it will compare equal.
Yes, they're guaranteed to return equal in this case. The specific wording (from N4659, ç[unord.req]/12) is:
Two unordered containers
a
andb
compare equal ifa.size() == b.size()
and, for every equivalent-key group[Ea1, Ea2)
obtained froma.equal_range(Ea1)
, there exists an equivalent-key group[Eb1, Eb2)
obtained fromb.equal_range(Ea1)
, such thatis_permutation(Ea1, Ea2, Eb1, Eb2)
returnstrue
.
So, as long as the keys in one are the same as the other (but possibly in a differently-permuted order), it will compare equal.
answered yesterday
Jerry Coffin
373k42439876
373k42439876
Nice. Any idea how it is implemented? I can see a pure hash table implementing this is in O(n log n), (i.e. collect the keys, sort them by their hash, check the values) but maybe there's better
â Ant
17 hours ago
@Ant Normally it is implemented as a balanced binary search tree, like red-black tree.
â hgminh
17 hours ago
@hgminh I meant, how is the equality comparison algorithm implemented (granted, it most likely depends on the underlying structure)
â Ant
16 hours ago
1
@hgm -- Red black tree? This question concerns unordered maps, not (ordered) maps.
â David Hammen
13 hours ago
1
@Ant: Unordered containers are hash tables, so they start out with all they keys that hashed to the same value in the same bucket. I'd expect they'd actually usestd::is_permutation
to check for keys in the same bucket. That can be O(n).
â Jerry Coffin
13 hours ago
 |Â
show 3 more comments
Nice. Any idea how it is implemented? I can see a pure hash table implementing this is in O(n log n), (i.e. collect the keys, sort them by their hash, check the values) but maybe there's better
â Ant
17 hours ago
@Ant Normally it is implemented as a balanced binary search tree, like red-black tree.
â hgminh
17 hours ago
@hgminh I meant, how is the equality comparison algorithm implemented (granted, it most likely depends on the underlying structure)
â Ant
16 hours ago
1
@hgm -- Red black tree? This question concerns unordered maps, not (ordered) maps.
â David Hammen
13 hours ago
1
@Ant: Unordered containers are hash tables, so they start out with all they keys that hashed to the same value in the same bucket. I'd expect they'd actually usestd::is_permutation
to check for keys in the same bucket. That can be O(n).
â Jerry Coffin
13 hours ago
Nice. Any idea how it is implemented? I can see a pure hash table implementing this is in O(n log n), (i.e. collect the keys, sort them by their hash, check the values) but maybe there's better
â Ant
17 hours ago
Nice. Any idea how it is implemented? I can see a pure hash table implementing this is in O(n log n), (i.e. collect the keys, sort them by their hash, check the values) but maybe there's better
â Ant
17 hours ago
@Ant Normally it is implemented as a balanced binary search tree, like red-black tree.
â hgminh
17 hours ago
@Ant Normally it is implemented as a balanced binary search tree, like red-black tree.
â hgminh
17 hours ago
@hgminh I meant, how is the equality comparison algorithm implemented (granted, it most likely depends on the underlying structure)
â Ant
16 hours ago
@hgminh I meant, how is the equality comparison algorithm implemented (granted, it most likely depends on the underlying structure)
â Ant
16 hours ago
1
1
@hgm -- Red black tree? This question concerns unordered maps, not (ordered) maps.
â David Hammen
13 hours ago
@hgm -- Red black tree? This question concerns unordered maps, not (ordered) maps.
â David Hammen
13 hours ago
1
1
@Ant: Unordered containers are hash tables, so they start out with all they keys that hashed to the same value in the same bucket. I'd expect they'd actually use
std::is_permutation
to check for keys in the same bucket. That can be O(n).â Jerry Coffin
13 hours ago
@Ant: Unordered containers are hash tables, so they start out with all they keys that hashed to the same value in the same bucket. I'd expect they'd actually use
std::is_permutation
to check for keys in the same bucket. That can be O(n).â Jerry Coffin
13 hours ago
 |Â
show 3 more comments
up vote
13
down vote
From [unord.red]/12
Two unordered containers
a
andb
compare equal ifa.size() == b.size()
and, for every equivalent-key group[Ea1, Ea2)
obtained froma.equal_ÃÂrange(Ea1)
, there exists an equivalent-key group[Eb1, Eb2)
obtained fromb.equal_ÃÂrange(Ea1)
, such thatis_ÃÂpermutation(Ea1, Ea2, Eb1, Eb2)
returnstrue
. [...]
So, as long as the keys are the same and the size is the same the containers will compare equal no matter what order the keys are in.
add a comment |Â
up vote
13
down vote
From [unord.red]/12
Two unordered containers
a
andb
compare equal ifa.size() == b.size()
and, for every equivalent-key group[Ea1, Ea2)
obtained froma.equal_ÃÂrange(Ea1)
, there exists an equivalent-key group[Eb1, Eb2)
obtained fromb.equal_ÃÂrange(Ea1)
, such thatis_ÃÂpermutation(Ea1, Ea2, Eb1, Eb2)
returnstrue
. [...]
So, as long as the keys are the same and the size is the same the containers will compare equal no matter what order the keys are in.
add a comment |Â
up vote
13
down vote
up vote
13
down vote
From [unord.red]/12
Two unordered containers
a
andb
compare equal ifa.size() == b.size()
and, for every equivalent-key group[Ea1, Ea2)
obtained froma.equal_ÃÂrange(Ea1)
, there exists an equivalent-key group[Eb1, Eb2)
obtained fromb.equal_ÃÂrange(Ea1)
, such thatis_ÃÂpermutation(Ea1, Ea2, Eb1, Eb2)
returnstrue
. [...]
So, as long as the keys are the same and the size is the same the containers will compare equal no matter what order the keys are in.
From [unord.red]/12
Two unordered containers
a
andb
compare equal ifa.size() == b.size()
and, for every equivalent-key group[Ea1, Ea2)
obtained froma.equal_ÃÂrange(Ea1)
, there exists an equivalent-key group[Eb1, Eb2)
obtained fromb.equal_ÃÂrange(Ea1)
, such thatis_ÃÂpermutation(Ea1, Ea2, Eb1, Eb2)
returnstrue
. [...]
So, as long as the keys are the same and the size is the same the containers will compare equal no matter what order the keys are in.
answered yesterday
NathanOliver
72.3k1599148
72.3k1599148
add a comment |Â
add a comment |Â
up vote
3
down vote
Below are quotes from cppreference.com about the std:unordered_map, operator==,!=(std::unordered_map):
The contents of two unordered containers lhs and rhs are equal if the following conditions hold:
- lhs.size() == rhs.size()
- each group of equivalent elements [lhs_eq1, lhs_eq2) obtained from lhs.equal_range(lhs_eq1) has a corresponding group of equivalent elements in the other container [rhs_eq1, rhs_eq2) obtained from rhs.equal_range(rhs_eq1), that has the following properties:
- std::distance(lhs_eq1, lhs_eq2) == std::distance(rhs_eq1, rhs_eq2).
- std::is_permutation(lhs_eq1, lhs_eq2, rhs_eq1) == true.
Note that:
The behavior is undefined if Key or T are not EqualityComparable.
The behavior is also undefined if Hash and KeyEqual do (until C++20)KeyEqual does (since C++20) not have the same behavior on lhs and rhs or if operator== for Key is not a refinement of the partition into equivalent-key groups introduced by KeyEqual (that is, if two elements that compare equal using operator== fall into different partitions)
Finally, to consider is the complexity:
Proportional to N calls to operator== on value_type, calls to the predicate returned by key_eq, and calls to the hasher returned by hash_function, in the average case, proportional to N2 in the worst case where N is the size of the container.
Therefore, if both unordered maps have the same size, and each key in one of the containers is looked for in the other plus, if it happens to be found then their values are compared then they are the considered the same.
add a comment |Â
up vote
3
down vote
Below are quotes from cppreference.com about the std:unordered_map, operator==,!=(std::unordered_map):
The contents of two unordered containers lhs and rhs are equal if the following conditions hold:
- lhs.size() == rhs.size()
- each group of equivalent elements [lhs_eq1, lhs_eq2) obtained from lhs.equal_range(lhs_eq1) has a corresponding group of equivalent elements in the other container [rhs_eq1, rhs_eq2) obtained from rhs.equal_range(rhs_eq1), that has the following properties:
- std::distance(lhs_eq1, lhs_eq2) == std::distance(rhs_eq1, rhs_eq2).
- std::is_permutation(lhs_eq1, lhs_eq2, rhs_eq1) == true.
Note that:
The behavior is undefined if Key or T are not EqualityComparable.
The behavior is also undefined if Hash and KeyEqual do (until C++20)KeyEqual does (since C++20) not have the same behavior on lhs and rhs or if operator== for Key is not a refinement of the partition into equivalent-key groups introduced by KeyEqual (that is, if two elements that compare equal using operator== fall into different partitions)
Finally, to consider is the complexity:
Proportional to N calls to operator== on value_type, calls to the predicate returned by key_eq, and calls to the hasher returned by hash_function, in the average case, proportional to N2 in the worst case where N is the size of the container.
Therefore, if both unordered maps have the same size, and each key in one of the containers is looked for in the other plus, if it happens to be found then their values are compared then they are the considered the same.
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Below are quotes from cppreference.com about the std:unordered_map, operator==,!=(std::unordered_map):
The contents of two unordered containers lhs and rhs are equal if the following conditions hold:
- lhs.size() == rhs.size()
- each group of equivalent elements [lhs_eq1, lhs_eq2) obtained from lhs.equal_range(lhs_eq1) has a corresponding group of equivalent elements in the other container [rhs_eq1, rhs_eq2) obtained from rhs.equal_range(rhs_eq1), that has the following properties:
- std::distance(lhs_eq1, lhs_eq2) == std::distance(rhs_eq1, rhs_eq2).
- std::is_permutation(lhs_eq1, lhs_eq2, rhs_eq1) == true.
Note that:
The behavior is undefined if Key or T are not EqualityComparable.
The behavior is also undefined if Hash and KeyEqual do (until C++20)KeyEqual does (since C++20) not have the same behavior on lhs and rhs or if operator== for Key is not a refinement of the partition into equivalent-key groups introduced by KeyEqual (that is, if two elements that compare equal using operator== fall into different partitions)
Finally, to consider is the complexity:
Proportional to N calls to operator== on value_type, calls to the predicate returned by key_eq, and calls to the hasher returned by hash_function, in the average case, proportional to N2 in the worst case where N is the size of the container.
Therefore, if both unordered maps have the same size, and each key in one of the containers is looked for in the other plus, if it happens to be found then their values are compared then they are the considered the same.
Below are quotes from cppreference.com about the std:unordered_map, operator==,!=(std::unordered_map):
The contents of two unordered containers lhs and rhs are equal if the following conditions hold:
- lhs.size() == rhs.size()
- each group of equivalent elements [lhs_eq1, lhs_eq2) obtained from lhs.equal_range(lhs_eq1) has a corresponding group of equivalent elements in the other container [rhs_eq1, rhs_eq2) obtained from rhs.equal_range(rhs_eq1), that has the following properties:
- std::distance(lhs_eq1, lhs_eq2) == std::distance(rhs_eq1, rhs_eq2).
- std::is_permutation(lhs_eq1, lhs_eq2, rhs_eq1) == true.
Note that:
The behavior is undefined if Key or T are not EqualityComparable.
The behavior is also undefined if Hash and KeyEqual do (until C++20)KeyEqual does (since C++20) not have the same behavior on lhs and rhs or if operator== for Key is not a refinement of the partition into equivalent-key groups introduced by KeyEqual (that is, if two elements that compare equal using operator== fall into different partitions)
Finally, to consider is the complexity:
Proportional to N calls to operator== on value_type, calls to the predicate returned by key_eq, and calls to the hasher returned by hash_function, in the average case, proportional to N2 in the worst case where N is the size of the container.
Therefore, if both unordered maps have the same size, and each key in one of the containers is looked for in the other plus, if it happens to be found then their values are compared then they are the considered the same.
answered yesterday
acarlstein
25419
25419
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f51710926%2fdoes-stdunordered-map-equality-depend-on-insertion-order%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Have you tried it? Also, that guarantee would follow from the according ISO standard, so that indirectly contain the answer.
â Ulrich Eckhardt
yesterday
@UlrichEckhardt I've tried, and the answer seems to be "yes, it depends on insertion order", but I'm not sure whether that is because I've made a mistake.
â Raedwald
yesterday
No. (This space intentionally left blank)
â n.m.
yesterday
Sample code showing equality of all permutations of insertion sequences for a map of 4 pairs<char, string>
â KarlM
yesterday
1
@UlrichEckhardt "Have you tried it" can't tell you whether "it doesn't depend on insertion order" is a feature of this implementation, or is guaranteed for all C++ implementations. (I suppose it can tell you that "it does depend on insertion order" - but all the answers below show that that would be a bug in the implementation.)
â Martin Bonner
19 hours ago