随笔 - 46  文章 - 39  trackbacks - 0
<2022年5月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(2)

随笔分类

随笔档案

友情链接

搜索

  •  

最新评论

阅读排行榜

评论排行榜

容器


类目:容器

描述


容器是一个可以存储对象(它的元素),并具有访问其元素的方法的一个对象。特别是,每一个容器模式类型都有一个关联的迭代器类型来遍历容器中的元素。

不能保证容器中的元素按特定的方式来存储;事实上,不同的是每次迭代器是如何通过容器的。也不能保证容器的多个迭代器是一直有效的。(特定的容器类型,像前向容器是提供这样的保证的。)

容器“拥有”它的元素:存储在一个容器中的元素的寿命不能超过容器本身。[1]

完善


Assignable

相关类型

(Value type)值类型  X::value_type  存储在容器中的对象类型。值类型必须是Assignable,但不必是DefaultConstructible.[2]
(Iterator type)迭代器类型 X::iterator  迭代器类型用来遍历容器的元素。迭代器的值类型就是容器的值类型。必须可以从iterator type转换成const iterator type。迭代器的类型必须是一个输入迭代器。[3]
(Const iterator type)常量迭代器类型 X::const_iterator 是一个可以查看但不能修改容器中元素的迭代器类型。[3][4]
(Reference type)引用类型 X::reference 是一个行为像容器值类型引用的类型。[5]
(Const reference type)常量引用类型 X::const_reference 是一个行为像容器值类型常量引用的类型。[5]
(Pointer type)指针类型 X::pointer 是一个行为像容器值类型指针的类型。[6]
(Distance type)距离类型 X::distance_type  一个有符号整数类型来表示两个容器迭代器之间的距离。此类型必须跟迭代器之间的距离类型是一样的。[2]
(Size type)大小类型 X::size_type 一个无符号整数类型来表示任何非负值的容器距离类型。[2]

标记法


X    容器模式对象
a,b  X类型对象
T    X类型的值

定义


容器的(size)大小就是它所包含的元素个数,它是一个非负数。

容器的(area)面积就是它占用的字节数。更确切地说,它是元素的面积的总和加上与容器本身相关的任何开销。如果容器的值类型T是一个简单的类型(而不是一个容器类型),那么这个容器的面积就是sizeof(T)的常数倍。也就是说,一个简单值类型的容器a的面积是O(a.size())。

一个(variable sized)可变大小的容器提供插入和/或移除元素的方法;容器大小可能会变化。一个(fixed size)固定大小的容器,它的大小在它的生命周期内是一只不变的。一些固定大小的容器类型,大小在编译时确定。

有效表达式


除了Assignable,EqualityComparable,和LessThanComparable这些已经定义的表达式,下面的表达式也必须是有效的。

名称      表达式         类型要求    返回类型
范围起始  a.begin()                  如果是可变的,返回值为iterator(迭代器),否则为const_iterator[4][7]
范围结束  a.end()                    如果是可变的,返回值为iterator(迭代器),否则为const_iterator[4]
大小      a.size()                   size_type
最大容量  a.max_size()               size_type
空容器    a.empty()                  可转换成bool类型
交换      a.swap(b)                  void

表达式语义


名称          表达式       前提    语义                                                         后置
拷贝构造函数  X(a)                                                                              X().size() == a.size()。X()包含了a中所有元素的副本。
拷贝构造函数  X b(a)                                                                            b().size() == a.size()。b包含了a中所有元素的副本。
赋值运算符    b = a                                                                             b().size() == a.size()。b包含了a中所有元素的副本。
析构函数      a.~X()               销毁a中所有的元素,并释放为它们分配的内存(如果有的话)。
范围起始      a.begin()            返回一个指向容器第一个元素的迭代器(iterator)。[7]            a.begin()要么是提领要么是past-the-end。仅仅当a.size == 0的时候它才是past-the-end。
范围结束      a.end()              返回一个指向容器的最后一个元素的后面的迭代器(iterator)。     a.end 是 past-the-end。
大小          a.size()             返回容器的大小,也就是元素的个数。[8]                        a.size() >= 0 && a.size <= a.max_size()
最大容量      a.max_size()         返回容器的最大容量。[8]                                      a.max_size() >= 0 && a.max_size >= a.size()
空容器        a.empty()            相当于 a.size() == 0 (但是可能更快)                        
交换          a.swap(b)            相当于swap(a,b)[9]

