C++11: does unordered_map/set guarantees traversing order as insert order?
I wrote some small code like
unordered_map<int, int> uii;
uii.insert(make_pair(12,4));
uii.insert(make_pair(3,2));
uii.insert(make_pair(6,1));
uii.insert(make_pair(16,9));
....
When I use for loop to visit this map, it prints key in the right order of my insertion. I tested unordered_set, same result.
So my question is, does c++ standard guarantees the visiting order as insert order, just like Java's LinkedHashMap?
Thanks a lot.
c++ c++11 insert order unordered-map
asked Nov 20 '18 at 9:18
Troskyvs
2,27111027
add a comment |
I wrote some small code like
unordered_map<int, int> uii;
uii.insert(make_pair(12,4));
uii.insert(make_pair(3,2));
uii.insert(make_pair(6,1));
uii.insert(make_pair(16,9));
....
When I use for loop to visit this map, it prints key in the right order of my insertion. I tested unordered_set, same result.
So my question is, does c++ standard guarantees the visiting order as insert order, just like Java's LinkedHashMap?
Thanks a lot.
c++ c++11 insert order unordered-map
asked Nov 20 '18 at 9:18
Troskyvs
2,27111027
3
It is unordered.
– Yola
Nov 20 '18 at 9:21
6
"Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key."
– HolyBlackCat
Nov 20 '18 at 9:23
Since it's trivial to reorder your four insert statements and see whether the loop still visits in insert order ... did you do this?
– Useless
Nov 20 '18 at 9:54
This is a counterexample, the output is out of order due to rehash.
– felix
Nov 20 '18 at 10:20
unordered_map is analogous to HashMap not LinkedHashMap.
– Paul Rooney
Nov 20 '18 at 10:47
add a comment |
I wrote some small code like
unordered_map<int, int> uii;
uii.insert(make_pair(12,4));
uii.insert(make_pair(3,2));
uii.insert(make_pair(6,1));
uii.insert(make_pair(16,9));
....
When I use for loop to visit this map, it prints key in the right order of my insertion. I tested unordered_set, same result.
So my question is, does c++ standard guarantees the visiting order as insert order, just like Java's LinkedHashMap?
Thanks a lot.
c++ c++11 insert order unordered-map
asked Nov 20 '18 at 9:18
Troskyvs
2,27111027
I wrote some small code like
unordered_map<int, int> uii;
uii.insert(make_pair(12,4));
uii.insert(make_pair(3,2));
uii.insert(make_pair(6,1));
uii.insert(make_pair(16,9));
....
When I use for loop to visit this map, it prints key in the right order of my insertion. I tested unordered_set, same result.
So my question is, does c++ standard guarantees the visiting order as insert order, just like Java's LinkedHashMap?
Thanks a lot.
c++ c++11 insert order unordered-map
c++ c++11 insert order unordered-map
asked Nov 20 '18 at 9:18
Troskyvs
2,27111027
asked Nov 20 '18 at 9:18
Troskyvs
2,27111027
asked Nov 20 '18 at 9:18
Troskyvs
2,27111027
asked Nov 20 '18 at 9:18
Troskyvs
2,27111027
asked Nov 20 '18 at 9:18
Troskyvs
2,27111027
2,27111027
3
It is unordered.
– Yola
Nov 20 '18 at 9:21
6
"Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key."
– HolyBlackCat
Nov 20 '18 at 9:23
Since it's trivial to reorder your four insert statements and see whether the loop still visits in insert order ... did you do this?
– Useless
Nov 20 '18 at 9:54
This is a counterexample, the output is out of order due to rehash.
– felix
Nov 20 '18 at 10:20
unordered_map is analogous to HashMap not LinkedHashMap.
– Paul Rooney
Nov 20 '18 at 10:47
add a comment |
3
It is unordered.
– Yola
Nov 20 '18 at 9:21
6
"Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key."
– HolyBlackCat
Nov 20 '18 at 9:23
Since it's trivial to reorder your four insert statements and see whether the loop still visits in insert order ... did you do this?
– Useless
Nov 20 '18 at 9:54
This is a counterexample, the output is out of order due to rehash.
– felix
Nov 20 '18 at 10:20
unordered_map is analogous to HashMap not LinkedHashMap.
– Paul Rooney
Nov 20 '18 at 10:47
3
3
It is unordered.
– Yola
Nov 20 '18 at 9:21
It is unordered.
– Yola
Nov 20 '18 at 9:21
6
6
"Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key."
– HolyBlackCat
Nov 20 '18 at 9:23
"Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key."
– HolyBlackCat
Nov 20 '18 at 9:23
Since it's trivial to reorder your four insert statements and see whether the loop still visits in insert order ... did you do this?
– Useless
Nov 20 '18 at 9:54
Since it's trivial to reorder your four insert statements and see whether the loop still visits in insert order ... did you do this?
– Useless
Nov 20 '18 at 9:54
This is a counterexample, the output is out of order due to rehash.
– felix
Nov 20 '18 at 10:20
This is a counterexample, the output is out of order due to rehash.
– felix
Nov 20 '18 at 10:20
unordered_map is analogous to HashMap not LinkedHashMap.
– Paul Rooney
Nov 20 '18 at 10:47
unordered_map is analogous to HashMap not LinkedHashMap.
– Paul Rooney
Nov 20 '18 at 10:47
add a comment |
1 Answer
1
active
oldest
votes
No, it is unordered, there is no such guarantee.
Elements in an unordered associative container are organized into
buckets, keys with the same hash will end up in the same bucket. The
number of buckets is increased when the size of the container
increases to keep the average number of elements in each bucket under
a certain value.
Rehashing invalidates iterator and might cause the elements to be
re-arranged in different buckets but it doesn't invalidate references
to the elements.
This is valid for both unordered_map and unordered_set.
You might also want to check this question Keep the order of unordered_map as we insert a new key
But, internally an implementation of unordered container might use list or other ordered container to store elements and store only references to sublists in its buckets, that would make iteration order to coincide with the insertion order until enough elements are inserted to cause list rearranging. That is the case with VS implementation.
answered Nov 20 '18 at 9:24
Yola
10.8k64671
The ordered bucket container will preserve insertion order if all the elements end up in the same bucket, but not otherwise.
– Useless
Nov 20 '18 at 9:56
@Useless sorry, i couldn't find such a requirement, and i believe in case of rehashing this doesn't hold.
– Yola
Nov 20 '18 at 10:06
Oh, I read your last section as asserting that an ordered bucket container would give you insertion-ordered traversal. You're actually saying some unordered implementations have an insertion-ordered underlying store and only hash references into it?
– Useless
Nov 20 '18 at 10:11
1
Yes, but every bucket has its own part of this underlying container. One need to insert enough elements to cause underlying container (list) to rearrange -- to move the front element somewhere in the middle of the list where its bucket belongs.
– Yola
Nov 20 '18 at 10:21
@Useless i updated the post, thanks for pointing out this mistake.
– Yola
Nov 20 '18 at 10:23
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53389732%2fc11-does-unordered-map-set-guarantees-traversing-order-as-insert-order%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
No, it is unordered, there is no such guarantee.
Elements in an unordered associative container are organized into
buckets, keys with the same hash will end up in the same bucket. The
number of buckets is increased when the size of the container
increases to keep the average number of elements in each bucket under
a certain value.
Rehashing invalidates iterator and might cause the elements to be
re-arranged in different buckets but it doesn't invalidate references
to the elements.
This is valid for both unordered_map and unordered_set.
You might also want to check this question Keep the order of unordered_map as we insert a new key
But, internally an implementation of unordered container might use list or other ordered container to store elements and store only references to sublists in its buckets, that would make iteration order to coincide with the insertion order until enough elements are inserted to cause list rearranging. That is the case with VS implementation.
answered Nov 20 '18 at 9:24
Yola
10.8k64671
The ordered bucket container will preserve insertion order if all the elements end up in the same bucket, but not otherwise.
– Useless
Nov 20 '18 at 9:56
@Useless sorry, i couldn't find such a requirement, and i believe in case of rehashing this doesn't hold.
– Yola
Nov 20 '18 at 10:06
Oh, I read your last section as asserting that an ordered bucket container would give you insertion-ordered traversal. You're actually saying some unordered implementations have an insertion-ordered underlying store and only hash references into it?
– Useless
Nov 20 '18 at 10:11
1
Yes, but every bucket has its own part of this underlying container. One need to insert enough elements to cause underlying container (list) to rearrange -- to move the front element somewhere in the middle of the list where its bucket belongs.
– Yola
Nov 20 '18 at 10:21
@Useless i updated the post, thanks for pointing out this mistake.
– Yola
Nov 20 '18 at 10:23
|
show 1 more comment
No, it is unordered, there is no such guarantee.
Elements in an unordered associative container are organized into
buckets, keys with the same hash will end up in the same bucket. The
number of buckets is increased when the size of the container
increases to keep the average number of elements in each bucket under
a certain value.
Rehashing invalidates iterator and might cause the elements to be
re-arranged in different buckets but it doesn't invalidate references
to the elements.
This is valid for both unordered_map and unordered_set.
You might also want to check this question Keep the order of unordered_map as we insert a new key
But, internally an implementation of unordered container might use list or other ordered container to store elements and store only references to sublists in its buckets, that would make iteration order to coincide with the insertion order until enough elements are inserted to cause list rearranging. That is the case with VS implementation.
answered Nov 20 '18 at 9:24
Yola
10.8k64671
The ordered bucket container will preserve insertion order if all the elements end up in the same bucket, but not otherwise.
– Useless
Nov 20 '18 at 9:56
@Useless sorry, i couldn't find such a requirement, and i believe in case of rehashing this doesn't hold.
– Yola
Nov 20 '18 at 10:06
Oh, I read your last section as asserting that an ordered bucket container would give you insertion-ordered traversal. You're actually saying some unordered implementations have an insertion-ordered underlying store and only hash references into it?
– Useless
Nov 20 '18 at 10:11
1
Yes, but every bucket has its own part of this underlying container. One need to insert enough elements to cause underlying container (list) to rearrange -- to move the front element somewhere in the middle of the list where its bucket belongs.
– Yola
Nov 20 '18 at 10:21
@Useless i updated the post, thanks for pointing out this mistake.
– Yola
Nov 20 '18 at 10:23
|
show 1 more comment
No, it is unordered, there is no such guarantee.
Elements in an unordered associative container are organized into
buckets, keys with the same hash will end up in the same bucket. The
number of buckets is increased when the size of the container
increases to keep the average number of elements in each bucket under
a certain value.
Rehashing invalidates iterator and might cause the elements to be
re-arranged in different buckets but it doesn't invalidate references
to the elements.
This is valid for both unordered_map and unordered_set.
You might also want to check this question Keep the order of unordered_map as we insert a new key
But, internally an implementation of unordered container might use list or other ordered container to store elements and store only references to sublists in its buckets, that would make iteration order to coincide with the insertion order until enough elements are inserted to cause list rearranging. That is the case with VS implementation.
answered Nov 20 '18 at 9:24
Yola
10.8k64671
No, it is unordered, there is no such guarantee.
Elements in an unordered associative container are organized into
buckets, keys with the same hash will end up in the same bucket. The
number of buckets is increased when the size of the container
increases to keep the average number of elements in each bucket under
a certain value.
Rehashing invalidates iterator and might cause the elements to be
re-arranged in different buckets but it doesn't invalidate references
to the elements.
This is valid for both unordered_map and unordered_set.
You might also want to check this question Keep the order of unordered_map as we insert a new key
But, internally an implementation of unordered container might use list or other ordered container to store elements and store only references to sublists in its buckets, that would make iteration order to coincide with the insertion order until enough elements are inserted to cause list rearranging. That is the case with VS implementation.
answered Nov 20 '18 at 9:24
Yola
10.8k64671
edited Nov 20 '18 at 10:23
answered Nov 20 '18 at 9:24
Yola
10.8k64671
answered Nov 20 '18 at 9:24
Yola
10.8k64671
answered Nov 20 '18 at 9:24
Yola
10.8k64671
10.8k64671
The ordered bucket container will preserve insertion order if all the elements end up in the same bucket, but not otherwise.
– Useless
Nov 20 '18 at 9:56
@Useless sorry, i couldn't find such a requirement, and i believe in case of rehashing this doesn't hold.
– Yola
Nov 20 '18 at 10:06
Oh, I read your last section as asserting that an ordered bucket container would give you insertion-ordered traversal. You're actually saying some unordered implementations have an insertion-ordered underlying store and only hash references into it?
– Useless
Nov 20 '18 at 10:11
1
Yes, but every bucket has its own part of this underlying container. One need to insert enough elements to cause underlying container (list) to rearrange -- to move the front element somewhere in the middle of the list where its bucket belongs.
– Yola
Nov 20 '18 at 10:21
@Useless i updated the post, thanks for pointing out this mistake.
– Yola
Nov 20 '18 at 10:23
|
show 1 more comment
The ordered bucket container will preserve insertion order if all the elements end up in the same bucket, but not otherwise.
– Useless
Nov 20 '18 at 9:56
@Useless sorry, i couldn't find such a requirement, and i believe in case of rehashing this doesn't hold.
– Yola
Nov 20 '18 at 10:06
Oh, I read your last section as asserting that an ordered bucket container would give you insertion-ordered traversal. You're actually saying some unordered implementations have an insertion-ordered underlying store and only hash references into it?
– Useless
Nov 20 '18 at 10:11
1
Yes, but every bucket has its own part of this underlying container. One need to insert enough elements to cause underlying container (list) to rearrange -- to move the front element somewhere in the middle of the list where its bucket belongs.
– Yola
Nov 20 '18 at 10:21
@Useless i updated the post, thanks for pointing out this mistake.
– Yola
Nov 20 '18 at 10:23
The ordered bucket container will preserve insertion order if all the elements end up in the same bucket, but not otherwise.
– Useless
Nov 20 '18 at 9:56
The ordered bucket container will preserve insertion order if all the elements end up in the same bucket, but not otherwise.
– Useless
Nov 20 '18 at 9:56
@Useless sorry, i couldn't find such a requirement, and i believe in case of rehashing this doesn't hold.
– Yola
Nov 20 '18 at 10:06
@Useless sorry, i couldn't find such a requirement, and i believe in case of rehashing this doesn't hold.
– Yola
Nov 20 '18 at 10:06
Oh, I read your last section as asserting that an ordered bucket container would give you insertion-ordered traversal. You're actually saying some unordered implementations have an insertion-ordered underlying store and only hash references into it?
– Useless
Nov 20 '18 at 10:11
Oh, I read your last section as asserting that an ordered bucket container would give you insertion-ordered traversal. You're actually saying some unordered implementations have an insertion-ordered underlying store and only hash references into it?
– Useless
Nov 20 '18 at 10:11
1
1
Yes, but every bucket has its own part of this underlying container. One need to insert enough elements to cause underlying container (list) to rearrange -- to move the front element somewhere in the middle of the list where its bucket belongs.
– Yola
Nov 20 '18 at 10:21
Yes, but every bucket has its own part of this underlying container. One need to insert enough elements to cause underlying container (list) to rearrange -- to move the front element somewhere in the middle of the list where its bucket belongs.
– Yola
Nov 20 '18 at 10:21
@Useless i updated the post, thanks for pointing out this mistake.
– Yola
Nov 20 '18 at 10:23
@Useless i updated the post, thanks for pointing out this mistake.
– Yola
Nov 20 '18 at 10:23
|
show 1 more comment
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53389732%2fc11-does-unordered-map-set-guarantees-traversing-order-as-insert-order%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
It is unordered.
– Yola
Nov 20 '18 at 9:21
6
"Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key."
– HolyBlackCat
Nov 20 '18 at 9:23
Since it's trivial to reorder your four insert statements and see whether the loop still visits in insert order ... did you do this?
– Useless
Nov 20 '18 at 9:54
This is a counterexample, the output is out of order due to rehash.
– felix
Nov 20 '18 at 10:20
unordered_map is analogous to HashMap not LinkedHashMap.
– Paul Rooney
Nov 20 '18 at 10:47