std::map::lower_bound or std::map::upper_bound when the key is not contained?
If I well understand, in a given map m:
If I want to find the first key greater or equal to a given key k, I use m.lower_bound(k).
If I want to find the first key strictly greater than a given key k, I use m.upper_bound(k).
If I still well understand, there is no difference if the key k is not contained yet in the map m. In this specific case (I KNOW my map doesn't contain the key), is there any reason to chose one or the other ? Is there one faster than the other ?
Note: I don't use C++11/14/17 for compatibility reason.
c++ stdmap c++03
asked Nov 13 '18 at 12:52
CaduchonCaduchon
2,45711556
|
show 3 more comments
If I well understand, in a given map m:
If I want to find the first key greater or equal to a given key k, I use m.lower_bound(k).
If I want to find the first key strictly greater than a given key k, I use m.upper_bound(k).
If I still well understand, there is no difference if the key k is not contained yet in the map m. In this specific case (I KNOW my map doesn't contain the key), is there any reason to chose one or the other ? Is there one faster than the other ?
Note: I don't use C++11/14/17 for compatibility reason.
c++ stdmap c++03
asked Nov 13 '18 at 12:52
CaduchonCaduchon
2,45711556
3
When you want to know what's faster, you should test it using something similar to your real environment.
– John Zwinck
Nov 13 '18 at 12:54
1
The only thing guaranteed by the standard is the abstract "big O" complexity, not the actual performance. You'll not find a guarantee about one being faster than the other (or both being equal) on all platforms, because the standard doesn't care about that (unless it rises to the level of a different "big O" complexity, which it surely will not).
– John Zwinck
Nov 13 '18 at 12:57
2
As to your performance concern, I wouldn't expect one to be faster than the other as a map is inherently a binary tree, and my intuition tells me thatupper_boundandlower_boundboth make use of a binary search. There is probably a difference of an inequality floating around (e.g.<=vs<)
– Joseph Wood
Nov 13 '18 at 13:01
1
Good reason (for my taste) is that "upper bound" conveys objective of your code better. Otherwise there most likely are no differences in that specific case.
– Öö Tiib
Nov 13 '18 at 13:08
3
@user463035818 -- no, both functions will return the same value if the key is not in the container. That gives you an empty range for elements that matchk. If all the elements are smaller thank, the first location where the new key could be inserted is at the end and the last location where the new key could be inserted is at the end. Similarly, if all elements are bigger thank, the new element goes at the beginning.
– Pete Becker
Nov 13 '18 at 13:54
|
show 3 more comments
If I well understand, in a given map m:
If I want to find the first key greater or equal to a given key k, I use m.lower_bound(k).
If I want to find the first key strictly greater than a given key k, I use m.upper_bound(k).
If I still well understand, there is no difference if the key k is not contained yet in the map m. In this specific case (I KNOW my map doesn't contain the key), is there any reason to chose one or the other ? Is there one faster than the other ?
Note: I don't use C++11/14/17 for compatibility reason.
c++ stdmap c++03
asked Nov 13 '18 at 12:52
CaduchonCaduchon
2,45711556
If I well understand, in a given map m:
If I want to find the first key greater or equal to a given key k, I use m.lower_bound(k).
If I want to find the first key strictly greater than a given key k, I use m.upper_bound(k).
If I still well understand, there is no difference if the key k is not contained yet in the map m. In this specific case (I KNOW my map doesn't contain the key), is there any reason to chose one or the other ? Is there one faster than the other ?
Note: I don't use C++11/14/17 for compatibility reason.
c++ stdmap c++03
c++ stdmap c++03
asked Nov 13 '18 at 12:52
CaduchonCaduchon
2,45711556
asked Nov 13 '18 at 12:52
CaduchonCaduchon
2,45711556
edited Jan 10 at 7:56
Caduchon
asked Nov 13 '18 at 12:52
CaduchonCaduchon
2,45711556
asked Nov 13 '18 at 12:52
CaduchonCaduchon
2,45711556
asked Nov 13 '18 at 12:52
CaduchonCaduchon
2,45711556
2,45711556
3
When you want to know what's faster, you should test it using something similar to your real environment.
– John Zwinck
Nov 13 '18 at 12:54
1
The only thing guaranteed by the standard is the abstract "big O" complexity, not the actual performance. You'll not find a guarantee about one being faster than the other (or both being equal) on all platforms, because the standard doesn't care about that (unless it rises to the level of a different "big O" complexity, which it surely will not).
– John Zwinck
Nov 13 '18 at 12:57
2
As to your performance concern, I wouldn't expect one to be faster than the other as a map is inherently a binary tree, and my intuition tells me thatupper_boundandlower_boundboth make use of a binary search. There is probably a difference of an inequality floating around (e.g.<=vs<)
– Joseph Wood
Nov 13 '18 at 13:01
1
Good reason (for my taste) is that "upper bound" conveys objective of your code better. Otherwise there most likely are no differences in that specific case.
– Öö Tiib
Nov 13 '18 at 13:08
3
@user463035818 -- no, both functions will return the same value if the key is not in the container. That gives you an empty range for elements that matchk. If all the elements are smaller thank, the first location where the new key could be inserted is at the end and the last location where the new key could be inserted is at the end. Similarly, if all elements are bigger thank, the new element goes at the beginning.
– Pete Becker
Nov 13 '18 at 13:54
|
show 3 more comments
3
When you want to know what's faster, you should test it using something similar to your real environment.
– John Zwinck
Nov 13 '18 at 12:54
1
The only thing guaranteed by the standard is the abstract "big O" complexity, not the actual performance. You'll not find a guarantee about one being faster than the other (or both being equal) on all platforms, because the standard doesn't care about that (unless it rises to the level of a different "big O" complexity, which it surely will not).
– John Zwinck
Nov 13 '18 at 12:57
2
As to your performance concern, I wouldn't expect one to be faster than the other as a map is inherently a binary tree, and my intuition tells me thatupper_boundandlower_boundboth make use of a binary search. There is probably a difference of an inequality floating around (e.g.<=vs<)
– Joseph Wood
Nov 13 '18 at 13:01
1
Good reason (for my taste) is that "upper bound" conveys objective of your code better. Otherwise there most likely are no differences in that specific case.
– Öö Tiib
Nov 13 '18 at 13:08
3
@user463035818 -- no, both functions will return the same value if the key is not in the container. That gives you an empty range for elements that matchk. If all the elements are smaller thank, the first location where the new key could be inserted is at the end and the last location where the new key could be inserted is at the end. Similarly, if all elements are bigger thank, the new element goes at the beginning.
– Pete Becker
Nov 13 '18 at 13:54
3
3
When you want to know what's faster, you should test it using something similar to your real environment.
– John Zwinck
Nov 13 '18 at 12:54
When you want to know what's faster, you should test it using something similar to your real environment.
– John Zwinck
Nov 13 '18 at 12:54
1
1
The only thing guaranteed by the standard is the abstract "big O" complexity, not the actual performance. You'll not find a guarantee about one being faster than the other (or both being equal) on all platforms, because the standard doesn't care about that (unless it rises to the level of a different "big O" complexity, which it surely will not).
– John Zwinck
Nov 13 '18 at 12:57
The only thing guaranteed by the standard is the abstract "big O" complexity, not the actual performance. You'll not find a guarantee about one being faster than the other (or both being equal) on all platforms, because the standard doesn't care about that (unless it rises to the level of a different "big O" complexity, which it surely will not).
– John Zwinck
Nov 13 '18 at 12:57
2
2
As to your performance concern, I wouldn't expect one to be faster than the other as a map is inherently a binary tree, and my intuition tells me that
upper_bound and lower_bound both make use of a binary search. There is probably a difference of an inequality floating around (e.g. <= vs <)– Joseph Wood
Nov 13 '18 at 13:01
As to your performance concern, I wouldn't expect one to be faster than the other as a map is inherently a binary tree, and my intuition tells me that
upper_bound and lower_bound both make use of a binary search. There is probably a difference of an inequality floating around (e.g. <= vs <)– Joseph Wood
Nov 13 '18 at 13:01
1
1
Good reason (for my taste) is that "upper bound" conveys objective of your code better. Otherwise there most likely are no differences in that specific case.
– Öö Tiib
Nov 13 '18 at 13:08
Good reason (for my taste) is that "upper bound" conveys objective of your code better. Otherwise there most likely are no differences in that specific case.
– Öö Tiib
Nov 13 '18 at 13:08
3
3
@user463035818 -- no, both functions will return the same value if the key is not in the container. That gives you an empty range for elements that match
k. If all the elements are smaller than k, the first location where the new key could be inserted is at the end and the last location where the new key could be inserted is at the end. Similarly, if all elements are bigger than k, the new element goes at the beginning.– Pete Becker
Nov 13 '18 at 13:54
@user463035818 -- no, both functions will return the same value if the key is not in the container. That gives you an empty range for elements that match
k. If all the elements are smaller than k, the first location where the new key could be inserted is at the end and the last location where the new key could be inserted is at the end. Similarly, if all elements are bigger than k, the new element goes at the beginning.– Pete Becker
Nov 13 '18 at 13:54
|
show 3 more comments
1 Answer
1
active
oldest
votes
According to standard, they both run in Logarithmic time and it doens't really matter if you map contains the key or not. If there are differences in performance it will be platform specific.
answered Nov 13 '18 at 13:01
darunedarune
1,134516
add a 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%2f53281447%2fstdmaplower-bound-or-stdmapupper-bound-when-the-key-is-not-contained%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
According to standard, they both run in Logarithmic time and it doens't really matter if you map contains the key or not. If there are differences in performance it will be platform specific.
answered Nov 13 '18 at 13:01
darunedarune
1,134516
add a comment |
According to standard, they both run in Logarithmic time and it doens't really matter if you map contains the key or not. If there are differences in performance it will be platform specific.
answered Nov 13 '18 at 13:01
darunedarune
1,134516
add a comment |
According to standard, they both run in Logarithmic time and it doens't really matter if you map contains the key or not. If there are differences in performance it will be platform specific.
answered Nov 13 '18 at 13:01
darunedarune
1,134516
According to standard, they both run in Logarithmic time and it doens't really matter if you map contains the key or not. If there are differences in performance it will be platform specific.
answered Nov 13 '18 at 13:01
darunedarune
1,134516
answered Nov 13 '18 at 13:01
darunedarune
1,134516
answered Nov 13 '18 at 13:01
darunedarune
1,134516
answered Nov 13 '18 at 13:01
darunedarune
1,134516
1,134516
add a comment |
add a 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.
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%2f53281447%2fstdmaplower-bound-or-stdmapupper-bound-when-the-key-is-not-contained%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
When you want to know what's faster, you should test it using something similar to your real environment.
– John Zwinck
Nov 13 '18 at 12:54
1
The only thing guaranteed by the standard is the abstract "big O" complexity, not the actual performance. You'll not find a guarantee about one being faster than the other (or both being equal) on all platforms, because the standard doesn't care about that (unless it rises to the level of a different "big O" complexity, which it surely will not).
– John Zwinck
Nov 13 '18 at 12:57
2
As to your performance concern, I wouldn't expect one to be faster than the other as a map is inherently a binary tree, and my intuition tells me that
upper_boundandlower_boundboth make use of a binary search. There is probably a difference of an inequality floating around (e.g.<=vs<)– Joseph Wood
Nov 13 '18 at 13:01
1
Good reason (for my taste) is that "upper bound" conveys objective of your code better. Otherwise there most likely are no differences in that specific case.
– Öö Tiib
Nov 13 '18 at 13:08
3
@user463035818 -- no, both functions will return the same value if the key is not in the container. That gives you an empty range for elements that match
k. If all the elements are smaller thank, the first location where the new key could be inserted is at the end and the last location where the new key could be inserted is at the end. Similarly, if all elements are bigger thank, the new element goes at the beginning.– Pete Becker
Nov 13 '18 at 13:54