复杂性担保

拷贝构造函数,复制操作符,析构函数跟容器大小呈线性关系。

begin()和end()的摊销时间为常数。

size()跟容器大小呈线性关系。[10] max_size()和empty()的摊销时间为常数。如果你要测试一个容器是否为空,你应该总是写c.empty而不是c.size() == 0。这两个表达式是等价的,但前者可能要快得多。

swap()的摊销时间为常数。[9]

不变量


有效范围     任何容器a, [a.begin(), a.end())是一个有效范围。[11]
范围大小     a.size()等于从a.begin()到a.end()的距离。
完整性       一个迭代算法[a.begin(), a.end()),将会遍历a中的每个元素。[11]

模型


vector

注释


[1]元素的寿命不能超过其容器可能看起来像一个严重的限制,事实上,它并不是限制。请注意指针和迭代器都是对象;就像任何其他对象一样,他们可以被存储在一个容器内。在这种情况下,容器拥有指针本身,而不是它们指向的对象。

[2]这种表达式必须是一个typedef,这是一个类型的代名词。

[3]这可能是一个typedef或者其他类型,或者一个定义嵌套类作为一个内部类的X的特定的类型。

[4]容器的iterator类型和const iterator类型可能是一样的:不能保证每个容器必须有一个相关的可变迭代器类型。例如,set和hash_set定义iterator和const iterator为同一类型。

[5]引用类型需要与普通C++引用类型有相同的语义,但它实际上并不是普通的C++引用。例如,在某些实现中,可能会提供额外的引用类型来支持非标准的内存模型。但是请注意,“智能引用”(用户定义的引用类型提供额外的功能)不是一个可行的选择。用户定义的类型不可能与C++引用类型具有相同语义,因为C++语言不支持重新定义的成员访问运算符(operator.)。

[6]跟[5]中的引用类型一样,指针类型需要与C++指针有相同的语义,但实际并不是C++指针。“智能指针”不同于“智能引用”是有可能的。因为可以为用户定义类型来定义的引用操作符和指针成员访问运算符可以访问运算符*和->。

[7]迭代器类型(iterator type)必须是一个输入迭代器(input iterator),它只提供了一个非常薄弱的担保;特别是,输入迭代算法必须都是“单通道”。容器只有一个简单的迭代器(iterator)可以随时激活。Forward Container(前向容器)没有这个限制。

[8]一个固定大小的容器,size() == max_size()。

[9]对于任何Assignable类型,swap可以定义分配条款。这需要三个任务,每一个容器类型,容器的大小呈线性关系。然而,在某种意义上,a.swap(b)是多余的。它的存在仅仅为了提高效率:许多容器,如vector和list,它实现swap的时间复杂度是不变的,而不是线性的。一些容器类型X,那么它们的模板化swap(X&,X&)可以简单地写在X::swap(X&)。也就是说X::swap(X&)只能定义在执行时间是常量的情况下。不是所有的容器类X都需要这样的一个成员函数,但是如果这样的函数存在,那么必须保证摊销时间为常量。

[10]对于许多容器,如vector和deque,size是O(1).这满足了O(N)的要求。

[11]虽然[a.begin(), a.end())必须是一个有效的范围,而且每个元素必须都包含在容器内,但是在这个范围内出现的顺序是不确定的。如果你两次遍历一个容器,它不能保证这两次的遍历顺序是相同的。Forward Container前向容器没有这个限制。

参见


