Overloading the increment operator in C++ Generic Programming

Question

I am having trouble getting to grips with a certain aspect of Generic Programming as explained in the book "The C++ Programming Language".

In Section 24.2. "Algorithms and Lifting" a general algorithm to accumulate values in a sequence of objects (also known in other languages as reduce, fold, sum, aggregate) is presented:

// quoted from "The C++ Programming Language" 4th ed. Section 24.2 p. 702
template<typename Iter, typename Val>
Val sum(Iter first, Iter last)
{
    Val s=0;
    while(first!=last) {
        s = s + *first;
        ++first;
    }
    return s;
}

This function template is intended to work on arbitrary types like arrays of double values or linked lists of user-defined types like this one that is presented in the next paragraph:

// quoted from "The C++ Programming Language" 4th ed. Section 24.2 p. 703
struct Node {
    Node* next; int data;
};
Node* operator++(Node* p) {return p->next;}
int operator*(Node* p) {return p->data;}
Node* end(Node* lst) {return nullptr;}

In order to work with the above function template "sum", the above code overloads the ++ and * operators for type Node*. It is my understanding that overloading these operators on pointer types is not possible. This is confirmed by my compilers (MSVC and GCC) who produce the following error messages:

'Node* operator++(Node*)' must have an argument of class or enumerated type
'int operator*(Node*)' must have an argument of class or enumerated type

Am I missing something here ?

Or shall I write a letter to the editor ?

Answer 1

In my copy of "The C++ Programming Language", Hanser Verlag 2015 (it is a translation from the english language edition, 4th edition 2013) the example reads as follows:

// quoted from section 24.2, page 761
struct Node { Node* next; int data; };
struct Node_iter { Node* pos; };

Node_iter operator++(Node_iter& p) { return p.pos=p.pos->next; }
int operator*(Node_iter p) { return p.pos->data; }
bool operator!=(Node_iter p, Node_iter q) { return p.pos != q.pos; }

void test(Node* lst)
{
    int s = sum<Node_iter,int>(lst,nullptr);
}

Answer 2

You may not overload built-in operators and such operators are already defined for pointer types like the type Node *.

You should wrap the type Node * into a user-defined type and define the required operators for this type.

There are many approaches to do this. You can for example write a real random access iterator. However what you need to run the function sum is to define the listed by your operators plus comparison operators.

For example

#include <iostream>
#include <initializer_list>

struct Node 
{
    Node() : next( nullptr )
    {
    }

    template <typename T>
    Node( std::initializer_list<T> lst )
    {
        Node *prev = nullptr;
        Node *current = this;

        for ( auto it = lst.begin(); it != lst.end(); ++it )
        {
            if ( prev ) 
            {
                prev->next = new Node();
                current = prev->next;
            }
            current->data = *it;
            prev = current;
        }
    }

    Node *next; 
    int data;
    struct iterator;

    static iterator begin( Node *node )
    {
        return iterator( node );
    }

    static iterator end( Node * )
    {
        return iterator( nullptr );
    }

    struct iterator
    {
        iterator( Node *node ) : node( node ) {}
        Node *node; 
    };
};


Node::iterator & operator++( Node::iterator &it ) 
{ 
    if ( it.node ) it.node = it.node->next;
    return it;
}

int operator *( Node::iterator &it ) 
{
    return it.node->data;
}

bool operator ==( const Node::iterator &it1, const Node::iterator &it2 )
{
    return it1.node == it2.node;
}

bool operator !=( const Node::iterator &it1, const Node::iterator &it2 )
{
    return !( it1.node == it2.node );
}

template<typename Iter, typename Val>
Val sum(Iter first, Iter last)
{
    Val s = 0;
    while (first != last) {
        s = s + *first;
        ++first;
    }
    return s;
}

int main()
{
    Node *head = new Node{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    std::cout << sum<Node::iterator, long long>( Node::begin( head ), Node::end( head )) << std::endl;

    return 0;
}

The program output is

55

The presented class Node is not complete. At least you need to write a destructor.

Answer 3

Iterators capabilities in the standard library are expressed through a standard template class called std::iterator_traits.

You can either specialise it, or allow the default specialisation to deduce types from your iterator class (which means you then have to correctly write the iterator).

example:

#include <iterator>

struct Node {
    Node* next; int data;
};

struct NodeIterator {

    using value_type = int;

    NodeIterator(Node* nodes = nullptr) : p_(nodes) {}

    NodeIterator& operator++() {
        p_ = p_->next;
    }

    value_type operator*() const {
        return p_->data;
    }

    bool operator==(NodeIterator& other) const {
        return p_ == other.p_;
    }

    bool operator!=(NodeIterator& other) const {
        return p_ != other.p_;
    }

    Node* p_;
};

namespace std {
    template<> struct iterator_traits<NodeIterator>
    {
        using difference_type = std::ptrdiff_t;
        using value_type = NodeIterator::value_type;
        using pointer = value_type*;
        using reference = const value_type&;
        using iterator_category = std::forward_iterator_tag;
    };
}

NodeIterator end(Node* lst) {return { nullptr };}


template<typename Iter>
auto sum(Iter first, Iter last) -> typename std::iterator_traits<Iter>::value_type
{
    using Val = typename std::iterator_traits<Iter>::value_type;
    Val s=0;
    while(first!=last) {
        s = s + *first;
        ++first;
    }
    return s;
}

int sumNodes(Node* nodes)
{
    return sum(NodeIterator(nodes), end(nodes));
}