Programmer - How to return a generic iterator (independent of particular container)?

Programmer Question

I'd like to design a class Foo that stores various data of different types and returns iterators over them. It's supposed to be generic, so the user of Foo does not know how the data is stored (Foo could be using std::set or std::vector or whatever).

I'm tempted to write an interface like this:

class Foo {
  class FooImpl;
  FooImpl* impl_;
public:
  const Iterator<std::string>& GetStrings() const;
  const Iterator<int>& GetInts() const;
};

where Iterator is something like this (like iterators in .NET):

template<class T>
class Iterator {
public:
  const T& Value() const = 0;
  bool Done() const = 0;
  void Next() = 0;
};

But I know that kind of iterator is not standard in C++, and it's better to use iterators the way the STL does, so you can use the STL algorithms on them.

How can I do that? (Do I need iterator_traits by any chance?)