C++ STL

1. STL介紹

1.1 STL基本概念

STL即standard template library的縮寫，标準模闆庫。主要是提升常用函數和資料結構的複用性。

STL從廣義上分為：容器、算法、疊代器

容器和算法之間通過疊代器無縫連接配接。

1.2 STL六大元件

STL大體上分為六大元件：容器、算法、疊代器、仿函數、擴充卡、空間配置器

1. 容器：各種資料結構，如vector、list、deque、set、map等,用來存放資料。
2. 算法：各種常用的算法，如sort、find、copy、for_each等
3. 疊代器：扮演了容器與算法之間的膠合劑。
4. 仿函數：行為類似函數，可作為算法的某種政策。
5. 擴充卡：一種用來修飾容器或者仿函數或疊代器接口的東西。
6. 空間配置器：負責空間的配置與管理。

1.3 STL容器、算法、疊代器初認識

STL容器就是将運用最廣泛的一些資料結構實作出來，包括數組、連結清單、樹、棧、隊列、集合、映射等。這些容器細分為序列式容器和關聯式容器。

序列式容器：強調值的排序，序列式容器中的每個元素均有固定的位置。

關聯式容器：二叉樹結構，元素之間沒有嚴格的實體上的順序關系。

質變算法：是指運算過程中會更改區間内的元素的内容。例如拷貝，替換，删除等等

非質變算法：是指運算過程中不會更改區間内的元素内容，例如查找、計數、周遊、尋找極值等等

疊代器種類：

種類	功能	支援運算
輸入疊代器	對資料的隻讀通路	隻讀，支援++、==、！=
輸出疊代器	對資料的隻寫通路	隻寫，支援++
前向疊代器	讀寫操作，并能向前推進疊代器	讀寫，支援++、==、！=
雙向疊代器	讀寫操作，并能向前和向後操作	讀寫，支援++、–，
随機通路疊代器	讀寫操作，可以以跳躍的方式通路任意資料，功能最強的疊代器	讀寫，支援++、–、[n]、-n、<、<=、>、>=

2. STL常用容器介紹

2.1 string

string是一個類，而char*是一個指針

2.1.1 string構造函數

• string();//建立一個空的字元串 例如: string str;
• string(const char*);//使用字元串s初始化
• string(const string& str); //使用一個string對象初始化另一個string對象
• string(int n, char c);//使用n個字元c初始化

2.1.2 string指派操作

• string& operator=(const char* s);

   //char*類型字元串 指派給目前的字元串；str1 = "hello world";

• string& operator=(const string &s);

   //把字元串s賦給目前的字元串

• string& operator=(char c);

   //字元指派給目前的字元串；str3 = 'a';

• string& assign(const char *s);

   //把字元串s賦給目前的字元串；str4.assign("hello c++");

• string& assign(const char *s, int n);

   //把字元串s的前n個字元賦給目前的字元串；str5.assign("hello c++",5);

• string& assign(const string &s);

   //把字元串s賦給目前字元串；str6.assign(str5);

• string& assign(int n, char c);

   //用n個字元c賦給目前字元串；str7.assign(5, 'x');

2.1.3 字元串拼接操作

• string& operator+=(const char* str);

   //重載+=操作符

• string& operator+=(const char c);

   //重載+=操作符

• string& operator+=(const string& str);

   //重載+=操作符

• string& append(const char *s);

   //把字元串s連接配接到目前字元串結尾

• string& append(const char *s, int n);

   //把字元串s的前n個字元連接配接到目前字元串結尾

• string& append(const string &s);

   //同operator+=(const string& str)

• string& append(const string &s, int pos, int n);

  //字元串s中從pos開始的n個字元連接配接到字元串結尾

2.1.4 string查找替換

• int find(const string& str, int pos = 0) const;

   //查找str第一次出現位置,從pos開始查找

• int find(const char* s, int pos = 0) const;

   //查找s第一次出現位置,從pos開始查找

• int find(const char* s, int pos, int n) const;

   //從pos位置查找s的前n個字元第一次位置

• int find(const char c, int pos = 0) const;

   //查找字元c第一次出現位置

• int rfind(const string& str, int pos = npos) const;

   //查找str最後一次位置,從pos開始查找

• int rfind(const char* s, int pos = npos) const;

   //查找s最後一次出現位置,從pos開始查找

• int rfind(const char* s, int pos, int n) const;

   //從pos查找s的前n個字元最後一次位置

• int rfind(const char c, int pos = 0) const;

   //查找字元c最後一次出現位置

• string& replace(int pos, int n, const string& str);

   //替換從pos開始n個字元為字元串str

