Trjtdtk

Pressure to defend the relevance of one's area of mathematics

Do I have to worry about players making “bad” choices on level up?

Where did the extra Pym particles come from in Endgame?

What is a Recurrent Neural Network?

Feels like I am getting dragged in office politics

Why is the origin of “threshold” uncertain?

Subtleties of choosing the sequence of tenses in Russian

Modify locally tikzset

Did Henry V’s archers at Agincourt fight with no pants / breeches on because of dysentery?

Does jamais mean always or never in this context?

Can a creature tell when it has been affected by a Divination wizard's Portent?

Will tsunami waves travel forever if there was no land?

What are the spoon bit of a spoon and fork bit of a fork called?

Phrase for the opposite of "foolproof"

You look catfish vs You look like a catfish

How to back up a running remote server?

Historically, were women trained for obligatory wars? Or did they serve some other military function?

How to stop co-workers from teasing me because I know Russian?

Build a trail cart

Pulling the rope with one hand is as heavy as with two hands?

What is the difference between `a[bc]d` (brackets) and `ab,cd` (braces)?

Need help understanding harmonic series and intervals

Airbnb - host wants to reduce rooms, can we get refund?

"ne paelici suspectaretur" (Tacitus)

Is std::next for vector O(n) or O(1)?

Concatenating 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;

14

2

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 InputIt or ForwardIt additionally meets the requirements of LegacyRandomAccessIterator, complexity is constant.

Does vector meet these requirements? And why "Legacy"?

c++

share|improve this question

edited Apr 11 at 11:26

El Profesor

11k32341

asked Apr 9 at 7:01

Martin PerryMartin Perry

5,31633269

• 
  
  
  

  
  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::vector reference).
  
  – Some programmer dude
  Apr 9 at 7:06
  
  

  
  
  
  

add a comment | 

14

2

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 InputIt or ForwardIt additionally meets the requirements of LegacyRandomAccessIterator, complexity is constant.

Does vector meet these requirements? And why "Legacy"?

c++

share|improve this question

edited Apr 11 at 11:26

El Profesor

11k32341

asked Apr 9 at 7:01

Martin PerryMartin Perry

5,31633269

• 
  
  
  

  
  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::vector reference).
  
  – 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 InputIt or ForwardIt additionally meets the requirements of LegacyRandomAccessIterator, complexity is constant.

Does vector meet these requirements? And why "Legacy"?

c++

share|improve this question

edited Apr 11 at 11:26

El Profesor

11k32341

asked Apr 9 at 7:01

Martin PerryMartin Perry

5,31633269

share|improve this question

edited Apr 11 at 11:26

El Profesor

11k32341

asked Apr 9 at 7:01

Martin PerryMartin Perry

5,31633269

share|improve this question

edited Apr 11 at 11:26

El Profesor

11k32341

asked Apr 9 at 7:01

Martin PerryMartin Perry

5,31633269

edited Apr 11 at 11:26

El Profesor

11k32341

edited Apr 11 at 11:26

El Profesor

11k32341

asked Apr 9 at 7:01

Martin PerryMartin Perry

5,31633269

asked Apr 9 at 7:01

Martin PerryMartin Perry

5,31633269

2 Answers
2

active

oldest

votes

17

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).

share|improve this answer

edited Apr 9 at 7:17

answered Apr 9 at 7:11

bartopbartop

3,5131132

add a comment | 

9

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."

share|improve this answer

answered Apr 9 at 7:11

Nikos C.Nikos C.

34.8k53967

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
);



);

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

17

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).

share|improve this answer

edited Apr 9 at 7:17

answered Apr 9 at 7:11

bartopbartop

3,5131132

add a comment | 

17

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).

share|improve this answer

edited Apr 9 at 7:17

answered Apr 9 at 7:11

bartopbartop

3,5131132

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).

share|improve this answer

edited Apr 9 at 7:17

answered Apr 9 at 7:11

bartopbartop

3,5131132

share|improve this answer

edited Apr 9 at 7:17

answered Apr 9 at 7:11

bartopbartop

3,5131132

answered Apr 9 at 7:11

bartopbartop

3,5131132

answered Apr 9 at 7:11

bartopbartop

3,5131132

9

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."

share|improve this answer

answered Apr 9 at 7:11

Nikos C.Nikos C.

34.8k53967

add a comment | 

9

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."

share|improve this answer

answered Apr 9 at 7:11

Nikos C.Nikos C.

34.8k53967

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."

share|improve this answer

answered Apr 9 at 7:11

Nikos C.Nikos C.

34.8k53967

share|improve this answer

answered Apr 9 at 7:11

Nikos C.Nikos C.

34.8k53967

answered Apr 9 at 7:11

Nikos C.Nikos C.

34.8k53967

answered Apr 9 at 7:11

Nikos C.Nikos C.

34.8k53967