第13章 標(biāo)準(zhǔn)庫中的容器

1、C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程第第13章章 標(biāo)準(zhǔn)庫中的容器標(biāo)準(zhǔn)庫中的容器 C+語言標(biāo)準(zhǔn)庫中，使用類模板實(shí)現(xiàn)了一些常用的數(shù)據(jù)結(jié)構(gòu)，稱為容器。程序員可以在自己的程序中方便的使用它們，這樣能夠提高編碼的速度和質(zhì)量。 本章介紹標(biāo)準(zhǔn)庫中的10種標(biāo)準(zhǔn)容器和2種近容器。 C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程知識(shí)體系知識(shí)體系本章要點(diǎn)：本章要點(diǎn)： 13.1 容器概述容器概述 13.2 第一類容器的第一類容器的iterator 13.3 容器中的嵌套類型容器中的嵌套類型 13.4 序列容器序列容器vector 13.5 序列容器序列容器deque 13.6 序列容器序列容器list 13.7 與函數(shù)對(duì)象有關(guān)

2、的類模板與函數(shù)對(duì)象有關(guān)的類模板 13.8 關(guān)聯(lián)容器關(guān)聯(lián)容器set C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程知識(shí)體系知識(shí)體系本章要點(diǎn)：本章要點(diǎn)： 13.9 關(guān)聯(lián)容器關(guān)聯(lián)容器multiset 13.10關(guān)聯(lián)容器關(guān)聯(lián)容器map 13.11關(guān)聯(lián)容器關(guān)聯(lián)容器multimap 13.12容器適配器容器適配器stack 13.13容器適配器容器適配器queue 13.14容器適配器容器適配器priority_queue 13.15近容器近容器bitset 13.16近容器近容器valarray C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.1 容器概述容器概述 STL（Standard Template Libra

3、ry）是標(biāo)準(zhǔn)模板庫的縮寫。在STL中，使用類模板實(shí)現(xiàn)的變長數(shù)組、鏈表、棧等數(shù)據(jù)結(jié)構(gòu)，被稱為容器。由于容器采用類模板實(shí)現(xiàn)，所以，容器中可以容納int、double等基礎(chǔ)數(shù)據(jù)類型的數(shù)據(jù)，也可以容納自定義類型的數(shù)據(jù)。容器對(duì)象可以看作是容納對(duì)象的對(duì)象。STL中的容器作為C+語言標(biāo)準(zhǔn)庫的一部分，均由“大師”級(jí)的程序員開發(fā)，它們不僅有很強(qiáng)的通用性，而且更高效、更安全。 STL中的容器分為3大類：序列容器、關(guān)聯(lián)容器和容器適配器。序列容器和關(guān)聯(lián)容器合稱第一類容器。 C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程 序列容器包括vector、deque和和list等3種容器，vector和deque都表示變長的數(shù)組結(jié)構(gòu)，l

4、ist表示雙向鏈表結(jié)構(gòu)；關(guān)聯(lián)容器包括set、multiset、map和和multimap等4種容器，它們都表示有序的，支持快速查找的數(shù)據(jù)結(jié)構(gòu)；容器適配器包括stack、queue和和priority_queue等3種容器，stack表示先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)（棧），queue表示先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（隊(duì)列），priority_queue表示保證最高“優(yōu)先級(jí)”的元素最先出的數(shù)據(jù)結(jié)構(gòu)（堆）。 之所以將容器stack、queue和priority_queue稱為容器適配器，是因?yàn)檫@些類模板并不是從零開始編寫的，它因?yàn)檫@些類模板并不是從零開始編寫的，它們是通過繼承或復(fù)合序列容器的方式得到的們是通過繼承或復(fù)合

5、序列容器的方式得到的 。 除了上述的容器以外，普通的數(shù)組、string類型、類模板valarray和類模板bitset被稱為近容器。 C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.2 第一類容器的第一類容器的iterator 每一種第一類容器（序列容器和關(guān)聯(lián)容器）都有自己的迭代器（iterator），并且它們擁有一個(gè)共同的名字iterator（統(tǒng)一名字的問題在13.3節(jié)講解）。使用容器的迭代器可以方便地訪問容器中的數(shù)據(jù)元素。 7種第一類容器根據(jù)自身底層數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，分別支持雙向迭代器和隨機(jī)訪問迭代器。其中，容器vector和deque支持隨機(jī)訪問迭代器，容器list、set、multiset、m