• string& replace(int pos, int n,const char* s);

   //替換從pos開始的n個字元為字元串s

3.1.6 string字元串比較

• int compare(const string &s) const;

   //與字元串s比較

• int compare(const char *s) const;

   //與字元串s比較
• = 傳回 0、> 傳回 1、< 傳回 -1

3.1.7 string字元存取

• char& operator[](int n);

   //通過[]方式取字元//str[3]

• char& at(int n);

   //通過at方法擷取字元//str.at(3）

3.1.8 string插入和删除

• string& insert(int pos, const char* s);

   //插入字元串

• string& insert(int pos, const string& str);

   //插入字元串

• string& insert(int pos, int n, char c);

   //在指定位置插入n個字元c

• string& erase(int pos, int n = npos);

   //删除從Pos開始的n個字元

3.1.9 string子串

• string substr(int pos = 0, int n = npos) const;

   //傳回由pos開始的n個字元組成的字元串

3.2 vector容器

vector與普通數組的差別：數組是靜态空間，而vector可以動态擴充。

動态擴充：并不是在原空間之後續接新空間，而是找更大的記憶體空間，然後将原資料拷貝新空間，釋放原空間

3.2.1 vector構造函數

• vector<T> v;

   //采用模闆實作類實作，預設構造函數

• vector<T> v1(v.begin(), v.end());

   //将v[begin(), end())區間中的元素拷貝給本身。

• vector<T> v(n, elem);

   //構造函數将n個elem拷貝給本身。

• vector<T> v(const vector &vec);

   //拷貝構造函數。

3.2.2 vector指派操作

• vector& operator=(const vector &vec);

  //重載等号操作符

• assign(beg, end);

   //将[beg, end)區間中的資料拷貝指派給本身。

• assign(n, elem);

   //将n個elem拷貝指派給本身。

3.2.3 vector容量和大小

• empty();

   //判斷容器是否為空

• capacity();

   //容器的容量

• size();

   //傳回容器中元素的個數

• resize(int num);

   //重新指定容器的長度為num，若容器變長，則以預設值填充新位置。

  ​ //如果容器變短，則末尾超出容器長度的元素被删除。

• resize(int num, elem);

   //重新指定容器的長度為num，若容器變長，則以elem值填充新位置。

  ​ //如果容器變短，則末尾超出容器長度的元素被删除

3.2.4 vector插入和删除

• push_back(ele);

   //尾部插入元素ele

• pop_back();

   //删除最後一個元素

• insert(const_iterator pos, ele);

   //疊代器指向位置pos插入元素ele

• insert(const_iterator pos, int count,ele);

  //疊代器指向位置pos插入count個元素ele

• erase(const_iterator pos);

   //删除疊代器指向的元素

• erase(const_iterator start, const_iterator end);

  //删除疊代器從start到end之間的元素

• clear();

   //删除容器中所有元素

3.2.5 vector資料存取

• at(int idx);

   //傳回索引idx所指的資料

• operator[];

   //傳回索引idx所指的資料

• front();

   //傳回容器中第一個資料元素

• back();

   //傳回容器中最後一個資料元素

3.2.6 vector互換容器

• swap(vec);

   // 将vec與本身的元素互換

3.2.7 vector預留白間

• 減少vector在動态擴充容量時的擴充次數

• reserve(int len);

  //容器預留len個元素長度，預留位置不初始化，元素不可通路
• 如果資料量較大，可以一開始利用reserve預留白間,減少數組擴充的開銷

3.3 deque容器

deque是雙端數組，可以對頭尾兩端進行插入删除操作。

deque與vector差別：

• vector對于頭部的插入删除效率低，資料量越大，效率越低
• deque相對而言，對頭部的插入删除速度回比vector快
• vector通路元素時的速度會比deque快,這和兩者内部實作有關

deque的構造函數、指派操作、大小操作和vector相同，不再闡述

3.3.1 deque插入删除

• push_back(elem);

   //在容器尾部添加一個資料

• push_front(elem);

   //在容器頭部插入一個資料

• pop_back();

   //删除容器最後一個資料

• pop_front();

   //删除容器第一個資料

• insert(pos,elem);

   //在pos位置插入一個elem元素的拷貝，傳回新資料的位置。

• insert(pos,n,elem);

   //在pos位置插入n個elem資料，無傳回值。

• insert(pos,beg,end);

   //在pos位置插入[beg,end)區間的資料，無傳回值。

• clear();

   //清空容器的所有資料

• erase(beg,end);

   //删除[beg,end)區間的資料，傳回下一個資料的位置。

• erase(pos);

   //删除pos位置的資料，傳回下一個資料的位置。

3.3.2 deque 資料存取