迭代器概述,输入迭代器,序列
posted @ 2012-03-13 13:20 canaan 阅读(1608) | 评论 (0)编辑 收藏
6、函数对象
    1、简介
    2、概念
         1、generator(不需要参数的函数)
         2、一元函数
         3、二元函数
     4、Adaptable Generator(可适应的不需要参数的函数)
     5、一元可适应函数
     6、二元可适应函数
     7、谓词
          1、谓词
          2、二元谓词
          3、可适应谓词
          4、二元可适应谓词
          5、StrictWeakOrdering
     8、Monoid曹错
     9、随机数生成器
    3、预定义函数对象
         1、算术运算
          1、加法
              2、减法
          3、乘法(原名“次”)
          4、除法
          5、取模运算
          6、否定
     2、比较算法
          1、equal_to
          2、not_equal_to
          3、less
          4、greater
          5、less_equal
          6、greater_equal
     3、逻辑操作
          1、logical_and(逻辑与)
          2、logical_or(逻辑或)
          3、logical_not(逻辑否)
     4、广义身份认证操作
          1、identity
          2、project1st
          3、project2nd
          4、select1st
          5、select2nd
     5、subtractive_rng
    4、函数对象适配器
         1、binder1st
     2、binder2nd
     3、ptr_fun
     4、pointer_to_unary_function
     5、pointer_to_binary_function
     6、unary_negate
     7、binary_negate
     8、unary_compose
     9、binary_compose
     10、成员函数适配器
          1、mem_fun
          2、mem_fun_ref
          3、mem_fun1
          4、mem_fun1_ref
7、Utilities
    1、概念
    1、Assignable
    2、Default Constructible
    3、Equality Comparable
    4、LessThan Comparable
    2、函数
        1、关系操作符
    3、类
        1、pair
8、内存分配
    1、类
        1、分配器
    2、raw_storage_iterator
    2、函数
        1、construct
    2、destroy
    3、uninitialized_copy
    4、uninitialized_copy_n
    5、uninitialized_fill
    6、uninitialized_fill_n
    7、temporary_buffer
    8、get_temporary_buffer
    9、return_temporary_buffer
9、设计文档
    1、线程安全
    2、复杂规格的意义
    3、字符串的表示
10、分类索引
11、全文索引
posted @ 2012-03-12 15:27 canaan 阅读(236) | 评论 (0)编辑 收藏
4、迭代器
   1、简介
   2、概念
        1、普通迭代器
        2、输入迭代器
        3、输出迭代器
        4、前向迭代器
        5、双向迭代器
        6、随机访问迭代
    3、迭代器标签
        1、简介
        2、iterator_traits
        3、iterator_category
        4、distance_type
        5、value_type
        6、迭代器标签类
              1、input_iterator_tag
              2、output_iterator_tag
              3、forward_iterator_tag
              4、bidirectional_iterator_tag
              5、random_access_iterator_tag
        7、迭代器基础类
              1、input_iterator
              2、output_iterator
              3、forward_iterator
              4、bidirectional_iterator
              5、random_access_iterator
    4、迭代函数
         1、distance
         2、advance
    5、迭代器类
         1、istream_iterator
         2、ostream_iterator
         3、front_insert_iterator
         4、back_insert_iterator
         5、insert_iterator
         6、reverse_iterator
         7、reverse_bidirectional_iterator
         8、raw_storage_iterator
         9、sequence_buffer