6、ap和multimap支持雙向迭代器。雙向迭代器作用在容器上時(shí)，可以進(jìn)行增1、減1的操作，即向后、向前移動(dòng)1個(gè)位置；隨機(jī)訪問迭代器除了具備雙向迭代器的功能以外，在不超出容器范圍的前提下，可以向后、向前移動(dòng)任意個(gè)位置。C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程 雙向迭代器和隨機(jī)訪問迭代器支持的運(yùn)算見下表: C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程 第一類容器中存在一些與迭代器有關(guān)的成員函數(shù)，容器適配器中則沒有這些成員函數(shù)。關(guān)于這些函數(shù)的名字及作用參見下表:C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.3 容器中的嵌套類型容器中的嵌套類型 代表“通用”容器的類模板中存在一些擁有相同名字的嵌套類型，這些嵌套類型有

7、的是在類模板中定義的嵌套類，有的僅僅是通過typedef定義的類型名。 下表中列舉了“通用”容器中一些常用的嵌套類型，在這些類型中有一些與迭代器有關(guān)的類型僅僅出現(xiàn)在第一類容器中，容器適配器則不支持這些嵌套類型的定義。 C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程在不同類型的容器中，這些嵌套類型的名字都是相同的。程序13.1中的函數(shù)模板swap_first_last用于交換第一類容器中首個(gè)和最后一個(gè)元素的位置。C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程1 /13.1 容器中嵌套類型的使用容器中嵌套類型的使用 2 #include 3 #include 4 #include 5 #include 6 #incl

8、ude 7 using std:cout; 8 using std:endl; 9 using std:ostream_iterator;10 using std:vector;11 using std:list;12 using std:copy;14 template15 void swap_first_last(T& container)16 T:iterator first=container.begin();18 T:iterator last=container.end();19 if(first=last)20 return;21 -last;22 T:value_typ

9、e tmp=*first;23 *first=*last;24 *last=tmp;25 27 int main()28 C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程29 ostream_iterator out1(cout, );30 vector int_v(5);31 for(int i=0;i5;+i)32 int_vi=i+1;33 coutint_v=;34 copy(int_v.begin(),int_v.end(),out1);35 coutendl;36 swap_first_last(int_v);37 coutint_v=;38 copy(int_v.begin(),int_v.

10、end(),out1);39 coutendl;41 ostream_iterator out2(cout);42 typedef list Lc;43 Lc char_l(3);44 char c=A;45 for(Lc:iterator p=char_l.begin();p!=char_l.end();+p)46 *p=c+;47 coutchar_l=;48 copy(char_l.begin(),char_l.end(),out2);49 coutendl;50 swap_first_last(char_l);51 coutchar_l=;52 copy(char_l.begin(),

11、char_l.end(),out2);53 coutendl;55 return 0;56 顯示結(jié)果：顯示結(jié)果：int_v=1 2 3 4 5int_v=5 2 3 4 1char_l=ABCchar_l=CBAC+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.4 序列容器序列容器vector 類模板vector屬于序列容器，它表示一個(gè)可變長的數(shù)組。在預(yù)分配的存儲(chǔ)空間存滿以后，再插入新數(shù)據(jù)時(shí)，存儲(chǔ)空間自動(dòng)翻倍。vector采用連續(xù)的存儲(chǔ)空間保存數(shù)據(jù)。因此，它的優(yōu)點(diǎn)是支持快速的隨機(jī)訪問，并且在其最后一個(gè)元素之后，高速的插入新數(shù)據(jù)（push_back），在尾部的刪除操作也是高速的（pop_back）。它的

