2

我在这里找到了很多关于该主题的答案，但我无法让我的代码运行。

编辑： 发布的示例现在可以在引入缺失的内容后工作。希望有人可以将这个例子作为自己实验的基础。我还介绍了将这个示例用作随机访问迭代器的缺失内容。它与 binary_search 算法一起工作效率更高。

如果我必须编写自己的迭代器，我会与 value_type 和其他“特价”一起使用 .

我在这里阅读了很多关于如何不编写迭代器的文章，但找不到任何可行的示例。特别是我读到我不应该从迭代器派生。所以我再问一次笨蛋：

如何定义迭代器的 value_type。它不适用于类定义，也不适用于手动定义 type_traits 结构。不知道怎么继续...

     #include <iostream>
     #include <algorithm>
     #include <type_traits>
     #include <iterator>

    using namespace std;

    int data[]= { 1,4,7,9,11,20,28 }; //Sorted data

    template < typename T >
    class MyIter
    {
        int offset;
        T* base;

        public:
        typedef int value_type;

        //add the following lines after reading the answers -> it works! 
        typedef std::ptrdiff_t difference_type;
        typedef T * pointer;
        typedef T & reference;
        typedef std::forward_iterator_tag iterator_category;

        // if you want to use as random access iterator:
        // typedef std::random_access_iterator_tag iterator_category;

        public:
        MyIter( T* _base, int _offset) : base(_base), offset(_offset) {}
        MyIter() {}

        bool operator !=( const MyIter& rhs) 
        {
            T* tmp1= base+offset;
            T* tmp2= rhs.base + rhs.offset;

            return tmp1 != tmp2;
        } 

        MyIter operator++(int)
        {
            MyIter tmp(*this);
            offset++;
            return tmp;
        }

        T operator*()
        {
            return *(base+offset);
        }

        // Addition: if used as random access iterator you must provide:
        int operator-(const MyIter& rhs)
        {
            return offset-rhs.offset;
        }

        MyIter operator+=(int off)
        {
            offset+=off;
            return *this;
        }


    };

    typedef MyIter<int> iterType ;

    int main()
    {
        cout << "ok" << endl;

        pair<iterType, iterType> bounds;

        MyIter<int> start( data,0);
        MyIter<int> ende ( data,7);

        bounds = equal_range( start, ende, 28 );

        for ( iterType it= bounds.first; it!=bounds.second; it++)
        {
            cout << "Found " << *it << endl;
        }


        return 0;
    }
4

3 回答 3

3

除了value_type标准库对迭代器的要求之外，您还缺少一些定义：

typedef std::ptrdiff_t difference_type;
typedef T * pointer;
typedef T & reference;
typedef std::forward_iterator_tag iterator_category;

或者，继承自std::iterator<std::forward_iterator_tag, T>会给你这些。我不知道你在哪里读到你不应该这样做，但这正是std::iterator它的目的。

此外，您缺少一个预增量运算符：

MyIter operator++()
{
    ++offset;
    return *this;
}

还有->和==运营商。此外，取消引用运算符可能应该返回一个引用来允许*it = 42，const重载返回一个值或const引用。

于 2013-02-06T12:54:05.207 回答
1

std::binary_search需要一个随机访问迭代器。这意味着迭代器必须支持加法和减法（+、和） +=，其语义与指针完全相同。并且任何数量的算法也将期望迭代器中有多个 typedef：派生 是获取它们的最简单方法。（从技术上讲，标准要求的是产生正确的值，因此您可以为您的迭代器显式实例化它。但它的默认实现在迭代器类中选择 typedef。）--=std::iteratorstd::iterator_traits

编辑：

重读您的帖子：您绝对应该公开从std::iterator. 谁说其他都是错的。

于 2013-02-06T12:45:13.883 回答
1

您缺少几个基本类型成员和预增量运算符（以及@MikeSeymour 指出的一堆其他取消引用和比较运算符）。将 thise 添加到您的类定义中（请注意，我根据当前缺少的前增量运算符重写了后增量运算符）以使您binary_search继续前进

typedef std::forward_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;

MyIter& operator++()
{
    ++offset;
    return *this;                      
}

MyIter operator++(int)
{
    MyIter tmp(*this);
    ++*this; // NOTE this will call the other operator++
    return tmp;
}

LiveWorkSpace上的输出正如@JamesKanze所指出的，这些缺失的 typedef 是通过继承 from 提供的std::iterator<std::forward_iterator_tag, T>。

于 2013-02-06T12:49:48.617 回答