5、算法
    1、不会改变内容的算法
         1、for_each
         2、find
         3、find_if
         4、adjacent_find
         5、find_fist_of
         6、count
         7、count_if
         8、mismatch
         9、equal
        10、search
        11、search_if
        12、find_end
    2、会改变内容的算法
         1、copy
         2、copy_n
         3、copy_backward
         4、交换
              1、swap
              2、iter_swap
              3、swap_ranges
         5、transform
         6、替换
              1、replace
              2、replace_if
              3、replace_copy
              4、replace_copy_if
         7、fill
         8、fill_n
         9、generate
        10、generate_n
        11、移除
               1、remove
               2、remove_if
               3、remove_copy
               4、remove_copy_if
        12、unique
    13、unique_copy
    14、reverse
    15、reverse_copy
    16、rotate
    17、rotate_copy
    18、random_shuffle
    19、random_sample
    20、random_sample_n
    21、partition
    22、stable_partition
    3、排序
         1、排序
          1、sort
          2、stable_sort
          3、partial_sort
          4、partial_sort_copy
          5、is_sorted
     2、nth_element
     3、二进制搜索
          1、lower_bound
          2、upper_bound
          3、equal_range
          4、binary_search
     4、merge
     5、inplace_merge
     6、排序范围内设置操作
          1、includes
          2、set_union
          3、set_intersection
          4、set_difference
          5、set_symmetric_difference
     7、堆操作
          1、push_heap
          2、pop_heap
          3、make_heap
          4、sort_heap
          5、is_heap
     8、最大值和最小值
          1、min
          2、max
          3、min_element
          4、max_element
     9、lexicographical_compare
    10、lexicographical_compare_3way
    11、next_permutation
    12、prev_permutation
    4、广义数值算法
         1、iota
     2、accumulate
     3、inner_product
     4、partial_sum
     5、adjacent_difference
     7、power

下一节 《标准模板库 目录三 函数对象、Utilities、内存分配
        
posted @ 2012-03-09 09:41 canaan 阅读(1069) | 评论 (0)编辑 收藏

在Microsoft Access 2007 中执行更新查询时,出现“操作或事件已被禁用模式阻止”。


选中“数据库工具”中的“消息栏”,然后单击“选项”。


选中“启用此内容”,确定。


posted @ 2012-03-08 15:46 canaan 阅读(1204) | 评论 (0)编辑 收藏


为什么你总是认为你的产品不够好
Why you'll always think your product is shit





我的产品还没有准备好。”你说这之前。我们都曾经说过。

每个人在发布他们第一个产品的时候都会觉得他们的产品还没有完全准备好。或者甚至是已经发布在使用的,也没有想象中的那么完美,因为如果你只是做一点点,他就会变的更好一点。在正常情况下,这会导致潜在很大的改善路线图,在一个不正常的情况下,它会导致这个产品无休止的迭代,始终得不到结果。

大约在一年前,我拜访了Pixar的办公室了解到有关此产品的一点,我想和大家分享下面的这个小故事:

Over at Pixar...
Matt Silas(@matty8r),Pixar的长期雇员带我参观了他们的办公室,我也接受了他的盛情款待。从Palo Alto出发经过长达一小时的车程终于到了Emeryville,Matt向我展示了整个个玻璃上的奥斯卡奖,然后开始全面的参观。我们有拍很多照片,所以这里好的像是:VentureBeat,Urbanpeak。

我一直是Pixar的粉丝--不仅仅是他们的产品,还有他们的历史和文化。关于Pixar和他们创造电影的过程是多么的迷人,还有很多话要讲,我推荐一本书:《To Infinity and Beyond》。它让我知道了在他们的电影中使用了一些非常的合作和迭代的方法,毕竟,做的比较多的还是软件。这里有一些简单的例子:

Pixar的团队是由有创意的人才和软件工程师组成的。这是反映在他们的高层,John Lasseter和Ed Catmull。

Pixar电影的过程是从一个故事开始的--然后故事情节--然后用一些方法来形成最后的蓝图。

他们每天在构建他们的“电影”,让他们知道他们的立场,在需要的地方用上素描和蹩脚的CGI--跟传统电影不同的是在它的最后。

有时候,他们与“玩具总动员”的原始版本,他们必须停止他们正在做的事情,然后重新开始这个电影制作过程直到所有事情确定下来--听起来很熟悉,有木有?

其他有关高科技世界的是Steve Jobs亲自监督他们的办公室空间的设计。《超人》导演Brad Bird对于这个有专业的说法:

