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

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

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