C++ 实现自定义类型的迭代器操作
##动机
我们知道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; }
效果:
以上为个人经验,希望能给大家一个参考,也希望大家多多支持。如有错误或未考虑完全的地方欢迎留言讨论,望不吝赐教。