容器

類目：容器

描述

容器是一個可以存儲對象（它的元素），并具有訪問其元素的方法的一個對象。特別是，每一個容器模式類型都有一個關聯的迭代器類型來遍歷容器中的元素。

不能保證容器中的元素按特定的方式來存儲；事實上，不同的是每次迭代器是如何通過容器的。也不能保證容器的多個迭代器是一直有效的。（特定的容器類型，像前向容器是提供這樣的保證的。）

容器“擁有”它的元素：存儲在一個容器中的元素的壽命不能超過容器本身。[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前向容器沒有這個限制。

參見

迭代器概述，輸入迭代器，序列

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、全文索引

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、內存分配》
        

在Microsoft Access 2007 中執行更新查詢時，出現“操作或事件已被禁用模式阻止”。




選中“啟用此內容”，確定。

“我的產品還沒有準備好。”你說這之前。我們都曾經說過。

每個人在發布他們第一個產品的時候都會覺得他們的產品還沒有完全準備好?；蛘呱踔潦且呀洶l布在使用的，也沒有想象中的那么完美，因為如果你只是做一點點，他就會變的更好一點。在正常情況下，這會導致潛在很大的改善路線圖，在一個不正常的情況下，它會導致這個產品無休止的迭代，始終得不到結果。

大約在一年前，我拜訪了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親自監督他們的辦公室空間的設計?！冻恕穼а軧rad 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/

標準模板庫 目錄一   容器

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(位集)

下一節 《標準模板庫 目錄二 迭代器》

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

如果你理解算法，迭代器和容器，那么就幾乎知道STL的所有。然后，STL還包括一些其他類型的組件。首先，STL包括一些utilities：在庫的不同地方使用的非?；镜母拍詈凸δ堋ssignable概念，例如，描述那些有賦值操作符和拷貝構造函數的類型。幾乎所有STL的類都是Assignable模式，幾乎所有的算法都要求他們的參數是Assignable模式的。

其次，STL包含一些低層次的機制來分配和釋放內存。分配器非常專業，無論你使用它們的目的是什么，你都可以安全的忽略它們。

最后，STL包括了大量的函數對象集，也被稱為函子(functors)。正如迭代器是指針的泛化，函數對象是函數的泛化：你可以使用普通的函數調用方法來調用一個函數對象：這里有幾種不同概念的函數對象關系，包括一元函數（只有一個參數的函數對象，即一個被稱為f(x)的函數對象）和二元函數（需要兩個參數的函數對象，即一個被稱為f(x,y)的函數對象）。函數對象是一般程序的一個重要組成部分，因為它們不僅僅允許對象類型抽象泛型編程還允許正在執行的操作抽象泛型編程。

改善(Refinement)

輸入迭代器實際上是一個比較薄弱的概念：它必須的要求很少。輸入迭代器必須支持指針的算術運算的一個子集（使用前綴和后綴操作符+來增加輸入迭代器）），但是并不是需要指針所有的算術運算。這對于find算法已經足夠了，但是一些另外的算法的參數需要滿足額外的要求。reverse算法，它的參數的“減少”(decrement)功能必須要像“增加”(increment)功能一樣的，它使用表達式 --last。在概念方面，我們說revers算法的參數必須是雙向迭代器(Bidirectional Iterator)模式，而不是輸入迭代器。

雙向迭代器概念非常類似于輸入迭代器概念：它只是簡單的增加了一些額外的要求。雙向迭代器模式類型是輸入迭代器模式類型的一個子集。任何一個類型，如果它是雙向迭代器模式，那么它肯定也是輸入迭代器模式。例如，int*，既是雙向迭代器模式又是輸入迭代器模式。但istream_iterator，只是一個輸入迭代器模式。它不符合更嚴格的雙向迭代器的要求。雙向迭代器是輸入迭代器的一個改進。改進這個概念就跟c++類中的繼承非常相似：我們使用不同的詞，而不叫它“繼承”的最主要的原因是強調“改進”的概念而不是實際類型。

除了我們已經討論的兩個迭代器概念，其實還有另外三個迭代器概念：這5個迭代器概念有輸出迭代器，輸入迭代器，前向迭代器，雙向迭代器和隨機訪問迭代器；前向迭代器是輸入迭代器的改進，雙向迭代器是前向迭代器的改進，隨機訪問迭代器是雙向迭代器的改進。輸出迭代器與其他四個迭代器是有關系的，擔不是一部分層次的改進：它不是任何其他迭代器概念的改進，也沒有其他迭代器是從改進它而來的。迭代器概述有更多關于迭代器一般的消息。

容器類，像迭代器一樣，被組織成一個層次的概念。所有容器都是容器概念模式；更完善的概念；如序列和關聯容器，描述特定類型的容器。

下一節 《STL的其他部分》

概念和建模(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)》

迭代器(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;
   }


下一節 《概念與建模》