12、缺點(diǎn)在于，在其數(shù)據(jù)結(jié)構(gòu)的中部插入或刪除元素的速度很慢。 程序13.2演示vector中主要成員函數(shù)的使用方法，同時(shí)驗(yàn)證預(yù)分配空間不滿足需要時(shí)，vector的存儲(chǔ)空間自動(dòng)翻倍。 C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程1 /13.2 序列容器序列容器vector 2 #include 3 #include 4 using std:cout; 5 using std:endl; 6 using std:vector;8 template 9 void print_vector(const vector& v)10 coutv.size()=v.size()endl;12 coutv.capac

13、ity()=v.capacity()endl;13 for(int i=0;iv.size();+i)14 coutvi ;15 coutn-endl;16 17 int main()18 vector v;20 for(int i=1;i=5;+i)21 22 v.push_back(i);23 print_vector(v);24 25 v.insert(v.begin()+2,6);26 print_vector(v);27 return 0;28 顯示結(jié)果：顯示結(jié)果：v.size()=1v.capacity()=11-v.size()=2v.capacity()=21 2-v.size

14、()=3v.capacity()=41 2 3-v.size()=4v.capacity()=41 2 3 4-v.size()=5v.capacity()=81 2 3 4 5-v.size()=6v.capacity()=81 2 6 3 4 5-C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.5 序列容器序列容器deque 類模板deque屬于序列容器，與vector相似，它也表示一個(gè)可變長的數(shù)組。與vector不同的是，vector將所有數(shù)據(jù)元素保存在一塊連續(xù)內(nèi)存中，而deque將數(shù)據(jù)元素保存在多塊連續(xù)的內(nèi)存中，同時(shí)在一個(gè)映射結(jié)構(gòu)中保存對(duì)這些內(nèi)存塊的跟蹤，以及它們的先后順序。在大部分需要使用

15、變長數(shù)組的情況下，我們應(yīng)該選擇deque，只有在確切知道數(shù)組最多存放多少個(gè)元素的情況下，最優(yōu)的選擇才是vector。類模板deque的缺陷在于，在中部插入或刪除數(shù)據(jù)的速度慢，這是連續(xù)存儲(chǔ)空間不可避免的缺陷。 程序13.3通過存放自定義類型的數(shù)據(jù)，來對(duì)vector和deque進(jìn)行比較。 C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程1 /13.3 序列容器序列容器deque 2 #include 3 #include 4 #include 5 using std:cout; 6 using std:endl; 7 using std:vector; 8 using std:deque;10 class A

16、11 12 int count;13 public:14 A()15 16 static int x=0;17 count=+x;18 coutcountcount的的A類型對(duì)象被構(gòu)造類型對(duì)象被構(gòu)造endl;19 20 A(const A& other)21 22 count=other.count;23 coutcountcount的的A類型對(duì)象發(fā)生拷貝構(gòu)造類型對(duì)象發(fā)生拷貝構(gòu)造endl;24 25 A()26 C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程27 coutcountcount的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)endl;28 29 ;30 int main()31 32 vec

17、tor v(2);34 cout-endl;35 v.push_back(A();36 cout-endl;37 38 cout-endl;39 40 41 deque d(2);42 cout-endl;43 d.push_back(A();44 cout-endl;45 46 cout-endl;47 48 return 0;49 顯示結(jié)果：顯示結(jié)果：count1的的A類型對(duì)象被構(gòu)造類型對(duì)象被構(gòu)造count1的的A類型對(duì)象發(fā)生拷貝構(gòu)造類型對(duì)象發(fā)生拷貝構(gòu)造count1的的A類型對(duì)象發(fā)生拷貝構(gòu)造類型對(duì)象發(fā)生拷貝構(gòu)造count1的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)-count2的的A類型對(duì)象被

18、構(gòu)造類型對(duì)象被構(gòu)造count1的的A類型對(duì)象發(fā)生拷貝構(gòu)造類型對(duì)象發(fā)生拷貝構(gòu)造count1的的A類型對(duì)象發(fā)生拷貝構(gòu)造類型對(duì)象發(fā)生拷貝構(gòu)造count2的的A類型對(duì)象發(fā)生拷貝構(gòu)造類型對(duì)象發(fā)生拷貝構(gòu)造count1的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)count1的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)count2的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)-count1的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)count1的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)count2的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)-count3的的A類型對(duì)象被構(gòu)造類型對(duì)象被構(gòu)造count3的的A類型對(duì)象發(fā)生拷貝構(gòu)造類型對(duì)象發(fā)生拷貝構(gòu)造

