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!

Azeem
  • 11,148
  • 4
  • 27
  • 40
bunny
  • 1,797
  • 8
  • 29
  • 58
  • https://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 '17 at 02:45

1 Answers1

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

A.S.H
  • 29,101
  • 5
  • 23
  • 50
  • 1
    To add to your answer, [std::next](http://en.cppreference.com/w/cpp/iterator/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: http://ideone.com/so0XEH. – Azeem Jul 30 '17 at 04: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 '17 at 04:23