欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++ 实现自定义类型的迭代器操作

程序员文章站 2022-06-17 14:26:19
##动机我们知道stl实现了很多算法(#include),如果项目是基于stl构建那么能够最大化使用现有代码当然是最好的。在stl中容器和算法之间的桥梁是迭代器。所以...

##动机

我们知道stl实现了很多算法(#include<algorithm>),如果项目是基于stl构建那么能够最大化使用现有代码当然是最好的。在stl中容器和算法之间的桥梁是迭代器。所以在定义好自定义类型的容器后,接下来就是迭代器的实现。

stl中的迭代器

迭代器模式是一种经典的设计模式,而stl的迭代器实现用到了模板的一些特性和技能,在这里稍微介绍一下

下面是stl中结构体iterator的定义,这么定义是给后面的算法多态和萃取时(具体见书中介绍)使用的。

其中的_category 和_ty 没有默认值,需要自己给参数的。

_ty就是元素的类型

template<class _category,
 class _ty,
 class _diff = ptrdiff_t,
 class _pointer = _ty *,
 class _reference = _ty&>
 struct iterator
 { // base type for iterator classes
 typedef _category iterator_category;
 typedef _ty value_type;
 typedef _diff difference_type;
 typedef _diff distance_type; // retained
 typedef _pointer pointer;
 typedef _reference reference;
 };

而_category是迭代器的类型,主要有以下几种

// iterator stuff (from <iterator>)
// iterator tags (from <iterator>)
struct input_iterator_tag //只读
 { // identifying tag for input iterators
 };
struct _mutable_iterator_tag //只写
 { // identifying tag for mutable iterators
 };
struct output_iterator_tag //只写
 : _mutable_iterator_tag
 { // identifying tag for output iterators
 };
struct forward_iterator_tag //前向移动
 : input_iterator_tag, _mutable_iterator_tag
 { // identifying tag for forward iterators
 };
struct bidirectional_iterator_tag //可双向移动
 : forward_iterator_tag
 { // identifying tag for bidirectional iterators
 };
struct random_access_iterator_tag //随机读写
 : bidirectional_iterator_tag
 { // identifying tag for random-access iterators
 };
//...

自定义迭代器

我希望迭代器有以下操作:*,++。另外还想要通过迭代器调用count_if函数。那看一下count_if都用到哪些操作符吧

// template function count_if
template<class _init,
 class _pr> inline
 typename iterator_traits<_init>::difference_type
 _count_if(_init _first, _init _last, _pr _pred)
 { // count elements satisfying _pred
 typename iterator_traits<_init>::difference_type _count = 0;
 for (; _first != _last; ++_first)
 if (_pred(*_first))
  ++_count;
 return (_count);
 }

可以看到用到了++,!=,*。所以我们的迭代器需要把这些都给实现了。代码很简单:

#include<iterator>
template<class t>
class myiterator : public iterator<input_iterator_tag, t>{
 public:
 myiterator(t* p){
  _ptr = p;
 }
 //赋值
 myiterator& operator = (const myiterator &iter)
 {
 _ptr = iter._ptr;
 }
 //不等于
 bool operator != (const myiterator &iter)
 {
 return _ptr!= iter._ptr;
 }
 //等于
 bool operator == (const myiterator &iter)
 {
 return _ptr == iter._ptr;
 }
 //前缀自加
 myiterator& operator ++ ()
 {
 _ptr++;
 return *this;
 }
 //后缀自加
 myiterator operator ++ (int)
 {
 myiterator tmp= *this;
 _ptr++;
 return tmp;
 }
 //取值
 t& operator * ()
 {
 return *_ptr;
 }
 private:
 t* _ptr;//实际的内容指针,通过该指针跟容器连接
};

自定义容器

下面给出个简单的数组容器,实现了数组的基本操作。并把刚刚定义的迭代器内置了

template<class t>
class myvector{
public:
 typedef myiterator<t> iterator;//所有类型迭代器用同一个名字,便于写出更通用的代码
 myvector(){
 _selfelems = new t[32];
 _count = 32;
 init();
 }
 myvector(int n){
 _selfelems = new t[n];
 _count = n;
 init();
 }
 void init(){
 memset(_selfelems, 0, sizeof(t)* _count);
 }
 //常用接口
 t& operator[](int i){
 return _selfelems[i];
 }
 iterator begin(){
 return iterator(_selfelems);
 }
 iterator end(){
 return iterator(_selfelems + _count);
 }
 int size() const {
 return _count;
 }
private:
 t* _selfelems;
 int _count;
};

##测试

定义一个vector和自定容器myvector,用迭代器去访问,并通过迭代器使用conunt_if函数,可以看到用法完全一样

bool eq_10(int k){
 return k == 10;
}
int main(){
 //自定义类型
 myvector<int> mv(10);
 mv[3] = 10; mv[9] = 10;
 myvector<int>::iterator it = mv.begin();
 cout <<"mv:"<<endl;
 while (it != mv.end()){
 cout << *(it++) << " ";
 }
 cout << endl;
 cout << count_if(mv.begin(), mv.end(), eq_10) << endl;
 //stl 容器
 vector<int> v(10,0);
 v[3] = 10; v[9] = 10;
 vector<int>::iterator it1 = v.begin();
 cout << "v:" << endl;
 while (it1 != v.end()){
 cout << *(it1++) << " ";
 }
 cout << endl;
 cout << count_if(mv.begin(), mv.end(), eq_10) << endl;
 getchar();
 return 0;

总结和思考

所以简单来说,如果想要定义自己容器的迭代器并想通过迭代器调用stl的算法函数的话。首先继承iteroter,然后实现必要的操作符即可。不过具体的算法函数对迭代器类型是有要求的,这个需要自己把握。

在这个简单的示例里面,直接用myvector的指针(mv._ptr)也是可以调用count_if的,因为stl通过模板偏特化技术使得迭代器也支持原生指针。不过既然把访问元素都放到迭代器中了,我们就可以对所有的容器用统一的方式访问了,而不用暴露每个容器的细节(myvector::_ptr):

//t为某种迭代器
template<class t>
void display(t it, t end){
 t it1 = it;
 while (it1 != end){
 cout << *(it1++) << " ";
 }
 cout << endl;
 cout << count_if(it,end, eq_10) << endl;
}
int main(){
 //自定义类型
 myvector<int> mv(10);
 mv[3] = 10; mv[9] = 10;
 //stl 容器
 vector<int> v(10, 0);
 v[3] = 10; v[9] = 10;
 //vector 和 myvector底层实现有很大区别,但是可用同一个函数做遍历等操作
 display(mv.begin(), mv.end());
 display(v.begin(), v.end());
 getchar();
 return 0;
}

迭代器赋予了容器更多的功能和通用性

补充知识:c++ 自定义迭代器(实现++递增两格)

//效果每次迭代器加移动两格

#pragma once
//myiterator.h
#include <iterator>
#include <exception>
template<typename container>
class myiterator :public std::iterator<std::random_access_iterator_tag, typename container::value_type>
{
protected:
  container& container;
  typename container::iterator pos;
public:
  explicit myiterator(container& c) :container(c), pos(c.begin()){}
  myiterator(const myiterator& rhs) :container(rhs.container),pos(rhs.pos) {}
  myiterator& operator =(const myiterator& rhs)
  {
    throw_ex(rhs.container);
    pos = rhs.pos;
    return *this;
  }
  //--等就省略了...
  myiterator& operator ++()
  {
    auto tmp = container.end() - 1;
    if (pos == tmp)
      ++pos;
    else
      pos += 2;
    return *this;
  }
  bool operator ==(const myiterator& rhs)const
  {
    try
    {
      if (&rhs.container == &container)
        return pos == rhs.pos;
      else
      {
        throw exception("对象错误");
      }
    }
      catch (exception &e)
      {
        cout << e.what();
        exit(exit_failure);
      }
    }
bool operator !=(const myiterator& rhs)const
{
  return !(*this == rhs);
}
typename container::value_type & operator *()
{
      return *pos;
}
void begin()
{
  pos = container.begin();
}
void end()
{
  pos = container.end();
}
private:
  void throw_ex(const container& c)
  {
    try
    {
      if (&c == &container)
        return;
      else
        throw exception("copy 构造失败");
    }
    catch (exception &e)
    {
      cout << e.what();
      exit(exit_failure);
    }
  }
};
//无法使用或添加vector<t> vec 成员函数vec.begin()或全局函数begin(vec)
//我们做个假冒的全局函数 start(vec) over(vec)
template<typename container>
myiterator<container> start(container& c)
{
    myiterator<container> mi(c);
    mi.begin();
    return mi;
}
template<typename container>
myiterator<container> over(container & c)
{
    myiterator<container> mi(c);
    mi.end();
    return mi;
}

//main.cpp

#include <iostream>
#include <vector>
#include "myiterator.h"
#include <list>
using namespace std;
//因继承了iterator<std::random_access_iterator_tag,container::value_type>才拥有此特性
template<typename iterator>
void printiterator(const iterator &it)
{
  cout << typeid(typename iterator_traits<iterator>::iterator_category).name() << endl;
}
int main()
{
  vector<int> coll{ 1,2,3,4,5,6,7,8,9,10 };
  myiterator<decltype(coll)> myit(coll);
  printiterator(myit);
  for (; myit != over(coll); ++myit)
  {
    cout << *myit << ends;
  }
  system("pause");
  return 0;
}

效果:

C++ 实现自定义类型的迭代器操作

以上为个人经验,希望能给大家一个参考,也希望大家多多支持。如有错误或未考虑完全的地方欢迎留言讨论,望不吝赐教。