Expose C++ container iterator to user

Question

Say I have a class Foo, which contains some kind of container, say a vector<Bar *> bars. I want to allow the user to iterate through this container, but I want to be flexible so that I might change to a different container in the future. I'm used to Java, where I could do this

public class Foo
{
    List<Bar> bars;         // may change to a different collection

    // User would use this
    public Iterator<Bar> getIter()
    {
        return bars.iterator();    // can change without user knowing
    } 
}

C++ iterators are designed to look like raw C++ pointers. How do I get the equivalent functionality? I could do the following, which returns the beginning and end of the collection as an iterator that the user can walk himself.

class Foo
{
    vector<Bar *> bars;

public:
    // user would use this
    std::pair<vector<Bar *>::iterator , vector<Bar *>::iterator > getIter()
    {
        return std::make_pair(bars.begin(), bars.end()); 
    }
}

It works, but I feel I must be doing something wrong.

1. Function declaration exposes the fact that I'm using a vector. If I change the implementation, I need to change the function declaration. Not a huge deal but kind of goes against encapsulation.

2. Instead of returning a Java-like iterator class that can do its own bounds check, I need to return both the .begin() and .end() of the collection. Seems a bit ugly.

Should I write my own iterator class?

Answer 1

You could adapt the vector behaviour and provide the same interface:

class Foo
{
    std::vector<Bar *> bars;

public:
    typedef std::vector<Bar*>::iterator iterator;

    iterator begin() {
        return bars.begin();
    }

    iterator end() {
        return bars.end();
    }
};

Use Foo::iterator as the iterator type outside of the container.

However, bear in mind that hiding behind the typedef offers less than it seems. You can swap the internal implementation as long as it provides the same guarantees. For example, if you treat Foo::iterator as a random access iterator, then you cannot swap a vector for a list internally at a later date without a comprehensive refactoring because list iterators are not random access.

You could refer to Scott Meyers Effective STL, Item 2: beware the illusion of container independent code for a comprehensive argument as to why it might be a bad idea to assume that you can change the underlying container at any point in future. One of the more serious points is iterator invalidation. Say you treat your iterators as bi-directional, so that you could swap a vector for a list at some point. An insertion in the middle of a vector will invalidate all of its iterators, while the same does not hold for list. In the end, the implementation details will leak, and trying to hide them might be Sisyphus work...

Answer 2

You are looking for type erasure. Basically you want an iterator with vector erased from it. This is roughly what it looks like:

#include <vector>
#include <memory>
#include <iostream>

template<class T>
class Iterator{ //the class that erases the iterator type
    //private stuff that the user should not care about
    struct Iterator_base{
        virtual void increment() = 0;
        virtual T &dereference() = 0;
        virtual ~Iterator_base() = default;
    };
    std::unique_ptr<Iterator_base> iter;
    template<class Iter>
    class Iterator_helper : public Iterator_base{
        void increment() override{
            ++iter;
        }
        T &dereference() override{
            return *iter;
        }
        Iter iter;
    public:
        Iterator_helper(const Iter &iter) : iter(iter){}
    };
public:
    template<class Iter>
    Iterator(const Iter &iter) : iter(new Iterator_helper<Iter>(iter)){}
    //iterator functions for the user
    Iterator &operator ++(){
        iter->increment();
        return *this;
    }
    T &operator *(){
        return iter->dereference();
    }
};

struct Bar{
    Bar(int i) : i(i){};
    int i;
};

class Foo
{
    std::vector<Bar> bars;

public:
    Foo(){ //just so we have some elements to point to
        bars.emplace_back(1);
        bars.emplace_back(2);
    }
    // user would use this
    Iterator<Bar> begin()
    {
        return bars.begin();
    }
};

int main(){
    Foo f;
    auto it = f.begin();
    std::cout << (*it).i << '\n'; //1
    ++it; //increment
    std::cout << (*it).i << '\n'; //2
    (*it).i++; //dereferencing
    std::cout << (*it).i << '\n'; //3
}

You can now pass any iterator (actually anything) to Iterator that support pre-increment, dereferencing and copy constuction, completely hiding the vector inside. You can even assign Iterators that have a vector::iterator inside to an Iterator that has a list::iterator inside, though that may not be a good thing.

This is a very bare-bone implementation, you would want to also implement operators ++ for post-increment, --, ->, ==, =, <, >, <=, >=, != and possibly []. Once you are done with that you need to duplicate the code into a Const_Iterator. If you don't want to do that yourself consider using boost::type_erasure.

Also note that you are paying for this encapsulation with unnecessary dynamic memory allocations, cache misses, virtual function calls that probably cannot be inlined and triply redundant code (same functions in Iterator, Iteratr_base and Iterator_helper).

vector is still present in the private part of Foo, you can get rid of that with a pimpl, adding another level of indirection.

I feel like this bit of encapsulation is not worth the cost, but your mileage may vary.