c++ - 在 C++ 泛型编程中重载增量运算符

Question

如“The C++ Programming Language”一书中所述，我无法掌握泛型编程的某个方面。

在第 24.2 节中。 “算法和提升”介绍了一种在对象序列中累加值的通用算法(在其他语言中也称为 reduce、fold、sum、aggregate):

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

此函数模板旨在处理任意类型，如 double 值数组或用户定义类型的链表，如下一段所示:

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