第八章 標準模板庫STL（一）

目錄

• string類
• STL容器
  • 基本概念
  • 型別
  • 成員函式
  • 迭代器
  • 演算法（函式模板）
  • vector
  • deque
  • list
• 函式物件
• less和greater函式物件

string類

1. 原型：typedef basic_string<char> string;

2. 常見操作

   //初始化
   string s1("Hello world!"),s2="Test",s3(8,'x')，s4; //代表8個x組成的字串
   s4='c';
   //定位&賦值
   s1[1]='A';s1.at(1)='B'; //at成員函式速度較慢，但會進行范圍檢查，陣列越界訪問會拋出例外out_of_range
   s1.assign(s2); //等價于s1=s2；
   s1.assign(s2,1,3); //將s2從下標1開始的3個字符賦給s1
   //連接
   s1+=s2;
   s1.append(s2); //等價于s1+=s2
   s1.append(s2,1,3); //將s2下標1開始的至多3個字符連接到s1
   //比較大小：可直接用>,>=,<,<=,==,!=，或
   bool b=s1.compare(s2);
   bool b=s1.compare(0,2,s2);
   bool b=s1.compare(0,2,s2,1,2); //將s1下標0開始的2個字符與s2從下標1開始的2個字符比較
   //交換s1和s2
   s1.swap(s2);
   //子串
   s2=s1.substr(0,3); //起始下標0，長度3
   //替換和插入
   s1.replace(1,3,s2); //s1下標1后3位字符替換成s2
   s1.replace(1,3,s2,0,5); //s1下標1后3位字符替換成s2下標0后的5位字符
   s1.insert(2,s2); //下標2處插入s2
   s1.insert(2,s2,0,5); //s2起始下標0，長度5
   //洗掉
   s1.erase(5); //洗掉下標5后面的全部字符
   //查找
   s1.find("lo"); //查找第一個“lo"字串起始下標，識別失敗回傳string::npos
   s1.find("lo",3); //從下標3開始查找
   s1.rfind("lo"); //反向查找
   s1.find_first_of("abcd"); //從頭查找第一次出現abcd任一字符的下標
   s1.find_last_of("abcd"); //查找最后一個
   s1.find_first_not_of("abcd");
   s1.find_last_not_of("abcd");
   //獲取char*型指標,修改string可能會導致指標p出錯
   const char *p=s1.c_str;
   const char *p=s1.data();
   

3. 字串流處理(需要加sstream頭檔案)

   istringsteam Input("This test 3.5 A"); 
   string s1,s2; double d; char ch;
   Input>>s1>>s2>>d>>ch;
   ostringstream Output;
   Output<<s1<<" "<<s2<<" "<<d<<" "<<ch<<endl;
   cout<<Output.str(); //該函式回傳string型別
   

STL容器

基本概念

1. 容器：可容納各種資料型別的通用結構 ,是類模板
2. 迭代器：可用于依次存取容器中元素，類似指標
3. 演算法： 用來操作容器中元素的函式模板

型別

1. 順序容器：無序，可在任意位置插入元素
   • 可變陣列vector（<vector>）：隨機訪問元素時間為常數，在尾部增刪元素的時間一般為常數
   • 雙向佇列deque（<deque>）：隨機訪問元素時間為常數（速度僅次于vector），在首尾插入元素時間一般為常速
   • 雙向鏈表list（<list>）：不支持隨機訪問，找到位置后在任意位置增刪元素時間為常數
2. 關聯容器：有序，增刪元素自動排序，查找性能佳
   • set/multiset集合
   • map/multimap 圖（映射）
3. 容器配接器
   • 堆疊stack（<stack>)
   • 佇列queue（<queue>)
   • 優先佇列priority_queue（<queue>)

成員函式

1. 順序容器和關聯容器都有的成員函式：begin(), end(), rbegin(), rend(), erase(), clear()
2. 順序容器的常用成員函式：front(), back(), push_back(), pop_back(), erase()

迭代器

1. 類似指標，分const和非const兩種，非const型可以修改其指向的元素

   容器類名::iterator 變數名
   容器類名::const_iterator 變數名
   

2. 分雙向迭代器和隨機迭代器

   • 雙向迭代器操作：++p，p++，--p，p--，*p，p=p1，==，!=
   • 隨機迭代器（如vector、deque）：支持雙向迭代器所有操作，支持加減整數，下標索引，大小比較，p-p1（計算兩指標元素個數）

3. 在模板中寫迭代器時，最好在前面加上 typename關鍵字，否則可能會編譯錯，VS可能無此問題，但是Dev C++和服務器上的編譯環境會有這個問題，比如：

   typename list<T>::iterator i; //typename用于指明list<T>::iterator是個型別
   

演算法（函式模板）

1. find順序查找

   template<class It,class T>
   It find(It first,It last,const T& val); 
   //用==判斷相等，找不到則回傳last指標
   

2. bianry_search二元查找，僅適用于由小到大排好序的順序容器，找到回傳true，否則false，用<判斷

vector

1. 示例

   int a[]={1,2,3,4,5};
   vector<int> v(a,a+5); //拷貝整個陣列
   cout<<v.end()-v.begin()<<endl; //迭代器相減
   v.insert(v.begin()+2,13); //v[2]處插入元素
   v.erase(v.begin()+2);//洗掉元素
   vector<int> v2(4,100);
   v2.insert(v2.begin(),v.begin()+1,v.begin()+3); //v2[0]插入v區間
   v.erase(v.begin()+1,v.begin()+3); //洗掉區間
   

deque

支持vector所有操作，且支持push_front和pop_front操作隊首元素 O(1)

list

1. 支持順序容器所有操作

2. 其他操作

   list<int> lst(a,a+5); //拷貝整個陣列
   push_front(T val);
   pop_front();
   sort(); //排序，不支持STL的排序函式
   sort(T op); //按照某種規則排序
   remove(T val); //洗掉指定值的元素
   unique(); //洗掉所有和前一個元素相等的元素（若去重，需要先sort）
   merge(list<T> lst); //與lst鏈表合并，并清空lst
   reverse(); //顛倒鏈表
    splice(It p1,list<T> lst2,It p2,It p3);//將lst2的[p2,p3)移動到p1前面
   

函式物件

1. 在類中對括號進行多載，使類物件具有類似函式的功能

2. 目的：增強函式復用性，不用針對每種情況撰寫一個函式

   template<class T>
   class SumPower{ //用于計算某個n次方和
   	int power;
   	public:
   	SumPower(int n):power(n){}
   	T operator() (const T& init,const T& tmp){
   		T v=tmp;
   		for(int i=0;i<power-1;++i) v*=tmp;
   		return init+v;
   	} 
   };
   template<class It,class T,class Pred>  //計算累加值
   T CalcPower(It first,It last,T init,Pred op){
   	for(;first!=last;++first) init=op(init,*first); 
   	return init;
   }
   int main(){
   	int a[]={1,2,3,4,5,6,7,8,9,10};
   	vector<int> v(a,a+10);
   	cout<<"立方和: "<<CalcPower(v.begin(),v.end(),0,SumPower<int>(3));
   	return 0;
   }
   

   less和greater函式物件

   1. less<T>()按照從小到大的方式排列
   2. greater<T>()按照從大到小的方式排列

標籤：C++

上一篇：第七章 2.泛型編程（模板）

下一篇：第九章 STL標準庫（二）