How can I have a Foo* iterator to a vector of Foo?

Question

If I have a class that contains a std::list<Foo> and which has public methods begin() and end() to return iterators for that list, how can I implement additional methods to return iterators to a std::list<Foo*>, preferably without using boost?

I'd rather not maintain a parallel container of pointers.

Edit:

I have a large code base that I want to improve. It has a tree-like data structure with a base class that has a method to return the children of the object:

class FooBase
{
    // ...
    virtual bool getChildren(std::vector<FooBase *>& children);
    virtual size_t getChildrenCount() const { return 0; };
    // ...
}

There is a templated class that implements collections of child objects:

template <class T>
class FooCollection: public FooBase
{
public:
    typedef typename std::list<T> ContainerType;
    typedef typename ContainerType::iterator iterator;
    typedef typename ContainerType::const_iterator const_iterator;
private:
    ContainerType _items;
public:
    // ...
    const_iterator begin() const { return itemsM.begin(); };
    const_iterator end() const { return itemsM.end(); };
    iterator begin() { return itemsM.begin(); };
    iterator end() { return itemsM.end(); };

    virtual bool getChildren(std::vector<FooBase *>& children)
    {
        for (iterator it = itemsM.begin(); it != itemsM.end(); ++it)
            children.push_back(&(*it));
        return (itemsM.size() != 0);
    };
    // ...
};

The code uses both the iterators the different FooCollection<> classes provide (where the class is known), and FooBase::getChildren() when it iterates over the tree. I was thinking that FooBase::getChildren() could be replaced with iterators, but maybe I'm wrong?

Answer 1

Obtaining a collection or containers of pointers to the Foo elements in std::list<Foo> can be created, but it will be unreliable. The problem is that the list owns the Foo items (it made a copy) and it is allowed to change the location of these items without approval. So if you have a pointer to the 3rd element in the list, the list can move the element and your pointer will be invalid (without your knowledge).

A better solution is to dynamically allocate the Foo items and store smart pointers in different lists. This allows you to have the items sorted by different keys. For example, you could have list1 sorted by the first field in Foo and another list sorted by the 3rd field in Foo.

You would have to come up with custom sorting functors, since the default operation would be to sort by the value of the smart pointer, which is what nobody really wants.

Answer 2

The dereference operator overload of std::list<Foo>::iterator returns a reference to the corresponding Foo object. Therefore, if you want the address of the Foo object at std::list<Foo>::iterator object it, then you could use &*it, which has type Foo*.

If you really need an incrementable iterator over the pointers, then you could write an iterator class that stores a std::list<Foo>::iterator member, say it, returning &*it upon dereference. Note that such an iterator class can only satisfy the const iterator concept for the reason that &*it is an r-value.

Answer 3

This struct will help. It modifies the iterator such that dereferencing it returns a pointer instead of a reference:

struct PointerInstead : public list<Foo>::iterator {
  PointerInstead(const list<Foo>::iterator &x) : list<Foo>::iterator(x) { }
  Foo * operator * () const {
    Foo &f = *(*( (list<Foo>::iterator *) (this) ));
    return &f;
  }
};

Here's an example of its use:

  for(PointerInstead i = l.begin(); i != l.end(); i++)  {
    cout << i->first << '\t' << i->second << endl;
    printf("%p\n", (*i));
  }

Then you could write a pointerBegin() method that returns something like a PointerInstead(this->begin()).

Answer 4

How about writing a simple iterator class like below and using it

class myIterator : std::iterator<std::list<Foo>::iterator::iterator_category
                               , Foo*, std::list<Foo>::iterator::distance_type
                               , Foo**, Foo*&>
{
public:
    myIterator(const std::list<Foo>::iterator& lIt) : it(lIt) {}
    myIterator(const myIterator& myIt) : it(myIt.it) {}
    myIterator& operator++() {++it;return *this;}
    myIterator operator++(int)
    {
        myIterator copy(*this);
        ++it;
        return copy;
    }
    myIterator& operator--() {--it;return *this;}
    myIterator operator--(int)
    {
        myIterator copy(*this);
        --it;
        return copy;
    }
    bool operator==(const myIterator& rhs) {return it==rhs.it;}
    bool operator!=(const myIterator& rhs) {return it!=rhs.it;}
    Foo* operator*() {return &(*it);}
private:
    std::list<Foo>::iterator it;
};