Is std::next for vector O(n) or O(1)? The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) The Ask Question Wizard is Live! Data science time! April 2019 and salary with experienceConcatenating two std::vectorsstd::wstring VS std::stringHow to find out if an item is present in a std::vector?Why is “using namespace std” considered bad practice?How do I use arrays in C++?Image Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionReplacing a 32-bit loop counter with 64-bit introduces crazy performance deviationsHow does std::list.size() have constant complexity?Why does std::vector reserve not “double” its capacity, while resize does?How std::advance iterator type is deduced?
Can the DM override racial traits?
The variadic template constructor of my class cannot modify my class members, why is that so?
Why can't devices on different VLANs, but on the same subnet, communicate?
Simulating Exploding Dice
Can a novice safely splice in wire to lengthen 5V charging cable?
Do working physicists consider Newtonian mechanics to be "falsified"?
Is there a writing software that you can sort scenes like slides in PowerPoint?
What is special about square numbers here?
How are presidential pardons supposed to be used?
In horse breeding, what is the female equivalent of putting a horse out "to stud"?
How many people can fit inside Mordenkainen's Magnificent Mansion?
Am I ethically obligated to go into work on an off day if the reason is sudden?
What was the last x86 CPU that did not have the x87 floating-point unit built in?
How can I define good in a religion that claims no moral authority?
Can a 1st-level character have an ability score above 18?
How to pronounce 1ターン?
Make it rain characters
Keeping a retro style to sci-fi spaceships?
How to politely respond to generic emails requesting a PhD/job in my lab? Without wasting too much time
Relations between two reciprocal partial derivatives?
Is every episode of "Where are my Pants?" identical?
Do warforged have souls?
Why does this iterative way of solving of equation work?
How did passengers keep warm on sail ships?
Is std::next for vector O(n) or O(1)?
The 2019 Stack Overflow Developer Survey Results Are In
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)
The Ask Question Wizard is Live!
Data science time! April 2019 and salary with experienceConcatenating two std::vectorsstd::wstring VS std::stringHow to find out if an item is present in a std::vector?Why is “using namespace std” considered bad practice?How do I use arrays in C++?Image Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionReplacing a 32-bit loop counter with 64-bit introduces crazy performance deviationsHow does std::list.size() have constant complexity?Why does std::vector reserve not “double” its capacity, while resize does?How std::advance iterator type is deduced?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
In C++11 I use std::next because If I want to change vector to list, I dont have to change the rest of code.
For list, std::next is O(n), because I need to iterate all elements. But how is it for a vector? I have found this note on cppreference:
However, if
InputItorForwardItadditionally meets the requirements of LegacyRandomAccessIterator, complexity is constant.
Does vector meet these requirements? And why "Legacy"?
c++
edited 2 days ago
El Profesor
11k32341
asked Apr 9 at 7:01
Martin PerryMartin Perry
5,22333267
add a comment |
In C++11 I use std::next because If I want to change vector to list, I dont have to change the rest of code.
For list, std::next is O(n), because I need to iterate all elements. But how is it for a vector? I have found this note on cppreference:
However, if
InputItorForwardItadditionally meets the requirements of LegacyRandomAccessIterator, complexity is constant.
Does vector meet these requirements? And why "Legacy"?
c++
edited 2 days ago
El Profesor
11k32341
asked Apr 9 at 7:01
Martin PerryMartin Perry
5,22333267
13
"Constant" meansO(1).
– Some programmer dude
Apr 9 at 7:03
1
I know that, but I dont know If it aplies to vector, since I dont understand LegacyRandomAccessIterator. Why Legacy?
– Martin Perry
Apr 9 at 7:04
4
@MartinPerry Follow the link? In the page you pull the quote from, the word "LegacyRandomAccessIterator" is a link to an explanation about it. And for vectors, iterators are (legacy) random-access iterators (as you should be able to find out in thestd::vectorreference).
– Some programmer dude
Apr 9 at 7:06
add a comment |
In C++11 I use std::next because If I want to change vector to list, I dont have to change the rest of code.
For list, std::next is O(n), because I need to iterate all elements. But how is it for a vector? I have found this note on cppreference:
However, if
InputItorForwardItadditionally meets the requirements of LegacyRandomAccessIterator, complexity is constant.
Does vector meet these requirements? And why "Legacy"?
c++
edited 2 days ago
El Profesor
11k32341
asked Apr 9 at 7:01
Martin PerryMartin Perry
5,22333267
In C++11 I use std::next because If I want to change vector to list, I dont have to change the rest of code.
For list, std::next is O(n), because I need to iterate all elements. But how is it for a vector? I have found this note on cppreference:
However, if
InputItorForwardItadditionally meets the requirements of LegacyRandomAccessIterator, complexity is constant.
Does vector meet these requirements? And why "Legacy"?
c++
c++
edited 2 days ago
El Profesor
11k32341
asked Apr 9 at 7:01
Martin PerryMartin Perry
5,22333267
edited 2 days ago
El Profesor
11k32341
asked Apr 9 at 7:01
Martin PerryMartin Perry
5,22333267
edited 2 days ago
El Profesor
11k32341
edited 2 days ago
El Profesor
11k32341
edited 2 days ago
El Profesor
11k32341
11k32341
asked Apr 9 at 7:01
Martin PerryMartin Perry
5,22333267
asked Apr 9 at 7:01
Martin PerryMartin Perry
5,22333267
asked Apr 9 at 7:01
Martin PerryMartin Perry
5,22333267
5,22333267
13
"Constant" meansO(1).
– Some programmer dude
Apr 9 at 7:03
1
I know that, but I dont know If it aplies to vector, since I dont understand LegacyRandomAccessIterator. Why Legacy?
– Martin Perry
Apr 9 at 7:04
4
@MartinPerry Follow the link? In the page you pull the quote from, the word "LegacyRandomAccessIterator" is a link to an explanation about it. And for vectors, iterators are (legacy) random-access iterators (as you should be able to find out in thestd::vectorreference).
– Some programmer dude
Apr 9 at 7:06
add a comment |
13
"Constant" meansO(1).
– Some programmer dude
Apr 9 at 7:03
1
I know that, but I dont know If it aplies to vector, since I dont understand LegacyRandomAccessIterator. Why Legacy?
– Martin Perry
Apr 9 at 7:04
4
@MartinPerry Follow the link? In the page you pull the quote from, the word "LegacyRandomAccessIterator" is a link to an explanation about it. And for vectors, iterators are (legacy) random-access iterators (as you should be able to find out in thestd::vectorreference).
– Some programmer dude
Apr 9 at 7:06
13
13
"Constant" means
O(1).– Some programmer dude
Apr 9 at 7:03
"Constant" means
O(1).– Some programmer dude
Apr 9 at 7:03
1
1
I know that, but I dont know If it aplies to vector, since I dont understand LegacyRandomAccessIterator. Why Legacy?
– Martin Perry
Apr 9 at 7:04
I know that, but I dont know If it aplies to vector, since I dont understand LegacyRandomAccessIterator. Why Legacy?
– Martin Perry
Apr 9 at 7:04
4
4
@MartinPerry Follow the link? In the page you pull the quote from, the word "LegacyRandomAccessIterator" is a link to an explanation about it. And for vectors, iterators are (legacy) random-access iterators (as you should be able to find out in the
std::vector reference).– Some programmer dude
Apr 9 at 7:06
@MartinPerry Follow the link? In the page you pull the quote from, the word "LegacyRandomAccessIterator" is a link to an explanation about it. And for vectors, iterators are (legacy) random-access iterators (as you should be able to find out in the
std::vector reference).– Some programmer dude
Apr 9 at 7:06
add a comment |
2 Answers
2
active
oldest
votes
There is a plan of adding concepts (compile time type constraints) in C++20. The new standard is supposed to contain concepts like InputIterator or RandomAccessIterator. To distinguish between the concepts and the old trait-like requirements cppreference uses LegacyRandomAccessIterator and so on for pre-concept requirements and RandomAccessIterator and so for concept requirements.
And so yes, std::vector::iterator meets requirements of LegacyRandomAccessIterator and actually will be fulfilling RandomAccessIterator concept as well. This leads straight to conclusion that std::next called on vector::iterator has complexity O(1).
answered Apr 9 at 7:11
bartopbartop
3,4931132
add a comment |
Does vector meet these requirements?
Yes, it does:
https://en.cppreference.com/w/cpp/container/vector
Quote: "iterator LegacyRandomAccessIterator"
And why "Legacy"?
The existing iterators have been renamed "legacy" because of the upcoming C++ library feature called ranges, which is a replacement for the current approach. Ranges will have new iterators. The existing ones will still be there, thus they're called "legacy."
answered Apr 9 at 7:11
Nikos C.Nikos C.
34.5k53967
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%2f55586847%2fis-stdnext-for-vector-on-or-o1%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
There is a plan of adding concepts (compile time type constraints) in C++20. The new standard is supposed to contain concepts like InputIterator or RandomAccessIterator. To distinguish between the concepts and the old trait-like requirements cppreference uses LegacyRandomAccessIterator and so on for pre-concept requirements and RandomAccessIterator and so for concept requirements.
And so yes, std::vector::iterator meets requirements of LegacyRandomAccessIterator and actually will be fulfilling RandomAccessIterator concept as well. This leads straight to conclusion that std::next called on vector::iterator has complexity O(1).
answered Apr 9 at 7:11
bartopbartop
3,4931132
add a comment |
There is a plan of adding concepts (compile time type constraints) in C++20. The new standard is supposed to contain concepts like InputIterator or RandomAccessIterator. To distinguish between the concepts and the old trait-like requirements cppreference uses LegacyRandomAccessIterator and so on for pre-concept requirements and RandomAccessIterator and so for concept requirements.
And so yes, std::vector::iterator meets requirements of LegacyRandomAccessIterator and actually will be fulfilling RandomAccessIterator concept as well. This leads straight to conclusion that std::next called on vector::iterator has complexity O(1).
answered Apr 9 at 7:11
bartopbartop
3,4931132
add a comment |
There is a plan of adding concepts (compile time type constraints) in C++20. The new standard is supposed to contain concepts like InputIterator or RandomAccessIterator. To distinguish between the concepts and the old trait-like requirements cppreference uses LegacyRandomAccessIterator and so on for pre-concept requirements and RandomAccessIterator and so for concept requirements.
And so yes, std::vector::iterator meets requirements of LegacyRandomAccessIterator and actually will be fulfilling RandomAccessIterator concept as well. This leads straight to conclusion that std::next called on vector::iterator has complexity O(1).
answered Apr 9 at 7:11
bartopbartop
3,4931132
There is a plan of adding concepts (compile time type constraints) in C++20. The new standard is supposed to contain concepts like InputIterator or RandomAccessIterator. To distinguish between the concepts and the old trait-like requirements cppreference uses LegacyRandomAccessIterator and so on for pre-concept requirements and RandomAccessIterator and so for concept requirements.
And so yes, std::vector::iterator meets requirements of LegacyRandomAccessIterator and actually will be fulfilling RandomAccessIterator concept as well. This leads straight to conclusion that std::next called on vector::iterator has complexity O(1).
answered Apr 9 at 7:11
bartopbartop
3,4931132
edited Apr 9 at 7:17
answered Apr 9 at 7:11
bartopbartop
3,4931132
answered Apr 9 at 7:11
bartopbartop
3,4931132
answered Apr 9 at 7:11
bartopbartop
3,4931132
3,4931132
add a comment |
add a comment |
Does vector meet these requirements?
Yes, it does:
https://en.cppreference.com/w/cpp/container/vector
Quote: "iterator LegacyRandomAccessIterator"
And why "Legacy"?
The existing iterators have been renamed "legacy" because of the upcoming C++ library feature called ranges, which is a replacement for the current approach. Ranges will have new iterators. The existing ones will still be there, thus they're called "legacy."
answered Apr 9 at 7:11
Nikos C.Nikos C.
34.5k53967
add a comment |
Does vector meet these requirements?
Yes, it does:
https://en.cppreference.com/w/cpp/container/vector
Quote: "iterator LegacyRandomAccessIterator"
And why "Legacy"?
The existing iterators have been renamed "legacy" because of the upcoming C++ library feature called ranges, which is a replacement for the current approach. Ranges will have new iterators. The existing ones will still be there, thus they're called "legacy."
answered Apr 9 at 7:11
Nikos C.Nikos C.
34.5k53967
add a comment |
Does vector meet these requirements?
Yes, it does:
https://en.cppreference.com/w/cpp/container/vector
Quote: "iterator LegacyRandomAccessIterator"
And why "Legacy"?
The existing iterators have been renamed "legacy" because of the upcoming C++ library feature called ranges, which is a replacement for the current approach. Ranges will have new iterators. The existing ones will still be there, thus they're called "legacy."
answered Apr 9 at 7:11
Nikos C.Nikos C.
34.5k53967
Does vector meet these requirements?
Yes, it does:
https://en.cppreference.com/w/cpp/container/vector
Quote: "iterator LegacyRandomAccessIterator"
And why "Legacy"?
The existing iterators have been renamed "legacy" because of the upcoming C++ library feature called ranges, which is a replacement for the current approach. Ranges will have new iterators. The existing ones will still be there, thus they're called "legacy."
answered Apr 9 at 7:11
Nikos C.Nikos C.
34.5k53967
answered Apr 9 at 7:11
Nikos C.Nikos C.
34.5k53967
answered Apr 9 at 7:11
Nikos C.Nikos C.
34.5k53967
answered Apr 9 at 7:11
Nikos C.Nikos C.
34.5k53967
34.5k53967
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%2f55586847%2fis-stdnext-for-vector-on-or-o1%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
13
"Constant" means
O(1).– Some programmer dude
Apr 9 at 7:03
1
I know that, but I dont know If it aplies to vector, since I dont understand LegacyRandomAccessIterator. Why Legacy?
– Martin Perry
Apr 9 at 7:04
4
@MartinPerry Follow the link? In the page you pull the quote from, the word "LegacyRandomAccessIterator" is a link to an explanation about it. And for vectors, iterators are (legacy) random-access iterators (as you should be able to find out in the
std::vectorreference).– Some programmer dude
Apr 9 at 7:06