“这是我们的建筑。这中间,他造了一个大的中庭区,最初似乎觉得这是在浪费空间。原因就是大家来之后都在各自的办公室空间工作。软件工程师在这里,画动画的在这里,还有那边是做设计的。Steve 把信箱,会议室,食堂,最出色的最想不到的是浴室,居然在最中间--当初让我们觉得很疯狂--每个人的一天都可以在这里完成。Jobs意识到当人们在于其他人眼神接触时,事情就会发生了。所以他想办法不让他们接触到其他公司。”

无论如何,我听到很多这样的故事--像预期的一样,这次参观是难以忘记的,最后,我们停在Pixar礼品店。
在那里,我问Matt一个休闲的问题,一年之后,我还清楚的记得:

我说:“Pixar电影中你最喜欢哪一部?”
Matt:  *叹气*
我笑着说: “为什么叹气?”
Matt:  “这是一个很棘手的问题,因为他们都是很好的。但是同时,因为你在这里工作,你花了那么长的时间在上面,你很难会去看它。你知道你所作的所有的小决定和所有采取的捷径。你也记得那些风险你必须放弃和结束的,因为你没有时间了。所以当你看电影的时候,你可以看到所有的缺陷,知道你看到你的朋友和家人时,你才会开始忘记这些。”

哇哦!如此深刻。

世界上像Pixar这样的公司,无疑会产生一些最令人喜爱和完美的经验,但是最后还是没能产生一个产品,让团队中所有的人都认为它是最好的。之后思考为什么会是这样呢,原因是显而易见的--用预见性和技能来完善一些能使之更好,还需要能力是一个巨大的关键点。比你的能力更关键的,我觉得是完善或者解决设计问题的速度不够快。因为所有的设计使整个系列平衡,这个时候你不结束,你到底想要什么呢。

教训:你永远是不会高兴的。

在这次谈话中我得到了,就是我们做很多工作让我们的产品更好,但是永远不会到达满意。一个伟人一旦说过你的产品是垃圾--也许你一直会认为它就是垃圾。然而在同一时间,它是我们创意的斗争,最终使我们的创作越来越好。有一天,即使你仍然认为你的产品很糟糕,你会看到你的顾客正在开心地使用它。

一个短暂的瞬间,你会忘记对于它你为什么会不满意。

特别感谢Matt Silas(@以撒1985, 关注它)给我一个独特的经验。(最后,我在Luxo Jr.旁边拍了一张照片后离开了。)



喜欢这篇文章吗?
如果你喜欢这篇文章,请订阅或者关注我的微薄。在这里你还可以找到更多的文章。
Andrew Chen写

Canaan翻译 微薄(@以撒1985)

2012年3月2日 下午7:27
原文:http://andrewchenblog.com/2012/03/02/why-your-product-will-never-seem-like-its-good-enough/
posted @ 2012-03-08 11:26 canaan 阅读(1025) | 评论 (1)编辑 收藏

标准模板库 目录一   容器

1、STL简介
2、如何使用文档
3、容器
    1、概念
        1、一般概念
           1、容器
           2、前向容器
           3、可逆容器
           4、随机访问容器
        2、序列
           1、序列
           2、前面插入序列
           3、后面插入序列
        3、关联容器
           1、关联容器
           2、简单关联容器
           3、结对关联容器
           4、排序关联容器
           5、哈希关联容器
           6、哈希函数
           7、单一关联容器
           8、多重关联容器
           9、单一排序关联容器
          10、多重排序关联容器
          11、单一哈希关联容器
          12、多重哈希关联容器
     2、容器类
        1、序列
           1、vector(向量)
           2、deque(队列)
           3、list(表)
           4、bit_vector(位向量)
        2、关联容器
           1、set(集合)
           2、map(映像)
           3、multiset(多重集)
           4、multimap(多重映像)
           5、hash_set(哈希集)
           6、hash_map(哈希映像)
           7、hash_multimap(哈希多重映像)
           8、hash(哈希)
        3、字符串包
           1、Character Traits
           2、char_traits
           3、basic_string
        4、rope
        5、容器适配器
           1、stack(栈)
           2、queue(队列)
           3、priority_queue(优先队列)
        6、bitset(位集)

