C++11 为自定义容器实现标准的forward迭代器

10km

发布于 2022-05-07 10:07:45

4590

发布于 2022-05-07 10:07:45

当前我的一个项目是基于C++11为基础开发的，在项目中需要用到哈希表来保持数据，C++11本身已经提供了丰富的容器类型(array,list,hashmap….vector)，但因为项目的特殊需要不能使用C++11现成的unordered_map容器。无奈所以我只能自己根据项目需要写了一个哈希表的模板类–HashTableAbstract–也就是自定义容器。然后问题了，为了让这个自定义的容器也能像unordered_map一样使用forward(向前)迭代器进行遍历数据，还要为它实现一个forward迭代器。下面以此为例来简要说明为自定义的容器实现标准的迭代器的办法。

HashTableAbstract的部分相关代码

/* 实现哈希表的抽象类,
 */
template<typename K, typename V>
class HashTableAbstract {
public:
    using  iterator=_HashTable_Iterator<V>;//定义迭代器类型
    iterator begin ()noexcept
    { return iterator(this->m_table); }//返回指向hashtable起始位置的迭代器
    iterator end()noexcept
    { return iterator(this->m_table,this->m_table.capacity); }//返回指向hashtable结尾位置的迭代器
}

下面是为HashTableAbstract定制的forward(向前)迭代器的主要的代码实现：

#include <cassert>
#include <type_traits>
#include <iterator>
/* 实现hashtable 标准的forward迭代器
 */
template<typename V>
// 继承自`std::iterator` V指哈希表中元素类型 
// std::forward_iterator_tag用于定义迭代器类型，这里是指forward迭代器
struct _HashTable_Iterator:public std::iterator<std::forward_iterator_tag,V>{
    typedef _HashTable_Iterator<V>      _Self;
    typedef _HashNode                   _Node;
    typedef V&                          reference;
    typedef V*                          pointer;
    const HashtableCore &m_table;
    HASH_TABLE_SIZE_TYPE m_index;
    HASH_NODE_PTR m_pNode;
    // 构造函数
    explicit
    _HashTable_Iterator(HashtableCore &table,decltype(m_index) index=0)noexcept:m_table(table),m_index(index){
//do somthing
    }
    /*_HashTable_Iterator(const _HashTable_Iterator &)=default;
    _Self& operator=(const _HashTable_Iterator &)=default;*/
    // 实现 前置自增操作符++
    _Self& operator++()noexcept{
    //do something
        return *this;
    }
    // 实现 后置自增操作符++
    _Self operator++(int){
        _Self tmp=*this;
        ++(*this);
        return tmp;
    }
    // 实现 取容器元素内容操作符*
    reference operator*() const noexcept
    { return *static_cast<V*>(m_pNode->obj);}
    // 实现 取对象地址操作符-> (访问容器元素的成员)
    pointer operator->() const noexcept
    { return static_cast<V*>(m_pNode->obj);}
    // 实现比较操作符(相等)==
    bool
    operator==(const _Self& v) const noexcept
    { return &m_table==&v.m_table&&m_index == v.m_index&&m_pNode==v.m_pNode; }
    // 实现比较操作符(不相等)!=
    bool
    operator!=(const _Self& v) const noexcept
    { return &m_table!=&v.m_table||m_index != v.m_index||m_pNode!=v.m_pNode; }
};

这样，HashTableAbstract就拥有了一个标准的向前(forward)迭代器,于是我们可以像使用其他标准容器一样用迭代器遍历整张哈希表:

HashTableAbstract <int,int> hashtab;
        for(auto itor=hashtab.begin();itor!=hashtab.end();itor++)
            top.insert((*itor), FCUtils::compare(node->code, code));

还可以利用C++11的新特性:基于范围的for循环( the range-base for statement)将代码更加简化：

HashTableAbstract <int,int> hashtab;
        for(const auto &node:hashtab)
            top.insert(node, FCUtils::compare(node.code, code));

总结

实现自定义的迭代器并不复杂,主要注意几点：

自定义迭代器必须继承自std::iterator, 其实std::iterator只是个元模板，里面没什么内容，主要是定义了迭代器特性(std::iterator_traits),为你的自定义迭代器定义了标准迭代器所需要的的5种数据类型,这里涉及到C++的元模板编程，不在本话题的范围，就不深入说了，有兴趣可以找找关于这方面的资料来看。

  template<typename _Tp>
    struct iterator_traits<_Tp*>
    {
      //迭代器类型 (分为output,input,forward,bidirectional,radom_access五种)
      typedef random_access_iterator_tag iterator_category;
      typedef _Tp                         value_type;//容器中元素的类型
      typedef ptrdiff_t                   difference_type;//步长类型(用于计算元素之间的距离)
      typedef _Tp*                        pointer;//容器中元素指针类型
      typedef _Tp&                        reference;//容器中元素引用类型
    };

必须实现指定类型的迭代器所必须的操作(符)

以本例中的forward迭代器为例，按照《C++标准库(第2版)》的说明需要实现以下操作符：

表达式	效果	说明
*iter	访问实际元素
iter->	访问实际元素的成员
++iter	向前步进(返回新位置)
++iter	向前步进(返回旧位置)
iter1==iter2	判断两个迭代器是否相等
iter1!=iter2	判断两个迭代器是否不相等
TYPE()	创建迭代器(default 构造函数)	*
TYPE(iter)	复制迭代器(copy 构造函数)	*
iter1=iter2	对迭代器赋值(assign)	*