19、count3的的A類型對(duì)象發(fā)生拷貝構(gòu)造類型對(duì)象發(fā)生拷貝構(gòu)造count3的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)-count4的的A類型對(duì)象被構(gòu)造類型對(duì)象被構(gòu)造count4的的A類型對(duì)象發(fā)生拷貝構(gòu)造類型對(duì)象發(fā)生拷貝構(gòu)造count4的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)-count3的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)count3的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)count4的的A類型對(duì)象發(fā)生析構(gòu)類型對(duì)象發(fā)生析構(gòu)-C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.6 序列容器序列容器list 類模板list表示一個(gè)鏈表的結(jié)構(gòu)，它的底層存儲(chǔ)結(jié)構(gòu)采用的是雙向鏈表。正是由于雙向鏈表結(jié)構(gòu)的特性，list不支持

20、隨機(jī)訪問，但是與vector和deque相比，list容器在任意位置插入或刪除元素都是高速的。 由于類模板list采用雙向鏈表作為底層數(shù)據(jù)結(jié)構(gòu)，這使list具備了一些vector和deque不具備的成員函數(shù)。 程序13.4演示這些成員函數(shù)的使用。C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程1 /13.4 序列容器序列容器list6 using std:cout; 7 using std:endl; 8 using std:list; 9 using std:ostream_iterator;10 using std:copy;12 void print_list(const list& l,c

21、onst char* str)13 ostream_iterator out(cout, );15 coutstr;16 copy(l.begin(),l.end(),out);17 coutendl;18 19 bool less_3(int n)20 return n3;22 23 int main()24 int a1=1,5,5,8,7,8,3,9,7;26 int a2=0,1,2,4,8,5,6;27 list l1(a1,a1+9);28 print_list(l1,l1:);29 list l2(a2,a2+7);30 print_list(l2,l2:);31 cout-en

22、dl;32 33 l1.remove(8);34 print_list(l1,l1:);C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程35 l2.remove_if(less_3);36 print_list(l2,l2:);37 cout-endl;39 l1.reverse();40 print_list(l1,l1:);41 cout-endl;43 l1.sort();44 print_list(l1,l1:);45 l2.sort();46 print_list(l2,l2:);47 l1.merge(l2);48 print_list(l1,l1:);49 print_list(l2,l2:

23、);50 cout-endl;52 l1.unique();53 print_list(l1,l1:);54 l2.insert(l2.begin(),a2,a2+4);55 print_list(l2,l2:);56 cout-endl;58 l2.splice(l2.end(),l1);59 print_list(l1,l1:);60 print_list(l2,l2:);61 cout-endl;63 return 0;64 顯示結(jié)果：顯示結(jié)果：l1:1 5 5 8 7 8 3 9 7l2:0 1 2 4 8 5 6-l1:1 5 5 7 3 9 7l2:4 8 5 6-l1:7 9 3

24、 7 5 5 1-l1:1 3 5 5 7 7 9l2:4 5 6 8l1:1 3 4 5 5 5 6 7 7 8 9l2:-l1:1 3 4 5 6 7 8 9l2:0 1 2 4-l1:l2:0 1 2 4 1 3 4 5 6 7 8 9-C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.7 與與函數(shù)對(duì)象函數(shù)對(duì)象有關(guān)的類模板有關(guān)的類模板 在介紹關(guān)聯(lián)容器之前，本節(jié)介紹標(biāo)準(zhǔn)庫中與函數(shù)對(duì)象有關(guān)的類模板。在頭文件中包含的類模板unary_function和binary_function，它們派生了許多與函數(shù)對(duì)象有關(guān)的類模板。其中，類模板unary_function派生與一元函數(shù)對(duì)象有關(guān)的類模板，類模板bi

