迭代器与traits编程技法

最新推荐文章于 2022-04-06 15:50:33 发布

delphiwcdj

最新推荐文章于 2022-04-06 15:50:33 发布

阅读量1k

点赞数

分类专栏： Genericity

本文链接：https://blog.csdn.net/delphiwcdj/article/details/9101827

版权

Genericity 专栏收录该内容

1 篇文章

订阅专栏

本文探讨了迭代器在设计模式中的重要性，特别是在STL中的应用，以及如何使用迭代器作为不同数据容器和算法之间的桥梁。迭代器类似于智能指针，主要通过重载`operator*`和`operator->`来实现其功能。文章还提到了Traits编程技法，当需要获取迭代器关联类型如value type时，利用模板参数推导的局限性，并指出在某些情况下需要专门的Traits类来获取这些信息。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

2013-06-15 wcdj

迭代器设计思维

(1) 迭代器（iterators）是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。

(2)《设计模式》一书提供有23个design patterns的完整描述，其中iterator模式定义为：提供一种方法，使之能够依序巡防某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。

(3) 不论是泛型思维或STL的实际运用，iterators都扮演着重要的角色。STL的中心思想在于：将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以一贴胶着剂将它们撮合在一起。容器和算法的泛型化，从技术角度看并不困难，C++的class templates和functiontemplates可分别达成目标。如何设计出两者之间的良好胶着剂才是大难题。以算法find为例，以下是容器、算法、迭代器的合作展示：

/**
   *  @if maint
   *  This is an overload used by find() for the Input Iterator case.
   *  @endif
  */
  template<typename _InputIterator, typename _Tp>
    inline _InputIterator
    __find(_InputIterator __first, _InputIterator __last,
	   const _Tp& __val, input_iterator_tag)
    {
      while (__first != __last && !(*__first == __val))
	++__first;
      return __first;
    }

只要给予不同的迭代器，find便能够对不同的容器进行查找操作：

// file: 3find.cpp
#include <vector>
#include <list>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
	const int arraySize = 7;
	int ia[arraySize] = {0,1,2,3,4,5,6};

	vector<int> ivect(ia, ia+arraySize);
	list<int> ilist(ia, ia+arraySize);
	deque<int> ideque(ia, ia+arraySize);

	vector<int>::iterator it1 = find(ivect.begin(), ivect.end(), 4);
	if (it1 == ivect.end())
	{
		cout << "4 not found." << endl;
	}
	else
	{
		cout << "4 found. " << *it1 << endl;  
	}

	list<int>::iterator it2 = find(ilist.begin(), ilist.end(), 6);
	if (it2 == ilist.end())
	{
		cout << "4 not found." << endl;
	}
	else
	{
		cout << "4 found. " << *it2 << endl;  
	}

	deque<int>::iterator it3 = find(ideque.begin(), ideque.end(), 8);
	if (it3 == ideque.end())
	{
		cout << "4 not found." << endl;
	}
	else
	{
		cout << "4 found. " << *it3 << endl;  
	}

	return 0;
}

/*
output:
mba:stl gerryyang$ g++ -o 3find 3find.cpp 
mba:stl gerryyang$ ls
3find		3find.cpp
mba:stl gerryyang$ ./3find 
4 found. 4
4 found. 6
4 not found.
*/

(4) 迭代器是一种smart pointer。迭代器是一种行为类似指针的对象，而指针的最常见行为是dereference和member acess，因此迭代器最重要的工作就是对operator*和operater->进行overloading工作。在C++标准库中auto_ptr是一个用来包装native pointer的对象，以解决声名狼藉的memory leak问题，auto_ptr用法和原生指针一模一样：

#include <iostream>
#include <string>
#include <memory>// auto_ptr class

using std::cout;
using std::endl;
using std::string;
using std::auto_ptr;

void f1()
{
	int *ip = new int(123);// dynamically allocate a new object
	cout << "&ip = " << ip << "; *ip = " << *ip << endl;

	/* code that throws an exception that is not caught inside f1() */

	delete ip;
}

