c++ - 无法基于 STL 迭代器编写我自己的迭代器

Question

我在尝试基于链表实现容器 Set 时遇到了一个小问题。是的，我知道有一个集合的 STL 实现，但这是家庭作业。 :)

所以，这就是我到目前为止所做的:

我的 Set.h 文件看起来像这样:

template <class T>
class Set {
private:
    typedef std::list<T> base_container;
    base_container items;
public:
    class myIterator {
    public:
        typename base_container::iterator base_iterator;
        myIterator() { }
    };
    void addItem(const T item) {
        items.push_back(item);
    }
    typedef typename Set<T>::myIterator setIterator;
    setIterator begin() { return items.begin(); }
    setIterator end() { return items.end(); }
    Set<T>(void) { }
    ~Set<T>(void) { }
};

现在，main.cpp:

#include "Set.h"

int main(void) {
    Set<int> mySet;

    mySet.addItem(1);
    mySet.addItem(2);
    mySet.addItem(3);
    mySet.addItem(4);

    Set<int>::myIterator x;
    x = mySet.begin();       // produces an error about non-convertible types.

    return EXIT_SUCCESS;
}

错误如下:

error C2664: 'Set<T>::myIterator::myIterator(const Set<T>::myIterator &)' : cannot convert parameter 1 from 'std::_List_iterator<_Mylist>' to 'const Set<T>::myIterator &' 

很明显我把事情搞砸了，但我不确定代码的哪一部分才是真正的问题。关于如何解决这个问题的任何建议？任何有用的信息将不胜感激。

谢谢。 :)

Answer 1

你的方法有很多问题。

正如其他人所说，您不能从基础类型创建迭代器类型:

setIterator begin() { return items.begin(); }
setIterator end() { return items.end(); }

这可以通过向您的类型添加构造函数来解决:

class myIterator {
    typedef typename base_container::iterator base_iterator_type;
public:
    explicit myIterator(base_iterator_type i) : base_iterator(i) { }
    base_iterator_type base_iterator;
    myIterator() { }
};

此构造函数应该是显式的，这意味着您需要更改创建它的方式:

setIterator begin() { return setIterator(items.begin()); }

下一个问题是你的类型没有实现迭代器接口(interface)，它没有提供 operator++或 operator*等等，它没有定义嵌套类型，例如 value_type和 iteratory_category也就是说，它不是一个迭代器(只是给它一个带有“迭代器”的名字并不能使它成为真的!)

一旦你解决了这个问题并且你的类型是一个有效的迭代器，你会发现你的容器不能与 STL 风格的算法一起使用，因为它没有实现容器要求。除其他外，它应该提供一个名为 iterator 的嵌套类型。不是 setIterator以便其他模板代码可以使用 S::iterator不关心是否S是 std::set<T>或 Set<T> .不要叫它Set<T>::setIterator , 就叫它 Set<T>::iterator .同样在这种情况下，没有必要定义 myIterator (没人在乎它是你的!:-) 然后用 typedef 来调用它 setIterator , 只需首先使用正确的名称命名类型，您不需要 typedef。