25、nary_function派生與二元函數(shù)對(duì)象有關(guān)的類模板。 C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程 除了類模板less以外，還有許多與函數(shù)對(duì)象有關(guān)的類模板。下表中列舉的與一元函數(shù)對(duì)象有關(guān)的函數(shù)模板繼承自u(píng)nary_function，與二元函數(shù)對(duì)象有關(guān)的函數(shù)模板繼承自binary_function。C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.8 關(guān)聯(lián)容器關(guān)聯(lián)容器set 關(guān)聯(lián)容器set表示集合。正常意義上的集合的特點(diǎn)是： 集合中的所有元素都是相同類型的； 集合中沒有重復(fù)元素； 集合中的元素是無序的。關(guān)聯(lián)容器set表示的集合，符合上述3點(diǎn)要求的前2點(diǎn)的同時(shí)，set為容器中的元素排了序。這是為了方便對(duì)容器

26、中元素進(jìn)行查找。1. 程序13.5演示類模板set的一些特性。C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程1 /13.5 關(guān)聯(lián)容器關(guān)聯(lián)容器set 2 #include 3 #include 4 #include 5 #include 6 using std:cout; 7 using std:endl; 8 using std:set; 9 using std:ostream_iterator;10 using std:copy;11 using std:pair;14 template15 void print_set(const T& s,const char* str)16 17 ost

27、ream_iterator out(cout, );18 coutstr;19 copy(s.begin(),s.end(),out);20 coutendl;21 23 int main()24 25 typedef set SI;26 SI s1;27 pair p1;28 for(int i=3;i0;-i)C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程29 p1=s1.insert(i);31 if(p1.second)32 cout為為s1插入插入*(p1.first)成功成功endl;33 34 p1=s1.insert(2);35 if(!p1.second)36 cout為為s1插入插入

28、*(p1.first)失敗失敗endl;37 print_set(s1,s1:);38 cout-endl;39 40 typedef setdouble,greater SD;41 SD s2;42 for(i=0;i10;+i)43 s2.insert(i*0.3);44 print_set(s2,s2:);45 if(s2.find(1.5)!=s2.end()46 couts2中存在中存在*s2.find(1.5)endl;47 if(s2.find(3.5)=s2.end()48 couts2中不存在中不存在3.5endl;49 cout-endl;51 return 0;52 顯示

29、結(jié)果：顯示結(jié)果：為為s1插入插入3成功成功為為s1插入插入2成功成功為為s1插入插入1成功成功為為s1插入插入2失敗失敗s1:1 2 3-s2:2.1 1.2 0s2中存在中存在1.2s2中不存在中不存在3.5-C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.9 關(guān)聯(lián)容器關(guān)聯(lián)容器multiset 關(guān)聯(lián)容器multiset也是為元素排序的容器，它與set的區(qū)別在于，multiset容器中允許重復(fù)元素的存在，因此，multiset容器的insert函數(shù)總是“成功”的。類模板multiset的聲明與set的聲明類似，這里不再贅述。由于類模板multiset允許有重復(fù)值的存在，因此它的insert、find

30、等函數(shù)與類模板set中的同名函數(shù)稍有不同。程序13.6介紹這些函數(shù)的使用方法。值得注意的是，類模板multiset和set同在中包含，并不存在名為的頭文件。C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.10 關(guān)聯(lián)容器關(guān)聯(lián)容器map 關(guān)聯(lián)容器map表示映射。如果把map容器看成線性表時(shí)，map容器中的每個(gè)元素都是“對(duì)兒”對(duì)象，即兩個(gè)對(duì)象的組合。如果把map容器看成二維表時(shí)，map容器中有2列元素，容器中的每行元素按第1列元素的值排序，第1列元素與第2列元素是一對(duì)一的映射。 程序13.7將使用map容器及其重載的“ ”運(yùn)算符函數(shù)，來統(tǒng)計(jì)一篇英文文章中各個(gè)單詞出現(xiàn)的次數(shù)。C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例

31、教程1 /13.7 關(guān)聯(lián)容器關(guān)聯(lián)容器map14 template 15 void print_map(const T& m)16 17 T:const_iterator p=m.begin();18 for(;p!=m.end();+p)19 coutfirst):second)=A&c=a&c=z)30 c= ;31 ss.put(c);32 33 string word;34 map words;35 while(ssword)36 +wordsword;37 print_map(words);39 return 0;40 顯示結(jié)果：顯示結(jié)果：But:1I:2If:

32、1a:1been:1had:1have:1i:6much:1so:1t:2the:4thought:13wasn:1wouldn:1C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.11 關(guān)聯(lián)容器關(guān)聯(lián)容器multimap 關(guān)聯(lián)容器multimap是允許關(guān)鍵字重復(fù)的容器。它與map的區(qū)別如同multiset與set的區(qū)別，即允許容器第1列元素值重復(fù)。由于這個(gè)原因，multimap容器不再支持“神奇”的“ ”運(yùn)算符。類模板multimap的聲明與類模板map的聲明類似，這里不再贅述。另外，類模板multimap被定義在中，并不存在名為的頭文件。 程序13.8改進(jìn)程序13.7，將程序13.7中map容器中的

33、數(shù)據(jù)轉(zhuǎn)存至一個(gè)multimap容器中，并按照單詞出現(xiàn)次數(shù)排降序。同時(shí)，在統(tǒng)計(jì)單詞出現(xiàn)次數(shù)時(shí)，不區(qū)分單詞的大小寫。 C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程1 /13.8 關(guān)聯(lián)容器關(guān)聯(lián)容器multimap 2 #include 3 #include 4 #include 5 #include 6 #include 7 using std:cout; 8 using std:endl; 9 using std:map;17 template 18 void print_map(const T& m)19 20 T:const_iterator p=m.begin();21 for(;p!=m.

34、end();+p)22 coutsecond):first)endl;23 25 class MyString:public string26 friend bool operator(const MyString& ms1,const MyString& ms2)28 29 int i;30 string s1=ms1;31 string s2=ms2;32 for(i=0;is1.size();+i)33 s1i=toupper(s1i);34 for(i=0;is2.size();+i)35 s2i=toupper(s2i);36 return s1=A&c=a&

35、amp;c=z)48 c= ;49 ss.put(c);50 51 MyString word;52 map words;53 while(ssword)54 +wordsword;55 56 multimapint,string,greater mwords;57 for(map:iterator p=words.begin();p!=words.end();+p)58 59 pair pa(p-second,p-first);60 mwords.insert(pa);61 62 print_map(mwords);64 return 0;65 顯示結(jié)果：顯示結(jié)果：thought:13I:8

36、the:4t:2a:1been:1But:1had:1have:1If:1much:1so:1wasn:1wouldn:1C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.12 容器適配器容器適配器stack 容器適配器stack表示先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)（棧）。之前曾經(jīng)提到，標(biāo)準(zhǔn)庫中容器適配器的代碼并不是從零開始編寫，而是適配某種序列容器。容器適配器stack可以使用3種序列容器中的任意一種適配，默認(rèn)使用deque。 程序13.9演示容器適配器stack的使用方法以及主要成員函數(shù)的使用。 C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程1 /13.9 容器適配器容器適配器stack13 template 14 vo

