Say I have deque element index "i". Deque allows element access by index in constant time. So it looks like we can quickly find element position in memory. But when it comes to get an iterator (to pass to erase() for example), we need to make begin() + i which will take linear time. Is it possible to convert index -> iterator in constant time? If not what's the difference between indexing/creating an iterator? Is the opposite operation possible: pointer to element/iterator -> index (without iterating to the begin/end)?
we need to make begin() + i which will take linear time.
No it won't.
Iterators that support operator+ should do it in constant time (this is true for the standard iterators, user-defined iterators could define operator+ that is linear, but that would be unconventional).
Iterators that don't support it in constant time need to be advanced with std::advance not operator+
std::deque::iterator is a random-access iterator, so begin() + i is valid and takes constant-time.