Making custom containers iterable

Question

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

Very related but not sure if duplicate: [How to implement an STL-style iterator and avoid common pitfalls?](http://stackoverflow.com/q/8054273/845092) — Mooing Duck, Dec 11 '14 at 20:21
Note that in your examples, `IteratorFromContainer` does not appear to be trying to be an iterator at all. It's an adaptor class, that _is itself iterable_. The type of `iter.begin()` should be an iterator. What type of iterator depends on the interface of that type, but I'd speculate it's easy enough to make it random access, which would use the `std::random_access_iterator_tag`. — Mooing Duck, Dec 11 '14 at 20:24
Also, if you're crafty, you don't need people to pass `T` to `IteratorFromContainer`, you can deduce it from `decltype(mc[0])`. — Mooing Duck, Dec 11 '14 at 20:26
`IteratorFromContainer` needs to implement the functions corresponding to the given iterator tag (like `std::output_iterator_tag`). The `iterator` base class only provides some typedefs. It it doesn't, the iterator may still work when the code using it doesn't make use of functionality that it promises but doesn't have. Concepts in C++17 will probably allow the compiler produce errors in such cases. — tmlen, Dec 11 '14 at 20:43
@MooingDuck Thanks for your advice. Well, `IteratorFromContainer` is at the same time the iterable and the iterator: `IteratorFromContainer begin () const { return IteratorFromContainer(theContainer); }` — cibercitizen1, Dec 11 '14 at 20:46
@cibercitizen1: That's... very weird and I recommend against it. Better to have a give line adaptor class that doesn't do anything but create iterators. — Mooing Duck, Dec 11 '14 at 21:59
@cibercitizen1: Like thus: http://coliru.stacked-crooked.com/a/548993ad8fcc075b — Mooing Duck, Dec 11 '14 at 22:22

score 2 · Accepted Answer · edited May 23 '17 at 11:57

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.

Making custom containers iterable

1 Answers1