【文章內容簡介】 utputInterator。 泛型算法 泛型算法分類： 1． 查找算法 ：有 13種查找算法用各種策略去判斷容器中是否存 在 一 個 指 定 值 。 equal_range() 、 lower_bound() 和upper_bound()提供對半查找形式 。 2． 排序和通用整序算法 ：共有 14種排序 （ sorting） 和通用整序 （ ordering） 算法 ， 為容器中元素的排序提供各種處理方法 。所謂整序 ， 是按一定規(guī)律分類 ， 如分割 （ partition） 算法把容器分為兩組 ， 一組由滿足某條件的元素組成 ， 另一組由不滿足某條件的元素組成 。 3．刪除和代替算法 ：有 15種刪除和代替算法。 4．排列組合算法 ：有 2種算法。排列組合是指全排列。如：三個字符 {a， b， c}組成的序列有 6種可能的全排列： abc， acb，bac， bca， cab， cba；并且六種全排列按以上順序排列，認為 abc最小， cba最大，因為 abc是全順序（從小到大）而 cba是全逆序（從大到小）。 泛型算法 5．生成和改變算法 ：有 6種，包含生成（ generate），填充（ fill）等等。 6．關系算法 ：有 7種關系算法，為比較兩個容器提供了各種策略，包括相等（ equal()），最大（ max()），最?。?min()）等等。 7．集合算法 ： 4種集合（ set）算法提供了對任何容器類型的通用集合操作。包括并（ union），交（ intersection），差（ difference）和對稱差（ symmetric difference）。 8. 堆算法 ：有 4種堆算法。堆是以數(shù)組來表示二叉樹的一種形式。標準庫提供大根堆（ max_heap），它的每個結點的關鍵字大于其子結點的關鍵字。 9. 算術算法 ：該類算法有 4種，使用時要求包含頭文件 numeric。 關聯(lián)容器 關聯(lián)容器 (associative container)的引入： 它們能通過關鍵字（ search key）直接訪問 (存儲和讀取元素 )。四個關聯(lián)容器為：集合（ set），多重集合（ multiset），映射（ map）和多重映射（ multimap）。 集合和多重集合類 映射和多重映射類 集合和多重集合類 集合和多重集合類引入： 它們提供了控制數(shù)值集合的操作，其中數(shù)值是關鍵字，即不必另有一組值與每個關鍵字相關聯(lián)。集合與多重集合類的主要差別在于多重集合允許重復的關鍵字，而集合不允許重復的關鍵字。 集合和多重集合類提供了控制數(shù)值集合的操作，其中數(shù)值是關鍵字，即不必另有一組值與每個關鍵字相關聯(lián)。 多重集合允許重復的關鍵字（ key），而集合不允許。 元素的順序由 比較器函數(shù)對象 （ parator function object）確定。如對整型 multiset，只要用比較器函數(shù)對象lessint排序關鍵字，元素即可按升序排列。 set類模板聲明為： templatetypename Key, typename Pred = lessKey, typename A = allocatorKey class set。 //模板參數(shù)表中的非類型參數(shù)同樣可有默認值 集合和多重集合類 set容器的構造函數(shù)： set ()。 //構造一個空的按默認次序排列的集合 set (pr)。 //構造一個空的按函數(shù)對象 pr排序的集合 set (first,last)。 //構造一個默認次序排列的集合， //元素值由區(qū)間 [first,last)指定的序列復制 set (first,last,pr)。 //同上，但按函數(shù)對象 pr排序 這些構造函數(shù)還可以顯式給出分配子 (Allocator)對象。 集合和多重集合類支持雙向迭代子。 multiset和 set通常實現(xiàn)為 紅黑二叉排序樹。 紅黑二叉排序樹是實現(xiàn)平衡二叉排序樹的方法之一。 【 例 】 整型多重集合關聯(lián)容器類 映射和多重映射類 映射和多重映射類引入： 它們提供了操作與關鍵字相關聯(lián)的映射值（ mapped value）的方法。映射和多重映射的主要差別在于多重映射允許存放與映射值相關聯(lián)的重復關鍵字，而映射只允許存放與映射值一一對應的單一關鍵字。 多重映射和映射關聯(lián)容器類用于快速存儲和讀取關鍵字與相關值（關鍵字 /數(shù)值對， key/value pair）。如果保存學生的簡明資料，要求按學號排序，使用映射關聯(lián)容器（因為不會重號）是最合適的。如用姓名排序，因姓名可能重復，使用多重映射更為合適。使用時要用頭文件 map。 映射和多重映射類 map類模板聲明： templatetypename Key,typename T,typename Pred = lessKey, typename A = allocatorpairconst Key,T class map。 map容器有多種 構造函數(shù) ： map ()。 //構造一個空的按默認次序排列的映射 map (pr)。 //構造一個空的按函數(shù)對象 pr排序的映射 map (first,last)。 //構造按默認次序排列的映射， //元素值由區(qū)間 [first,last)指定的有序序列復制 map (first,last,pr)。 //同上，但按函數(shù)對象 pr排序 這些構造函數(shù)還可以顯式給出分配子 (allocator)對象。 映射和多重映射類 映射的使用： 映射和多重映射類 支持雙向迭代子 。 映射定義了成員操作符 []： Tamp。 operator[const Keyamp。 key] 這樣映射的使用是非常方便的，就如同一個數(shù)組，關鍵字作為下標，相關值作為元素值。 【 例 】 我國部分省份與面積映射關聯(lián)容器類的演示 。 容器適配器 容器適配器 （ container adapter） ： 棧，隊列和優(yōu)先級隊。所謂適配器并不獨立，它依附在一個順序容器上。如要聲明一個用矢量實現(xiàn)的字符型堆棧，聲明如下： stackvectorchar sk。 然后它可以象順序容器一樣使用。但它沒有自己的構造和析構函數(shù)，它使用其實現(xiàn)類（如 vector）的構造和析構函數(shù)。隊列（ queue）默認用 deque為基礎，棧（ stack）可用vector或 deque為基礎。 棧類 隊列類 優(yōu)先級隊列類 棧類 棧并不獨立，它依附在一個順序容器上。 棧（ stack）可用 vector或 deque為基礎。 聲明一個用矢量實現(xiàn)的字符型堆棧，格式如下： stackvectorchar sk。 【 例 】 演示堆棧的壓入和彈出。 棧類的引入： 隊列類 隊列（ queue）： 默認以 deque為基礎 【 例 】 演示隊列的入隊和出隊。 優(yōu)先級隊列類 優(yōu)先級隊列（ priority_queue）適配器： 用以實現(xiàn)優(yōu)先級隊列。元素插入是自動按優(yōu)先級順序插入，使最高優(yōu)先級元素首先從優(yōu)先級隊列中取出。常用矢量為基礎容器。默認時 priority_queue用 vector為基礎數(shù)據(jù)結構。 【 例 】 優(yōu)先級隊列類演示，頭文件用queue，優(yōu)先級用數(shù)表示，數(shù)值越大優(yōu)先級越高。 第十一章 標準模板庫（ 選讀 ） 課程全部結束 祝同學們有一個好成績！ 表 標準庫容器類 標準庫容器類 說明 順序容器 vector（參量） deque（雙端隊列） list（列表） 從后面快速插入與刪除，直接訪問任何元素 從前面或后面快速插入與刪除，直接訪問任何元素 從任何地方快速插入與刪除，雙鏈表 關聯(lián)容器 set（集合） multiset（多重集合） map（映射） multimap（多重映射） 快速查找，不允許重復值 快速查找，允許重復值 一對一映射，基于關鍵字快速查找，不允許重復值 一對多映射，基于關鍵字快速查找，允許重復值 容器適配器 stack（棧） queue（隊列） priority_queue （優(yōu)先級隊列） 后進先出（ LIFO） 先進先出（ FIFO） 最高優(yōu)先級元素總是第一個出列 表 所有標準庫容器共有的函數(shù)（ 1） 提供容器默認初始化的構造函數(shù)。通常每個容器都有幾個不同的構造函數(shù)，提供容器不同的初始化方法 將容器初始化為現(xiàn)有同類容器副本的構造函數(shù) 撤消容器時，進行內存處理 判容器是否為空，空返回 true,不空返回 false 返回容器中最多允許的元素量 返回容器當前元素量 默認構造函數(shù) 復制構造函數(shù) 析構函數(shù) empty() max_size() size() 說明 標準庫容器共有的函數(shù) 將一個容器賦值復制給另一個同類容器 交換兩個容器的元素 如果前面的容器小于后面的容器，則返回 true，否則返回 false，不適用于 priority_queue 如果前面的容器小于等于后面的容器，則返回 true，否則返回 false，不適用于 priority_queue 如果前面的容器大于后面的容器，則返回 true，否則返回 false，不適用于 priority_queue 如果前面的容器大于等于后面的容器，則返回 true，否則返回 false，不適用于 priority_queue 如果前面的容器等于后面的容器，則返回 true，否則返回 false，不適用于 priority_queue 如果前面的容器不等于后面的容器，則返回 true，否則返回 false，不適用于 priority_queue operator= swap() operator operator= operator operator= operator== operator!= 說明 標準庫容器共有的函數(shù) 表 所有標準庫容器共有的函數(shù)（ 2） 表 所有標準庫容器共有的函數(shù)（