Is std::next for vector O(n) or O(1)? The 2019 Stack Overflow Developer Survey Results Are In Unicorn Meta Zoo #1: Why another podcast? Announcing the arrival of Valued Associate #679: Cesar Manara 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?

Deal with toxic manager when you can't quit

Why did Peik Lin say, "I'm not an animal"?

What do I do when my TA workload is more than expected?

Why don't hard Brexiteers insist on a hard border to prevent illegal immigration after Brexit?

Presidential Pardon

Windows 10: How to Lock (not sleep) laptop on lid close?

What was the last x86 CPU that did not have the x87 floating-point unit built in?

Can we generate random numbers using irrational numbers like π and e?

Is it ok to offer lower paid work as a trial period before negotiating for a full-time job?

Is this wall load bearing? Blueprints and photos attached

Did the new image of black hole confirm the general theory of relativity?

What aspect of planet Earth must be changed to prevent the industrial revolution?

Can the DM override racial traits?

Why can't wing-mounted spoilers be used to steepen approaches?

Why not take a picture of a closer black hole?

Student Loan from years ago pops up and is taking my salary

How do spell lists change if the party levels up without taking a long rest?

Are spiders unable to hurt humans, especially very small spiders?

How did the audience guess the pentatonic scale in Bobby McFerrin's presentation?

What force causes entropy to increase?

Using dividends to reduce short term capital gains?

Keeping a retro style to sci-fi spaceships?

Do I have Disadvantage attacking with an off-hand weapon?

Is there a writing software that you can sort scenes like slides in PowerPoint?



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



The 2019 Stack Overflow Developer Survey Results Are In
Unicorn Meta Zoo #1: Why another podcast?
Announcing the arrival of Valued Associate #679: Cesar Manara
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;








12















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










share|improve this question



















  • 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


















12















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










share|improve this question



















  • 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














12












12








12


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










share|improve this question
















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















share|improve this question













share|improve this question




share|improve this question








edited yesterday









El Profesor

11k32341




11k32341










asked Apr 9 at 7:01









Martin PerryMartin Perry

5,22333267




5,22333267







  • 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













  • 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








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













2 Answers
2






active

oldest

votes


















15














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
































    8















    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























      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


















      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









      15














      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





























        15














        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



























          15












          15








          15







          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















          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














          share|improve this answer



          share|improve this answer








          edited Apr 9 at 7:17

























          answered Apr 9 at 7:11









          bartopbartop

          3,4631132




          3,4631132























              8















              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



























                8















                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

























                  8












                  8








                  8








                  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














                  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












                  share|improve this answer



                  share|improve this answer










                  answered Apr 9 at 7:11









                  Nikos C.Nikos C.

                  34.4k53967




                  34.4k53967



























                      draft saved

                      draft discarded
















































                      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.




                      draft saved


                      draft discarded














                      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





















































                      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







                      Popular posts from this blog

                      Sum ergo cogito? 1 nng

                      三茅街道4182Guuntc Dn precexpngmageondP