• at(int idx);

   //傳回索引idx所指的資料

• operator[];

   //傳回索引idx所指的資料

• front();

   //傳回容器中第一個資料元素

• back();

   //傳回容器中最後一個資料元素

3.4 stack容器

構造函數：

• stack<T> stk;

   //stack采用模闆類實作， stack對象的預設構造形式

• stack(const stack &stk);

   //拷貝構造函數

指派操作：

• stack& operator=(const stack &stk);

   //重載等号操作符

資料存取：

• push(elem);

   //向棧頂添加元素

• pop();

   //從棧頂移除第一個元素

• top();

   //傳回棧頂元素

大小操作：

• empty();

   //判斷堆棧是否為空

• size();

   //傳回棧的大小

3.5 queue

構造函數：

• queue<T> que;

   //queue采用模闆類實作，queue對象的預設構造形式

• queue(const queue &que);

   //拷貝構造函數

指派操作：

• queue& operator=(const queue &que);

   //重載等号操作符

資料存取：

• push(elem);

   //往隊尾添加元素

• pop();

   //從隊頭移除第一個元素

• back();

   //傳回最後一個元素

• front();

   //傳回第一個元素

大小操作：

• empty();

   //判斷堆棧是否為空

• size();

   //傳回棧的大小

3.6 list容器

連結清單（list）是一種實體存儲單元上非連續的存儲結構，資料元素的邏輯順序是通過連結清單中的指針連結實作的

list的優點：

• 采用動态存儲配置設定，不會造成記憶體浪費和溢出
• 連結清單執行插入和删除操作十分友善，修改指針即可，不需要移動大量元素

list的缺點：

• 連結清單靈活，但是空間(指針域) 和 時間（周遊）額外耗費較大

3.6.1 構造函數

• list<T> lst;

   //list采用采用模闆類實作,對象的預設構造形式：

• list(beg,end);

   //構造函數将[beg, end)區間中的元素拷貝給本身。

• list(n,elem);

   //構造函數将n個elem拷貝給本身。

• list(const list &lst);

   //拷貝構造函數。

3.6.2 指派和交換

• assign(beg, end);

   //将[beg, end)區間中的資料拷貝指派給本身。

• assign(n, elem);

   //将n個elem拷貝指派給本身。

• list& operator=(const list &lst);

   //重載等号操作符

• swap(lst);

   //将lst與本身的元素互換。

3.6.3 list大小操作

• size();

   //傳回容器中元素的個數

• empty();

   //判斷容器是否為空

• resize(num);

   //重新指定容器的長度為num，若容器變長，則以預設值填充新位置。

  ​ //如果容器變短，則末尾超出容器長度的元素被删除。

• resize(num, elem);

   //重新指定容器的長度為num，若容器變長，則以elem值填充新位置。

3.6.4 list插入和删除

• push_back(elem);//在容器尾部加入一個元素
• pop_back();//删除容器中最後一個元素
• push_front(elem);//在容器開頭插入一個元素
• pop_front();//從容器開頭移除第一個元素
• insert(pos,elem);//在pos位置插elem元素的拷貝，傳回新資料的位置。
• insert(pos,n,elem);//在pos位置插入n個elem資料，無傳回值。
• insert(pos,beg,end);//在pos位置插入[beg,end)區間的資料，無傳回值。
• clear();//移除容器的所有資料
• erase(beg,end);//删除[beg,end)區間的資料，傳回下一個資料的位置。
• erase(pos);//删除pos位置的資料，傳回下一個資料的位置。
• remove(elem);//删除容器中所有與elem值比對的元素。

3.6.5 list資料存取

• front();

   //傳回第一個元素。

• back();

   //傳回最後一個元素。

3.6.6 list反轉和排序

• reverse();

   //反轉連結清單

• sort();

   //連結清單排序

3.6.7 排序案例

案例描述：将Person自定義資料類型進行排序，Person中屬性有姓名、年齡、身高

排序規則：按照年齡進行升序，如果年齡相同按照身高進行降序

#include <list>
#include <string>
class Person {
public:
	Person(string name, int age , int height) {
		m_Name = name;
		m_Age = age;
		m_Height = height;
	}

public:
	string m_Name;  //姓名
	int m_Age;      //年齡
	int m_Height;   //身高
};


bool ComparePerson(Person& p1, Person& p2) {

	if (p1.m_Age == p2.m_Age) {
		return p1.m_Height  > p2.m_Height;
	}
	else
	{
		return  p1.m_Age < p2.m_Age;
	}

}

