Unable to write my own iterator based on an STL iterator

Question

I have a little problem while trying to implement a container, Set, based on a linked list. Yeah, I know that there's an STL implementation of a set, but this is for homework. :)

So, this is what I have done so far:

my Set.h file looks like that:

template <class T>
class Set {
private:
    typedef std::list<T> base_container;
    base_container items;
public:
    class myIterator {
    public:
        typename base_container::iterator base_iterator;
        myIterator() { }
    };
    void addItem(const T item) {
        items.push_back(item);
    }
    typedef typename Set<T>::myIterator setIterator;
    setIterator begin() { return items.begin(); }
    setIterator end() { return items.end(); }
    Set<T>(void) { }
    ~Set<T>(void) { }
};

Now, main.cpp:

#include "Set.h"

int main(void) {
    Set<int> mySet;

    mySet.addItem(1);
    mySet.addItem(2);
    mySet.addItem(3);
    mySet.addItem(4);

    Set<int>::myIterator x;
    x = mySet.begin();       // produces an error about non-convertible types.

    return EXIT_SUCCESS;
}

The error is as follows:

error C2664: 'Set<T>::myIterator::myIterator(const Set<T>::myIterator &)' : cannot convert parameter 1 from 'std::_List_iterator<_Mylist>' to 'const Set<T>::myIterator &'

Clearly I messed things up, but I'm not sure which part of the code is actually the problem. Any suggestions about how to fix this? Any helpful information will be appreciated.

Thanks. :)

oh, yeah, of course, sorry: error C2664: 'Set<T>::myIterator::myIterator(const Set<T>::myIterator &)' : cannot convert parameter 1 from 'std::_List_iterator<_Mylist>' to 'const Set<T>::myIterator &' — Catalyst
– Catalyst, Commented Jan 19, 2013 at 14:15

Jonathan Wakely · Accepted Answer · 2013-01-19 14:47:00Z

There are many problems with your approach.

As others have said, you can't create your iterator type from the underlying type:

setIterator begin() { return items.begin(); }
setIterator end() { return items.end(); }

This can be solved by adding a constructor to your type:

class myIterator {
    typedef typename base_container::iterator base_iterator_type;
public:
    explicit myIterator(base_iterator_type i) : base_iterator(i) { }
    base_iterator_type base_iterator;
    myIterator() { }
};

This constructor should be explicit, which means you need to change how you create it:

setIterator begin() { return setIterator(items.begin()); }

The next problem is that your type doesn't implement the iterator interface, it doesn't provide operator++ or operator* etc. and it doesn't define nested types such as value_type and iteratory_category i.e. it's not an iterator (just giving it a name with "iterator" in it doesn't make it true!)

Once you fix that and your type is a valid iterator, you'll find your container can't be used with STL-style algorithms because it doesn't implement the container requirements. Among other things, it should provide a nested type called iterator not setIterator so that other template code can use S::iterator without caring if S is a std::set<T> or a Set<T>. Don't call it Set<T>::setIterator, just call it Set<T>::iterator. Also in this case there's no point defining myIterator (noone cares that it's yours! :-) then having a typedef to call it setIterator, just name the type with the right name in the first place and you don't need a typedef.

NPE · Accepted Answer · 2013-01-19 14:16:08Z

1

The problem is here:

setIterator begin() { return items.begin(); }
setIterator end() { return items.end(); }

The values you're trying to return have the wrong type. They are of type base_iterator and not setIterator, and there's no way to implicitly convert from the former to the latter.

answered Jan 19, 2013 at 14:16

NPE

503k114 gold badges970 silver badges1k bronze badges

3 Comments

Catalyst Over a year ago

OK, so how can I 'offer' an stl-like iterator? is deriving from std::iterator the only way for accomplishing that?

NPE Over a year ago

@Catalyst: The easiest is probably to encapsulate the underlying iterator in your iterator. Then you might wish to consider having a conversion constructor in your iterator class.

Stack Overflow is garbage Over a year ago

@Catalyst no, you don't actaully need to inherit from std::iterator. It is merely a helper class which gives you a few things for free, but you don't actually need it to create a STL-compatible iterator. You just have to expose the right typedefs, specialize the right traits, and overload the right iterators.

TemplateRex · Accepted Answer · 2013-01-19 23:18:12Z

1

You can derive from std::iterator<T> and provide the approprate iterator category tag. This will automatically give your iterator the required nested types such as value_type in terms of T. You will still need to write function members such as operator++ and operator* (depending on your iterator category, e.g. you also need operator[] for random access iterators)

edited Jan 19, 2013 at 23:18

answered Jan 19, 2013 at 14:15

TemplateRex

70.9k21 gold badges176 silver badges316 bronze badges

1 Comment

Jonathan Wakely Over a year ago

but won't give it operator++ or operator*

Collectives™ on Stack Overflow

Unable to write my own iterator based on an STL iterator

3 Answers 3

Comments

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related