What is the runtime complexity of 'advance()' when when used for std::set in c++?

user_9468628 0
Viewed 1104

I am curious about the runtime complexity of std::advance() when used for std::set.

eg.

std::set<in> s;
auto x=s.begin();
advance(x,n/2);

how much time (order of n) does the above code take.

stl c++
2 Answers

std::set has bidirectional iterators. Bidirectional iterators are incrementable and decrementable, but not random access addressable -- meaning that to reach the Nnth node requires incrementing N times.

This means that advancing by N will be O(N)

user_16787700

According to the documentation of std::advance over at cppreference:

Complexity

Linear.

However, if InputIt additionally meets the requirements of LegacyRandomAccessIterator, complexity is constant.

So unless you have a LegacyRandomAccessIterator on your hands (like the one of, say int[100]) you have linear complexity. A std::set however, has "only" a LegacyBidirectionalIterator, which is weaker than random access.

So, you here, you are guaranteed to have linear runtime.

user_4307660
Related