14

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

JFMR
  • 23,265
  • 4
  • 52
  • 76
Martin Perry
  • 9,232
  • 8
  • 46
  • 114
  • 13
    "Constant" means `O(1)`. – Some programmer dude Apr 09 '19 at 07:03
  • 1
    I know that, but I dont know If it aplies to vector, since I dont understand LegacyRandomAccessIterator. Why Legacy? – Martin Perry Apr 09 '19 at 07:04
  • 4
    @MartinPerry Follow the link? In the page you pull the quote from, the word "[LegacyRandomAccessIterator](https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator)" 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`](https://en.cppreference.com/w/cpp/container/vector) reference). – Some programmer dude Apr 09 '19 at 07:06

2 Answers2

18

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

bartop
  • 9,971
  • 1
  • 23
  • 54
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."

Nikos C.
  • 50,738
  • 9
  • 71
  • 96