C 链接列表的 C++ 迭代器：使用基于范围的 for 循环

Question

我正在使用遗留 C 代码，新代码是用 C++ 编写的。为了使用 C++ 标准库，我在 Adaptation.

上阅读 Bjarne Stroustrup 的博客 post 后，为遗留 LinkedList 编写了一个简单的 Iterator，如下所示

我的问题是：

我想为另一个 struct 说 struct TokenList 创建另一个 Iterator。我不确定如何使用 namespace 并且仍然能够使用 range-based for 循环。任何指针都会有所帮助。
是 Iterator 的适配器，即：begin、end、++、*、!= 正确的？目前，我有兴趣使用基于范围的 for 循环阅读 LinkedList 的内容。

#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

迭代器是伪指针类型。那就是说他们本身就是正规的。

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

在这里你混合了引用和指针。这是一个严重的反模式，因为赋值是做什么的？没有合理的答案。

我会完全删除 c 成员。

接下来您需要广播一个迭代器类型。你的看起来像一个前向迭代器。所有结束迭代器都可以相等。

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

这些看起来不错。只需删除 *c.

请注意，名称不必是 Iterator。 begin/end必须在LinkedList的命名空间中定义，但return类型不必是。

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

我通常将其实现为一个成员函数，同时实现预增量和post增量； post使用pre和copy实现。

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

这是错误的。它应该 return *p.current 作为 double&.

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

当然可以。还将 == 实现为 !(lhs!=rhs).

查找前向迭代器概念和前向迭代器标记。包括 std::iterator_traits.

所需的类型

对于其他要迭代的东西，给迭代器一个不同的名字。这可以通过不同的命名空间。

如果不同之处只是值的类型，您可以很容易地将其设为模板。那么你只需要手动写begin/end.

如果 v 的名称也发生变化，您可以在作为自定义点编写的 GetValue(List*) 函数上使用 ADL。

现在，可在基于范围的 for 中使用与作为迭代器不同。基于范围的 for 稍微容易一些；但是上面的代码将你升级为一个完整的前向迭代器，这反过来又减少了当你尝试使用标准算法或其他任何东西时的意外。

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

C 链接列表的 C++ 迭代器：使用基于范围的 for 循环

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

c++

iterator