In fact std::string::iterator IS an example of an iterator which is not guaranteed to iterate over contiguous memory.