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

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?)

Answer 1

Use a typedef to return an boost::iterator_range. For example (never mind the names),

class Container
{
     typedef std::vector<int> Collection; 

     public:
     typedef boost::iterator_range<Collection::iterator> CollectionRange;
     typedef Collection::iterator CollectionIterator;
     Range range() const {
          return make_iterator_range(collection_.begin(), collection_.end());
     }

     private:
     Collection collection_;          
};

The user code will be

Container c;
// ...
FOREACH(int i, c.range()) { //... }
Container::Range r = c.range();
for(Container::iterator j = r.begin(); j!= r.end(); j++) { // ... }

This is not generic, but the same idea can be used with templates.

Answer 2

A c++ class with iterators has to provide at least two functions if they have to work with the std library

iterator begin() //returns an iterator at starting pos
iterator end() //returns an iterator one past end or just invald

The iterator has to overload the increment operators, equals and *

iterator operator++()
iterator operator==()//make sure that an invalid iterator equals end()
T& operator*()

You can use the iterator class to wrap around the iterator of the internal storage to ensure that the user is limited to these methods.

template <typename T> iter
{
   iter(T::iterator& intern)
   T::value_type& operator*(){return *intern}
  iter operator++(){return iter(++intern);}
  bool operator==(iter const& other)const{return intern == other.intern;}
}

Where T is the type of your container.(The class is incomplete and I may have mixed something up)

Answer 3

Do you understand why the STL chose to put iterator implementation details in the header file? JIT frameworks are able to inline across compilation units, but C++ can only inline within a compilation unit. Advancing through a sequence is much faster when inlined, the cost of a function call dominates actually traversing the data structure.

If you really want to hide the implementation details, go ahead. You could make an STL-compatible iterator that implements operator++ and operator!= and operator-> in terms of protected virtual functions, the Next, Done, and Value you've mentioned would be decent names. Just expect to pay for the encapsulation with lower performance.

Answer 4

To fulfill the requirement that the particular container (vector, set, ...) is not mentioned in the header file, and the user will be able to iterate over all strings, is to use the visitor pattern. The downside, of course, is that the user won't be able to use the STL algorithms on the strings.

// foo.h
class StringVisitor {
public:
  void accept(const std::string& str) {
    std::cout << str << std::endl;
  }
};
class Foo {
  class Impl;
  Impl* impl_;
public:
  Foo();
  ~Foo();
  void VisitStrings(StringVisitor v) const;
};

// foo.cc
class Foo::Impl {
  typedef std::vector<std::string> StringContainer;
  StringContainer str_;
public:
  Impl() {
    str_.push_back("a");
    str_.push_back("b");
  }
  void VisitStrings(StringVisitor v) const {
    for(StringContainer::const_iterator it = str_.begin();
    it != str_.end(); ++it){
      v.accept(*it);
    }
  }  
};

Foo::Foo() : impl_(new Impl()) {}
Foo::~Foo() {delete impl_;}
void Foo::VisitStrings(StringVisitor v) const {
  impl_->VisitStrings(v);
}

// main.cc
int main() {
  Foo foo;
  foo.VisitStrings(StringVisitor());
  return 0;
}

Answer 5

It almost looks like you're trying to create container-independent code, which is not (in general) a good idea, unless you are writing an algorithm which can operate solely with iterators. (See Scott Myers Effective STL Item 2: Beware the illusion of container-independent code)

The problem is that most of the standard containers do not provide overlapping functionality. If you're writing code for a particular container, assume you're writing code for that container. Don't bother trying to make it container-independent.