在學習c++提高-STL總結了筆記,并分享出來。有問題請及時聯系部落客:Alliswell_WP,轉載請注明出處。
05-c++STLday11
目錄:一、常用容器1、上節作業——評委打分2、stack棧容器3、queue隊列容器4、list容器測試API、測試:删除自定義資料類型5、set容器(1)測試API(2)pair對組的建立方式——兩種(3)測試排序規則6、map容器測試API7、STL容器使用時機二、總結
一、常用容器
1、上節作業——評委打分
有5名選手:選手ABCDE,10個評委分别對每一名選手打分,去除最高分,去除評委中最低分,取平均分。
//1. 建立五名選手,放到vector中
//2. 周遊vector容器,取出來每一個選手,執行for循環,可以把10個評分打分存到deque容器中
//3. sort算法對deque容器中分數排序,pop_back pop_front去除最高和最低分
//4. deque容器周遊一遍,累加分數,累加分數/d.size()
//5. person.score = 平均分
1 /*
2 create by wp
3 2020.06.16
4 檔案功能...
5
6 func()...幹嘛的 參數1....
7 */
8 #define _CRT_SECURE_NO_WARNINGS
9 #include<iostream>
10 using namespace std;
11 #include<vector>
12 #include<deque>
13 #include<algorithm>
14 #include<string>
15 #inlcude<ctime>
16 /*
17 有5名選手:選手ABCDE,10個評委分别對每一名選手打分,去除最高分,去除評委中最低分,取平均分。
18 //1. 建立五名選手,放到vector中
19 //2. 周遊vector容器,取出來每一個選手,執行for循環,可以把10個評分打分存到deque容器中
20 //3. sort算法對deque容器中分數排序,pop_back pop_front去除最高和最低分
21 //4. deque容器周遊一遍,累加分數,累加分數/d.size()
22 //5. person.score = 平均分
23 */
24
25 class Person
26 {
27 public:
28 Person(string name, int score)
29 {
30 this->m_Name = name;
31 this->m_Score = score;
32 }
33
34 string m_Name;//人名
35 int m_Score;//分數
36 };
37
38 void createPerson(vector<Person>& v)
39 {
40 string nameSeed = "ABCDE";
41 for(int i = 0; i < 5; i++)
42 {
43 string name = "選手";
44 name += nameSeed[i];
45
46 int score = 0;
47 Person p(name, score);
48
49 v.push_back(p);
50 }
51
52
53 }
54
55 void setScore(vector<Person>& v)
56 {
57 for(vector<Person>::iterator it = v.begin(); it != v.end(); it++)
58 {
59 //對5個人進行打分
60 deque<int>d;
61 for(int i = 0; i < 10; i++)
62 {
63 int score = rand() % 41 + 60;//60~100
64
65 d.push_back(score);
66 }
67 /*
68 //先測試看下打分
69 for(deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
70 {
71 cout << *dit << " ";
72 }
73 cout << endl;
74 */
75
76 //排序
77 sort(d.begin(), d.end());
78
79 //去除最高和最低
80 d.pop_back();//最高
81 d.pop_front();
82
83 int sum = 0;
84 for(deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
85 {
86 sum += *dit;
87 }
88
89 //平均分
90 int avg = sum / d.size();
91
92 it->m_Score = avg;
93 }
94
95 }
96
97 void showScore(vector<Person>& v)
98 {
99 for(vector<Person>::iterator it = v.begin(); it != v.end(); it++)
100 {
101 cout << "姓名:" << it->m_Name << "最終平均分:" << it->m_Score << endl;
102 }
103
104 }
105
106 void test01()
107 {
108 //為友善測試,最後設定随機數種子
109 srand(unsigned int)time(NULL);
110
111 //建立容器,存放選手
112 vector<Person>v;
113
114 //建立5名選手
115 createPerson(v);
116
117 /*
118 //測試
119 for(vector<Person>::iterator it = v.begin(); it != v.end(); it++)
120 {
121 cout << "姓名:" << (*it).m_Name << endl;
122 }
123 */
124
125 //打分
126 SetScore(v);
127
128 //展示平均分
129 showScore(v);
130 }
131
132 int main()
133 {
134 test01();
135
136 system("pause");
137 return EXIT_SUCCESS;
138 }
2、stack棧容器
stack容器基本概念
stack是一種先進後出(First In Last Out,FILO)的資料結構,它隻有一個出口,形式如圖所示。stack容器允許新增元素,移除元素,取得棧頂元素,但是除了最頂端外,沒有任何其他方法可以存取stack的其他元素。換言之,stack不允許有周遊行為。
有元素推入棧的操作稱為:push,将元素推出stack的操作稱為pop.
stack沒有疊代器
Stack所有元素的進出都必須符合”先進後出”的條件,隻有stack頂端的元素,才有機會被外界取用。Stack不提供周遊功能,也不提供疊代器。
測試API:
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 //包含stack頭檔案
5 #include<stack>
6
7 /*
8 //stack構造函數
9 stack<T> stkT;//stack采用模闆類實作, stack對象的預設構造形式:
10 stack(const stack &stk);//拷貝構造函數
11
12 //stack指派操作
13 stack& operator=(const stack &stk);//重載等号操作符
14
15 //stack資料存取操作
16 push(elem);//向棧頂添加元素
17 pop();//從棧頂移除第一個元素
18 top();//傳回棧頂元素
19
20 //stack大小操作
21 empty();//判斷堆棧是否為空
22 size();//傳回堆棧的大小
23
24 */
25
26
27 void test01()
28 {
29 stack<int>s;
30 //放入資料 push
31 s.push(10);
32 s.push(30);
33 s.push(20);
34 s.push(40);
35
36 while(s.size() != 0)
37 {
38 cout << "棧頂為:" << s.top() << endl;//40 20 30 10
39 //彈出棧頂元素
40 s.pop();
41 }
42 cout << "size = " << s.size() << endl;
43
44 }
45
46 int main()
47 {
48 test01();
49
50 system("pause");
51 return EXIT_SUCCESS;
52 }
3、queue隊列容器
queue容器基本概念
Queue是一種先進先出(First In First Out,FIFO)的資料結構,它有兩個出口,queue容器允許從一端新增元素,從另一端移除元素。
queue沒有疊代器
Queue所有元素的進出都必須符合”先進先出”的條件,隻有queue的頂端元素,才有機會被外界取用。Queue不提供周遊功能,也不提供疊代器。
測試API:
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 //包含隊列頭檔案
5 #include<queue>
6
7 /*
8 //queue構造函數
9 queue<T> queT;//queue采用模闆類實作,queue對象的預設構造形式:
10 queue(const queue &que);//拷貝構造函數
11
12 //queue存取、插入和删除操作
13 push(elem);//往隊尾添加元素
14 pop();//從隊頭移除第一個元素
15 back();//傳回最後一個元素
16 front();//傳回第一個元素
17
18 //queue指派操作
19 queue& operator=(const queue &que);//重載等号操作符
20
21 //queue大小操作
22 empty();//判斷隊列是否為空
23 size();//傳回隊列的大小
24
25 */
26
27 void test01()
28 {
29 queue<int>q;
30 q.push(10);//往隊尾添加元素
31 q.push(30);
32 q.push(20);
33 q.push(40);
34
35 while(!q.empty())
36 {
37 cout << "隊頭:" << q.front() << endl;//10 40 30 40 20 40 40 40
38 cout << "隊尾:" << q.back() << endl;
39 //彈出隊頭
40 q.pop();
41 }
42 cout << "size:" << q.size() << endl;
43 }
44
45 int main()
46 {
47 test01();
48
49 system("pause");
50 return EXIT_SUCCESS;
51 }
4、list容器
list容器基本概念
連結清單是一種實體存儲單元上非連續、非順序的存儲結構,資料元素的邏輯順序是通過連結清單中的指針連結次序實作的。連結清單由一系列結點(連結清單中每一個元素稱為結點)組成,結點可以在運作時動态生成。每個結點包括兩個部分:一個是存儲資料元素的資料域,另一個是存儲下一個結點位址的指針域。
相較于vector的連續線性空間,list就顯得負責許多,它的好處是每次插入或者删除一個元素,就是配置或者釋放一個元素的空間。是以,list對于空間的運用有絕對的精準,一點也不浪費。而且,對于任何位置的元素插入或元素的移除,list永遠是常數時間。
List和vector是兩個最常被使用的容器。List容器是一個雙向連結清單。
>采用動态存儲配置設定,不會造成記憶體浪費和溢出
>連結清單執行插入和删除操作十分友善,修改指針即可,不需要移動大量元素
>連結清單靈活,但是空間和時間額外耗費較大list容器的疊代器
List容器不能像vector一樣以普通指針作為疊代器,因為其節點不能保證在同一塊連續的記憶體空間上。List疊代器必須有能力指向list的節點,并有能力進行正确的遞增、遞減、取值、成員存取操作。所謂”list正确的遞增,遞減、取值、成員取用”是指,遞增時指向下一個節點,遞減時指向上一個節點,取值時取的是節點的資料值,成員取用時取的是節點的成員。
由于list是一個雙向連結清單,疊代器必須能夠具備前移、後移的能力,是以list容器提供的是Bidirectional Iterators.
List有一個重要的性質,插入操作和删除操作都不會造成原有list疊代器的失效。這在vector是不成立的,因為vector的插入操作可能造成記憶體重新配置,導緻原有的疊代器全部失效,甚至List元素的删除,也隻有被删除的那個元素的疊代器失效,其他疊代器不受任何影響。list容器的資料結構
list容器不僅是一個雙向連結清單,而且還是一個循環的雙向連結清單。
測試API:
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 #include<list>
5 #include<algorithm>
6 #include<string>
7
8 //list是雙向循環連結清單
9 void test01()
10 {
11 list<int> myList;
12 for (int i = 0; i < 10; i ++){
13 myList.push_back(i);
14 }
15
16 list<int>::_Nodeptr node = myList._Myhead->_Next;
17
18 for (int i = 0; i < myList._Mysize * 2;i++){
19 cout << "Node:" << node->_Myval << endl;
20 node = node->_Next;
21 if (node == myList._Myhead){
22 node = node->_Next;
23 }
24 }
25
26 }
27
28 /*
29 //list構造函數
30 list<T> lstT;//list采用采用模闆類實作,對象的預設構造形式:
31 list(beg,end);//構造函數将[beg, end)區間中的元素拷貝給本身。
32 list(n,elem);//構造函數将n個elem拷貝給本身。
33 list(const list &lst);//拷貝構造函數。
34
35 //list資料元素插入和删除操作
36 push_back(elem);//在容器尾部加入一個元素
37 pop_back();//删除容器中最後一個元素
38 push_front(elem);//在容器開頭插入一個元素
39 pop_front();//從容器開頭移除第一個元素
40 insert(pos,elem);//在pos位置插elem元素的拷貝,傳回新資料的位置。
41 insert(pos,n,elem);//在pos位置插入n個elem資料,無傳回值。
42 insert(pos,beg,end);//在pos位置插入[beg,end)區間的資料,無傳回值。
43 clear();//移除容器的所有資料
44 erase(beg,end);//删除[beg,end)區間的資料,傳回下一個資料的位置。
45 erase(pos);//删除pos位置的資料,傳回下一個資料的位置。
46 remove(elem);//删除容器中所有與elem值比對的元素。
47
48 */
49
50 void printList(list<int>& L)
51 {
52 for(list<int>::iterator it = L.begin(); it != L.end(); it++)
53 {
54 cout << *it << " ";
55 }
56 cout << endl;
57 }
58
59 void test02()
60 {
61 list<int>L(10, 10);
62 list<int>L2(L.begin(), L.end());
63
64 printList(L);
65 printList(L2);
66 L2.push_back(100);
67
68 //逆向列印
69 for(list<int>::reverse_iterator it = L2.rbegin(); it != L2.rend(); it++)
70 {
71 cout << *it << " ";
72 }
73 cout << endl;
74
75 //list疊代器不支援随機通路
76 list<int>::iterator itBegin = L2.begin();
77 //itBegin = itBegin + 1;
78
79 //插入資料
80 list<int>L3;
81 L3.push_back(10);
82 L3.push_back(30);
83 L3.push_back(20);
84 L3.push_front(100);
85 L3.push_front(300);
86 L3.push_front(200);
87
88 printList(L3);//200 300 100 10 30 20
89
90 //删除兩端的資料
91 L3.pop_front();//頭删
92 L3.pop_back();//尾删
93 printList(L3);//300 100 10 30
94
95 L3.insert(L3.begin(), 1000);
96 printList(L3);//1000 300 100 10 30
97
98 //remove(elem);//删除容器中所有與elem值比對的元素
99 L3.push_back(10);//1000 300 100 10 30 10
100 L3.remove(10);//參數,直接放值
101
102 printList(L3);//1000 300 100 30
103 }
104
105 /*
106 //list大小操作
107 size();//傳回容器中元素的個數
108 empty();//判斷容器是否為空
109 resize(num);//重新指定容器的長度為num,
110 若容器變長,則以預設值填充新位置。
111 如果容器變短,則末尾超出容器長度的元素被删除。
112 resize(num, elem);//重新指定容器的長度為num,
113 若容器變長,則以elem值填充新位置。
114 如果容器變短,則末尾超出容器長度的元素被删除。
115
116 //list指派操作
117 assign(beg, end);//将[beg, end)區間中的資料拷貝指派給本身。
118 assign(n, elem);//将n個elem拷貝指派給本身。
119 list& operator=(const list &lst);//重載等号操作符
120 swap(lst);//将lst與本身的元素互換。
121
122 //list資料的存取
123 front();//傳回第一個元素。
124 back();//傳回最後一個元素。
125
126 */
127
128 void test03()
129 {
130 list<int>L3;
131 L3.push_back(10);
132 L3.push_back(30);
133 L3.push_back(20);
134 L3.push_front(100);
135 L3.push_front(300);
136 L3.push_front(200);
137
138 cout << "大小:" << L3.size() << endl;
139 if(L3.empty())
140 {
141 cout << "L3為空" << endl;
142 }
143 else
144 {
145 cout << "L3不為空" << endl;
146 }
147
148 L3.resize(10);
149 printList(L3);//200 300 100 10 30 20 0 0 0 0
150
151 L3.resize(3);
152 printList(L3);//200 300 100
153
154 list<int> L4;
155 L4.assign(L3.begin(), L3.end());
156
157 cout << "front:" << L4.front() << endl;//200
158 cout << "back:" << L4.back() << endl;//100
159
160 }
161
162 /*
163 //list反轉排序
164 reverse();//反轉連結清單,比如lst包含1,3,5元素,運作此方法後,lst就包含5,3,1元素。
165 sort(); //list排序
166 */
167 bool myCompare(int v1, int v2)
168 {
169 return v1 > v2;
170 }
171
172 void test04()
173 {
174 list<int>L;
175
176 L.push_back(10);
177 L.push_back(20);
178 L.push_back(40);
179 L.push_back(30);
180
181 L.reverse();
182 printList(L);//30 40 20 10
183
184 //所有不支援随機通路的疊代器,不可以用系統提供的算法
185 //如果不支援用系統提供算法,那麼這個類内部會提供
186 //sort(L.begin(), L.end());
187 L.sort();//從小到大
188
189 printList(L);
190
191 //從大到小
192 L.sort(myCompare);
193 printList(L);
194 }
195
196 //自定義資料類型
197 class Person
198 {
199 public:
200 Person(string name, int age, int height)
201 {
202 this->m_Name = time;
203 this->m_Age = age;
204 this->m_Height = height;
205 }
206
207
208 string m_Name;
209 int m_Age;
210 int m_Height;//身高
211 };
212
213 //Person排序規則:如果年齡相同,按照身高升序排序
214 bool myComparePerson(Person& p1, Person& p2)
215 {
216 /*
217 if(p1.m_Age > p2.m_Age)
218 {
219 return true;
220 }
221 return false;
222 */
223
224 if(p1.m_Age == p2.m_Age)
225 {
226 return p1.m_Height < p2.m_Height;
227 }
228 else
229 {
230 return p1.m_Age > p2.m_Age;
231 }
232 }
233
234 void test05()
235 {
236 list<Person>L;
237
238 Person p1("亞瑟", 10, 165);
239 Person p2("德瑪西亞", 20, 170);
240 Person p3("火槍", 17, 177);
241 Person p4("德雷福斯", 19, 120);
242 Person p5("MT", 18, 200);
243 Person p6("狗蛋", 18, 166);
244 Person p7("狗剩", 18, 210);
245
246 L.push_back(p1);
247 L.push_back(p2);
248 L.push_back(p3);
249 L.push_back(p4);
250 L.push_back(p5);
251 L.push_back(p6);
252 L.push_back(p7);
253
254 //需求:列印資料時候,按照年齡的降序輸出
255 //對于自定義資料類型,必須要指定排序規則
256 L.sort(myComparePerson);
257
258 for(list<Person>::iterator it = it = L.begin(); it != L.end(); it++)
259 {
260 cout << "姓名:" << it->m_Name << "年齡:" << *it.m_Age << "身高:" << it->m_Height << endl;
261 }
262 }
263
264
265
266
267 int main()
268 {
269 test01();
270
271 system("pause");
272 return EXIT_SUCCESS;
273 }
測試:删除自定義資料類型
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 #include<list>
5 #include<algorithm>
6 #include<string>
7
8
9 //自定義資料類型
10 class Person
11 {
12 public:
13 Person(string name, int age, int height)
14 {
15 this->m_Name = time;
16 this->m_Age = age;
17 this->m_Height = height;
18 }
19
20 //重載 == 讓remove可以删除自定義的Person類型
21 bool operator==(const Person& p)//必須加const
22 {
23 if(this->m_Name == p.m_Name && this->m_Age == p.m_Age && this->m_Height == p.m_Height)
24 {
25 return true;
26 }
27 return false;
28 }
29
30
31 string m_Name;
32 int m_Age;
33 int m_Height;//身高
34 };
35
36 //Person排序規則:如果年齡相同,按照身高升序排序
37 bool myComparePerson(Person& p1, Person& p2)
38 {
39 /*
40 if(p1.m_Age > p2.m_Age)
41 {
42 return true;
43 }
44 return false;
45 */
46
47 if(p1.m_Age == p2.m_Age)
48 {
49 return p1.m_Height < p2.m_Height;
50 }
51 else
52 {
53 return p1.m_Age > p2.m_Age;
54 }
55 }
56
57 void test01()
58 {
59 list<Person>L;
60
61 Person p1("亞瑟", 10, 165);
62 Person p2("德瑪西亞", 20, 170);
63 Person p3("火槍", 17, 177);
64 Person p4("德雷福斯", 19, 120);
65 Person p5("MT", 18, 200);
66 Person p6("狗蛋", 18, 166);
67 Person p7("狗剩", 18, 210);
68
69 L.push_back(p1);
70 L.push_back(p2);
71 L.push_back(p3);
72 L.push_back(p4);
73 L.push_back(p5);
74 L.push_back(p6);
75 L.push_back(p7);
76
77 //需求:列印資料時候,按照年齡的降序輸出
78 //對于自定義資料類型,必須要指定排序規則
79 L.sort(myComparePerson);
80
81 for(list<Person>::iterator it = it = L.begin(); it != L.end(); it++)
82 {
83 cout << "姓名:" << it->m_Name << "年齡:" << *it.m_Age << "身高:" << it->m_Height << endl;
84 }
85
86 cout << "----------" << endl;
87 //删除 狗蛋
88 L.remove(p6);
89 for(list<Person>::iterator it = it = L.begin(); it != L.end(); it++)
90 {
91 cout << "姓名:" << it->m_Name << "年齡:" << *it.m_Age << "身高:" << it->m_Height << endl;
92 }
93
94 }
95
96
97
98
99 int main()
100 {
101 test01();
102
103 system("pause");
104 return EXIT_SUCCESS;
105 }
5、set容器
set/multiset容器基本概念set容器基本概念
Set的特性是。所有元素都會根據元素的鍵值自動被排序。Set的元素不像map那樣可以同時擁有實值和鍵值,set的元素即是鍵值又是實值。Set不允許兩個元素有相同的鍵值。
我們可以通過set的疊代器改變set元素的值嗎?不行,因為set元素值就是其鍵值,關系到set元素的排序規則。如果任意改變set元素值,會嚴重破壞set組織。換句話說,set的iterator是一種const_iterator.
set擁有和list某些相同的性質,當對容器中的元素進行插入操作或者删除操作的時候,操作之前所有的疊代器,在操作完成之後依然有效,被删除的那個元素的疊代器必然是一個例外。multiset容器基本概念
multiset特性及用法和set完全相同,唯一的差别在于它允許鍵值重複。set和multiset的底層實作是紅黑樹,紅黑樹為平衡二叉樹的一種。
樹的簡單知識:
二叉樹就是任何節點最多隻允許有兩個位元組點。分别是左子結點和右子節點。
二叉樹示意圖二叉搜尋樹,是指二叉樹中的節點按照一定的規則進行排序,使得對二叉樹中元素通路更加高效。二叉搜尋樹的放置規則是:任何節點的元素值一定大于其左子樹中的每一個節點的元素值,并且小于其右子樹的值。是以從根節點一直向左走,一直到無路可走,即得到最小值,一直向右走,直至無路可走,可得到最大值。那麼在兒茶搜尋樹中找到最大元素和最小元素是非常簡單的事情。下圖為二叉搜尋樹:
上面我們介紹了二叉搜尋樹,那麼當一個二叉搜尋樹的左子樹和右子樹不平衡的時候,那麼搜尋依據上圖表示,搜尋9所花費的時間要比搜尋17所花費的時間要多,由于我們的輸入或者經過我們插入或者删除操作,二叉樹失去平衡,造成搜尋效率降低。
是以我們有了一個平衡二叉樹的概念,所謂的平衡不是指的完全平衡。
RB-tree(紅黑樹)為二叉樹的一種。
(1)測試API:
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 #include<set>
5 /*
6 //set構造函數
7 set<T> st;//set預設構造函數:
8 mulitset<T> mst; //multiset預設構造函數:
9 set(const set &st);//拷貝構造函數
10
11 //set指派操作
12 set& operator=(const set &st);//重載等号操作符
13 swap(st);//交換兩個集合容器
14
15 //set大小操作
16 size();//傳回容器中元素的數目
17 empty();//判斷容器是否為空
18
19 //set插入和删除操作
20 insert(elem);//在容器中插入元素。
21 clear();//清除所有元素
22 erase(pos);//删除pos疊代器所指的元素,傳回下一個元素的疊代器。
23 erase(beg, end);//删除區間[beg,end)的所有元素 ,傳回下一個元素的疊代器。
24 erase(elem);//删除容器中值為elem的元素。
25
26 */
27 void printSet(set<int>& s)
28 {
29 for(set<int>::iterator it = s.begin(); it != s.end(); it++)
30 {
31 cout << *it << " ";
32 }
33 cout << endl;
34 }
35
36
37 void test01()
38 {
39 set<int>s1;
40
41 //關聯式容器,key進行排序,從小到大
42 s1.intsert(5);
43 s1.intsert(1);
44 s1.intsert(9);
45 s1.intsert(3);
46 s1.intsert(7);
47
48 printSet(s1);//1 3 5 7 9
49
50 if(s1.empty())
51 {
52 cout << "空" << endl;
53 }
54 else
55 {
56 cout << "size = " << s1.size() << endl;
57 }
58
59 s1.erase(s1.begin());// 3 5 7 9
60 printSet(s1);
61 s1.erase(3);//5 7 9
62 printSet(s1);
63
64 }
65
66 /*
67 //set查找操作
68 find(key);//查找鍵key是否存在,若存在,傳回該鍵的元素的疊代器;若不存在,傳回set.end();
69 count(key);//查找鍵key的元素個數
70 lower_bound(keyElem);//傳回第一個key>=keyElem元素的疊代器。
71 upper_bound(keyElem);//傳回第一個key>keyElem元素的疊代器。
72 equal_range(keyElem);//傳回容器中key與keyElem相等的上下限的兩個疊代器。
73
74 */
75 void test02()
76 {
77 set<int>s1;
78 s1.intsert(5);
79 s1.intsert(1);
80 s1.intsert(9);
81 s1.intsert(3);
82 s1.intsert(7);
83
84 //對于set,沒有value,key就是value
85
86 set<int>::iterator pos = s1.find(3);
87 //判斷是否找到
88 if(pos != s1.end())
89 {
90 cout << "找到了,值為:" << *pos << endl;
91 }
92 else
93 {
94 cout << "未找到" << endl;
95 }
96
97 //count(key);//查找鍵key的元素個數,對于set而言,結果0或者1
98 int num = s1.count(1);
99 cout << "2的個數為:" << num << endl;
100
101 //lower_bound(keyElem);//傳回第一個key>=keyElem元素的疊代器
102 set<int>::iterator it = s1.lower_bound(3);//10就是未找到
103 if(it != s1.end())
104 {
105 cout << "找到了,lower_bound(3)的值為:" << *it << endl;
106 }
107 else
108 {
109 cout << "未找到" << endl;
110 }
111 //upper_bound(keyElem);//傳回第一個key>keyElem元素的疊代器
112 set<int>::iterator it2 = s1.lower_bound(3);
113 if(it2 != s1.end())
114 {
115 cout << "找到了,lower_bound(3)的值為:" << *it2 << endl;
116 }
117 else
118 {
119 cout << "未找到" << endl;
120 }
121 //equal_range(keyElem);//傳回容器中key與keyElem相等的上下限的兩個疊代器
122 //上下限就是 lower_bound upper_bound
123 pair<set<int>::iterator, set<int>::iterator> ret = s1.equal_range(3);
124 //擷取第一個值
125 if(ret.first != s1.end())
126 {
127 cout << "找到equal_range中的lower_bound的值:" << *(ret.first) << endl;
128 }
129 else
130 {
131 cout << "未找到" << endl;
132 }
133 //擷取第二個值
134 if(ret.second != s1.end())
135 {
136 cout << "找到equal_range中的upper_bound的值:" << *(ret.second) << endl;
137 }
138 else
139 {
140 cout << "未找到" << endl;
141 }
142
143 }
144
145 int main()
146 {
147 test01();
148
149 system("pause");
150 return EXIT_SUCCESS;
151 }
(2)pair對組的建立方式——兩種
對組(pair)将一對值組合成一個值,這一對值可以具有不同的資料類型,兩個值可以分别用pair的兩個公有屬性first和second通路。
類模闆:template <class T1, class T2> struct pair.
測試:
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 #include<string>
4 using namespace std;
5
6 //建立對組,使用對組pair不需要引用頭檔案
7 void test01()
8 {
9 //第一種括号
10 pair<string, int>p(string("Tom"), 100);
11
12 //取值
13 cout << "姓名:" << p.first << endl;
14 cout << "年齡:" << p.second << endl;
15
16 //第二種建立
17 pair<string, int> p2 = make_pair("Jerry", 200);
18 cout << "姓名:" << p2.first << endl;
19 cout << "年齡:" << p2.second << endl;
20
21 }
22
23 int main()
24 {
25 test01();
26
27 system("pause");
28 return EXIT_SUCCESS;
29 }
(3)測試排序規則:
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 #include<set>
5 #include<string>
6
7 void printSet(set<int>& s)
8 {
9 for(set<int>::iterator it = s.begin(); it != s.end(); it++)
10 {
11 cout << *it << " ";
12 }
13 cout << endl;
14 }
15
16 //set容器,不允許插入重複的鍵值
17 void test01()
18 {
19 set<int>s1;
20
21 pair<set<int>::iterator, bool> ret = s1.intsert(10);
22
23
24 if(ret.second)
25 {
26 cout << "插入成功" << endl;
27 }
28 else
29 {
30 cout << "插入失敗" << endl;
31 }
32 s1.intsert(10);
33
34
35 if(ret.second)
36 {
37 cout << "第二次插入成功" << endl;
38 }
39 else
40 {
41 cout << "第二次插入失敗" << endl;
42 }
43
44 printSet(s1);//10
//multiset允許插入重複的值 multiset<int>mul; mul.insert(10); mul.insert(10);
45 }
46
47 //指定set排序規則,從大到小
48 //仿函數
49 class myCompare
50 {
51 public:
52 //重載()
53 bool operator()(int v1, int v2)
54 {
55 return v1 > v2;
56 }
57
58
59 };
60
61 //set容器排序
62 void test02()
63 {
64 set<int, myCompare>s1;
65
66 s1.insert(5);
67 s1.insert(1);
68 s1.insert(9);
69 s1.insert(3);
70 s1.insert(7);
71
72 //printSet(s1);
73
74 //從大到小排序
75 //在插入之前就指定排序規則
76
77 for(set<int, myCompare>::iterator it = s1.begin(); it != s1.end(); it++)
78 {
79 cout << *it << " ";
80 }
81 cout << endl;
82
83 }
84
85 //自定義資料類型
86 class Person
87 {
88 public:
89 Person(string name, int age)
90 {
91 this->m_Name = name;
92 this->m_Age = age;
93 }
94
95 string m_Name;
96 int m_Age;
97 };
98
99 class myComparePerson
100 {
101 public:
102 bool operator()(const Person& p1, const Person& p2)//必須加入const
103 {
104 if(p1.m_Age > p2.m_Age)//降序
105 {
106 return true;
107 }
108 return false;
109 }
110
111
112 };
113
114 void test03()
115 {
116 set<Person, myComparePerson> s1;
117
118 Person p1("大娃", 100);
119 Person p2("二娃", 90);
120 Person p3("六娃", 10);
121 Person p4("爺爺", 1000);
122
123 s1.insert(p1);
124 s1.insert(p2);
125 s1.insert(p3);
126 s1.insert(p4);
127
128 //插入自定義資料類型,一開始就指定排序規則
129
130 //顯示
131 for(set<Person, myComparePerson>::iterator it = s1.begin(); it != s1.end(); it++)
132 {
133 cout << "姓名:" << (*it).m_Name << "年齡:" << (*it).m_Age << endl;
134 }
135 }
136
137
138
139
140
141
142 int main()
143 {
144 test01();
145
146 system("pause");
147 return EXIT_SUCCESS;
148 }
6、map容器
map/multimap基本概念
Map的特性是,所有元素都會根據元素的鍵值自動排序。Map所有的元素都是pair,同時擁有實值和鍵值,pair的第一進制素被視為鍵值,第二進制素被視為實值,map不允許兩個元素有相同的鍵值。我們可以通過map的疊代器改變map的鍵值嗎?答案是不行,因為map的鍵值關系到map元素的排列規則,任意改變map鍵值将會嚴重破壞map組織。如果想要修改元素的實值,那麼是可以的。
Map和list擁有相同的某些性質,當對它的容器元素進行新增操作或者删除操作時,操作之前的所有疊代器,在操作完成之後依然有效,當然被删除的那個元素的疊代器必然是個例外。
Multimap和map的操作類似,唯一差別multimap鍵值可重複。
Map和multimap都是以紅黑樹為底層實作機制。
測試API:
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 //引入頭檔案
5 #include<map>
6
7 /*
8 //map構造函數
9 map<T1, T2> mapTT;//map預設構造函數:
10 map(const map &mp);//拷貝構造函數
11
12 //map指派操作
13 map& operator=(const map &mp);//重載等号操作符
14 swap(mp);//交換兩個集合容器
15
16 //map大小操作
17 size();//傳回容器中元素的數目
18 empty();//判斷容器是否為空
19
20 //map插入資料元素操作
21 map.insert(...); //往容器插入元素,傳回pair<iterator,bool>
22 map<int, string> mapStu;
23 // 第一種 通過pair的方式插入對象
24 mapStu.insert(pair<int, string>(3, "小張"));
25 // 第二種 通過pair的方式插入對象
26 mapStu.inset(make_pair(-1, "校長"));
27 // 第三種 通過value_type的方式插入對象
28 mapStu.insert(map<int, string>::value_type(1, "小李"));
29 // 第四種 通過數組的方式插入值
30 mapStu[3] = "小劉";
31 mapStu[5] = "小王";
32
33 */
34
35
36 void test01()
37 {
38 map<int, int>m;
39 //插入值
40 //4種方式
41 //第一種
42 m.insert(pair<int, int>(1, 10));
43 //第二種 推薦
44 m.insert(make_pair(2,20));
45 //第三種
46 m.insert(map<int, int>::value_type(3, 30));
47 //第四種,如果保證key存在,那麼可以通過[]通路
48 m[4] = 40;
49
50 for(map<int, int>::iterator it = m.begin(); it != m.end(); it++)
51 {
52 cout << "key = " << it->first << "value = " << it->second << endl;
53 }
54
55 //cout << m[5] << endl;
56
57 for(map<int, int>::iterator it = m.begin(); it != m.end(); it++)
58 {
59 cout << "key = " << it->first << "value = " << it->second << endl;
60 }
61
62 cout << m[4] << endl;
63
64 if(m.empty())
65 {
66 cout << "空" << endl;
67 }
68 else
69 {
70 cout << "size = " << m.size() << endl;
71 }
72
73 }
74
75 /*
76 //map删除操作
77 clear();//删除所有元素
78 erase(pos);//删除pos疊代器所指的元素,傳回下一個元素的疊代器。
79 erase(beg,end);//删除區間[beg,end)的所有元素 ,傳回下一個元素的疊代器。
80 erase(keyElem);//删除容器中key為keyElem的對組。
81
82 //map查找操作
83 find(key);//查找鍵key是否存在,若存在,傳回該鍵的元素的疊代器;/若不存在,傳回map.end();
84 count(keyElem);//傳回容器中key為keyElem的對組個數。對map來說,要麼是0,要麼是1。對multimap來說,值可能大于1。
85 lower_bound(keyElem);//傳回第一個key>=keyElem元素的疊代器。
86 upper_bound(keyElem);//傳回第一個key>keyElem元素的疊代器。
87 equal_range(keyElem);//傳回容器中key與keyElem相等的上下限的兩個疊代器。
88
89 */
90
91 void test02()
92 {
93 map<int, int>m;
94 m.insert(pair<int, int>(1, 10));
95 m.insert(make_pair(2,20));
96 m.insert(map<int, int>::value_type(3, 30));
97 m[4] = 40;
98
99 m.erase(1);
100 for(map<int, int>::iterator it = m.begin(); it != m.end(); it++)
101 {
102 cout << "key = " << it->first << "value = " << it->second << endl;
103 }
104
105 map<int, int>::iterator pos = m.find(2);
106 if(pos != m.end())
107 {
108 cout << "找到,key:" << pos->first << "value:" << pos->second << endl;
109 }
110 else
111 {
112 cout << "未找到" << endl;
113 }
114
115 int num = m.count(3);//map的count要麼0,要麼1
116 cout << "num = " << endl;
117
118 //lower_bound(keyElem);//傳回第一個key>=keyElem元素的疊代器
119 map<int, int>::iterator ret = m.lower_bound(3);
120 if(ret != m.end())
121 {
122 cout << "lower_bound中key:" << ret->first << "value:" << ret->second << endl;
123 }
124 else
125 {
126 cout << "未找到" << endl;
127 }
128
129 //upper_bound(keyElem);//傳回第一個key>keyElem元素的疊代器
130 map<int, int>::iterator ret = m.upper_bound(3);
131 if(ret != m.end())
132 {
133 cout << "upper_bound中key:" << ret->first << "value:" << ret->second << endl;
134 }
135 else
136 {
137 cout << "未找到" << endl;
138 }
139
140 //equal_range(keyElem);//傳回容器中key與keyElem相等的上下限的兩個疊代器
141 pair<map<int, int>::iterator, map<int, int>::iterator> ret2 = m.equal_range(3);
142
143 if(ret2.first != m.end())
144 {
145 cout << "找到了equal_range中的lower_bound的key" << ret2.first->first << "value:" << ret2.first->second << endl;
146 }
147 else
148 {
149 cout << "未找到" << endl;
150 }
151
152 if(ret2.second != m.end())
153 {
154 cout << "找到了equal_range中的upper_bound的key" << ret2.second->first << "value:" << ret2.second->second << endl;
155 }
156 else
157 {
158 cout << "未找到" << endl;
159 }
160
161 }
162
163 //指定排序規則
164 class myCompare
165 {
166 public:
167 bool operator()(int v1, int v2)
168 {
169 return v1 > v2;
170 }
171 };
172
173
174 void test03()
175 {
176 //從大到小排序
177 map<int, int, myCompare>m;
178 m.insert(pair<int, int>(1, 10));
179 m.insert(make_pair(2,20));
180 m.insert(map<int, int>::value_type(3, 30));
181 m[4] = 40;
182
183 for(map<int, int, myCompare>::iterator it = m.begin(); it != m.end(); it++)
184 {
185 cout << "key = " << it->first << "value = " << it->second << endl;
186 }
187
188 }
189
190
191
192 int main()
193 {
194 test01();
195
196 system("pause");
197 return EXIT_SUCCESS;
198 }
7、STL容器使用時機
vector | deque | list | set | multiset | map | multimap | |
典型記憶體結構 | 單端數組 | 雙端數組 | 雙向連結清單 | 二叉樹 | 二叉樹 | 二叉樹 | 二叉樹 |
可随機存取 | 是 | 是 | 否 | 否 | 否 | 對key而言:不是 | 否 |
元素搜尋速度 | 慢 | 慢 | 非常慢 | 快 | 快 | 對key而言:快 | 對key而言:快 |
元素安插移除 | 尾端 | 頭尾兩端 | 任何位置 | - | - | - | - |
》vector的使用場景:比如軟體曆史操作記錄的存儲,我們經常要檢視曆史記錄,比如上一次的記錄,上上次的記錄,但卻不會去删除記錄,因為記錄是事實的描述。
》deque的使用場景:比如排隊購票系統,對排隊者的存儲可以采用deque,支援頭端的快速移除,尾端的快速添加。如果采用vector,則頭端移除時,會移動大量的資料,速度慢。
vector與deque的比較:
一:vector.at()比deque.at()效率高,比如vector.at(0)是固定的,deque的開始位置 卻是不固定的。
二:如果有大量釋放操作的話,vector花的時間更少,這跟二者的内部實作有關。
三:deque支援頭部的快速插入與快速移除,這是deque的優點。
》list的使用場景:比如公共汽車乘客的存儲,随時可能有乘客下車,支援頻繁的不确實位置元素的移除插入。
》set的使用場景:比如對手機遊戲的個人得分記錄的存儲,存儲要求從高分到低分的順序排列。
》map的使用場景:比如按ID号存儲十萬個使用者,想要快速要通過ID查找對應的使用者。二叉樹的查找效率,這時就展現出來了。如果是vector容器,最壞的情況下可能要周遊完整個容器才能找到該使用者。
二、總結
1 stack棧容器
1.1 先進後出
1.2 棧頂 top
1.3 壓棧 push
1.4 彈出棧頂 pop
1.5 大小 size
1.6 為空 empty2 queue 隊列容器
2.1 先進先出
2.2 隊頭 front 隊尾 back
2.3 入隊 push
2.4 彈出隊頭 pop
2.5 大小 size
2.6 為空 empty3 List容器
3.1 指派、構造、大小、為空、删除 、添加
3.2 移除 remove( 10 ) 删除容器中所有與10 比對的元素
3.3 雙向循環連結清單
3.4 疊代器是不支援随機通路的
3.5 反轉排序
3.5.1 reverse 反轉
3.5.2 排序 成員函數 sort
3.5.3 預設排序 從小到大
3.5.4 自定義資料類型,必須指定排序規則
3.5.5 進階
3.6 remove删除list容器中自定義資料類型4 set容器
4.1 關聯式容器
4.2 插入資料自動排序 按照key
4.3 insert 插入值
4.4 erase 參數可以傳值 或者 疊代器
4.5 find() 傳回值 疊代器 找不到傳回的 end()
4.6 count 計數 對于set而言 結果 就是 0 或者1
4.7 lower_bound(keyElem);//傳回第一個key>=keyElem元素的疊代器。
4.8 upper_bound(keyElem);//傳回第一個key>keyElem元素的疊代器。
4.9 equal_range(keyElem);//傳回容器中key與keyElem相等的上下限的兩個疊代器。
4.10 對組 pair
4.10.1 第一個值 first
4.10.2 第二個值 second
4.10.3 預設括号
4.10.4 make_pair()
4.11 set插入傳回值是 對組 < 疊代器, 是否成功标示>
4.12 指定set排序規則,利用仿函數
4.13 set插入自定義資料類型 5 map容器
5.1 每個元素 都是一個pair
5.2 對于map而言 key是不可以重複
5.3 multimap可以
5.4 4中插入方式
5.5 count 統計 map 0 或1 multimap可能大于1
5.6 排序規則自己指定
在學習c++提高-STL總結了筆記,并分享出來。有問題請及時聯系部落客:Alliswell_WP,轉載請注明出處。