3

首先，我对 C++ 相当陌生，所以如果这是初学者编码错误，那么我很抱歉。

我目前正在为我在学校得到的家庭作业准备一个绘图课。我应该能够将边存储在集合、数组和链表中。由于我在单独的课程中完成了所有这些工作，因此我现在正试图通过模板使它们全部一起工作。对ie来说一切正常。std::set，但是当我使用我自己的链表实现时，它会以某种方式失败 - 看起来我的迭代器在某个地方搞砸了，并且它们上的前缀和后缀运算符都会导致相同的行为（在 for 循环中）。我还要补充一点，我没有使用 std::list 因为我应该自己实现链表。

我当前的迭代器实现：

template<typename T>
class Iterator{
    public: node<T>* pointer;
    public:
        Iterator(): pointer(0){}
        Iterator(node<T>* _pointer): pointer(_pointer){}

        Iterator<T> operator++()    { pointer = pointer->next; }
        Iterator<T> operator++(int) { pointer = pointer->next; }

        bool operator!=(Iterator<T> rval){ return !(pointer == rval.pointer); }
        bool operator==(Iterator<T> rval){ return (pointer == rval.pointer); }

        node<T>* operator()(){ return pointer; }

        T operator*(){ return pointer->data; }

};

单链表节点：

template <typename T>
struct node{
    node(): next(0){}
    node(T val): data(val), next(0){}
    node(node<T>* _next): data(0), next(_next){}
    node(T val, node<T>* _next): data(val), next(_next){}

    T data;
    node<T>* next;
};

以及我的列表类如何实现 begin() 和 end()：

typedef Iterator<T> iterator;
iterator  begin()   { return iterator(new node<T>(b)); }
iterator  end()     { return iterator(); }

注意b指向链表中的第一个元素

最后是我如何访问元素（这是在包含列表的不同类中）：

void tree_recurse_f(int node, std::ofstream* file, int level = 0){
   [some output code here]
   typename T::iterator it;
   for (it = Database[node].first.begin(); it != Database[node].first.end(); ++it){
      tree_recurse_f(*it, file, (level+1));
   }
}

Database是一个std::map<int,std::pair<>>并且.first指向由T(set, list or vector)指定的类型

现在解决问题：

  1. 不知何故，对于 list' 的当前实现begin()，它指向输出函数中的一个空节点（++it 和 it++ 产生相同的结果）
  2. 更改begin()toreturn iterator(b)似乎消除了 for 循环中的错误，尽管 ++it 和 it++ 都导致相同的事情
  3. 我已经设法通过仅测试列表类来发现这两个错误 - 如果我将它实现到图形类中，它会在输出函数中进入一个永无止境的循环（*它总是指向 0 并且似乎不会随着 + +它）

对我来说，迭代器看起来像是一些奇怪的东西（尤其是它单独工作的事实，但在另一个类中却没有）

// 如果有人好奇，我会大致遵循http://www.cplusplus.com/articles/Lw6AC542/上的链表教程

4

3 回答 3

7

您的前缀和后缀运算符执行相同的操作，因为您将它们定义为执行相同的操作：

Iterator<T> operator++()    { pointer = pointer->next; }
Iterator<T> operator++(int) { pointer = pointer->next; }

代码是相同的，但最重要的是，它具有Undefined Behavior，因为您的函数应该返回一个类型的值Iterator<T>，相反，它们什么也不返回。根据 C++11 标准的第 6.6.3/2 段：

[...] 从函数末尾流出相当于没有值的返回；这会导致值返回函数中的未定义行为。

您应该将前缀迭代器更改为如下内容：

Iterator<T> operator++() 
{ 
    pointer = pointer->next; 
    return *this;
}

你的后缀迭代器变成这样的：

Iterator<T> operator++(int) 
{ 
    node<T>* previous = pointer;
    pointer = pointer->next; 
    return Iterator<T>(previous);
}

另外，如果我正确理解您的设计，我真的认为您不应该这样做：

iterator begin() { return iterator(new node<T>(b)); }

我宁愿这样做：

iterator begin() { return iterator(b); }
于 2013-02-27T21:36:49.930 回答
2

这里的operator++实现没有return声明。返回值是前增量和后增量之间的关键区别。Pre-increment 接受一个迭代器，递增它，并返回新的迭代器值。它通常通过引用返回，因为原始迭代器与返回值相同。后增量获取一个迭代器，将其松鼠，增加原始迭代器，并返回保存的副本。这通常按值返回，因为它返回的迭代器与其应用的迭代器不同。所以更改签名以匹配这些：

Iterator<T>& operator++();
Iterator<T> operator++(int);

并更改实现以匹配我所描述的。

于 2013-02-27T21:37:29.537 回答
0

您的前缀和后缀++运算符实际上并没有返回任何内容。我很惊讶你的编译器没有抱怨。

前缀++运算符应该只返回*this. 后缀++运算符应在修改之前创建一个临时副本，*this然后返回该副本。

于 2013-02-27T21:35:59.040 回答