Increment operator overloading in C ++ Generic Programming

Question

I am having problems with some aspects of general programming, as described in the book "C ++ Programming Language".

Section 24.2. "Algorithms and rise" presents a general algorithm for accumulating values ​​in a sequence of objects (also known in other languages ​​as reduction, bending, sum, totality):

// 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 designed to work with arbitrary types, such as arrays of double values ​​or related lists of user types like this, which is presented in the following 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;}

"sum", ++ * Node*. , . (MSVC GCC), :

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

- ?

?

Answer 1

std::iterator_traits.

, ( , ).

:

#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));
}

Answer 2

, , Node *.

Node * .

. , . , , .

#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;
}

55

Node . .

Answer 3

In my copy of the C ++ Programming Language, Hanser Verlag 2015 (this is a translation from the English edition, 4th edition of 2013), this example looks like this:

// 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);
}