c++ - 自己的迭代器类不适用于 std::binary_search

Question

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

编辑:发布的示例现在可以在引入缺失的东西后使用。希望有人可以使用这个例子作为自己实验的基础。我还介绍了将此示例用作随机访问迭代器所缺少的东西。它与 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;
    }

Answer 1

除了 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引用。