我有一个自定义容器类,我想为它写iterator类和const_iterator类。

我以前从来没有这样做过,我也没有找到合适的操作方法。关于创建迭代器的指导原则是什么?我应该注意什么?

我还希望避免代码重复(我觉得const_iterator和iterator共享很多东西;一个应该子类化另一个吗?)

脚注:我很确定Boost有一些东西可以缓解这个问题,但由于许多愚蠢的原因,我不能在这里使用它。


当前回答

我有兴趣知道这是如何正确的,但似乎工作作为一个滚动您自己的迭代器内部数据存储

template<typename T>
struct iterator_type
{
    using self_type             = iterator_type;
    using iterator_category     = std::random_access_iterator_tag;
    using difference_type       = std::ptrdiff_t;
    using value_type            = std::remove_cv_t<T>;
    using pointer               = T*;
    using reference             = T&;

    iterator_type( pointer ptr ) noexcept
        : _ptr{ ptr }
    {}

    reference operator*() noexcept { return *_ptr; }
    pointer operator->() noexcept { return _ptr; }

    self_type operator++() noexcept { ++_ptr; return *this; }
    self_type operator++(int) noexcept { self_type tmp = *this; ++_ptr; return tmp; }

    self_type operator--() noexcept { --_ptr; return *this; }
    self_type operator--(int) noexcept { self_type tmp = *this; --_ptr; return tmp; }

    bool operator==( const self_type &other ) const noexcept { return _ptr == other._ptr; }
    bool operator!=( const self_type &other ) const noexcept { return _ptr != other._ptr; }

private:
    pointer _ptr;
};


template<typename T>
using const_iterator_type = iterator_type<std::add_const_t<T>>;

然后我只是把这些添加到我的类,似乎工作如预期。

template<typename T>
class Container
{
public:
    using iterator               = iterator_type<T>;
    using const_iterator         = const_iterator_type<T>;
    using reverse_iterator       = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

...

    iterator begin() { return _begin; }
    iterator end() { return _begin + _size; }

    const_iterator cbegin() const { return _begin; }
    const_iterator cend() const { return _begin + _size; }

    reverse_iterator rbegin() { return reverse_iterator(_begin + _size); }
    reverse_iterator rend() { return reverse_iterator(_begin); }

    const_reverse_iterator crbegin() const { return const_reverse_iterator(_begin + _size); }
    const_reverse_iterator crend() const { return const_reverse_iterator(_begin); }

private:
    T*         _begin;
    size_t     _size;
    size_t     _capacity;
};

唯一的事情是,使它与std::cbegin(), std::rcbegin(), std::cend()和std::rcend()函数,我必须扩展std命名空间:

namespace std
{
    template<typename T>
    typename Container<T>::const_iterator cbegin( Container<T> &c ) { return c.cbegin(); }

    template<typename T>
    typename Container<T>::const_iterator cend( Container<T> &c ) { return c.cend(); }

    template<typename T>
    typename Container<T>::const_reverse_iterator crbegin( Container<T> &c ) { return c.crbegin(); }

    template<typename T>
    typename Container<T>::const_reverse_iterator crend( Container<T> &c ) { return c.crend(); }
}

其他回答

Boost可以提供帮助:Boost。迭代器库。

更准确地说是本页:boost::iterator_adaptor。

非常有趣的是教程示例,它从头开始展示了一个自定义类型的完整实现。

template <class Value> class node_iter : public boost::iterator_adaptor< node_iter<Value> // Derived , Value* // Base , boost::use_default // Value , boost::forward_traversal_tag // CategoryOrTraversal > { private: struct enabler {}; // a private type avoids misuse public: node_iter() : node_iter::iterator_adaptor_(0) {} explicit node_iter(Value* p) : node_iter::iterator_adaptor_(p) {} // iterator convertible to const_iterator, not vice-versa template <class OtherValue> node_iter( node_iter<OtherValue> const& other , typename boost::enable_if< boost::is_convertible<OtherValue*,Value*> , enabler >::type = enabler() ) : node_iter::iterator_adaptor_(other.base()) {} private: friend class boost::iterator_core_access; void increment() { this->base_reference() = this->base()->next(); } };

正如前面提到的,要点是使用单个模板实现并对其进行类型定义。

检查下面的代码,它工作

#define MAX_BYTE_RANGE 255

template <typename T>
class string
{
public:
    typedef char *pointer;
    typedef const char *const_pointer;
    typedef __gnu_cxx::__normal_iterator<pointer, string> iterator;
    typedef __gnu_cxx::__normal_iterator<const_pointer, string> const_iterator;

