2

Suppose I have an std::unordered_set<int> named as myset and I want to return a random number from myset in O(1) time. I first use rand() to generate a random number as:

int n = rand() %  myset.size();

Then, I do:

myset.begin() + n;

I would like to know if myset.begin() + n is in O(n) or O(1)?

Thanks!

1
  • stackoverflow.com/a/31113618/493106 states that, at least in GCC, it maintains a linked list across the entries, so it would be O(n) - though as ash said, not sure you can anctually use operator+ on the iterator.
    – xaxxon
    Jul 30, 2017 at 2:45

1 Answer 1

6

The std::unordered_set<>::iterator (which results from myset.begin()) is a Constant ForwardIterator. Ref

A ForwardIterator supports incrementation (++myIterator) but not random incrementation, unlike the RandomAccessIterator.

Therefore myset.begin() + n is not guaranteed to compile by the standard. It doesn't compile here.

You can do the ++ incrementation n times with a loop, but then of course, complexity is at least O(n).

2
  • 1
    To add to your answer, std::next would be the right choice to get an iterator as required by the statement myset.begin() + n i.e. std::next( myset.begin(), n ). Example: ideone.com/so0XEH.
    – Azeem
    Jul 30, 2017 at 4:02
  • 1
    @Azeem good addition thanks. std:next takes a ForwardIterator so its internal implementation is likely a similar loop when such iterator that does not support random access. Should be the case for unordered_set in most implementations, but exceptions are theoretically possible.
    – A.S.H
    Jul 30, 2017 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.