下一节 《标准模板库 目录二 迭代器》
posted @ 2012-03-01 15:23 canaan 阅读(1119) | 评论 (0)编辑 收藏

STL的其他部分(Other parts of the STL)

如果你理解算法,迭代器和容器,那么就几乎知道STL的所有。然后,STL还包括一些其他类型的组件。首先,STL包括一些utilities:在库的不同地方使用的非常基本的概念和功能。Assignable概念,例如,描述那些有赋值操作符和拷贝构造函数的类型。几乎所有STL的类都是Assignable模式,几乎所有的算法都要求他们的参数是Assignable模式的。

其次,STL包含一些低层次的机制来分配和释放内存。分配器非常专业,无论你使用它们的目的是什么,你都可以安全的忽略它们。

最后,STL包括了大量的函数对象集,也被称为函子(functors)。正如迭代器是指针的泛化,函数对象是函数的泛化:你可以使用普通的函数调用方法来调用一个函数对象:这里有几种不同概念的函数对象关系,包括一元函数(只有一个参数的函数对象,即一个被称为f(x)的函数对象)和二元函数(需要两个参数的函数对象,即一个被称为f(x,y)的函数对象)。函数对象是一般程序的一个重要组成部分,因为它们不仅仅允许对象类型抽象泛型编程还允许正在执行的操作抽象泛型编程。
posted @ 2012-03-01 14:47 canaan 阅读(1201) | 评论 (0)编辑 收藏
改善(Refinement)

输入迭代器实际上是一个比较薄弱的概念:它必须的要求很少。输入迭代器必须支持指针的算术运算的一个子集(使用前缀和后缀操作符+来增加输入迭代器)),但是并不是需要指针所有的算术运算。这对于find算法已经足够了,但是一些另外的算法的参数需要满足额外的要求。reverse算法,它的参数的“减少”(decrement)功能必须要像“增加”(increment)功能一样的,它使用表达式 --last。在概念方面,我们说revers算法的参数必须是双向迭代器(Bidirectional Iterator)模式,而不是输入迭代器。

双向迭代器概念非常类似于输入迭代器概念:它只是简单的增加了一些额外的要求。双向迭代器模式类型是输入迭代器模式类型的一个子集。任何一个类型,如果它是双向迭代器模式,那么它肯定也是输入迭代器模式。例如,int*,既是双向迭代器模式又是输入迭代器模式。但istream_iterator,只是一个输入迭代器模式。它不符合更严格的双向迭代器的要求。双向迭代器是输入迭代器的一个改进。改进这个概念就跟c++类中的继承非常相似:我们使用不同的词,而不叫它“继承”的最主要的原因是强调“改进”的概念而不是实际类型。

除了我们已经讨论的两个迭代器概念,其实还有另外三个迭代器概念:这5个迭代器概念有输出迭代器,输入迭代器,前向迭代器,双向迭代器和随机访问迭代器;前向迭代器是输入迭代器的改进,双向迭代器是前向迭代器的改进,随机访问迭代器是双向迭代器的改进。输出迭代器与其他四个迭代器是有关系的,担不是一部分层次的改进:它不是任何其他迭代器概念的改进,也没有其他迭代器是从改进它而来的。迭代器概述有更多关于迭代器一般的消息。

容器类,像迭代器一样,被组织成一个层次的概念。所有容器都是容器概念模式;更完善的概念;如序列和关联容器,描述特定类型的容器。

下一节 《STL的其他部分》
posted @ 2012-02-28 10:33 canaan 阅读(2196) | 评论 (0)编辑 收藏

概念和建模(Concepts and Modeling)