    string() : length(0)
    {
    }
    size_t size() const
    {
        return length;
    }
    void operator=(const_pointer value)
    {
        if (value == nullptr)
            throw std::invalid_argument("value cannot be null");
        auto count = strlen(value);
        if (count > 0)
            _M_copy(value, count);
    }
    void operator=(const string &value)
    {
        if (value.length != 0)
            _M_copy(value.buf, value.length);
    }
    iterator begin()
    {
        return iterator(buf);
    }
    iterator end()
    {
        return iterator(buf + length);
    }
    const_iterator begin() const
    {
        return const_iterator(buf);
    }
    const_iterator end() const
    {
        return const_iterator(buf + length);
    }
    const_pointer c_str() const
    {
        return buf;
    }
    ~string()
    {
    }

private:
    unsigned char length;
    T buf[MAX_BYTE_RANGE];

    void _M_copy(const_pointer value, size_t count)
    {
        memcpy(buf, value, count);
        length = count;
    }
};

Choose type of iterator which fits your container: input, output, forward etc. Use base iterator classes from standard library. For example, std::iterator with random_access_iterator_tag.These base classes define all type definitions required by STL and do other work. To avoid code duplication iterator class should be a template class and be parametrized by "value type", "pointer type", "reference type" or all of them (depends on implementation). For example: // iterator class is parametrized by pointer type template <typename PointerType> class MyIterator { // iterator class definition goes here }; typedef MyIterator<int*> iterator_type; typedef MyIterator<const int*> const_iterator_type; Notice iterator_type and const_iterator_type type definitions: they are types for your non-const and const iterators.

参见:标准库参考

EDIT: std::iterator自c++ 17起已弃用。请在这里查看相关讨论。

我将向您展示如何轻松地为自定义容器定义迭代器,但以防万一,我已经创建了一个c++11库,允许您轻松地为任何类型的容器(连续或不连续)创建具有自定义行为的自定义迭代器。

你可以在Github上找到它

下面是创建和使用自定义迭代器的简单步骤:

创建“自定义迭代器”类。 在“自定义容器”类中定义typedefs。 例如:typedef blRawIterator<类型>迭代器; 例如:typedef blRawIterator< const Type > const_iterator; 定义"begin"和"end"函数 例如:迭代器begin(){返回迭代器(&m_data[0]);}; 例如:const_iterator cbegin()const{return const_iterator(&m_data[0]);}; 我们完成了! !

最后,定义我们的自定义迭代器类:

注意:在定义自定义迭代器时,我们从标准迭代器类别派生,以让STL算法知道我们所创建的迭代器的类型。

在这个例子中,我定义了一个随机访问迭代器和一个反向随机访问迭代器:

