Complexity of iterating through std :: set
I know that the time complexity of iterating over the entire set takes O(n)
time, where n
is the size of the set. The question is, what is the complexity of iterating between two iterators, itBegin
and itEnd
? Maybe it is something like O(itEnd - itBegin + log n)
, but I cannot prove it.
source to share
The algorithmic complexity of iterating an integer std::set
is O (n). But the time consumption is greater than iteration std::vector
because the vector uses a single block of memory.
If you want to iterate between 2 iterators itBegin
and itEnd
, that will also be O (n1), but n1
something like std::distance(itEnd, itBegin)
, which is less than n
the first case. This is the case when you already have an iterator.
If you want to find these positions by value before iterating (you don't have iterators at the beginning) - this becomes O(log n) + O(n2)
, which really is O(log n)
. Let's say if you want to iterate from value 123
to end - this will be O(log n)
to find an iterator for 123
and O(n2)
for iteration.
source to share