I have a custom container that provides access to its elements via a unique ID (simple int64). This ID is not an index hoverer, so the users of the container shouldn't care about the order of elements inside.
I have implemented simplest possible forward iterator which provides operator++ to be able to use the container with range-based for loops.
But now, I want to get random element from the container by generating random number and using std::next, all of this in constant time, so forward iterator is not sufficient since its operator++ will be called N times introducing linear complexity. To achieve constant speed I have to provide operator+= which will make my forward iterator a kind of random access iterator (the container is capable of providing constant time access). Am i correct here? If so, it introduces a concept of order which isn't really applicable to my container.
So, I need constant time random access, but no strict order as in vector, for example. Where is the error in my logic?
Your strategy of modifying container::iterator to give you access to a "random" element is unidiomatic. Because you will always be picking a number between 0 and container::size(), and adding it to container::begin(), you need to hold onto the container, not just an iterator
What you should instead do is add a member template< class Generator > container::reference container::random_element( Generator& g ), delegating to std::uniform_int_distribution to pick the element, and leave container::iterator as a ForwardIterator (or potentially a BidirectionalIterator).