很弱很弱的c++ 2004-5-10 19:27
<open>c++:Iterator分不分类型？
rt
boynoon 2004-5-10 19:39
Re:<open>c++:Iterator分不分类型？
这个，不清楚
求助助教大人
omale 2004-5-10 19:43
Re:<open>c++:Iterator分不分类型？
标准模板库(The Standard Template Library, STL)定义了五种迭代器。下面的图表画出了这几种：
<!-- CETagParser ~code
<br><table cellpadding=0 cellspacing=0 border=0 WIDTH=94% bgcolor='#000066' align=center><tr><td><table width=100% cellpadding=5 cellspacing=1[/img]<TR><TD BGCOLOR='#f4f4f4'>input iterators output iterators
\ /
forward iterators
|
bidirectional iterators
|
random access iterators<!-- CETagParser ~/code
</td></tr></table></td></tr></table><br>
要注意，上面这图表并不是表明它们之间的继承关系：而只是描述了迭代器的种类和接口。处于图表下层的迭代器都是相对于处于图表上层迭代器的扩张集。例如：forward迭代器不但拥有input和output迭代器的所有功能，还拥有更多的功能。
下面是关于这些迭代器功能的简短说明：
Input 迭代器：允许向前递增迭代器而使其指向下一个元素(使用 ++ 操作符)，并可以读取迭代器指向(使用 * 操作符)的数据。
Output迭代器：允许向前递增迭代器而使其指向下一个元素，并可以给迭代器指向的对象赋新值。
Forward迭代器：支持读、写操作；提供一个遍历方向。
Bidirectional迭代器：允许在两个遍历方向。
Random access迭代器：支持访问容器任意位置的算法操作。例如：
string::iterator it = s.begin();
char c = *(it+5); // skip five characters
很弱很弱的c++ 2004-5-10 19:57
Re:<open>c++:Iterator分不分类型？
OutputIterator filter （<!-- CETagParser ~color=#DC143C
<font color="#DC143C">InputIterator<!-- CETagParser ~/color
</font> first, InputIterator last, <!-- CETagParser ~color=#FF1493
<font color="#FF1493">OutputIterator <!-- CETagParser ~/color
</font> at,
const ElemType &val, Comp pred)
这两个Iterator一定要设成不一样的类型么？
一样的话会有什么影响？
omale 2004-5-10 21:21
Re:<open>c++:Iterator分不分类型？
不太明白楼上的意思。
能否详细叙述一下。
thanks
很弱很弱的c++ 2004-5-11 14:14
Re:<open>c++:Iterator分不分类型？
我要THANKS才对！
这个是那个函数：
template
<typename InputIterator, typename OutputIterator, typename ElemType, typename Comp>
OutputIterator filter (<!-- CETagParser ~color=#DC143C
<font color="#DC143C">InputIterator <!-- CETagParser ~/color
</font> first, InputIterator last, <!-- CETagParser ~color=#DC143C
<font color="#DC143C">OutputIterator <!-- CETagParser ~/color
</font> at,
const ElemType &val, Comp pred)
{
while((first=find_if(first, last, bind2nd(pred, val)))!=last)
{
cout<<"filter number:"<<*first<<endl;
*at++=*first++;
}
return at;
}
first和at是两个不一样类型的Iterator么？
为什么要这样子？
（sorry，口表能力差了点）
chen15959 2004-5-12 17:49
Re:Re:<open>c++:Iterator分不分类型？
[quote]
[b]很弱很弱的c++: Re:<open>c++:Iterator分不分类型？[/b]
template <typename InputIterator, typename OutputIterator, typename ElemType, typename Comp>
OutputIterator filter (InputIterator first, InputIterator last, OutputIterator at,
const ElemType &val, Comp pred)
{
while((first=find_if(first, last, bind2nd(pred, val)))!=last)
{
cout<<"filter number:"<<*first<<endl;
*at++=*first++;
}
return at;
}[/quote]
你所标出的InputIterator/OutputIterator只是一个类型名而已，是自己使用的标识符（见模板定义）。如果硬要与omale大哥说的内容联系起来的话，就是first/last可以是input iterator，at可以是output iterator。这样可以使用不同类型的迭代器。
[img]http://bbs.tongji.net/images/smiles/dozingoff.gif[/img] 我想我也没说明白。谁让我一直用且仅用random access iterator来着。
如果只是针对你的特定问题，那么可以使用相同类型的iterator。
OwnWaterloo 2008-10-8 01:38
这样使得这个函数更加泛化
先将原来的代码从新帖一遍， 那样子看着太累了……[code]tempalte< class InIt,class OutIt,typename Elem,class F2 >
OutIt Filter( InIt first , InIt last , OutIt dst , const Elem& val , F2 f ) {
while ( ( first=std::find_if( first , last , std::bind2nd(f,val) ) )!=last ) {
std::cout<<"Filter: <<*first<<std::endl;
*dst++ = *first++;
}
return dst;
}[/code]1.
原来来代码里的 < InputIterator,OutputIterator,ElemType,Comp > 可以理解成一个[color=red]占位符[/color]。
更正规一点地说， 它们叫模板形参列表 [b][color=red]template[/color][/b] [b][color=red]parameter[/color][/b](s) [b][color=red]list[/color][/b]
所以，我改成InIt,OutIt,Elem,F2和原来表达的是完全相同的含义。
以函数[color=red]声明[/color]为例 ：
return_type function( p1 a1, p2 a2, p3 a3, p4 a4 ); 同
return_type funciont( p1 v1, p2 v2, p3 v3 , p4 v4 ); 是完全一样的， 甚至可以这样写：
return_type funciont( p1 , p2, p3 , p4 ); 也算一个合法的声明。
也就是说 函数声明 仅需要指出
1.返回类型
2.函数名
3.函数参数列表
更近一步， 函数的参数列表是由参数[color=red]个数[/color]以及它们[color=red]各自的类型[/color]（可变参数也算一种特殊的参数类型……）决定， 与[color=red]参数名[b]无关[/b][/color]， 甚至可以[color=red]省略[/color]。
这个声明说明的是， 这个函数有[color=red]4个[/color]参数， 类型分别是[color=red] p1, p2, p3, p4[/color] ， 参数直接被无视了。
而函数模板或者类模板的模板参数列表：[code]template< class InputIterator, class OutoutIterator, typename ElemType, class Comp> 同
template< class InIt, class OutIt, typename Elem , class F2> 是完全一样的， 甚至可以这样写
template< class , class , typename, class > 也ok[/code]也就是说 —— 决定模板参数列表是否等同的仅仅是[color=red]类型参数[/color]的[b][color=red]个数[/color][/b]而已。
这3个模板参数列表说明的都是同一件事： 有4个[color=red]类型参数[/color]
对于声明来说， 这就足够了。
btw： 使用class 和 typename 的区别是： [b]没有区别[/b]！
如果非要说一点区别的话， class是首先引入的， typename是后来加入的一个关键字。
而不支持参数列表里使用typename的编译器已经是非常少见了。
有一个默认的习惯就是， 使用class 暗指这是一个用户自定义类型， 使用typename暗指这即可以是用户自定义类型，也可以是内建类型。
但这也仅仅是一个习惯而已……
2.再回忆一下， 编写函数的时候， 什么时候需要写出变量名？
答案是， 在写函数体的时候，而且仅当需要[color=red]使用[/color]这个参数的时候， 才必须[color=red]给形参赋予一个名字[/color]。否则没法使用它。
例子： 某些编译器会在函数没有使用参数的时候， 给出一个警告。 这时候省略这个参数名字就可以了。
LRESULT OnClose(HWND /* hwnd */, UINT /* msg */ , WPARAM /* wparam */ , LPARAM /* lparam */) {
return 1; // 不许关闭
}
同理，模板参数列表也是在当且仅当需要[color=red]使用这个类型[/color]的时候， 才需要赋予它一个名字。
比如一个变态的类模板声明：[code]template< class, typename >
struct pair;
接着是它的定义：
template<typename F,class S>
struct pair {
...
};[/code]但是函数模板[color=red]通常[/color]要赋予[color=red]类型参数[/color]一个名字，因为函数模板不能仅声明一个参数列表就够了…… 马上接着的就是函数的声明， 而[color=red]函数需要类型名字[/color]。
所以一下是一个完整的函数模板声明（也是可以算是上面两份函数模板定义的声明）：[code]template<class InIt,class OutIt,typename Elem,class F2>
OutIt Filter(InIt ,InIt ,OutIt ,const Elem&, F2 );[/code]因为需要 OutIt , InIt, Elem, F2 来声明这个函数的[color=red]返回值类型[/color]和[color=red]参数列表[/color]， 所以需要取一个名字。
而函数定义的时候， 完全可以另外换一套名字， 不考虑代码的可读性的话，它们仅仅是一个占位符一样的东西。
（类模板声明和函数模板声明，同样可以干类似函数声明一个参数而不去使用而不命名的事， 这个比较不重要， 一般不会这么做…… 下面会继续解释）
3.现在可以解释：
[quote]
这两个Iterator一定要设成不一样的类型么？
一样的话会有什么影响？
first和at是两个不一样类型的Iterator么？
为什么要这样子？
[/quote]
如果函数模板是这样子：[code]template< class Iterator, class E, class F>
Iteraotr Filter(Iterator first,Iterator last,Iterator at, const E& v,F f);[/code]就和上面若干个声明完全不同了 ——
模板参数列表变了， 个数少了。
函数参数列表也不一样了， first,last 同 at 现在[color=red]必须[/color]是[color=red]相同[/color]的类型。 而以前是可以不同， 也可以[color=red]相同[/color]。
这样带来的影响就是： 降低了函数的[color=red][b]泛化程度[/b][/color]。
例子：[code]int a[] = {1,2,3,4,5,4,3,2,1};
std::vector<int> v;
Filter_original(a, a+sizeof(a)/sizeof(a[0]), std::back_insert(v), 3, std::less<int>() );
是可以的， 其中四个模板实参分别是 int*, std::back_inserter_iterator<std::vector<int,std::allocator<int> > > , int , std::less<>[/code]而新的函数限制了first, last, at必须是同类型， 所以只能这样使用：[code]int a[] = {1,2,3,4,5,4,3,2,1};
std::vector<int> src(a,a+sizeof(a)/sizeof(a[0]) );
std::vector<int> dst;
Fillter_new(src.begin(),src.end(), std::back_insert(src), 3, std::less<int>() );
int b[sizeof(a)/sizeof(a[0])] = {0};
Fillter_new(a,a+sizeof(a[0]), b, 3 , std::less<int>() ); [/code]// [color=red][b]注意[/b][/color]， 如果不是因为有Filter的实现代码， 这样使用是[color=red]危险[/color]的， 因为b不会[color=red]自动增长[/color]。 这里仅仅是为了说明前3个参数类型必须相同而已。
再举一个函数的例子：
说了这么多才说明白（有说明白么……） 一个问题…… 我都觉得自己很罗嗦…… 老了……
LONG InterlockedIncrement(LONG volatile* Addend); 同
LONG InterlockedAdd(LONG volatile* Addend,LONG Value); 相比
前者只能加1 ， *Addend += 1;
而后者通过[color=red]多了一个参数[/color]，可以做到可以加任意的数 *Addend += Value; 从而更灵活。
将类型定为4种，而不是3种， 使得可以[color=red]接受不同的迭代器[/color]， 从而更[color=red]泛化[/color]一点。
那为什么MS要设计那2个函数？ 为什么不只设计一个？
因为可能有硬件不支持Add，只支持Increament，后者用前者模拟实现。
将类型定为4种而不是5种从而让让函数参数可以是5种不同的类型可以么？
一般不会这样， 因为 [first,last) 指出一个容器的区间， 肯定来自同一个容器对象， 它的迭代器类型也肯定是相同的。
规定first,last, 也许会丧失一部分泛化的能力， 但能检查出更多的编译错误。
[[i] 本帖最后由 OwnWaterloo 于 2008-10-8 01:48 编辑 [/i]]
OwnWaterloo 2008-10-8 02:14
补充一下， 关于unnamed template parameter。
类模板比于函数模板多（但不限于）一个特性： 可以有默认（类型）参数。
template< class T1,class T2, class /*unnamed_and_reserve_for_future*/ = void>
class C {};
同时，也比函数模板少（也不限于）一个特性： 自动参数推导。
C< int,int > ii; // ok;
C< char,long, i_want_to_use_type > lcu; //ok
C< short > missing; // 少了一个类型参数
使用unnamed template parameter ，只要放在最后， 给定一个默认参数， 不会造成太大的困扰。
编译器会默默的忍受……
但是一般没有这样的设计。
函数模板相反， 没有默认类型参数（以后可能会加入）， 但是有参数推导机制。
template<class T>
T1 max(const T& v1,const T& v2) { ... }
max('a','z'); // max<char>('a',"z");
max(0.1,0.2); // max<double>(0.1,0.2);
不能被推导的参数，必须像上面一样指定出来。
template< typename dst_type , typename src_type >
dst_type union_cast(src_type src) {
union {
src_type src;
dst_type dst;
} u = { src };
return u.dst;
}
typedef int (*func_t)(int);
func_t fun = union_cast<func_t>( & strcmp );
现在 函数指针fun和strcmp 有相同的地址 （注意 不能直接调用 *fun() ）
返回类型不参与类型参数推导， 所以（返回类型是模板类型参数的话）一般放在第1个， 否则这个参数之前（包含它自己）的类型参数都要指定才行。 现实中的例子（上面那个也算）还有 std::get_temporary_buffer 。
比如
func_t fun = union_cast< int (*)(const char*,const char*) , func_t >( & strcmp );
就让人很难受 ……
同时， 如果函数模板有一个unnamed template parameter， 那肯定不会出现函数的参数列表里， 也肯定不能被推导， 视这个参数在列表中的位置， 要明确写出很多参数才行 ……
template< class T1, class T2, ... , class /**/ , class Ti , ... class Tn >
void bad_design( ... );
bad_design<A1,A2, ... , A_for_unnamed /* 余下的是否要写要看能否自动推导出来 */ > ( ... );
[[i] 本帖最后由 OwnWaterloo 于 2008-10-8 02:19 编辑 [/i]]
OwnWaterloo 2008-10-8 02:37
iterator_category
解释了上面的问题后， 再来看STL对iterator的分类。
同何牛所说， STL将iterator按照[color=red]接口[/color]分为5类。
在泛型程序设计中， 接口这个到处都在使用的概念， 有一个特定与这个领域的名词：
[color=red][b]concept[/b][/color]s
也就是这种类型必须
1.支持的操作
例子：
5种迭代器分别需要支持的操作何牛已经说了。
函数对象必须支持调用操作符 operator() ( parameter-list );
2.满足的语义。
例子：
std::auto_ptr 不能同STL 容器协同工作， 因为后者需要元素具有 “值语义” 。
关联容器的比较类型必须满足严格弱排序。
3.有特定的命名函数
例子：
std::back_inserter_iterator ，std::stack , std::queue 要求容器提供名称为 push_back 的函数
4.有特定的嵌套类型
例子：
可适配函数对象都必须有 result_type , first_argument_type 这2个嵌套类型， 二元可适配函数对象还必须有 second_argument_type
iterator 必须有 iterator_category, value_type, difference_type, reference, pointer （或者必须特化 std::iterator_traits ）
5.想不出来了……
可以说明STL中iterator分类的最好例子就是， 同时也可以说明为什么他们之间有继承关系…… （其实是多余的……）
std::distance 和 std::advance 的实现。 有兴趣可以参考相关书籍 如 《STL源码剖析》
[[i] 本帖最后由 OwnWaterloo 于 2008-10-8 02:40 编辑 [/i]]
OwnWaterloo 2008-10-8 02:51
5种分类
namespace std {
struct input_iterator_tag { /* implement_definition */ };
struct output_iterator_tag { /* implement_definition */ };
struct forward_iterator_tag : input_iterator_tag
{ /* implement_definition */ };
struct bidirectional_iterator_tag : forward_iterator_tag
{ /* implement_definition */ };
struct random_access_iterator_tag : bidirectional
{ /* implement_definition */ };
} // end namespace
如果用户想自定义iterator类型， （而且打算和STL协同工作， 为什么不呢）
则该类型C必须有以下一些嵌套类型（也不一定全部需要）
iterator_category 为上面5种之一 （以后可能还会扩展）
value_type 该迭代器 *it 的东西
reference 一般就是 value_type&
pointer 一般就是 value_type* 即 &(*it)
difference_type it1-it2 得到的类型
STL提供了一个
template<class C,class T,class D = ptrdiff_t ,class P = T* ,class R = T& >
struct std::iterator {
typedef C iterator_category;
typedef D difference_type;
typedef P pointer;
typedef R reference;
}
用户可以由它继承（滥用…… 仅仅是方便而已） 直接得到这5种嵌套类型。
class MyIt : public std::iterator< random_access_iterator_tag,int > { ... }
MyIt::iterator_category 等等就都有了。