37、id push_pop_stack(T& s,const char* str)15 cout.setf(ios:fixed);17 T:value_type seed=T:value_type();18 for(int i=0;i5;+i)19 s.push(+seed+64);20 coutstr;21 while(!s.empty()22 couts.top() ;24 s.pop();25 26 coutendl;27 28 int main()29 30 stack s1;31 push_pop_stack(s1,s1:);32 33 stackdouble,vector s2

38、;34 push_pop_stack(s2,s2:);36 stackchar,list s3;37 push_pop_stack(s3,s3:);39 return 0;40 顯示結(jié)果：顯示結(jié)果：s1:69 68 67 66 65s2:69.000000 68.000000 67.000000 66.000000 65.000000s3:E D C B AC+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.13 容器適配器容器適配器queue 容器適配器queue表示先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（隊(duì)列）。容器適配器queue可以使用3種序列容器中的deque和list適配，默認(rèn)使用deque。不能使用vecto

39、r適配的原因是，vector只能從容器的一端進(jìn)行高速的插入和刪除數(shù)據(jù)，即類模板vector僅有push_back、pop_back函數(shù)，而不存在push_front、pop_front函數(shù)。類模板queue的聲明如下：templateclass T , class C = deque class queue ; 程序13.10演示容器適配器queue的使用方法以及主要成員函數(shù)的使用。C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程1 /13.10 容器適配器容器適配器queue 2 #include 3 #include 4 using std:cout; 5 using std:endl; 6 usin

40、g std:queue;8 int main() 9 queue q;11 for(int i=1;i=5;+i)12 q.push(i);13 while(!q.empty()14 15 coutq.front() ;16 q.pop();17 18 coutendl;19 20 return 0;21 顯示結(jié)果：顯示結(jié)果：1 2 3 4 5C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.14 容器適配器容器適配器priority_queue 容器適配器priority_queue表示最“大”元素總是最先被刪除的數(shù)據(jù)結(jié)構(gòu)（堆），當(dāng)然這里的最“大”是指在某種比較大小方式下的最“大”，用戶在使用容器適

41、配器priority_queue時(shí)，可以通過顯式提供模板參數(shù)改變默認(rèn)的比較大小方式。 容器適配器priority_queue可以使用3種序列容器中的vector和deque適配，默認(rèn)使用vector。 程序13.11演示容器適配器priority_queue的使用方法以及主要成員函數(shù)的使用。C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程1 /13.11 容器適配器容器適配器priority_queue 2 #include 3 #include 4 using std:cout; 5 using std:endl; 6 using std:priority_queue; 7 8 int main() 9

42、 10 priority_queue q;11 q.push(3);12 q.push(5);13 q.push(4);14 while(!q.empty()15 16 coutq.top() ;17 q.pop();18 19 coutendl;20 21 return 0;22 顯示結(jié)果：顯示結(jié)果：5 4 3C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程13.15 近容器近容器bitset 近容器bitset是二進(jìn)制位的集合，它的成員函數(shù)封裝一些常用的位運(yùn)算操作。bitset也是標(biāo)準(zhǔn)庫中唯一使用了非類類型參數(shù)的類模板，它的聲明如下： template class bitset; 參數(shù)N表示容器中持有

43、二進(jìn)制位的個(gè)數(shù)。程序13.12演示了容器bitset常用成員函數(shù)的使用方法。C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程1 /13.12 近容器近容器bitset 2 #include 3 #include 4 #include 5 using std:cout; 6 using std:endl; 7 using std:bitset; 8 using std:string; 9 using std:boolalpha;11 int main()12 13 bitset b;14 for(int i=9;i=0;-i)15 couti;16 coutendl;18 coutb:初始初始bendl;1

44、9 b.set(3);20 coutb:b.set(3)endl;21 b.set();22 coutb:b.set()endl;24 b.reset(3);25 coutb:b.reset(3)endl;26 b.reset();27 coutb:b.reset()endl;29 b.flip(3);C+程序設(shè)計(jì)實(shí)例教程程序設(shè)計(jì)實(shí)例教程30 coutb:b.flip(3)endl;31 b.flip();32 coutb:b.flip()endl;34 cout(b=2):b=2endl;35 cout=2)=2endl;36 cout(b&=10):b&=10endl;37

45、 cout(b|=10):b|=10endl;38 cout-endl;40 string str=b.to_string();41 coutstr:strendl;42 unsigned long ul=b.to_ulong();43 coutul:ulendl;45 coutb3:b3endl;46 coutb.at(3):b.at(3)endl;47 coutb.test(3):b.test(3)endl;48 coutb.count():b.count()endl;49 coutb.any():boolalphab.any()endl;50 coutb.none():b.none()endl;53 return 0;54 顯示結(jié)果：顯示結(jié)果：98765432100000000000:初始初始b0000001000:b.set(3)1111111111:b.set()1111110111:b.reset(3)0000000000:b.reset()0000001000:b.flip(3)1111110111:b.flip()1111011100:b=20000000010:b&=100000001010:b|=10-str:00000