任何模板函数的一个非常重要的问题,不仅仅是关于STL算法,而是什么类型集可以正确的替换形式模板参数。很明显,例如,int* 或double*可以替换find函数的形式模板参数InputIterator。同样清楚的是,int或double可能不行:find函数使用表达式*first,和用操作符,从而使int类型对象或double类型对象没意义。那么基本的答案是,发现STL隐式定义了一套类型的需求,它可以满足这些要求的实例。替换InputIterator的任何类型必须提供这些操作:它必须能够比较两个对象是否相等,它必须可以增加该类型的一个对象,它必须可以通过该类型的引用来获得它指向的对象,依次类推。

find函数并不是STL中有这些需求的唯一的算法;for_each函数和count函数,还有其他算法函数的参数也必须要满足这些要求。这些要求相当重要,值得我们给它们一个名字:我们称这种类型集的要求为概念(concept),我们称这个特定的概念为输入迭代器(Input Iterator)。一个类型如果满足了所有这些要求,我们说这个类型符合一个概念,或者说是一个概念模型。我们说int*是一个输入迭代器(Input Iterator)的模型,因为int*提供了输入迭代器的所有要求的操作。

概念不是C++语言的一部分;没有办法在一个程序中定义一个或者申明一个概念模型的特定类型。然而,概念是STL的一个极其重要的组成部分。使用概念(concepts)使得写程序时有可能把接口从实现中清楚地分离:find函数的作者只需要考虑这个接口符合输入迭代器(Input Iterator)概念,而不是去实现每一个可能的类型符合这个概念。同样,如果你想使用find函数,你只需要确保你传递给他的参数是输入迭代(Input Iterator)模型。这就是find函数和reverse函数可以用于lists,vector,C数组,和许多其他类型的原因:概念编程,而不是为特定类型编程,使得它可以重用软件组件和结合这些组件。

下一节 《改进(refinement)》
posted @ 2012-02-23 13:41 canaan 阅读(1284) | 评论 (0)编辑 收藏
迭代器(Iterators)

在上面C数组逆向排序的例子中,reverse的参数明显是double*类型。如果用reverse逆向排序vector或list, 参数又是什么呢?也就是说reverse申明的是什么参数,还有v.begin

()和v.end()返回什么?

答案就是reverse的参数是迭代器(iterators)就是指针对一般化。指针本身就是迭代器,所以reverse可以逆向排序C数组中的元素。类似的,vector申明了嵌套类型iterator和

const_iterator。在上面的例子中,v.begin()和v.end()的返回类型是 vector<int>::iterator。也有一些迭代器,像istream_iterator和ostream_iterator,它们与容器是没有

关联的。

迭代器是让算法与容器分离成为可能:算法是模板,需要被迭代类型参数化使用,所以它们不会限制在某一种容器类型。考虑,例如,如何写一个算法在一个范围内进行线性搜索

。下面是STL中find算法。

   template<class InputIterator, class T>
   InputIterator find(InputIterator first, InputIterator last, const T&value)
   {
    while(first != last && *first != value)++first;
        return first;
  }

find函数需要三个参数:两个迭代器定义一个范围,还有一个value值查找。它在[first,last)这个范围内从开始到最后一个一个检查迭代,当它找到一个迭代指向的值跟我们寻找

的值相同时或者它到达范围的结束时,就停止查找。
first和last被申明为InputIterator类型,而InputIterator是一个模板参数。也就是说实际上没有一个类型为InputIterator:当你调用find函数时,编译器会把形式参数

InputIterator和T替换成实际类型参数。如果find函数的前面两个参数类型为int*,第三个参数类型为int,那么就像调用下面的函数。
   int* find(int* first, int* last, const int& value)
   {
      while(first != last && *first != value)++first;
      return first;
   }


下一节 《概念与建模》
posted @ 2012-02-22 14:52 canaan 阅读(1182) | 评论 (0)编辑 收藏
仅列出标题
共5页: 1 2 3 4 5