If you're using them, there's no need to get SCAREd... just ignore their SCARY-ness.
If you're making them, that means you have to make your iterators independent of the container's allocator type, and of other generic parameters to the container that don't affect the iterators.