//------------------------------------------------------------------- // Raw iterator with random access //------------------------------------------------------------------- template<typename blDataType> class blRawIterator { public: using iterator_category = std::random_access_iterator_tag; using value_type = blDataType; using difference_type = std::ptrdiff_t; using pointer = blDataType*; using reference = blDataType&; public: blRawIterator(blDataType* ptr = nullptr){m_ptr = ptr;} blRawIterator(const blRawIterator<blDataType>& rawIterator) = default; ~blRawIterator(){} blRawIterator<blDataType>& operator=(const blRawIterator<blDataType>& rawIterator) = default; blRawIterator<blDataType>& operator=(blDataType* ptr){m_ptr = ptr;return (*this);} operator bool()const { if(m_ptr) return true; else return false; } bool operator==(const blRawIterator<blDataType>& rawIterator)const{return (m_ptr == rawIterator.getConstPtr());} bool operator!=(const blRawIterator<blDataType>& rawIterator)const{return (m_ptr != rawIterator.getConstPtr());} blRawIterator<blDataType>& operator+=(const difference_type& movement){m_ptr += movement;return (*this);} blRawIterator<blDataType>& operator-=(const difference_type& movement){m_ptr -= movement;return (*this);} blRawIterator<blDataType>& operator++(){++m_ptr;return (*this);} blRawIterator<blDataType>& operator--(){--m_ptr;return (*this);} blRawIterator<blDataType> operator++(int){auto temp(*this);++m_ptr;return temp;} blRawIterator<blDataType> operator--(int){auto temp(*this);--m_ptr;return temp;} blRawIterator<blDataType> operator+(const difference_type& movement){auto oldPtr = m_ptr;m_ptr+=movement;auto temp(*this);m_ptr = oldPtr;return temp;} blRawIterator<blDataType> operator-(const difference_type& movement){auto oldPtr = m_ptr;m_ptr-=movement;auto temp(*this);m_ptr = oldPtr;return temp;} difference_type operator-(const blRawIterator<blDataType>& rawIterator){return std::distance(rawIterator.getPtr(),this->getPtr());} blDataType& operator*(){return *m_ptr;} const blDataType& operator*()const{return *m_ptr;} blDataType* operator->(){return m_ptr;} blDataType* getPtr()const{return m_ptr;} const blDataType* getConstPtr()const{return m_ptr;} protected: blDataType* m_ptr; }; //------------------------------------------------------------------- //------------------------------------------------------------------- // Raw reverse iterator with random access //------------------------------------------------------------------- template<typename blDataType> class blRawReverseIterator : public blRawIterator<blDataType> { public: blRawReverseIterator(blDataType* ptr = nullptr):blRawIterator<blDataType>(ptr){} blRawReverseIterator(const blRawIterator<blDataType>& rawIterator){this->m_ptr = rawIterator.getPtr();} blRawReverseIterator(const blRawReverseIterator<blDataType>& rawReverseIterator) = default; ~blRawReverseIterator(){} blRawReverseIterator<blDataType>& operator=(const blRawReverseIterator<blDataType>& rawReverseIterator) = default; blRawReverseIterator<blDataType>& operator=(const blRawIterator<blDataType>& rawIterator){this->m_ptr = rawIterator.getPtr();return (*this);} blRawReverseIterator<blDataType>& operator=(blDataType* ptr){this->setPtr(ptr);return (*this);} blRawReverseIterator<blDataType>& operator+=(const difference_type& movement){this->m_ptr -= movement;return (*this);} blRawReverseIterator<blDataType>& operator-=(const difference_type& movement){this->m_ptr += movement;return (*this);} blRawReverseIterator<blDataType>& operator++(){--this->m_ptr;return (*this);} blRawReverseIterator<blDataType>& operator--(){++this->m_ptr;return (*this);} blRawReverseIterator<blDataType> operator++(int){auto temp(*this);--this->m_ptr;return temp;} blRawReverseIterator<blDataType> operator--(int){auto temp(*this);++this->m_ptr;return temp;} blRawReverseIterator<blDataType> operator+(const int& movement){auto oldPtr = this->m_ptr;this->m_ptr-=movement;auto temp(*this);this->m_ptr = oldPtr;return temp;} blRawReverseIterator<blDataType> operator-(const int& movement){auto oldPtr = this->m_ptr;this->m_ptr+=movement;auto temp(*this);this->m_ptr = oldPtr;return temp;} difference_type operator-(const blRawReverseIterator<blDataType>& rawReverseIterator){return std::distance(this->getPtr(),rawReverseIterator.getPtr());} blRawIterator<blDataType> base(){blRawIterator<blDataType> forwardIterator(this->m_ptr); ++forwardIterator; return forwardIterator;} }; //-------------------------------------------------------------------

现在在你的自定义容器类中:

template<typename blDataType>
class blCustomContainer
{
public: // The typedefs

    typedef blRawIterator<blDataType>              iterator;
    typedef blRawIterator<const blDataType>        const_iterator;

    typedef blRawReverseIterator<blDataType>       reverse_iterator;
    typedef blRawReverseIterator<const blDataType> const_reverse_iterator;

                            .
                            .
                            .

public:  // The begin/end functions

    iterator                                       begin(){return iterator(&m_data[0]);}
    iterator                                       end(){return iterator(&m_data[m_size]);}

    const_iterator                                 cbegin(){return const_iterator(&m_data[0]);}
    const_iterator                                 cend(){return const_iterator(&m_data[m_size]);}

    reverse_iterator                               rbegin(){return reverse_iterator(&m_data[m_size - 1]);}
    reverse_iterator                               rend(){return reverse_iterator(&m_data[-1]);}

    const_reverse_iterator                         crbegin(){return const_reverse_iterator(&m_data[m_size - 1]);}
    const_reverse_iterator                         crend(){return const_reverse_iterator(&m_data[-1]);}

                            .
                            .
                            .
    // This is the pointer to the
    // beginning of the data
    // This allows the container
    // to either "view" data owned
    // by other containers or to
    // own its own data
    // You would implement a "create"
    // method for owning the data
    // and a "wrap" method for viewing
    // data owned by other containers

    blDataType*                                    m_data;
};

我不知道Boost有没有什么有用的东西。

我喜欢的模式很简单:取一个模板参数,它等于value_type,无论是否有const限定。如果需要,还可以使用节点类型。然后,好吧,一切都有条不紊了。

只需要记住参数化(模板化)所有需要的东西,包括复制构造函数和operator==。在大多数情况下,const的语义将创建正确的行为。

template< class ValueType, class NodeType >
struct my_iterator
 : std::iterator< std::bidirectional_iterator_tag, T > {
    ValueType &operator*() { return cur->payload; }

    template< class VT2, class NT2 >
    friend bool operator==
        ( my_iterator const &lhs, my_iterator< VT2, NT2 > const &rhs );

    // etc.

private:
    NodeType *cur;

    friend class my_container;
    my_iterator( NodeType * ); // private constructor for begin, end
};

typedef my_iterator< T, my_node< T > > iterator;
typedef my_iterator< T const, my_node< T > const > const_iterator;