Iterators should work on containers without random-access iterators as long as they have an O(1) container::size() method and an efficient std::advance() specialization (which is certainly possible with red-black trees used for set and map – though implementations may vary).