Creating a Custom Iterator over a Novel Container

[Vituperous]

Greetings. I'm very glad that websites like this exist, and that domain experts such as yourselves take the time to answer Very Dumb Questions such as this one for people such as myself.

It's my understanding that iterators are one of the fundamental constructs of C++. Things I've read suggest that there are essentially three things that can, and should, be passed around: functions, simple variables, and iterators.

Iterators reference a container structure filled with interesting data, and have two boundaries, a beginning and an end, and offer the ability to easily perform an operation over the span of elements between the two. The beginning boundary is found with a method called begin, and the ending boundary is found with a method called end; these methods return something called iterator objects [terminology?], which have, among other things (which other things?), a reference to the relevant container, and a pointer to the "current" element in the container between the boundaries.

Iterators have three fundamental operations: a dereference operator (operator*()), an equality operator (operator!=()), and an incremental operator (operator++()). (Assuming that an instantiated operator [terminology?] is named ite, the latter operator accommodates only the ++ite, but doesn't include the ite++ operation, which as a quirk of C++ is covered by the operator++(int x) operator method overload [terminology?].)

Suppose that I have a container that I wish to iterate over. Normally, it seems, it would be sufficient to expose the underlying iterator mechanism of the "child" container, but in this case the container has no native iterator.

Suppose that this container is a bitset of fixed size, e.g.,

std::bitset<9> set("111111111");,
std::bitset<9> set("110110101");,
or std::bitset<9> set("110100011");,

and the bit positions are related to the sequential values as follows: 987654321,

and I would like to iterate over this bitset with a range-based for-loop, e.g.,

for (auto b : B) {
    std::cout << b;
} std::cout << std::endl;

,

which should produce, for the latter bitset example above, the output 12689\n.

As I understand it, I need to construct two classes, one a "parent" container of the bitset, with various attributes, including things to make it recognizable as compatible with iterator operations, including but not limited to the begin() and end() methods; and one an "iterator" class, which will, among other things, store the current increment of the iterator, and provide various operator overloads [terminology?] such as dereferencing (uint8_t operator*() { ... }), equality (bool operator!=() { ... }), and incrementation (SetIter operator++() { ... }).

Cribbing liberally from the following guide: https://users.cs.northwestern.edu/~riesbeck/programming/c++/stl-iterator-define.html,

I wrote the following code:

#include <iostream>
#include <bitset>

class SetIter;

class Set {
public:
    typedef SetIter iterator;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef uint8_t value_type;
    typedef uint8_t * pointer;
    typedef uint8_t & reference;

    friend class SetIter;

    Set(std::string set) : m_set(set) { };

    uint8_t at(uint8_t i) { return m_set.test(i); }

    SetIter begin() { return SetIter(*this, 0); }
    SetIter end() { return SetIter(*this, 9); }
private:
    std::bitset<9> m_set;
};

class SetIter {
public:
    SetIter(Set &set, int at) : m_set(set), i(at) { };
    SetIter operator++() { ++i; return *this; }
    uint8_t operator*() { return m_set.at(i); }
    void operator!=(Set &cmp_set) { /* ??? */ }
private:
    Set m_set;
    uint8_t i;
};

int main()
{
    Set S("111111111");
}

The guide promised that this would work, but it doesn't. I get a number of errors, namely:

"forward declaration of 'SetIter'"
"incomplete result type 'SetIter' in function definition"
"invalid use of incomplete type 'SetIter'"

So I suspect that Set is unable to access the internal structure of SetIter, but that's the extent of my understanding the contours of this problem.

And I don't fully understand the implications of the typedefs in the definition of Set.

Thanks in advance.

[jonnin]

I don't see it yet but if you take out begin() and end() it compiles.

typedef just renames things and makes it more confusing for your enjoyment.

[mbozzi]

Typedef just renames things and makes it more confusing for your enjoyment.

Providing member types by those names makes your iterator type compatible with the standard library.

[coder777]

I get a number of errors, namely:

Yes, you cannot use any members (including the constructor) of a forward declaration (line 4). Hence you need to implement the functions that uses members of the forward class after the class is actually defined:

#include <iostream>
#include <bitset>
#include <cstddef> // ptrdiff_t

class SetIter;

class Set {
public:
    typedef SetIter iterator;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef uint8_t value_type;
    typedef uint8_t * pointer;
    typedef uint8_t & reference;

    friend class SetIter;

    Set(std::string set) : m_set(set) { };

    uint8_t at(uint8_t i) { return m_set.test(i); }

    SetIter begin(); // Note
    SetIter end();  // Note
private:
    std::bitset<9> m_set;
};

class SetIter {
public:
    SetIter(Set &set, int at) : m_set(set), i(at) { };
    SetIter operator++() { ++i; return *this; }
    uint8_t operator*() { return m_set.at(i); }
    void operator!=(Set &cmp_set) { /* ??? */ } // bool operator!=(Set &cmp_set) { return (m_set != cmp_set.m_set) ... }
private:
    Set m_set;
    uint8_t i;
};

    SetIter Set::begin() { return SetIter(*this, 0); }  // Note
    SetIter Set::end() { return SetIter(*this, 9); }  // Note

int main()
{
    Set S("111111111");
}

[jonnin]

I can see that mobzzi but why not name them what you wanted in the first place, rather than alias approach?

also, I would add references to complex objects to your list (unless you consider that a simple type?!). Im sure not going to pass an iterator to one item, its clutter for no gain.

Things I've read suggest that there are essentially three things that can, and should, be passed around: functions, simple variables, and iterators.

[dhayden]

or std::bitset<9> set("110100011");,

and the bit positions are related to the sequential values as follows: 987654321,

and I would like to iterate over this bitset with a range-based for-loop, e.g.,

for (auto b : B) {
    std::cout << b;
} std::cout << std::endl;

which should produce, for the latter bitset example above, the output 12689\n.

What you are describing is not an iterator:
std::cout << b; You can't output an iterator itself, only what it points to.

which should produce, for the latter bitset example above, the output 12689

Then your "iterator" iterates over some of the items, not all of them.

You need to go through the bitset, test if the bits are set, and print out the ones that are.

[Vituperous]

jonnin:

typedef just renames things and makes it more confusing for your enjoyment.

Should typedef be avoided in most circumstances?

mbozzi:

Providing member types by those names makes your iterator type compatible with the standard library.

Okay, that makes sense. So any object (class? what's the right word here...) with a certain set of operators is implicitly "interpreted" to be an iterator. Is there an effective difference between defining an operator with operator...() and typedef? Does one take precedence? Should one be preferred? Would it make more sense to write the latter two typedefs as

typedef uint8_t *pointer;
typedef uint8_t &reference;

?

coder777:

I get a number of errors, namely: Yes, you cannot use any members (including the constructor) of a forward declaration (line 4). Hence you need to implement the functions that uses members of the forward class after the class is actually defined:

Thanks, that makes sense. Is this considered best practice, or are there common alternatives?

jonnin:

I would add references to complex objects to your list (unless you consider that a simple type?!). Im sure not going to pass an iterator to one item, its clutter for no gain.

How often are references to complex objects passed around without resorting to iterators? How often do people pass copied structures instead of const or non-const references to complex objects in non-performance-critical code? (Subjectively.)

dhayden:

You can't output an iterator itself, only what it points to.

I may not have been clear. The point of the iterator is to iterate over the integers corresponding to the index positions in the bitset.

As suggested above, by exposing an "iterator interface" (in the form of "iterator operators"), standard library functions can be applied to the data in the iterator.

But that isn't quite what I want to do. I want to use a range-based for-loop as I do here:

#include <iostream>
#include <bitset>

class SetIter;

class Set
{
public:
    typedef SetIter iterator;
    // typedef ptrdiff_t difference_type;
    // typedef size_t size_type;
    // typedef uint8_t value_type;
    // typedef uint8_t * pointer;
    // typedef uint8_t & reference;
    friend class SetIter;
    Set(std::string bits) : m_bits(bits) { }
    uint8_t at(uint8_t i) { return m_bits.test(i); }
    SetIter begin();
    SetIter end();

private:
    std::bitset<9> m_bits;
};

class SetIter
{
public:
    SetIter(Set &set, int at) : m_set(set), i(at) { };
    SetIter operator++()
    {
        do {
            ++i;
            if (i >= 9) {
                i = -1;
                break;
            }
        } while (m_set.at(i) != 1);
        return *this;
    }
    uint8_t operator*() { return i + 1; }
    bool operator!=(SetIter &cmp_setiter)
    {
        if (i == -1) return false;
        return (i != cmp_setiter.i);
    }

private:
    Set m_set;
    int8_t i;
};

SetIter Set::begin() { return SetIter(*this, 0); }
SetIter Set::end() { return SetIter(*this, 9); }

int main()
{
    Set B("111010111");

    for (auto b : B) {
        std::cout << int(b) << std::endl;
    }
}

It's like I'm running a filter before I go for the "mapping" iteration.

In Python I would just do something like this:

B = bitset("111010111")
for n in (i + 1 for i, b in enumerate(B) if b == 1):
    print(n)

And expect the output:

1
2
3
4
7
8
9

Does that make things clearer? Or is it just not an iterator when you don't touch every single element in an "iterator span"?

[jonnin]

How often are references to complex objects passed around without resorting to iterators? How often do people pass copied structures instead of const or non-const references to complex objects in non-performance-critical code? (Subjectively.)

It happens all the time. If nowhere else, inside the class itself (example, = operator) you pass a const reference to a single object into it.
but consider when you only have 1 of something. An iterator for a single instance of something is just bloat.

all code is performance critical on little stuff like this that should just be a habit. C++ is a complex an difficult language and its primary argument for being in use today is that it outperforms the easier to use languages. ONE of the reasons it can do that is programmer discipline and habits. If you want to be sloppy and write slow code to avoid typing an &, you would be better off using like python or some other sluggish language. I don't mean to soapbox here but making fat things a reference parameter is one of the most basic best practices in the language; you would have to be stubbornly ignoring that by intent to do otherwise after your first month or two in the language.