CODEWITHSUNDEEP
c++stliterator
cibercitizen1
cibercitizen1

Reputation: 21476

Making custom containers iterable

When defining my custom containers, it is more easy and very general (for me) making them iterable by just adding size() and []. This is, having the following member methods:

unsigned int size() const { . . . }
T & operator[] (unsigned int pos) { . . . }

In order to benefit from the STL algorithms, I provide an adaptor from any container class having the above methods to an iterator valid for the STL functions. With it, I can write easily things like

MyContainer<int, 5> mc;
IteratorFromContainer<MyContainer<int,5>, int> iter (&mc);
int i=1; for (auto & e : iter) { e = i++; }
for (auto e=iter.begin(); e!=iter.end(); ++e) { cout << (*e) << endl; }  
int sum = std::accumulate(iter.begin(), iter.end(), 0);
int prod = std::accumulate(iter.begin(), iter.end(), 1, [](int a, int b) {return a*b;});

Surprisingly (to me) my adaptor (template) class works (the above sample code) equally well with any of the following (1, 2, or 3):

template<typename Container, typename T>
// 1. 
class  IteratorFromContainer : public std::iterator<input_iterator_tag, T>  {
// 2. 
class  IteratorFromContainer : public std::iterator<output_iterator_tag, T>  {
// 3. 
class  IteratorFromContainer {

Why?. Should not the adaptor derive from std::iterator always? What kind of iterator (what _tag) should I use, considering that the iterator is based in random access (size() and []) and has output and input capabilities: RandomAccess, ContinguousIterator?

Thanks

Upvotes: 1

Views: 1932

Answers (1)

Mooing Duck
Mooing Duck

Reputation: 66912

C++ uses a thing called duck-typing, which has awesome pros, and some really wierd cons. One of those cons are, if you break the interface contract, it might not notice until much later, if ever. When you use the for-loops, the compiler uses the iterator's copy constructor, operator++(), operator==(...) and operator*(), which you have, so it sometimes may work fine (I'm pretty sure GCC will point out the error in your options #2 & #3 though). I don't know the exact requirements for std::accumulate, but most likely they're similar. And so as long as you have those your code "works".

However, with options #2 and #3, you're breaking the "contract" about what it means to be an iterator. As such, the compiler or library may receive an update, and your code may stop working. The requirements for each iterator type depends on the type of iterator you're modeling, for more details see this page: How to implement an STL-style iterator and avoid common pitfalls?. However, the minimum requirements are you must have these operations: 

    iterator(const iterator&);
    ~iterator();
    iterator& operator=(const iterator&);
    iterator& operator++(); //prefix increment
    reference operator*() const;

and also std::iterator_traits<IteratorFromContainer> must have these typedefs:

typedef ???? difference_type; //almost always ptrdif_t
typedef ???? value_type; //almost always T
typedef ???? reference; //almost always T& or const T&
typedef ???? pointer; //almost always T* or const T*
typedef ???? iterator_category;  //usually std::forward_iterator_tag or similar

For simplicity, if you don't specialize std::iterator_traits yourself, it will check if your iterator has those typedefs, and if so, it will copy the ones from your iterator. std::iterator has these typedefs, and so if you inherit from it, you automatically have the typedefs, and so std::iterator_traits will automatically have them, so you'll meet the contractual guarantees. But inheriting from std::iterator is not necessary, you can add the typedefs yourself, or specialize iterator_traits.

Since you're working with operator[], it makes sense for you to use std::random_access_iterator_tag, which has many more requirements than those listed above. Again, see my other answer linked above for details on exactly what those members are.

Upvotes: 2

Related Questions