How to realize a custom implementation of a std-like iterator?

Question

I have written a very simple file managing database that basicly looks like this:

class FileDB
{
public:
    FileDB(std::string dir) : rootDir(dir) { }

    void loadFile(std::string filename, File &file) const;
    void saveFile(std::string filename, const File &file) const;

private:
    std::string rootDir;
}

Now I would like to iterate through all files contained in the database like using a std::iterator:

void iterateFiles()
{
    FileDB filedb("C:\\MyFiles");

    for (FileDB::iterator file_it = filedb.begin(); file_it != filedb.end(); ++file_it)
    {
        File f = *file_it;
        // do something with file
    }
}

I've read answers to similar questions, some suggesting to derive std::iterator, some to use std::iterator_traits, but I don't really understand how to do that. What can possibly go wrong when trying to implement a custom iterator? And what's a simple yet elegant way to do it?

EDIT: Please don't consider using boost, my question is of more conceptual nature.

EDIT 2:

The FileDB works like this:

• rootDir

  • foo1
    • bar1
      • foo1bar1_1.txt
      • foo1bar1_2.txt
    • bar2
      • foo1bar2_1.txt
      • foo1bar2_2.txt

  • foo2

  • fooN

    • barM

      • fooNBarM_x.txt

So basicly, I can find a file by its name.

As my container is not in memory, I don't have pointers to its data. So my idea was to store the file's path in the iterator. This way, I can implement operator== with a string comparison, as the paths should be unique. The iterator returned from fileDB.end() would be an empty string and operator* would call fileDB::loadFile() with its filepath.

My biggest concern is about operator++. Having the filename, I can find out the containing directory and search for the next file, but this is really ineffective. Any ideas on how to do that? Or am I completely wrong with my whole concept?

Answer 1

Writing iterators yourself is hardly ever pretty. The pretiest way to add an iterator to your classes is to reuse an existing one. You should be aware, that pointers for example are just as good as iterators in C++ so there are many ways to provide an iterator without actually having to write your own.

This is basically how C++ works in many ways. It tries to make the language expendable and simple for end users by putting a lot of burden on library writers. I.e. library writers can write all the unpretty stuff, so the end user doesn't have to. Iterators are usally a part of a library.

Having said that, here comes the actual ugly part:

To be able to write your own iterators, here are some things you need to be aware of.

Type traits:

Type traits are a simple mechanism to add aditional information to types in C++ which works even with types which cannot be changed themselves. For example for an iterator it is important to know what it iterates over (i.e. the contained type). The way to get this information for a given iterator depends a lot on the iterator. For iterators which actually are objects, you can add typedefs in the class and use those, but for iterators which are pointers you need to infer it from the pointer type. To make this possible the information is stored in a type trait instead so there is a single place an code can look this information. This is the std::iterator_traits type trait.

std::iterator_traits work on anything, which is derived from the std::iterator template as well as on any kind of pointer, without any tweaking. So often it is best to use std::iterator as a base to avoid having to write your own traits specialisation. In case you cannot do this, it is still possible to provide the necessary traits, but it will be harder.

Tag classes and iterator types:

There are several different types of iterators available in C++ which have different behaviour and can/cannot do a lot of different things. Have a look at http://cplusplus.com/reference/std/iterator/ to see what kind of iterators are available and what they can do. The diagrams are not meant to be in an object oriented way (i.e. an input_iterator is neither a sub nor a base class of a forward_iterator), but rather as an API kind of derivation. I.e. you can use all algorithms which were written for an input iterator also with an forward iterator. The table on the page will tell you which methods you have to provide for each category.

Since these categories are not actually sub classes of each other (they shouldn't be, especially when comming from different types of collections), another mechanism is used to identify the capabilities of each iterator. An empty tag class is also included in the std::iterator_traits describing each iterator, which tells what this iterator can do and what it cannot do. If you do not write your own traits, you need to supply this tag class to the std::iterator template upon instantiation.

Example:

This example is taken from the cplusplus.com section on iterators:

class myiterator : public iterator<input_iterator_tag, int>
{
  int* p;
public:
  myiterator(int* x) :p(x) {}
  myiterator(const myiterator& mit) : p(mit.p) {}
  myiterator& operator++() {++p;return *this;}
  myiterator operator++(int) {myiterator tmp(*this); operator++(); return tmp;}
  bool operator==(const myiterator& rhs) {return p==rhs.p;}
  bool operator!=(const myiterator& rhs) {return p!=rhs.p;}
  int& operator*() {return *p;}
};

This iterator does not really make sense, since it only wraps a pointer, which could also have been used directly. However it can serve as an explanation. The iterator is derived from std::iterator as an input_iterator by supplying the appropriate tag. Also the template is told, that this iterator is iterating over ints. All other types, which are needed difference_type, reference, poiner etc. are automatically infered by the template. In some cases it may make sense to change some of these types manually (for example a std::shared_ptr has to be used as a pointer sometimes). Also the traits needed for this iterator will exist automatically, since it is already derived from std::iterator and the std::iterator_traits know where to find all necessary information.