C++ Iterator for C Linked Lists: to use range-based for loops

Question

I am working with legacy C code and the new code is written in C++. To use the C++ standard library, I wrote a simple Iterator for the legacy LinkedList as shown below after reading through Bjarne Stroustrup's blog post on Adaptation.

My question is:

1. I want to create another Iterator for another struct say struct TokenList. I am not sure how to use namespace and still be able to use the range-based for loops. Any pointers would be helpful.

2. Are the adapters for the Iterator namely: begin, end, ++, *, != correct? Currently, I'm an interested in reading the contents of the LinkedList using range-based for loops.

Coliru

#include <cstdio>
#include <numeric>
#include <algorithm>

struct LinkedList {
    double v;
    LinkedList *next;
};

struct Iterator {
    LinkedList *current;
    LinkedList &c;
};

Iterator begin(LinkedList *c) { return Iterator {c, *c}; }
Iterator end(LinkedList *c) { return Iterator {nullptr, *c}; }
Iterator &operator++(Iterator &p) { p.current = p.current->next; return p; }
LinkedList *operator*(Iterator p) { return p.current; }
bool operator!=(Iterator lhs, Iterator rhs) { return (lhs.current != rhs.current); }

int main()
{
    LinkedList *node1 = new LinkedList;
    LinkedList *node2 = new LinkedList;
    LinkedList *node3 = new LinkedList;

    node1->v = 1; node1->next = node2;
    node2->v = 2; node2->next = node3;
    node3->v = 3; node3->next = nullptr;

    printf("// C style: iteration\n");
    for (auto ptr = node1; ptr; ptr = ptr->next) {
        printf("%e\n", ptr->v);
    }

    auto head = node1;
    // make use of begin(), end(), ++, != and *
    printf("// Modern C++ style: range based for-loop\n");
    for (const auto& it : head) {
        printf("%e\n", it->v);
    }

    delete node3;
    delete node2;
    delete node1;

    return 0;
}

Answer 1

Iterators are pseudo-pointer types. That means they themselves are regular.

struct Iterator {
  LinkedList *current;
  LinkedList &c;
};

Here you mix references and pointers. This is a serious anti-pattern, as what does assignment do? There is no sensible answer.

I would remove the c member entirely.

Next you need to broadcast an iterator type. Yours looks like a forward iterator. All end iterators can be equal.

Iterator begin(LinkedList *c) { return Iterator {c, *c}; }
Iterator end(LinkedList *c) { return Iterator {nullptr, *c}; }

These look ok. Just remove *c.

Note that the name does not have to be Iterator. begin/end must be defined in the namespace of LinkedList, but the return type does not have to be.

Iterator &operator++(Iterator &p) { p.current = p.current->next; return p; }

I usually implement this as a member function, and implement both pre and post increment; post is implemented using pre and copy.

LinkedList *operator*(Iterator p) { return p.current; }

This is wrong. It should return *p.current as a double&.

bool operator!=(Iterator lhs, Iterator rhs) { return (lhs.current != rhs.current); }

sure. Also implement == as !(lhs!=rhs).

Look up the forward iterator concept and forward iterator tag. Include the types needed for std::iterator_traits.

For other things to iterate, give the iterator a different name. This can be via a different namespace.

If the thing that differs is just the type of the value, you can make it a template pretty easy. Then you only have to manually write begin/end.

If the name of v also changes, you could use ADL on a GetValue(List*) function you write as a customization point.

---

Now, being usable in a ranged based for is different than being an iterator. Ranged based for is a tad easier; but the above upgrades you to a full forward iterator, which in turn reduces surprise when you try to use a std algorithm or basically anything else.

---

How I would write it:

// Iteration::LinkedListIterator<X> assumes that X is a linked list node
// with members ->next and ->value.  If it isn't, override the customization
// points GetNextNode and GetListElement in the namespace of X.

namespace Iteration {
  template<class List>
  List* GetNextNode( List* l ) {
    if (!l) return l;
    return l->next;
  }
  template<class List>
  decltype(auto) GetListElement( List* l ) {
    return l->value;
  }
  template<class List>
  struct LinkedListIterator {

    using self=LinkedListIterator;
    List *current;
    self& operator++(){ current = GetNextNode(current); return *this; }
    self operator++(int)&{ auto copy = *this; ++*this; return copy; }
    decltype(auto) operator*() {
      return GetListElement(current);
    }
    decltype(auto) operator*() const {
      return GetListElement(current);
    }
    auto operator->() {
      return std::addressof(GetListElement(current));
    }
    auto operator->() const {
      return std::addressof(GetListElement(current));
    }
    friend bool operator==(self const& lhs, self const& rhs) {
      return lhs.current == rhs.current;
    }
    friend bool operator!=(self const& lhs, self const& rhs) {
      return lhs.current != rhs.current;
    }

    using iterator_category = std::forward_iterator_tag;
    using value_type = std::decay_t<decltype(GetListElement(std::declval<List*>()))>;
    using difference_type = std::ptrdiff_t;
    using pointer = value_type*;
    using reference = value_type&;
  };
};

struct LinkedList {
    double v;
    LinkedList *next;
};

// customization point; the name of 
double& GetListElement( LinkedList* l ) { return l->v; }
double const& GetListElement( LinkedList const* l ) { return l->v; }
Iteration::LinkedListIterator<LinkedList> begin( LinkedList* l ) {
  return {l};
}
Iteration::LinkedListIterator<LinkedList> end( LinkedList* l ) {
  return {nullptr};
}