文章目錄
? ? ?一、STL---string類
1. 常用構造函數
2. 常用操作
3. 字符串流處理
二、STL---容器
1. STL及基本概念
2. 順序容器簡介
3. 關聯容器簡介
4. 容器適配器簡介
5. 常用成員函數
三、STL---迭代器
1. 普通迭代器
2. 雙向、隨機訪問迭代器
3. 不同容器的迭代器
四、STL---常用算法
1. find順序查找
2. binary_search二分查找
3. sort快速排序
五、其他知識點
一、STL---string類
1. 常用構造函數
string s1("hhh");
cout << s1 << endl;//hhhstring s2(8,'x');
cout << s2 << endl;//xxxxxxxxstring s;
s = 'a';
cout << s << endl;//astring s1{'a','\0','b','c'};
cout << s1 << endl;//abc
cout << s1.length() << endl;//4
cout << s1.c_str() << endl;//以C語言風格打出,結果: a
2. 常用操作
2.1 獲取長度:使用成員函數length()獲取。
string s("hello");
cout << s.length() << endl;//打印5
2.2 支持流讀取運算符:cin >> s; 以空格為結束。
string s;
cin >> s;//輸入hello world
cout << s << endl;//打印hello
2.3 支持getline函數:getline(cin, s); 以換行為結束。
string s;
getline(cin, s);//輸入hello world
cout << s << endl;//打印hello world
2.4 復制對象內容:①使用=賦值;②使用成員函數assign()。
string s1("hello");
//使用賦值=
string s2;
s2 = s1;
cout << s2 << endl;//打印hello
//使用成員函數assign()
string s3;
s3.assign(s1);
cout << s3 << endl;//打印hello
//assign函數實現部分復制
string s4;
s4.assign(s1, 1, 3);//復制s1中下標1開始的3字符
cout << s4 << endl;//打印ell
2.5 訪問對象字符:①使用[]訪問(常用);②使用成員函數at()訪問。at()會做范圍檢查,若超出范圍則拋出out of range異常,而[]訪問方式不做范圍檢查。
string s("hello world");
//使用[]訪問
for (int i = 0; i < s.length(); ++i) {cout << s[i];
}
//使用at()訪問
for (int i = 0; i < s.length(); ++i) {cout << s.at(i);
}
2.6 連接字符串:①使用+=;②使用成員函數append。使用append可以實現部分增加。
string s1("hello ");
string s2("world ");
//使用+=在s1后增加s2
s1 += s2;
cout << s1 << endl;//打印hello world
//使用append在s2后增加s1
s2.append(s1);
cout << s2 << endl;//打印world hello world
//使用append在s1后增加s2中下標1開始的3字符
s1.append(s2, 1, 3);
cout << s1 << endl;//打印hello world orl
2.7 比較大小:①>、<、==、<=等關系運算符已經被重載了,返回值都是bool類型。②使用成員函數compare,返回值為0、1或-1。compare可以比較兩個string的一部分。
string s1("hello ");
string s2("hella ");
//使用關系運算符比較
bool flag = (s1 < s2);
cout << flag << endl;//打印0
//使用compare比較一部分
int ret = s1.compare(1, 2, s2, 0, 3);//el與hel比較
cout << ret << endl;//打印-1
2.8 獲取子串:使用成員函數substr。
string s1("hello world");
//substr(i, j)表示從下標i開始的j個字符
cout << s1.substr(6, 5) << endl;//打印world
2.9 交換string內容:使用成員函數swap。
string s1("hello world");
string s2(8, 'h');
s1.swap(s2);
cout << s1 << endl;//打印hhhhhhhh
cout << s2 << endl;//打印hello world
2.10 主串中查找子串:①從前往后找:使用成員函數find。②從后往前找:使用成員函數rfind。③從指定位置開始查找:s.find("ll", 1);從s下標為1的地方開始查找"ll"。若找到則返回子串在主串中的首下標,未找到返回string::npos靜態變量(VS2022中定義為-1)。
string s1("hello world");
string s2("ll");
//從前往后找
int fronRet = s1.find(s2);
cout << fronRet << endl;//打印2
//從后往前找
int RearRet = s1.rfind(s2);
cout << RearRet << endl;//打印2
//從指定位置查找
int posRet = s1.find(s2, 4);//s1下標4開始查找
cout << posRet << endl;//打印-1表示沒找到
2.11 刪除內容:使用成員函數erase。
string s1("hello world");
s1.erase(5);//刪除下標5以及之后的所有內容
cout << s1 << endl;//打印hello
cout << s1.length() << endl;//打印5
cout << s1.size() << endl;//打印5
2.12 替換內容:使用成員函數replace。
string s1("hello world");
s1.replace(2, 3, "xxxx");//將s1下標2開始的3字符替換為xxxx
cout << s1 << endl;//打印hexxxx world
2.13 插入內容:使用成員函數insert。
string s1("hello world");
string s2("insert");
//s1下標5插入s2
s1.insert(5, s2);
cout << s1 << endl;//打印helloinsert world
//s1下標0插入s2下標0開始的3字符
s1.insert(0, s2, 0, 3);
cout << s1 << endl;//打印inshelloinsert world
2.14 轉換成C語言風格的字符串:①使用成員函數c_str(),返回const char*類型字符串,且該字符串以'\0'結尾。②使用成員函數data(),返回char*類型字符串,對其進行修改可能會出錯。
string s1("hello world");
const char* s2 = s1.c_str();
printf("%s", s2);//打印hello world
3. 字符串流處理
(1) 字符串輸入流:將字符串中的內容保存為指定變量。例如,將"hello world 2 A 5.6"分別保存為兩個string類型、一個int類型、一個char類型和一個double類型。需要包含頭文件#include <iostream>、#include <string>和#include <sstream>。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <sstream>
using namespace std;int main()
{string target("hello world 2 A 5.6");istringstream input(target);//定義存儲的變量string s1, s2;int n;char c;double d;//字符串輸入流input >> s1 >> s2 >> n >> c >> d;//打印結果cout << s1 << endl;//打印hellocout << s2 << endl;//打印worldcout << n << endl;//打印2cout << c << endl;//打印Acout << d << endl;//打印5.6return 0;
}
(2) 字符串輸出流:將某些變量的值以字符串形式呈現。例如,將"hello"、5和"world"存放于一個字符串中。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <sstream>
using namespace std;int main()
{string s1("hello"), s2("world");int a = 5;//字符串輸出流ostringstream output;output << s1 << s2 << a;cout << output.str() << endl;//打印helloworld5return 0;
}
二、STL---容器
1. STL及基本概念
1.1 STL:
- 是Standard Template Liabrary的縮寫,即標準模板庫。
- 標準模板庫是常用數據結構和算法的模板的集合。它將常用的數據結構(如數組、集合和鏈表等)和常用的算法(如排序和查找等)寫成類模板和函數模板。
1.2?基本概念:
- 容器:可容納指定數據類型的數據結構,是類模板。對象被插入容器時,被插入的是對象的一個復制品。
- 順序容器:vector(動態數組)、deque(雙端隊列)、list(循環雙鏈表)
- 關聯容器:set、multiset、map、multimap
- 容器適配器:stack(棧)、queue(隊列)、priority_queue(優先級隊列)
- 迭代器:可用于依次訪問容器中的元素,類似于指針。
- 算法:用于操作容器中的元素,是函數模板。一些算法支持操作容器內部分元素,因此在傳實參時要傳入首尾元素的迭代器。在使用這些算法時,需要添加頭文件<algorithm>
2. 順序容器簡介
- 順序容器并非排序的,元素的插入位置與該元素的值無關。
- vector:頭文件<vector>?動態數組,其大小可以動態變化。元素在內存里是連續存儲的,通過下標可以訪問某個元素,時間復雜度為O(1)。在頭部或者中間位置插入或刪除元素,時間復雜度為O(n)。在尾部插入和刪除元素一般是常數時間,但是涉及擴容時會申請新空間,然后將已有的元素拷貝至新空間,時間復雜度為O(n)。
- deque:頭文件<deque>?雙端隊列,元素在內存連續存放。隨機存取任何元素的時間復雜度為O(1),但次于vector。在兩端增刪元素的時間復雜度大部分情況是O(1),因為只需要改變元素和移動頭尾指針。但是,當涉及擴容時時間復雜度為O(n)。
- list:頭文件<list>?循環雙向鏈表,元素不是連續存儲的,不支持隨機存取操作。在已知位置的情況下,增刪元素的時間復雜度為O(1),因為只需要更改相關的指針即可。
3. 關聯容器簡介
- 元素是排序的。在插入元素時,需要根據排序規則來確定其位置。通常以平衡二叉樹的方式來實現,查找和插入的時間復雜度為O(log n)。
- set/multiset:頭文件<set> 集合。set中不允許有相同的元素,multiset中允許有相同元素。
- map/multimap:頭文件<map> 鍵值對,有且僅有兩個成員變量first和second。first存放排序的關鍵字,根據first來排序所有對象,因此在查找時就能根據first快速定位。map不允許有相同的first,但multimap允許有相同的first。
- 關聯容器支持以下成員函數:
find | 查找等于某個值的元素(判定等于的機制:x<y和y<x同時不成立) |
lower_bound | 查找某個值的下界區間,返回迭代器it,使得[begin, it)內所有值均小于指定值。 |
upper_bound | 查找某個值的上界區間,返回迭代器it,使得[it, end)內所有值均大于指定值。 |
equal_range | 同時查找lower_bound和upper_bound,返回pair<it,it> |
count | 計算等于某個值的元素個數(判定等于的機制同上) |
insert | 插入一個元素或一個區間 |
4. 容器適配器簡介
- stack:頭文件<stack> 棧。只能操作棧頂的元素,符合后進先出的原則。
- queue:頭文件<queue> 單向隊列。只能在隊頭進行刪除、查找和修改,只能在隊尾進行插入。符合先進先出的原則。
- priority_queue:頭文件<queue> 優先級隊列。最高優先級元素總是第一個出隊。
5. 常用成員函數
5.1 順序容器和關聯容器都有的成員函數:
begin 返回第一個元素的迭代器 end 返回最后一個元素后面位置的迭代器 rbegin 返回最后一個元素的迭代器 rend 返回第一個元素的前面位置的迭代器 erase 刪除一個或多個元素 clear 刪除所有元素
5.2 順序容器常用的成員函數:
front 返回第一個元素的引用 back 返回最后一個元素的引用 push_back 在容器末尾增加新元素 pop_back 刪除容器末尾的元素 erase 刪除迭代器指向的元素(可能會使該迭代器失效)。也可以刪除一個區間,返回被刪除元素后面鄰接元素的迭代器。
三、STL---迭代器
1. 普通迭代器
1.1 迭代器簡介:
- 是一種訪問順序和關聯容器元素的“中介”。
- 存在const和非const兩種。對于const迭代器,只能訪問元素;對于非const迭代器,可以訪問和修改元素。
1.2 定義迭代器:
- 方式一:"容器類名::iterator? 變量名;"
- 方式二:"容器類名::const_iterator? 變量名;"
1.3 訪問迭代器指向的元素:"*迭代器變量名"。注意:迭代器可以使用++操作來指向后一個元素,但是當其指向的地址已經超出容器范圍,就會報錯。
1.4 代碼示例:常量迭代器、非常量迭代器、反向迭代器
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> using namespace std;int main() {//創建vector容器vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//常量迭代器vector<int>::const_iterator i;for (i = v.begin(); i != v.end(); i++) {cout << *i << " ";}cout << endl;//非常量迭代器vector<int>::iterator j;for (j = v.begin(); j != v.end(); j++) {(*j)++;cout << *j << " ";}cout << endl;//反向迭代器vector<int>::reverse_iterator r;for (r = v.rbegin(); r != v.rend(); r++) {cout << *r << " ";}cout << endl;return 0; }
2. 雙向、隨機訪問迭代器
- 雙向迭代器不僅能往后訪問容器元素,還能使用--往前訪問元素。
- 注意:雙向迭代器在遍歷時,不能使用<來比較臨界條件,而只能用!=。
- 隨機訪問迭代器支持以下操作:
p+=i | p向后移動i個元素 |
p-=i | p向前移動i個元素 |
p+i | 其值為p后第i個元素的迭代器 |
p-i | 其值為p前第i個元素的迭代器 |
p[i] | 其值為p后第i個元素的引用 |
p<p1等比較 | 比較p和p1的前后位置 |
3. 不同容器的迭代器
vector | 隨機訪問迭代器 |
deque | 隨機訪問迭代器 |
list | 雙向迭代器 |
set/multiset | 雙向迭代器 |
map/multimap | 雙向迭代器 |
stack | 不支持 |
queue | 不支持 |
priority_queue | 不支持 |
注意:有些算法需要用到隨機訪問迭代器,那么這些算法就不適用于雙向迭代器和不支持迭代器的容器。
四、STL---常用算法
1. find順序查找
(1) 函數模板:
template <class Inlt, class T> Inlt find(Inlt first, Inlt last, const T& val);
(2) 參數說明:
- first和last分別是容器迭代器的查找區間起點和終點,查找范圍為[first, last)。
- val為查找的元素,內部使用==判斷是否相等。
- 返回值:若找到元素,則返回指向該元素的迭代器;否則返回指向last的迭代器。
(3) 代碼示例:
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std;int main() {//創建vector容器對象vector<int> v;v.push_back(24); v.push_back(4);v.push_back(5); v.push_back(16);//find順序查找元素vector<int>::iterator p;p = find(v.begin(), v.end(), 1);//查找范圍:[24,4,5,16]if (p != v.end())cout << "找到了:" << *p << endl;elsecout << "未找到!" << endl;return 0; }
2. binary_search二分查找
前提需要將容器排序。具體細節見C++中的binary_search函數詳解_c++ binary search-CSDN博客。
3. sort快速排序
默認是從小到大排序的,若手動傳入比較函數則可以自定義比較方式。不支持隨機存取特性的容器無法使用。但是往往這些容器內會有成員函數sort可以調用,例如list。具體細節見sort()函數——C++標準庫函數_sort函數頭文件-CSDN博客。
五、其他知識點
【1】vector容器創建二維動態數組:
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> using namespace std;int main() {//創建二維數組vector< vector<int> > v(3);for (int i = 0; i < v.size(); i++) {for (int j = 0; j < i + 1; j++) {v[i].push_back(j);}}//遍歷二維數組元素for (int i = 0; i < v.size(); i++) {for (int j = 0; j < v[i].size(); j++) {cout << v[i][j] << " ";}cout << endl;}return 0; }
【2】list成員函數:
list除了具有順序容器都有的成員函數外,還具有如下的成員函數:
push_front 在前面插入 pop_front 在前面彈出 sort 排序。由于list不支持隨機訪問,無法采用STL算法的sort remove 刪除和指定值相同的所有元素 unique 刪除所有與前一個元素相同的元素 merge 合并兩個鏈表,并清空被合并的那個。注意:merge調用前需要將這兩個鏈表排序,否則運行錯誤。 reverse 翻轉鏈表 splice 在指定位置插入另一鏈表中的一個或多個元素,并刪除另一鏈表中被插入的元素。
【3】list代碼示例:
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <list> #include <algorithm> using namespace std;//定義A類 class A { private:int n; public:A(int n) : n(n) {}friend ostream& operator<<(ostream& cout, const A& p) {cout << p.n;return cout;}friend bool operator<(const A& p1, const A& p2) {return p1.n < p2.n;}friend bool operator==(const A& p1, const A& p2) {return p1.n == p2.n;} };//打印list的函數模板 template <class T> void printList(const list<T> & lst) {typename list<T>::const_iterator p;for (p = lst.begin(); p != lst.end(); p++) {cout << *p << " ";}cout << endl; }int main() {//創建list1: 2 3 4 1 1list<A> list1;list1.push_back(2); list1.push_back(3);list1.push_back(4); list1.push_back(1);list1.push_back(1);cout << "list1: ";printList(list1);//創建list2: 40 10 15 30 65 85list <A> list2;list2.push_back(15); list2.push_front(10);list2.push_front(40); list2.push_back(30);list2.push_back(65); list2.push_back(85);cout << "list2: ";printList(list2);//給兩個list排序list1.sort();list2.sort();cout << "排序后的list1: ";printList(list1);cout << "排序后的list2: ";printList(list2);//將list2融入list1,并清空list2list1.merge(list2);cout << "融合后的list1: ";printList(list1);return 0; }
【4】函數對象:若一個類重載了運算符(),那么這個類創建的對象就是函數對象。
class A { public://重載運算符()int operator()(int a, int b, int c) {return a + b + c;} };A a;//函數對象 cout << a(1, 2, 3) << endl;//等價于a.operator()(1,2,3)