void f2()
{
	auto_ptr<int> ap(new int(456));// allocate a new object
	cout << "&ap = " << &ap << "; *ap = " << *ap << endl;

	/* code that throws an exception that is not caught inside f2() */

	// auto_ptr freed automatically when function ends
}

void f3()
{
	auto_ptr<string> ap_string(new string("delphiwcdj"));
	cout << "ap_string = " << *ap_string << endl;

	*ap_string = "gerry";
	cout << "ap_string = " << *ap_string << endl;

	if (ap_string->empty())
	{
		cout << "ap_string is empty" << endl;
	}
	else
	{
		cout << "ap_string is non-empty" << endl;
	}

}


int main() 
{
	cout << "auto_ptr usage\n" << endl;

	f1();

	f2();

	f3();

	return 0;
}
/*
g++ -Wall -g -o auto_ptr auto_ptr.cpp 

output:
auto_ptr usage

&ip = 0x804b008; *ip = 123
&ap = 0xbfa85d70; *ap = 456
ap_string = delphiwcdj
ap_string = gerry
ap_string is non-empty
*/

(5) 为了完成一个针对某种容器而设计的迭代器，我们无可避免地会暴露了太多此容器实现细节，即要设计出某种容器的迭代器，首先必须对此容器的实现细节有非常丰富的了解，既然这无可避免，干脆就把迭代器的开发工作交给容器的设计者好了，如此一来，所有实现细节反而得以封装起来不被使用者看到。这正是为什么每一种STL容器都提供有专属迭代器的缘故。

(6) 迭代器相应型别（associated types）

假设算法中有必要声明一个变量，以“迭代器所指对象的型别”为型别如何是好？毕竟C++只支持sizeof()，并未支持typeof()，即便动用RTTI性质中的typeid()，获得的也只是型别名称，不能拿来做变量声明之用。解决办法是：利用function template的参数推导（argument deducation）机制。

PS: 面向对象编程所依赖的多态性称为运行时多态性，泛型编程所依赖的多态性称为编译时多态性或参数式多态性。

#include <iostream>
using namespace std;

template <class I, class T>
void func_impl(I iter, T t)
{
    T tmp;// 这里解决了问题，T就是迭代器所指之物的型别，本例为int/short

    // 这里做原本func()应该做的全部工作
    cout << "func_impl: sizeof(tmp)=" << sizeof(tmp) << endl;
    cout << "func_impl: t=" << t << endl;
}

template <class I>
inline
void func(I iter)
{
    func_impl(iter, *iter);// func的全部工作移交给func_impl
}

int main()
{
    int i = 10;
    func(&i);

    short j = 20;
    func(&j);

    return 0;
}
/*
output:
mba:stl gerryyang$ g++ -o 3find 3find.cpp 
mba:stl gerryyang$ ./3find 
func_impl: sizeof(tmp)=4
func_impl: t=10
func_impl: sizeof(tmp)=2
func_impl: t=20
*/

#include <iostream>
using namespace std;

template <typename I, typename T>
T func_impl(I iter, T t)
{
	T tmp;// 这里解决了问题，T就是迭代器所指之物的型别，本例为int/short

	// 这里做原本func()应该做的全部工作
	cout << "func_impl: sizeof(tmp)=" << sizeof(tmp) << endl;
	cout << "func_impl: t=" << t << endl;
	return t+1;
}

template <typename I>
inline
void func(I iter)
{
	*iter = func_impl(iter, *iter);// func的全部工作移交给func_impl
}

int main()
{
	int i = 10;
	func(&i);
	cout << "i=" << i << endl;

	short j = 20;
	func(&j);
	cout << "j=" << j << endl;

	return 0;
}
/*
output:
mba:stl gerryyang$ g++ -o 3find 3find.cpp 
mba:stl gerryyang$ ./3find 
func_impl: sizeof(tmp)=4
func_impl: t=10
i=11
func_impl: sizeof(tmp)=2
func_impl: t=20
j=21
*/

注意：迭代器相应型别不只是“迭代器所指对象的型别（value type）”一种而已，最常用的相应型别有5种，然而并非任何情况下任何一种都可以利用上述的template参数推导机制来取得。