void test01() {

	list<Person> L;

	Person p1("劉備", 35 , 175);
	Person p2("曹操", 45 , 180);
	Person p3("孫權", 40 , 170);
	Person p4("趙雲", 25 , 190);
	Person p5("張飛", 35 , 160);
	Person p6("關羽", 35 , 200);

	L.push_back(p1);
	L.push_back(p2);
	L.push_back(p3);
	L.push_back(p4);
	L.push_back(p5);
	L.push_back(p6);

	for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
		cout << "姓名： " << it->m_Name << " 年齡： " << it->m_Age 
              << " 身高： " << it->m_Height << endl;
	}

	cout << "---------------------------------" << endl;
	L.sort(ComparePerson); //排序

	for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
		cout << "姓名： " << it->m_Name << " 年齡： " << it->m_Age 
              << " 身高： " << it->m_Height << endl;
	}
}

int main() {

	test01();

	system("pause");

	return 0;
}
           

3.7 set和multiset

• set/multiset屬于關聯式容器，底層結構是用二叉樹實作。

set和multiset差別：

• set不允許容器中有重複的元素
• multiset允許容器中有重複的元素
• set插入資料的同時會傳回插入結果，表示插入是否成功
• multiset不會檢測資料，是以可以插入重複資料

set構造:

• set<T> st;

   //預設構造函數：

• set(const set &st);

   //拷貝構造函數

set指派:

• set& operator=(const set &st);

set大小和交換：

• size();

   //傳回容器中元素的數目

• empty();

   //判斷容器是否為空

• swap(st);

   //交換兩個集合容器

set插入和删除：

• insert(elem);

   //在容器中插入元素。

• clear();

   //清除所有元素

• erase(pos);

   //删除pos疊代器所指的元素，傳回下一個元素的疊代器。

• erase(beg, end);

   //删除區間[beg,end)的所有元素 ，傳回下一個元素的疊代器。

• erase(elem);

   //删除容器中值為elem的元素。

set查找和統計：

• find(key);

   //查找key是否存在,若存在，傳回該鍵的元素的疊代器；若不存在，傳回set.end();

• count(key);

   //統計key的元素個數

pair對組建立：

• pair<type, type> p ( value1, value2 );

• pair<type, type> p = make_pair( value1, value2 );

3.7.1 set容器排序

• set容器預設排序規則為從小到大，掌握如何改變排序規則
• 利用仿函數，可以改變排序規則

#include <set>

class MyCompare 
{
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};
void test01() 
{    
	set<int> s1;
	s1.insert(10);
	s1.insert(40);
	s1.insert(20);
	s1.insert(30);
	s1.insert(50);

	//預設從小到大
	for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	//指定排序規則
	set<int,MyCompare> s2;
	s2.insert(10);
	s2.insert(40);
	s2.insert(20);
	s2.insert(30);
	s2.insert(50);

	for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}
           

3.8 map/multimap容器

• map中所有元素都是pair
• pair中第一個元素為key（鍵值），起到索引作用，第二個元素為value（實值）
• 所有元素都會根據元素的鍵值自動排序
• map/multimap屬于關聯式容器，底層結構是用二叉樹實作。
• map不允許容器中有重複key值元素，multimap允許容器中有重複key值元素

map構造和指派：

• map<T1, T2> mp;

   //map預設構造函數:

• map(const map &mp);

   //拷貝構造函數

• map& operator=(const map &mp);

   //重載等号操作符

map大小和交換：

• size();

   //傳回容器中元素的數目

• empty();

   //判斷容器是否為空

• swap(st);

   //交換兩個集合容器

map插入和删除：

• insert(elem);

   //在容器中插入元素。

• clear();

   //清除所有元素

• erase(pos);

   //删除pos疊代器所指的元素，傳回下一個元素的疊代器。

• erase(beg, end);

   //删除區間[beg,end)的所有元素 ，傳回下一個元素的疊代器。

• erase(key);

   //删除容器中值為key的元素。

map查找和統計：

• find(key);

   //查找key是否存在,若存在，傳回該鍵的元素的疊代器；若不存在，傳回set.end();

• count(key);

   //統計key的元素個數

3.8.1 map容器排序

#include <map>

class MyCompare {

public:

    bool operator()(int v1, int v2) {

        return v1 > v2;

    }

};

void test01() 

{

    //預設從小到大排序

    //利用仿函數實作從大到小排序

    map<int, int, MyCompare> m;

    m.insert(make_pair(1, 10));

    m.insert(make_pair(2, 20));

    m.insert(make_pair(3, 30));

    m.insert(make_pair(4, 40));

    m.insert(make_pair(5, 50));

    for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {

        cout << "key:" << it->first << " value:" << it->second << endl;

    }

}

int main() {

    test01();

    system("pause");

    return 0;

}