Interface-based programming in C++ in combination with iterators. How too keep this simple?

Question

In my developments I am slowly moving from an object-oriented approach to interface-based-programming approach. More precisely:

• in the past I was already satisfied if I could group logic in a class
• now I tend to put more logic behind an interface and let a factory create the implementation

A simple example clarifies this.

In the past I wrote these classes:

• Library
• Book

Now I write these classes:

• ILibrary
• Library
• LibraryFactory
• IBook
• Book
• BookFactory

This approach allows me to easily implement mocking classes for each of my interfaces, and to switch between old, slower implementations and new, faster implementations, and compare them both within the same application.

For most cases this works very good, but it becomes a problem if I want to use iterators to loop over collections.

Suppose my Library has a collection of books and I want to iterator over them. In the past this wasn't a problem: Library::begin() and Library::end() returned an iterator (Library::iterator) on which I could easily write a loop, like this:

for (Library::iterator it=myLibrary.begin();it!=mylibrary.end();++it) ...

Problem is that in the interface-based approach, there is no guarantee that different implementations of ILibrary use the same kind of iterator. If e.g. OldLibrary and NewLibrary both inherit from ILibrary, then:

• OldLibrary could use an std::vector to store its books, and return std::vector::const_iterator in its begin and end methods
• NewLibrary could use an std::list to store its books, and return std::list::const_iterator in its begin and end methods

Requiring both ILibrary implementations to return the same kind of iterator isn't a solution either, since in practice the increment operation (++it) needs to be implemented differently in both implementations.

This means that in practice I have to make the iterator an interface as well, meaning that application can't put the iterator on the stack (typical C++ slicing problem).

I could solve this problem by wrapping the iterator-interface within a non-interface class, but this seems a quite complex solution for what I try to obtian.

Are there better ways to handle this problem?

EDIT: Some clarifications after remarks made by Martin.

Suppose I have a class that returns all books sorted on popularity: LibraryBookFinder. It has begin() and end() methods that return a LibraryBookFinder::const_iterator which refers to a book.

To replace my old implementation with a brand new one, I want to put the old LibraryBookFinder behind an interface ILibraryBookFinder, and rename the old implementation to OldSlowLibraryBookFinder.

Then my new (blistering fast) implementation called VeryFastCachingLibraryBookFinder can inherit from ILibraryBookFinder. This is where the iterator problem comes from.

Next step could be to hide the interface behind a factory, where I can ask the factory "give me a 'finder' that is very good at returning books according popularity, or according title, or author, .... You end up with code like this:

ILibraryBookFinder *myFinder = LibraryBookFinderFactory (FINDER_POPULARITY);
for (ILibraryBookFinder::const_iterator it=myFinder->begin();it!=myFinder.end();++it) ...

or if I want to use another criteria:

ILibraryBookFinder *myFinder = LibraryBookFinderFactory (FINDER_AUTHOR);
for (ILibraryBookFinder::const_iterator it=myFinder->begin();it!=myFinder.end();++it) ...

The argument of LibraryBookFinderFactory may be determined by an external factor: a configuration setting, a command line option, a selection in a dialog, ... And every implementation has its own kind of optimizations (e.g. the author of a book doesn't change so this can be a quite static cache; the popularity can change daily which may imply a totally different data structure).

Answer 1

You are mixing metaphors here.

If a library is a container then it needs its own iterator it can't re-use an iterator of a member. Thus you would wrap the member iterator in an implementation of ILibraryIterator.

But strictly speaking a Library is not a container it is a library.
Thus the methods on a library are actions (think verbs here) that you can perform on a library. A library may contain a container but strictly speaking it is not a container and thus should not be exposing begin() and end().

So if you want to perform an action on the books you should ask the library to perform the action (by providing the functor). The concept of a class is that it is self contained. User should not be using getter to get stuff about the object and then put stuff back the object should know how to perform the action on itself (this is why I hate getters/setters as they break encapsulation).

class ILibrary
{
    public:
         IBook const& getBook(Index i) const;

         template<R,A>
         R checkBooks(A const& librarianAction);
};

Answer 2

If your libraries hold a lot of books, you should consider putting your "aggregate" functions into your collections and pass in the action want it to be perform.

Something in the nature of:

class ILibrary
{
public:
  virtual ~Ilibrary();
  virtual void for_each( boost::function1<void, IBook> func ) = 0;
};

LibraryImpl::for_each( boost::function1<void, IBook> func )
{
    std::for_each( myImplCollection.begin(), myImplCollection.end(), func );
}

Although probably not exactly like that because you may need to deal with using shared_ptr, constness etc.

Answer 3

For this purpose (or in general in implementations where I make heavy use of interfaces), I have also created an interface for an iterator and other objects return this. It becomes pretty Java-a-like.

If you care about having the iterator in most cases of the stack: Your problem is of course that you don't really know the size of the iterator at compile time so you cannot allocate a stack variable of the correct size. But if you really care a lot about this: Maybe you could write some wrapper which either allocates a specific size on the stack (e.g. 128 bytes) and if the new iterator fits in, it moves it there (be sure that your iterator has a proper interface to allow this in a clean way). Or you could use alloca(). E.g. your iterator interface could be like:

struct IIterator {
   // iterator stuff here
   // ---
   // now for the handling on the stack
   virtual size_t size() = 0; // must return own size
   virtual void copyTo(IIterator* pt) = 0;
};

and your wrapper:

struct IteratorWrapper {
   IIterator* pt;
   IteratorWrapper(IIterator* i) {
       pt = alloca(i->size());
       i->copyTo(pt);
   }
   // ...
};

Or so.

---

Another way, if in theory it would be always clear at compile time (not sure if that holds true for you; it is a clear restriction): Use functors everywhere. This has many other disadvantages (mainly having all real code in header files) but you will have really fast code. Example:

template<typename T>
do_sth_with_library(T& library) {
   for(typename T::iterator i = library.begin(); i != library.end(); ++i)
      // ...
}

But the code can become pretty ugly if you do rely too heavy on this.

---

Another nice solution (making the code more functional -- implementing a for_each interface) was provided by CashCow.

With current C++, this could make the code also a bit complicated/ugly to use though. With the upcoming C++0x and lambda functions, this solution can become much more clean.