2.2 STL 基本概念

• STL（Standard Template Library，標(biāo)準(zhǔn)模板庫(kù)）
• ST從廣義上分為：容器（container），算法（algorithm）和迭代器（iterator）
• 容器和算法之間通過迭代器進(jìn)行無縫連接屡限。
• STL幾乎所有的代碼都采用了模板類或者模板函數(shù)

2.3 STL 六大組件

STL大體分為六大組件品嚣，分別是容器、算法钧大、迭代器翰撑、仿函數(shù)、適配器（配接器）啊央、空間配置器

1. 容器：各種數(shù)據(jù)結(jié)構(gòu)眶诈，如vector、list瓜饥、deque逝撬、set、map等压固，用來存放數(shù)據(jù)球拦。
2. 算法：各種常用的算法，如sort帐我、find坎炼、copy、for_each等拦键。
3. 迭代器：扮演了容器與算法之間的膠合劑谣光。
4. 仿函數(shù)：行為類似函數(shù)，可作為算法的某種策略芬为。
5. 適配器：一種用來修飾容器或者仿函數(shù)或迭代器接口的東西萄金。
6. 空間配置器：負(fù)責(zé)空間的配置與管理。

2.4 STL 中容器媚朦、算法氧敢、迭代器

容器：置物之所也

STL容器就是將運(yùn)用最廣泛的一些數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)出來

常用的數(shù)據(jù)結(jié)構(gòu)：數(shù)組鏈表樹，棧询张，隊(duì)列孙乖，集合，映射表等

這些容器分為序列式容器和關(guān)聯(lián)式容器兩種

• 序列式容器：強(qiáng)調(diào)值的排序份氧，序列式容器中的每個(gè)元素均有固定的位置
• 關(guān)聯(lián)式容器：二叉樹結(jié)構(gòu)唯袄，各元素之間沒有嚴(yán)格的物理上的順序關(guān)系

算法：問題之解法也

有限的步驟，解決邏輯或數(shù)學(xué)上的問題蜗帜，這一門學(xué)科我們叫做算法（Algorithms）

算法分為：質(zhì)變算法和非質(zhì)變算法恋拷。

• 質(zhì)變算法：是指運(yùn)算過程中會(huì)更改區(qū)間內(nèi)的元素的內(nèi)容例如拷貝，替換厅缺，刪除等等
• 非質(zhì)變算法：是指運(yùn)算過程中不會(huì)更改區(qū)間內(nèi)的元素內(nèi)容蔬顾，例如查找宴偿、計(jì)數(shù)、遍歷阎抒、尋找極值等等

迭代器：容器和算法之間粘合劑

提供一種方法酪我，使之能夠依序?qū)ぴL某個(gè)容器所含的各個(gè)元素，而又無需暴露該容器的內(nèi)部表示方式且叁。

每個(gè)容器都有自己專屬的迭代器

迭代器使用非常類似于指針都哭，初學(xué)階段我們可以先理解代器為指針

迭代器種類：

常用的容器中迭代器種類為雙向迭代器，和隨機(jī)訪問迭代器

2.5 容器算法迭代器初識(shí)

了解STL中容器甩恼、算法却盘、迭代器概念之后，我們利用代碼感受STL的魅力

STL中最常用的容器為Vector媳拴，可以理解為數(shù)組，下面我們將學(xué)習(xí)如何向這個(gè)容器中插入數(shù)據(jù)兆览、并遍歷這個(gè)容器

2.5.1 vector 存放內(nèi)置數(shù)據(jù)類型

容器：vector

算法：for_each

迭代器：vector<int>::iterator

示例：

#include <iostream>
//容器頭文件
#include <vector>
//標(biāo)準(zhǔn)算法頭文件
#include <algorithm>

using namespace std;

void myPrint(int val) {
  cout << val << ", ";
}

void test01() {
  //創(chuàng)建一個(gè)vector容器（數(shù)組）
  vector<int> v;
  //向容器中插入數(shù)據(jù)
  for (int i = 0; i < 10; ++i) {
    v.push_back((i + 1) * 10);
  }
  //通過迭代器訪問容器中的數(shù)據(jù)
  vector<int>::iterator itBegin = v.begin();  //起始迭代器屈溉，指向元素中第一個(gè)元素
  vector<int>::iterator itEnd = v.end();      //結(jié)束迭代器，指向元素中最后一個(gè)元素的下一個(gè)位置

  //第一種遍歷方式
  cout << "第一種遍歷方式：" << endl;
  while (itBegin != itEnd) {
    cout << *itBegin << (itBegin == itEnd - 1 ? "\n" : ", ");
    itBegin++;
  }
  //第二種遍歷方式
  cout << "第二種遍歷方式：" << endl;
  for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
  //第三種遍歷方式
  cout << "第三種遍歷方式：" << endl;

  for_each(v.begin(), v.end(), myPrint);
}

int main() {
  test01();

  system("pause");

  return 0;
}

2.5.2 vector 存放自定義數(shù)據(jù)類型

示例：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class Person {
  public:
  Person(string name, short age) {
    this->m_Name = name;
    this->m_Age = age;
  }

  string m_Name;
  short m_Age;
};

//存放自定義數(shù)據(jù)類型
void test01() {
  //創(chuàng)建容器
  vector<Person> v;
  //人物信息
  Person p1("唐三藏", 30);
  Person p2("孫悟空", 1000);
  Person p3("豬悟凈", 999);
  Person p4("沙悟凈", 998);
  Person p5("白龍馬", 997);
  //向容器中添加數(shù)據(jù)
  v.push_back(p1);
  v.push_back(p2);
  v.push_back(p3);
  v.push_back(p4);
  v.push_back(p5);
  //遍歷容器中的數(shù)據(jù)
  for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
    //解引用訪問
    cout << (*it).m_Name << "的年齡是"
      //箭頭訪問
      << it->m_Age << "歲抬探。" << endl;
  }
}

//存放自定義數(shù)據(jù)類型的指針
void test02() {
  //創(chuàng)建容器
  vector<Person *> v;
  //人物信息
  Person p1("唐三藏", 30);
  Person p2("孫悟空", 1000);
  Person p3("豬悟凈", 999);
  Person p4("沙悟凈", 998);
  Person p5("白龍馬", 997);
  //向容器中添加數(shù)據(jù)
  v.push_back(&p1);
  v.push_back(&p2);
  v.push_back(&p3);
  v.push_back(&p4);
  v.push_back(&p5);
  //遍歷容器中的數(shù)據(jù)
  for (vector<Person *>::iterator it = v.begin(); it != v.end(); it++) {
    //解引用訪問
    cout << (**it).m_Name << "的年齡是"
      //箭頭訪問
      << (*it)->m_Age << "歲子巾。" << endl;
  }
}

int main() {
  test01();
  test02();

  system("pause");

  return 0;
}

2.5.3 vector 容器嵌套容器

示例：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void test01() {
  vector<vector<int>> v;
  //創(chuàng)建小容器
  vector<int> v1;
  vector<int> v2;
  vector<int> v3;
  vector<int> v4;
  //向小容器中添加數(shù)據(jù)
  for (int i = 0; i < 4; ++i) {
    v1.push_back(i + 1);
    v2.push_back((i + 1) * 2);
    v3.push_back((i + 1) * 3);
    v4.push_back((i + 1) * 4);
  }
  //將小容器插入到大容器中
  v.push_back(v1);
  v.push_back(v2);
  v.push_back(v3);
  v.push_back(v4);
  //通過大容器帆赢，把所有數(shù)據(jù)遍歷
  for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++) {
    //(*it) -- 容器 vector<int>
    for (vector<int>::iterator vit = it->begin(); vit != it->end(); vit++) {
      cout << *vit << (vit == it->end() - 1 ? "\n" : "\t");
    }
  }
}

int main() {
  test01();

  system("pause");

  return 0;
}

3 STL 常用容器

3.1 string 容器

3.1.1 string 基本概念

本質(zhì)：

• string是C++風(fēng)格的字符串，而string本質(zhì)上是一個(gè)類

string和char *區(qū)別:：

• char *是一個(gè)指針
• string是一個(gè)類线梗，類內(nèi)部封裝了char *椰于，管理這個(gè)字符串，是一個(gè)char型的容器仪搔。

特點(diǎn)：
string類內(nèi)部封裝了很多成員方法

例如：查找find瘾婿，拷貝copy，刪除delete烤咧，替換replace偏陪，插入insert

string管理char所分配的內(nèi)存，不用擔(dān)心復(fù)制越界和取值越界等煮嫌，由類內(nèi)部進(jìn)行負(fù)責(zé)

3.1.2 string 構(gòu)造函數(shù)

構(gòu)造函數(shù)原型：

• string(); //創(chuàng)建一個(gè)空的字符串笛谦，例如：string str;
• string(const char *s); //使用字符串s初始化
• string(const string &str); //使用一個(gè)string對(duì)象初始化另一個(gè)string對(duì)象
• string(int n, char c); //使用n個(gè)字符c初始化

示例：

#include <iostream>
#include <string>

using namespace std;

void test01() {
  //默認(rèn)構(gòu)造
  string s1;
  //使用字符串初始化
  const char *str = "Hello world!";
  string s2(str);
  cout << s2 << endl;
  //使用一個(gè)string對(duì)象初始化另一個(gè)string對(duì)象
  string s3(s2);
  cout << s3 << endl;
  //使用n個(gè)字符c初始化
  string s4(10, 'a');
  cout << s4 << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

總結(jié)：string的多種構(gòu)造方法沒有可比性，靈活使用過即可

3.1.3 string 賦值操作

功能描述：

• 給string字符串進(jìn)行賦值

賦值的函數(shù)原型：

• string &operator=(const char *s)昌阿； //char*類型字符串賦值給當(dāng)前的字符串
• string &operator=(const string &s); //把字符串s賦給當(dāng)前的字符串
• string &operator=(char c); //字符賦值給當(dāng)前的字符串
• string &assign(const char *s); //把字符串s賦給當(dāng)前的字符串
• string &assign(const char *s饥脑，int n); //把符串s的前n個(gè)字符賦給當(dāng)前的字符串
• string &assign(const string &s); //把字符串s賦給當(dāng)前字符串
• string &assign(int n, char c); //用n個(gè)字符c賦給當(dāng)前字符串

示例：

#include <iostream>
#include <string>

using namespace std;

void test01() {
  //char*類型字符串賦值給當(dāng)前的字符串
  string s1;
  s1 = "Hello world 1";
  cout << "s1 = " << s1 << endl;
  //把字符串s賦給當(dāng)前的字符串
  string s2;
  s2 = s1;
  cout << "s2 = " << s2 << endl;
  //字符賦值給當(dāng)前的字符串
  string s3;
  s3 = 'a';
  cout << "s3 = " << s3 << endl;

  //把字符串s賦給當(dāng)前的字符串
  string s4;
  s4.assign("Hello world 2");
  cout << "s4 = " << s4 << endl;
  //把符串s的前n個(gè)字符賦給當(dāng)前的字符串
  string s5;
  s5.assign("Hello world", 5);
  cout << "s5 = " << s5 << endl;
  //把字符串s賦給當(dāng)前字符串
  string s6;
  s6.assign(s5);
  cout << "s6 = " << s6 << endl;
  //用n個(gè)字符c賦給當(dāng)前字符串
  string s7;
  s7.assign(10, 'a');
  cout << "st = " << s7;
}

int main() {
  test01();

  system("pause");

  return 0;
}

總結(jié)：string的賦值方式有很多，operator=這種方式是比較實(shí)用的

3.1.4 string 字符串拼接

功能描述：

• 實(shí)現(xiàn)在字符串末尾拼接字符串

函數(shù)原型：

• string &operator+=(const char *str); //重載+=操作符
• string &operator+=(const char c); //重載+=操作符
• string &operator+=(const string &str); //重載+=操作符
• string &append(const char *s); //把字符串s連接到當(dāng)前字符串結(jié)尾
• string &append(const char *s, int n); //把字符串s的前n個(gè)字符連接到當(dāng)前字符串結(jié)尾
• string &append(const string &s); //同operator+=(const string &str);
• string &append(const string &s, int pos, int n); //字符串s從pos開始的n個(gè)字符連接到字符串結(jié)尾

示例：

#include <iostream>
#include <string>

using namespace std;

void test01() {
  string str1 = "I";
  cout << str1 << endl;
  //string &operator+=(const char *str);                   //重載+=操作符
  str1 += (" like coding");
  cout << str1 << endl;
  //string &operator+=(const char c);                      //重載+=操作符
  str1 += ',';
  cout << str1 << endl;
  //string &operator+=(const string &str);                 //重載+=操作符
  string str2 = " C, C++, Java and Python. ";
  str1 += str2;
  cout << str1 << endl;
  //string &append(const char *s);                         /把字符串s連接到當(dāng)前字符串結(jié)尾
  str1.append("Coding is ");
  cout << str1 << endl;
  //string &append(const char *s, int n);                  //把字符串s的前n個(gè)字符連接到當(dāng)前字符串結(jié)尾
  str1.append("veryabcdefg ", 4);
  cout << str1 << endl;
  //string &append(const string &s);                       //同operator+=(const string &str);
  string str4 = " fun";
  str1.append(str4);
  cout << str1 << endl;
  //string &append(const string &s, int pos, int n);       //字符串s從pos開始的n個(gè)字符連接到字符串結(jié)尾
  string str5 = ".,/?!\'\"\\[]{}()";
  str1.append(str5, 4, 1);
  cout << str1 << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.1.5 string 查找和替換

功能描述：

• 查找：查找指定字符串是否存在
• 替換：在指定的位置替換字符串

函數(shù)原型

• int find(const string &str, int pos = 0) const; //從pos開始查找str第一次出現(xiàn)的位置
• int find(const char *s, int pos = 0) const; //從pos開始查找s第一次出現(xiàn)的位置
• int find(const char *s, int pos, int n) const; //從pos位置查找s的前n個(gè)字符第一次出現(xiàn)的位置
• int find(const char c, int pos = 0) const; //查找字符c第一次出現(xiàn)位置
• int rfind(const string &str, int pos = npos) const; //從pos開始查找str最后一次出現(xiàn)的位置
• int rfind(const char *s, int pos = npos) const; //從pos開始查找str最后一次出現(xiàn)的位置
• int rfind(const char *s, int pos, int n) const; //從pos開始查找s的前n個(gè)字符最后一次出現(xiàn)的位置
• int rfind(const char c, int pos = 0) const; //查找字符c最后一次出現(xiàn)的位置
• string &replace(int pos, int n, const string &str); //將從pos開始的n個(gè)字符替換為字符串str
• string &replace(int pos, int n, const chat *s); //將從pos開始的n個(gè)字符替換為字符串s

示例：

#include <iostream>
#include <string>

using namespace std;

void test01() {
  string str1 = "abcdefghij";
  string str2 = "de";
  //int find(const string &str, int pos = 0) const;           //從pos開始查找str第一次出現(xiàn)位置
  int pos = str1.find(str2);
  cout << "int pos = str1.find(str2);\t\t\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int find(const char *s, int pos = 0) const;               //從pos開始查找s第一次出現(xiàn)位置
  pos = str1.find("fh");
  cout << "int pos = str1.find(\"fh\");\t\t\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int find(const char *s, int pos, int n) const;            //從pos位置查找s的前n個(gè)字符第一次出現(xiàn)的位置
  pos = str1.find("fghijk", 0, 3);
  cout << "int pos = str1.find(\"fghijk\", 0, 3);\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int find(const char c, int pos = 0) const;                //查找字符c第一次出現(xiàn)位置
  pos = str1.find('h');
  cout << "int pos = str1.find(\'h\');\t\t\t\t";
  pos == -1 ? cout << "未找到字符" << endl : cout << "pos = " << pos << endl;
  //int rfind(const string &str, int pos = npos) const;       //從pos開始查找str最后一次出現(xiàn)的位置
  pos = str1.rfind(str2);
  cout << "int pos = str1.rfind(str2);\t\t\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int rfind(const char *s, int pos = npos) const;           //從pos開始查找str最后一次出現(xiàn)的位置
  pos = str1.rfind("fg");
  cout << "pos = str1.rfind(\"fg\");\t\t\t\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int rfind(const char *s, int pos, int n) const;           //從pos開始查找s的前n個(gè)字符最后一次出現(xiàn)的位置
  pos = str1.rfind("fhgijk", 0, 3);
  cout << "pos = str1.rfind(\"fhgijk\", 0, 3);\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
  //int rfind(const char c, int pos = 0) const;               //查找字符c最后一次出現(xiàn)的位置
  pos = str1.rfind('h');
  cout << "pos = str1.rfind(\'h\');\t\t\t\t\t";
  pos == -1 ? cout << "未找到字符串" << endl : cout << "pos = " << pos << endl;
}

void test02() {
  string str1 = "abcdefg";
  //string &replace(int pos, int n, const string &str);       //將從pos開始的n個(gè)字符替換為字符串str
  string str2 = "1234";
  str1.replace(1, 3, str2);
  cout << "str1.replace(1, 3, str2);\t" << str1 << endl;
  //string &replace(int pos, int n, const chat *s);           //將從pos開始的n個(gè)字符替換為字符串s
  str1.replace(1, 3, "4321");
  cout << "str1.replace(1, 3, \"4321\");\t" << str1 << endl;
}

int main() {
  test01();
  cout << "-=-=-=-=-=-=-=-=-=-=-=替  換-=-=-=-=-=-=-=-=-=-=-=" << endl;
  test02();

  system("pause");

  return 0;
}

總結(jié)：

• find查找是從左往后懦冰， rfind從右往左
• find找到字符串后返回查找的第一個(gè)字符位置灶轰，找不到返回-1
• replace在替換時(shí)，要指定從哪個(gè)位置起儿奶，多少個(gè)字符框往，替換成什么樣的字符串

3.1.6 string 字符串比較

比較方式：

• 字符串的比較是按字符的ASCII碼進(jìn)行對(duì)比
• = 返回 0
> 返回 1
< 返回 -1

函數(shù)原型：

• int compare(const string &s) const; //與字符串s比較
• int compare(const char *s) const; //與字符串s比較

#include <iostream>
#include <string>

using namespace std;

void compareStrings(string &str1, string &str2) {
  //int compare(const string &s) const;   //與字符串s比較
  if (str1.compare(str2) == 0) { cout << str1 << " 等于 " << str2 << endl; }
  else if (str1.compare(str2) > 0) { cout << str1 << " 大于 " << str2 << endl; }
  else if (str1.compare(str2) < 0) { cout << str1 << " 小于 " << str2 << endl; }
}

void test01() {
  string str1 = "hello";
  string str2 = "hello";
  string str3 = "hellO";
  string str4 = "xello";
  compareStrings(str1, str2);
  compareStrings(str1, str3);
  compareStrings(str1, str4);
  //int compare(const char *s) const;     //與字符串s比較
}

int main() {
  test01();

  system("pause");

  return 0;
}

總結(jié)：字符串對(duì)比主要是用于比較兩個(gè)字符串是否相等，判斷誰(shuí)大誰(shuí)小的意義并不是很大

3.1.7 string 字符存取

string中單個(gè)字符存取方式有兩種

• char &operator[](int n); //通過[]方式獲取字符
• char &at(int a); //通過at方式獲取字符

示例：

#include <iostream>
#include <string>

using namespace std;

void test01() {
  string str = "Hello!";
  cout << "str = " << str << endl;
  //char &operator[](int n);      //通過[]方式獲取字符
  for (int i = 0; i < str.size(); ++i) {
    cout << str[i] << " ";
  }
  cout << endl;
  //char &at(int a);                //通過at方式獲取字符
  for (int i = 0; i < str.size(); ++i) {
    cout << str.at(i) << " ";
  }
  cout << endl;

  //修改單個(gè)字符
  str[0] = 'x';
  cout << "str = " << str << endl;
  str.at(1) = 'E';
  cout << "str = " << str << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

總結(jié)：string字符串中單個(gè)字符存取方式有兩種：利用[]或at

3.1.8 string 插入和刪除

函數(shù)原型：

• string &insert(int pos, const char *s); //插入字符串
• string &insert(int pos, const string &str); //插入字符串
• string &insert(int pos, int n, char c); //在指定位置插入n個(gè)字符c
• string &erase(int pos, int n = npos); //刪除從pos開始的n個(gè)字符

示例：

#include <iostream>
#include <string>

using namespace std;

void test01() {
  string str1 = "H, ";
  cout << "str1 = " << str1 << endl;
  //string &insert(int pos, const char *s);       //插入字符串
  str1.insert(1, "eo");
  cout << "str1 = " << str1 << endl;
  //string &insert(int pos, const string &str);   //插入字符串
  string str2 = "world aha!";
  str1.insert(5, str2);
  cout << "str1 = " << str1 << endl;
  //string &insert(int pos, int n, char c);       //在指定位置插入n個(gè)字符c
  str1.insert(2, 2, 'l');
  cout << "str1 = " << str1 << endl;
  //string &erase(int pos, int n = npos);         //刪除從pos開始的n個(gè)字符
  str1.erase(str1.find(" aha"), 4);
  cout << "str1 = " << str1 << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

總結(jié)：插入和刪除的起始下標(biāo)都是從0開始

3.1.9 string 子串

功能描述：

• 從string中獲取想要的子串

函數(shù)原型：

• string substr(int pos = 0, int n = npose) const; //返回由pos開始的n個(gè)字符組成的字符串

示例：

#include <iostream>
#include <string>

using namespace std;

void test01() {
  string str1 = "abcdefg";
  cout << "str1 = " << str1 << endl;
  //string substr(int pos = 0, int n = npose) const;  //返回由`pos`開始的`n`個(gè)字符組成的字符串
  string substr = str1.substr(1, 4);
  cout << "substr = " << substr << endl;
}

//實(shí)用操作
void test02() {
  string email1 = "zhangsan@qq.com";
  string email2 = "lisi@google.com";
  //從郵件地址中獲取用戶名信息
  string usrName1 = email1.substr(0, email1.find('@'));
  cout << usrName1 << endl;
  string usrName2 = email2.substr(0, email2.find('@'));
  cout << usrName2 << endl;
  //從郵件地址中獲取郵箱供應(yīng)商
  string provider1 = email1.substr(email1.find('@') + 1, email1.find('.') - email1.find('@') - 1);
  cout << provider1 << endl;
  string provider2 = email2.substr(email2.find('@') + 1, email2.find('.') - email2.find('@') - 1);
  cout << provider2 << endl;
}

int main() {
  test01();
  test02();

  system("pause");

  return 0;
}

總結(jié)：靈活運(yùn)用求子串功能闯捎，可以在實(shí)際開發(fā)中獲取有效的信息

3.2 vector 容器

3.2.1 vector基本概念

功能：

• vector數(shù)據(jù)結(jié)構(gòu)和數(shù)組非常相似椰弊，也稱為單端數(shù)組

vector與普通數(shù)組區(qū)別：

• 不同之處在于數(shù)組是靜態(tài)空間，而vector可以動(dòng)態(tài)擴(kuò)展

動(dòng)態(tài)擴(kuò)展：

• 并不是在原空間之后續(xù)接新空間瓤鼻，而是找更大的內(nèi)存空間秉版，然后將原數(shù)據(jù)拷貝新空間，釋放原空間

vector容器

vector容器的迭代器支持隨機(jī)訪問

3.2.2 vector構(gòu)造函數(shù)

函數(shù)原型：

• vector<T> v; //采用模板實(shí)現(xiàn)茬祷，默認(rèn)構(gòu)造函數(shù)
• vector(v.begin(), v.end()); //將 v.begin v.end() 中區(qū)間中的元素拷貝給本身
• vector(n, elem); //將n個(gè)elem拷貝給本身
• vector(const vector &vec); //拷貝構(gòu)造函數(shù)

示例：

#include <iostream>
#include <vector>

using namespace std;

void printVector(vector<int> &v) {
  for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  //vector<T> v;                  //采用模板實(shí)現(xiàn)清焕，默認(rèn)構(gòu)造函數(shù)
  vector<int> v1;
  for (int i = 0; i < 10; ++i) {
    v1.push_back(i);
  }
  printVector(v1);
  //vector(v.begin(), v.end());   //將[v.begin, v.end())中區(qū)間中的元素拷貝給本身
  vector<int> v2(v1.begin(), v1.end());
  printVector(v2);
  //vector(n, elem);                //將n個(gè)elem拷貝給本身
  vector<int> v3(10, 100);
  printVector(v3);
  //vector(const vector &vec);    //拷貝構(gòu)造函數(shù)
  vector<int> v4(v3);
  printVector(v4);
}

int main() {
  test01();

  system("pause");

  return 0;
}

總結(jié)：vector的多種構(gòu)造方式?jīng)]有可比性，靈活使用即可

3.2.3 vector 賦值操作

函數(shù)原型：

• vector &operator=(const vector &vec); //重載operator=（等號(hào)操作符）
• assign(beg, end); //將 beg end 區(qū)間中的數(shù)據(jù)拷貝賦值給本身
• assign(n, elem); //將n個(gè)elem拷貝賦值給本身

示例：

#include <iostream>
#include <vector>

using namespace std;

void printVector(vector<int> &v) {
  for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  vector<int> v1;
  for (int i = 0; i < 10; ++i) {
    v1.push_back(i + 1);
  }
  printVector(v1);

  //vector &operator=(const vector &vec);     //重載operator=（等號(hào)操作符）
  vector<int> v2 = v1;
  printVector(v2);
  //assign(beg, end);                         //將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身
  vector<int> v3;
  v3.assign(v1.begin(), v1.end());
  printVector(v3);
  //assign(n, elem);                          //將n個(gè)elem拷貝賦值給本身
  vector<int> v4;
  v4.assign(10, 100);
  printVector(v4);
}

int main() {
  test01();

  system("pause");

  return 0;
}

總結(jié)：vector賦值方式比較簡(jiǎn)單祭犯，使用operator=或者assign()都可以

3.2.4 vector 容量和大小

函數(shù)原型：

• empty(); //判斷容器是否為空
• capacity(); //容器的容量
• size(); //返回容器中元素的個(gè)數(shù)
• resize(int num); //重新指定容器的長(zhǎng)度為num秸妥，若容器變長(zhǎng)，則以默認(rèn)值填充新位置沃粗。
  //如果容器變短粥惧，則未尾超出容器長(zhǎng)度的元素被刪除。
• resize(int num, elem); //重新指定容器的長(zhǎng)度為num最盅，若容器變長(zhǎng)突雪，則以elem值填充新位置起惕。
  //如果容器變短，則未尾超出容器長(zhǎng)度的元素被刪除咏删。

示例：

#include <iostream>
#include <vector>

using namespace std;

void printVector(vector<int> &v) {
  for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  vector<int> v1;
  for (int i = 0; i < 10; ++i) {
    v1.push_back(i + 1);
  }
  printVector(v1);

  //empty();                  //判斷容器是否為空
  v1.empty() ? cout << "v1 is empty!" << endl : cout << "v1 is not empty!" << endl;
  vector<int> v2;
  v2.empty() ? cout << "v2 is empty!" << endl : cout << "v2 is not empty!" << endl;
  //capacity();               //容器的容量
  cout << "v1.capacity() = " << v1.capacity() << endl;
  cout << "v2.capacity() = " << v2.capacity() << endl;
  //size();                   //返回容器中元素的個(gè)數(shù)
  cout << "v1.size() = " << v1.size() << endl;
  //resize(int num);          //重新指定容器的長(zhǎng)度為num惹想，若容器變長(zhǎng)，則以默認(rèn)值填充新位置督函。
  v1.resize(15);
  printVector(v1);
  //resize(int num, elem);    //重新指定容器的長(zhǎng)度為num嘀粱，若容器變長(zhǎng)，則以elem值填充新位置侨核。
  v1.resize(20, 100);
  printVector(v1);
  //如果容器變短草穆，則未尾超出容器長(zhǎng)度的元素被刪除。
  v1.resize(5);
  printVector(v1);
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.2.5 vector 插入和刪除

函數(shù)原型：

• push_back(ele); //尾部插入元素ele
• pop_back(); //刪除最后一個(gè)元素
• insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele
• insert(const_iterator pos, int count, ele); //迭代器指向位置pos插入count個(gè)元素ele
• erase(const_iterator pos); //刪除迭代器指向的元素
• erase(const_iterator start, const_iterator end); //刪除迭代器從start到end之間的元素
• clear(); //刪除容器中所有元素

示例：

#include <iostream>
#include <vector>

using namespace std;

void printVector(vector<int> &v) {
  if (v.begin() == v.end()) {
    cout << "The vector is empty!" << endl;
    return;
  }
  for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  vector<int> v1;
  for (int i = 0; i < 10; ++i) {
    //push_back(ele);                               //尾部插入元素ele
    v1.push_back(i + 1);
  }
  printVector(v1);
  //pop_back();                                       //刪除最后一個(gè)元素
  v1.pop_back();
  printVector(v1);
  //insert(const_iterator pos, ele);                  //迭代器指向位置`pos`插入元素`ele`
  v1.insert(v1.begin(), 0);
  printVector(v1);
  //insert(const_iterator pos, int count, ele);       //迭代器指向位置`pos`插入`count`個(gè)元素`ele`
  v1.insert(v1.begin(), 2, -1);
  printVector(v1);
  //erase(const_iterator pos);                        //刪除迭代器指向的元素
  v1.erase(v1.begin());
  printVector(v1);
  //erase(const_iterator start, const_iterator end);  //刪除迭代器從`start`到`end`之間的元素
  v1.erase(v1.begin(), v1.begin() + 2);
  printVector(v1);
  //clear();                                          //刪除容器中所有元素
  v1.clear();
  printVector(v1);
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.2.6 vector 數(shù)據(jù)存取

函數(shù)原型：

• at(int idx) //返回索引idx所指向的數(shù)據(jù)
• operator[] //返回索引idx所指向的數(shù)據(jù)
• front() //返回容器中第一個(gè)數(shù)據(jù)元素
• back() //返回容器中最后一個(gè)數(shù)據(jù)元素

示例：

#include <iostream>
#include <vector>

using namespace std;

void test01() {
  vector<int> v;
  for (int i = 0; i < 10; ++i) {
    v.push_back(i + 1);
  }
  //at(int idx)   //返回索引idx所指向的數(shù)據(jù)
  for (int i = 0; i < v.size(); ++i) {
    cout << v.at(i) << (i == v.size() - 1 ? "\n" : ", ");
  }
  //operator[]    //返回索引idx所指向的數(shù)據(jù)
  for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << (i == v.size() - 1 ? "\n" : ", ");
  }
  //front()       //返回容器中第一個(gè)數(shù)據(jù)元素
  cout << "The first element is " << v.front() << endl;
  //back()        //返回容器中最后一個(gè)數(shù)據(jù)元素
  cout << "The last element is " << v.back() << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.2.7 vector 互換容器

函數(shù)原型：

• swap(vec) //將vec與本身的元素互換

示例：

#include <iostream>
#include <vector>

using namespace std;

void printVector(vector<int> &v) {
  if (v.begin() == v.end()) {
    cout << "The vector is empty!" << endl;
    return;
  }
  for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  cout << "交換前：" << endl;
  vector<int> v1;
  cout << "\tv1 = ";
  for (int i = 0; i < 10; ++i) {
    v1.push_back(i + 1);
  }
  printVector(v1);
  vector<int> v2;
  cout << "\tv2 = ";
  for (int i = 10; i > 0; --i) {
    v2.push_back(i);
  }
  printVector(v2);

  cout << "交換后：" << endl;
  v1.swap(v2);
  cout << "\tv1 = ";
  printVector(v1);
  cout << "\tv2 = ";
  printVector(v2);
}

//實(shí)際運(yùn)用
//巧用swap可以收縮內(nèi)存空間
void test02() {
  vector<int> v;
  for (int i = 0; i < 100000; ++i) {
    v.push_back(i);
  }
  cout << "The capacity of v is " << v.capacity() << endl;
  cout << "The size of v is " << v.size() << endl;
  cout << "-=-=-=-=-=RESIZE-=-=-=-=-=" << endl;
  v.resize(3);
  cout << "The capacity of v is " << v.capacity() << endl;
  cout << "The size of v is " << v.size() << endl;
  //巧用swap收縮內(nèi)存
  vector<int>(v).swap(v);
  //vector<int>(v)    //匿名對(duì)象
  //(v).swap(v)       //交換對(duì)象
  //原來的v變?yōu)槟涿麑?duì)象搓译，執(zhí)行結(jié)束后立即銷毀
  cout << "-=-=vector<int>(v).swap(v);-=-=" << endl;
  cout << "The capacity of v is " << v.capacity() << endl;
  cout << "The size of v is " << v.size() << endl;
}

int main() {
  test01();
  cout << "\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n" << endl;
  test02();

  system("pause");

  return 0;
}

3.2.8 vector 預(yù)留空間

功能描述：

• 減少vector在動(dòng)態(tài)擴(kuò)展容量時(shí)的擴(kuò)展次數(shù)

函數(shù)原型：

• reserve(int len); //容器預(yù)留len個(gè)元素長(zhǎng)度悲柱，預(yù)留位置不初始化，元素不可訪問

#include <iostream>
#include <vector>

using namespace std;

//reserve(int len);     //容器預(yù)留len個(gè)元素長(zhǎng)度些己，預(yù)留位置不初始化豌鸡，元素不可訪問

void test01() {
  vector<int> v1;
  int num = 0;        //統(tǒng)計(jì)開辟次數(shù)
  int *p = nullptr;
  for (int i = 0; i < 100000; ++i) {
    v1.push_back(i + 1);
    //統(tǒng)計(jì)開辟新空間次數(shù)
    if (p != &v1[0]) {
      p = &v1[0];
      num++;
    }
  }
  cout << "v1.size() = " << v1.size() << endl;
  cout << "v1.capacity = " << v1.capacity() << endl;
  cout << "num = " << num << endl;

  vector<int> v2;
  //reserve(int len);     //容器預(yù)留len個(gè)元素長(zhǎng)度，預(yù)留位置不初始化段标，元素不可訪問
  v2.reserve(100000);
  num = 0;        //統(tǒng)計(jì)開辟次數(shù)
  p = nullptr;
  for (int i = 0; i < 100000; ++i) {
    v2.push_back(i + 1);
    //統(tǒng)計(jì)開辟新空間次數(shù)
    if (p != &v1[0]) {
      p = &v1[0];
      num++;
    }
  }
  cout << "v2.size() = " << v2.size() << endl;
  cout << "v2.capacity = " << v2.capacity() << endl;
  cout << "num = " << num << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

總結(jié)：如果數(shù)據(jù)量較大涯冠，可以一開始用reserve預(yù)留空間

3.3 deque 容器

3.3.1 deque 容器基本概念

功能：

• 雙端數(shù)組，可以對(duì)頭端進(jìn)行插入刪除操作

deque與vector區(qū)別

• vector對(duì)于頭部的插入效率低逼庞，數(shù)據(jù)量越大蛇更，效率越低
• deque相對(duì)而言，對(duì)頭部的插入刪除速度會(huì)比vector快
• vector訪問元素時(shí)的速度會(huì)比deque快赛糟，這和兩者內(nèi)部實(shí)現(xiàn)有關(guān)

deque容器

deque內(nèi)部工作原理：

• deque內(nèi)部有個(gè)中控器派任，維護(hù)每段緩沖區(qū)中的內(nèi)容，緩沖區(qū)中存放真實(shí)數(shù)據(jù)

• 中控器維護(hù)的是每個(gè)緩沖區(qū)的地址璧南，使得使用deque時(shí)像一片連續(xù)的內(nèi)存空間

deque容器 - 中控器

• deque容器的迭代器也是支持隨機(jī)訪問的

3.3.2 deque 構(gòu)造函數(shù)

函數(shù)原型：

• deque<T> deqT; //默認(rèn)構(gòu)造形式
• deque(beg, end); //構(gòu)造函數(shù)將 beg end 區(qū)間中的元素拷貝給本身
• deque(n, elem); //構(gòu)造函數(shù)將n個(gè)elem拷貝給本身
• deque(const deque &deq); //拷貝構(gòu)造函數(shù)

示例：

#include <iostream>
#include <deque>

using namespace std;

void printDeque(const deque<int> &d) {
  for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++) {
    //*it = 100;    //只讀迭代器中的容器不可修改
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  //deque<T> deqT;            //默認(rèn)構(gòu)造形式
  deque<int> d1;
  for (int i = 0; i < 10; ++i) {
    d1.push_back(i + 1);
  }
  printDeque(d1);
  //deque(beg, end);          //構(gòu)造函數(shù)將[beg, end)區(qū)間中的元素拷貝給本身
  deque<int> d2(d1.begin(), d1.end());
  printDeque(d2);
  //deque(n, elem);           //構(gòu)造函數(shù)將n個(gè)elem拷貝給本身
  deque<int> d3(10, 1);
  printDeque(d3);
  //deque(const deque &deq);  //拷貝構(gòu)造函數(shù)
  deque<int> d4(d1);
  printDeque(d4);
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.3.3 duque 賦值操作

函數(shù)原型：

• deque &operator=(const deque &deq); //operator=重載
• assign(beg, end); //將 beg end 區(qū)間中的數(shù)據(jù)拷貝賦值給本身
• assign(n, elem); //將n個(gè)elem拷貝賦值給本身

示例：

#include <iostream>
#include <deque>

using namespace std;

void printDeque(const deque<int> &d) {
  for (auto it = d.begin(); it < d.end(); it++) {
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  deque<int> d1;
  for (int i = 0; i < 10; ++i) {
    d1.push_back(i + 1);
  }
  printDeque(d1);
  //deque &operator=(const deque &deq);   //operator=重載
  deque<int> d2 = d1;
  printDeque(d2);
  //assign(beg, end);                     //將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身
  deque<int> d3(d1.begin(), d1.end());
  printDeque(d3);
  //assign(n, elem);                      //將n個(gè)elem拷貝賦值給本身
  deque<int> d4(10, 1);
  printDeque(d4);
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.3.4 deque 容器大小操作

函數(shù)原型：

• deque.empty(); //判斷容器是否為空
• deque.size(); //返回容器中元素個(gè)數(shù)
• deque.resize(num); //重新指定容器的長(zhǎng)度為num掌逛，若容器變長(zhǎng)，則以默認(rèn)值填充新位置司倚。
  //如果容器變短豆混，則未尾超出容器長(zhǎng)度的元素被刪除。
• deque.resize(num, elem); //重新指定容器的長(zhǎng)度為num动知，若容器變長(zhǎng)皿伺，則以elem值填充新位置。
  //如果容器變短盒粮，則未尾超出容器長(zhǎng)度的元素被刪除心傀。

示例：

#include <iostream>
#include <deque>

using namespace std;

void printDeque(const deque<int> &d) {
  for (auto it = d.begin(); it < d.end(); it++) {
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  deque<int> d1;
  for (int i = 0; i < 10; ++i) {
    d1.push_back(i + 1);
  }
  printDeque(d1);

  //deque.empty();            //判斷容器是否為空
  d1.empty() ? cout << "d1 is empty!" << endl : cout << "d1 is not empty!" << endl;
  deque<int> d2;
  d2.empty() ? cout << "d2 is empty!" << endl : cout << "d2 is not empty!" << endl;
  //deque.size();             //返回容器中元s素的個(gè)數(shù)
  cout << "d1.size() = " << d1.size() << endl;
  //resize(int num);          //重新指定容器的長(zhǎng)度為num，若容器變長(zhǎng)拆讯，則以默認(rèn)值填充新位置脂男。
  d1.resize(15);
  printDeque(d1);
  //resize(int num, elem);    //重新指定容器的長(zhǎng)度為num，若容器變長(zhǎng)种呐，則以elem值填充新位置宰翅。
  d1.resize(20, 100);
  printDeque(d1);
  //如果容器變短，則未尾超出容器長(zhǎng)度的元素被刪除爽室。
  d1.resize(5);
  printDeque(d1);
}

int main() {
  test01();

  system("pause");

  return 0;
}

總結(jié)：deque沒有容量的概念

3.3.5 deque 插入和刪除

兩端插入操作：

• deque.push_back(elem); //在容器尾部添加一個(gè)數(shù)據(jù)
• deque.push_front(elem); //在容器頭部添加一個(gè)數(shù)據(jù)
• deque.pop_back(elem); //刪除容器最后一個(gè)數(shù)據(jù)
• deque.pop_front(elem); //刪除容器第一個(gè)數(shù)據(jù)

指定位置操作：

• deque.insert(pos, elem); //在pos位置插入一個(gè)elem元素的拷貝汁讼，返回新數(shù)據(jù)的位置
• deque.insert(os, n, elem); //在pos位置插入n個(gè)elem元素，無返回值
• deque.insert(pos, begin, end); //在pos位置插入 beg end 區(qū)間的數(shù)據(jù)阔墩，無返回值
• deque.clear(); //清空容器的所有數(shù)據(jù)
• deque.erase(beg, end); //刪除 beg end 區(qū)間的數(shù)據(jù)嘿架，返回下一個(gè)數(shù)據(jù)的位置
• deque.erase(pos); //刪除pos位置的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置

示例：

#include <iostream>
#include <deque>

using namespace std;

void printDeque(const deque<int> &d) {
  for (auto it = d.begin(); it < d.end(); it++) {
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

//兩端插入操作
void test01() {
  deque<int> d;
  for (int i = 0; i < 5; ++i) {
    //deque.push_back(elem);    //在容器尾部添加一個(gè)數(shù)據(jù)
    d.push_back(i + 1);
  }
  printDeque(d);
  for (int i = 0; i > -6; --i) {
    //deque.push_front(elem);   //在容器頭部添加一個(gè)數(shù)據(jù)
    d.push_front(i);
  }
  printDeque(d);
  //deque.pop_back(elem);         //刪除容器最后一個(gè)數(shù)據(jù)
  d.pop_back();
  printDeque(d);
  //deque.pop_front(elem);        //刪除容器第一個(gè)數(shù)據(jù)
  d.pop_front();
  printDeque(d);
}

//指定位置操作
void test02() {
  deque<int> d1;
  for (int i = 0; i < 5; ++i) {
    d1.push_back((i + 1) * 2);
  }
  printDeque(d1);
  //deque.insert(pos, elem);          //在pos位置插入一個(gè)elem元素的拷貝啸箫，返回新數(shù)據(jù)的位置
  d1.insert(d1.begin(), 1);
  printDeque(d1);
  //deque.insert(os, n, elem);        //在pos位置插入n個(gè)elem元素耸彪，無返回值
  d1.insert(d1.end(), 5, 100);
  printDeque(d1);
  //deque.insert(pos, begin, end);    //在pos位置插入[beg, end)區(qū)間的數(shù)據(jù)，無返回值
  deque<int> d2;
  d2.push_back(1);
  d2.push_back(2);
  d2.push_back(3);
  d1.insert(d1.end() - 3, d2.begin(), d2.end());
  printDeque(d1);
  //deque.erase(beg, end);            //刪除[beg, end)區(qū)間的數(shù)據(jù)忘苛，返回下一個(gè)數(shù)據(jù)的位置
  d1.erase(d1.begin() + 10, d1.end());
  printDeque(d1);
  //deque.erase(pos);                 //刪除pos位置的數(shù)據(jù)蝉娜，返回下一個(gè)數(shù)據(jù)的位置
  //deque<int>::iterator it2 = d1.end() - 5;
  auto it2 = d1.end() - 5;
  d1.erase(it2);
  printDeque(d1);
  //deque.clear();                    //清空容器的所有數(shù)據(jù)
  d1.clear();
  if (d1.empty()) { cout << "d1 is empty!" << endl; } else {printDeque(d1);}
}

int main() {
  test01();
  test02();

  system("pause");

  return 0;
}

總結(jié)：插入和刪除提供的位置是迭代器

3.3.6 deque 數(shù)據(jù)存取

功能描述：

• 對(duì)deque中數(shù)據(jù)的存取操作

函數(shù)原型：

• at(int idx); //返回索引idx所指的數(shù)據(jù)
• operator []; //返回索引idx所指的數(shù)據(jù)
• front(); //返回容器中第一個(gè)數(shù)據(jù)元素
• back(); //返回容器中最后一個(gè)數(shù)據(jù)元素

示例：

#include <iostream>
#include <deque>

using namespace std;

void printDeque(const deque<int> &d) {
  for (auto it = d.begin(); it < d.end(); it++) {
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  deque<int> d;
  for (int i = 0; i < 10; ++i) {
    d.push_back(i + 1);
  }
  printDeque(d);
  //at(int idx);  //返回索引idx所指的數(shù)據(jù)
  cout << "d.at(2) = " << d.at(2) << endl;
  //operator [];  //返回索引idx所指的數(shù)據(jù)
  cout << "d[5] = " << d[5] << endl;
  //front();      //返回容器中第一個(gè)數(shù)據(jù)元素
  cout << "d.front() = " << d.front() << endl;
  //back();       //返回容器中最后一個(gè)數(shù)據(jù)元素
  cout << "d.back() = " << d.back() << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.3.7 duque 排序

功能描述：

• 利用算法實(shí)現(xiàn)對(duì)deque容器進(jìn)行排序

算法：

• sort(iterator beg, iterator end); //對(duì)beg和end區(qū)間內(nèi)元素進(jìn)行排序

示例：

#include <iostream>
#include <deque>
#include <algorithm>
#include <vector>

using namespace std;

void printDeque(const deque<int> &d) {
  for (auto it = d.begin(); it < d.end(); it++) {
    cout << *it << (it == d.end() - 1 ? "\n" : ", ");
  }
}

void test01() {
  deque<int> d;

  cout << "排序前：";
  d.push_back(20);
  d.push_back(406);
  d.push_back(152);
  d.push_back(-123);
  d.push_front(73);
  d.push_front(-42);
  d.push_front(321);
  d.push_front(81);
  printDeque(d);
  //排序前：81, 321, -42, 73, 20, 406, 152, -123

  cout << "排序后：";
  sort(d.begin(), d.end());
  printDeque(d);
  //排序后：-123, -42, 20, 73, 81, 152, 321, 406

  //對(duì)于支持隨機(jī)訪問的迭代器的容器，都可以利用sort()算法直接對(duì)其進(jìn)行排序
  cout << "-=-=-=-=-=-=-=-=- vector -=-=-=-=-=-=-=-=-" << endl;
  cout << "排序前：";
  vector<int> v;
  v.push_back(2);
  v.push_back(40);
  v.push_back(-14);
  v.push_back(192);
  v.push_back(37);
  v.push_back(32);
  v.push_back(-185);
  v.push_back(18);
  for (auto it = v.begin(); it < v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
  sort(v.begin(), v.end());
  cout << "排序胡：";
  for (auto it = v.begin(); it < v.end(); it++) {
    cout << *it << (it == v.end() - 1 ? "\n" : ", ");
  }
}

int main() {
  test01();

  system("pause");

  return 0;
}

總結(jié)：sort()默認(rèn)升序排列

3.4 案例 - 評(píng)委打分

3.4.1 案例描述

有5名選手：選手哦ABCDE扎唾，10個(gè)評(píng)委分別對(duì)每名選手打分召川，去除最高分，去除評(píng)委中最低分胸遇，取平均分

3.4.2 實(shí)現(xiàn)步驟

1. 創(chuàng)建5名選手荧呐，放到vector中
2. 遍歷vector容器，取出來每一個(gè)選手纸镊，執(zhí)行for循環(huán)倍阐，可以把10個(gè)評(píng)委的打分存到deque容器中
3. sort算法對(duì)deque容器中分?jǐn)?shù)排序，去除最高和最低分
4. deque容器遍歷一遍薄腻，累加總分
5. 獲取平均分

示例：

#include <algorithm>
#include <deque>
#include <iostream>
#include <random>
#include <string>
#include <ctime>
#include <utility>
#include <vector>

using namespace std;

//c++11 random library
uniform_int_distribution<unsigned> u(60, 100);
default_random_engine e(time(nullptr));

class Competitor {
  public:
  Competitor(string name, int score) {
    this->m_Name = std::move(name);
    this->m_Score = score;
  }

  string m_Name; //姓名
  int m_Score;   //平均分
};

void createCompetitor(vector<Competitor> &v) {
  string nameSeed[] = {"劉一", "陳二", "張三", "李四", "王五", "趙六"};
  for (int i = 0; i < nameSeed->size(); ++i) {
    string name = "選手：";
    name += nameSeed[I];
    int score = 0;
    Competitor p(name, score);
    v.push_back(p);
  }
}

void setScore(vector<Competitor> &v) {
  for (auto &vectorItem : v) {
    //將評(píng)委的分?jǐn)?shù)放入deque
    deque<int> d;
    for (int i = 0; i < 10; ++i) {
      //隨機(jī)數(shù)
      //int score = rand() % 41 + 60;
      int score = u(e);
      d.push_back(score);
    }
    /*
        //輸出
        cout << vectorItem.m_Name << " 的得分是：";
        for (auto &dequeItem :d) {
            cout << dequeItem << (dequeItem == *(d.end() - 1) ? "" : ", ");
        }
        cout << endl;
         */
    //排序
    sort(d.begin(), d.end());
    //去除最高和最低分
    d.pop_front();
    d.pop_back();
    //取平均分
    int sum = 0;
    for (auto &dequeItem : d) { sum += dequeItem; }
    int avg = sum / d.size();
    //將平均分賦值給選手
    vectorItem.m_Score = avg;
  }
}

void showScore(vector<Competitor> &v) {
  for (auto &item:v) {
    cout << item.m_Name << " 的平均分是 " << item.m_Score << " 分" << endl;
  }
}

int main() {
  //創(chuàng)建選手
  vector<Competitor> v;   //存放選手容器
  createCompetitor(v);
  //給選手打分
  setScore(v);
  //顯示分?jǐn)?shù)
  showScore(v);

  system("pause");

  return 0;
}

3.5 stack 容器

3.5.1 stack 基本概念

概念：stack是一種先進(jìn)后出 (First In Last Out, FILO) 的數(shù)據(jù)結(jié)構(gòu)收捣，它只有一個(gè)出口

stack容器

棧中只有頂端的元素才可以被外界使用，因此棧不允許有遍歷行為

• 棧中進(jìn)入數(shù)據(jù)稱為 - 入棧 push
• 棧中彈出數(shù)據(jù)稱為 - 出棧 pop

3.5.2 stack 常用接口

構(gòu)造函數(shù)：

• stack<T> stk; //stack采用模板實(shí)現(xiàn)庵楷，stack對(duì)象的默認(rèn)構(gòu)造形式
• stack(const stack &stk); //拷貝構(gòu)造函數(shù)

賦值操作：

• stack &operator=(const stack &stk); //重載等號(hào)操作符

數(shù)據(jù)存劝瞻：

• push(elem); //向棧頂添加元素
• pop() //從棧頂移除第一個(gè)元素
• top() //返回棧頂元素

大小操作：

• empty() //判斷堆棧是否為空
• size() //返回棧的大小

示例：

#include <iostream>
#include <stack>

using namespace std;

void test01() {
  stack<int> stk;
  for (int i = 0; i < 5; ++i) {
    stk.push(i + 1);
  }
  cout << "棧的大小：" << stk.size() << endl;

  while (!stk.empty()) {
    cout << "棧頂元素為：" << stk.top() << endl;
    //出棧
    stk.pop();
  }

  cout << "棧的大芯∨Α：" << stk.size() << endl;
}

int main() {
  test01();

  system("pause");

  return 0;
}

3.6 queue 容器

3.6.1 queue 容器概念

概念：queue容器是一種先進(jìn)先出 (First In First Out, FIFO) 的數(shù)據(jù)結(jié)構(gòu)咐蚯，它有兩個(gè)出口

queue容器

隊(duì)列容器允許從一端新增元素，從另一端移除元素

隊(duì)列中只有隊(duì)頭和隊(duì)尾才可以被外界使用弄贿，因此隊(duì)列不允許有遍歷行為

• 隊(duì)列中進(jìn)入數(shù)據(jù)稱為 - 入隊(duì) push
• 隊(duì)列中彈出數(shù)據(jù)稱為 - 出隊(duì) pop

3.6.2 queue 常用接口

構(gòu)造函數(shù)：

• queue<T> que; //queue采用模板實(shí)現(xiàn)春锋，queue對(duì)象的默認(rèn)構(gòu)造形式
• queue(const queue &que); //拷貝構(gòu)造函數(shù)

賦值操作：

• queue &operator=(const queue &que); //重載等號(hào)操作符

數(shù)據(jù)存取：

• push(elem); //向隊(duì)尾添加元素
• pop()差凹； //從隊(duì)頭移除第一個(gè)元素
• back()期奔； //返回最后一個(gè)元素
• front()‘ //返回第一個(gè)元素

大小操作：

• empty()侧馅； //判斷堆隊(duì)列是否為空
• size()； //返回隊(duì)列的大小

示例：

#include <iostream>
#include <queue>

using namespace std;

class Person {
  public:
  Person(string name = "name", short age = 0) {
    this->m_Name = move(name);
    this->m_Age = age;
  }

  string m_Name;
  short m_Age;
};

void test01() {
  Person p1("唐僧", 30);
  Person p2("孫悟空", 1000);
  Person p3("豬悟能", 999);
  Person p4("沙悟凈", 998);
  //創(chuàng)建隊(duì)列
  queue<Person> q;
  //入隊(duì)
  q.push(p1);
  q.push(p2);
  q.push(p3);
  q.push(p4);
  cout << "隊(duì)列大小為：" << q.size() << endl;
  //如果隊(duì)列不為空呐萌，查看隊(duì)頭馁痴，查看隊(duì)尾，出隊(duì)
  while (!q.empty()) {
    //查看隊(duì)頭元素
    cout << "隊(duì)頭元素：" << q.front().m_Name << ", " << q.front().m_Age << ", ";
    //查看隊(duì)尾元素
    cout << "隊(duì)尾元素：" << q.back().m_Name << ", " << q.back().m_Age << endl;
    //出隊(duì)
    q.pop();
  }
  cout << "隊(duì)列大小為：" << q.size() << endl;
}

int main() {
  test01();
  system("pause");

  return 0;
}

3.7 list 容器

3.7.1 list 基本概念

功能：將數(shù)據(jù)進(jìn)行鏈?zhǔn)絻?chǔ)存

鏈表 (list)：是一種物理儲(chǔ)存單元上非連續(xù)的存儲(chǔ)結(jié)構(gòu)肺孤，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接實(shí)現(xiàn)的

鏈表的組成：鏈表由一系列結(jié)點(diǎn)組成

結(jié)點(diǎn)的組成：一個(gè)是儲(chǔ)存數(shù)據(jù)單元的數(shù)據(jù)域罗晕，另一個(gè)數(shù)儲(chǔ)存下一個(gè)結(jié)點(diǎn)地址的指針域

STL中的鏈表是一個(gè)雙向循環(huán)鏈表

list容器

由于鏈表的存儲(chǔ)方式并不是連續(xù)的內(nèi)存空間，因此鏈表list中的迭代器只支持前移和后移赠堵，屬于雙向迭代器

list的優(yōu)點(diǎn)：

• 采用動(dòng)態(tài)存儲(chǔ)分配小渊，不會(huì)造成內(nèi)存浪費(fèi)和溢出
• 鏈表執(zhí)行插入和刪除操作十分方便，修改指針即可茫叭，不需要移動(dòng)大量元素

list的缺點(diǎn)：

• 鏈表靈活酬屉，但是空間（指針域）和時(shí)間（遍歷）額外耗費(fèi)較大

list有一個(gè)重要的性質(zhì)，插入操作和刪除操作都不會(huì)造成原有list迭代器的失效杂靶，這在vector是不成立的

總結(jié)：STL中list和vector是兩個(gè)最常被使用的容器梆惯，各有優(yōu)缺點(diǎn)

3.7.2 list 構(gòu)造函數(shù)

函數(shù)原型：

• list<T> lst; //list采用模板類實(shí)現(xiàn)，對(duì)象的默認(rèn)構(gòu)造函數(shù)
• list(beg, end); //構(gòu)造函數(shù)將 beg end 區(qū)間中的元素拷貝給本身
• list(n, elem); //構(gòu)造函數(shù)將n個(gè)elem拷貝給本身
• list(const list &lst); //拷貝構(gòu)造函數(shù)

示例：

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int> &l) {
  for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

void test01() {
  //list<T> lst;              //list采用模板類實(shí)現(xiàn)吗垮，對(duì)象的默認(rèn)構(gòu)造函數(shù)
  list<int> l1;
  for (int i = 0; i < 10; ++i) {
    l1.push_back(i + 1);
  }
  printList(l1);
  // list(beg, end);           //構(gòu)造函數(shù)將[beg, end)區(qū)間中的元素拷貝給本身
  list<int>l2(l1.begin(), l1.end());
  printList(l2);
  // list(n, elem);            //構(gòu)造函數(shù)將n個(gè)elem拷貝給本身
  list<int>l3(10, 1);
  printList(l3);
  // list(const list &lst);    //拷貝構(gòu)造函數(shù)
  list<int>l4(l1);
  printList(l4);
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.7.3 list 賦值和交換

功能描述：

• 給list容器進(jìn)行賦值垛吗，以及交換list容器

函數(shù)原型：

• assign(beg, end); //將 beg end 區(qū)間中的數(shù)據(jù)拷貝賦值給本身
• Assign(n, elem); //將n個(gè)elem拷貝賦值給本身
• list &operator=(const list &lst); //重載等號(hào)操作符
• swap(lst); //將lst與本身的元素互換

示例：

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int> &l) {
  for (auto it = l.cbegin(); it != l.cend(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

void test01() {
  list<int> l1;
  for (int i = 0; i < 10; ++i) {
    l1.push_back(i + 1);
  }
  printList(l1);
  //assign(beg, end);                     //將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身
  list<int> l2;
  l2.assign(l1.begin(), l1.end());
  printList(l2);
  //Assign(n, elem);                      //將n個(gè)elem拷貝賦值給本身
  list<int> l3;
  l3.assign(10, 1);
  printList(l3);
  //list &operator=(const list &lst);     //重載等號(hào)操作符
  list<int> l4 = l1;
  printList(l4);
}

void test02() {
  list<int> l1;
  for (int i = 0; i < 5; ++i) {
    l1.push_back(i + 1);
  }
  list<int> l2;
  l2.assign(10, 5);
  cout << "-=-=-=-=-=-交換前-=-=-=-=-=-" << endl;
  cout << "l1: ";
  printList(l1);
  cout << "l2: ";
  printList(l2);

  //swap(lst);                            //將lst與本身的元素互換
  l1.swap(l2);
  cout << "-=-=-=-=-=-交換后-=-=-=-=-=-" << endl;
  cout << "l1: ";
  printList(l1);
  cout << "l2: ";
  printList(l2);
}

int main() {
  test01();
  test02();
  system("pause");
  return 0;
}

3.7.4 list 大小操作

函數(shù)原型：

• size(); //返回容器中元素的個(gè)數(shù)
• empty(); //判斷容器是否為空
• resize(num); //重新指定容器的長(zhǎng)度為num，若容器變長(zhǎng)烁登，則以默認(rèn)值填充新位置
  //如果容器變短怯屉，則末尾超出容器長(zhǎng)度的元素被刪除
• resize(num, elem); //重新指定容器的長(zhǎng)度為num，若容器變長(zhǎng)饵沧，則以elem值填充新位置
  //如果容器變短锨络，則末尾超出容器長(zhǎng)度的元素被刪除

示例：

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int> &l) {
  for (auto it : l) { cout << it << " "; }
  cout << endl;
}

void test01() {
  list<int> l1;
  for (int i = 0; i < 10; ++i) {
    l1.push_back(i + 1);
  }
  cout << "l1: ";
  printList(l1);
  list<int> l2;
  cout << "l2: ";
  printList(l2);
  //size();               //返回容器中元素的個(gè)數(shù)
  cout << "l1.size() = " << l1.size() << endl;
  cout << "l2.size() = " << l2.size() << endl;
  //empty();              //判斷容器是否為空
  cout << "l1.empty() = " << l1.empty() << " (" << (l1.empty() ? "True" : "False") << ")" << endl;
  cout << "l2.empty() = " << l2.empty() << " (" << (l2.empty() ? "True" : "False") << ")" << endl;
  //resize(num);          //重新指定容器的長(zhǎng)度為num，若容器變長(zhǎng)狼牺，則以默認(rèn)值填充新位置
  //                      //如果容器變短羡儿，則末尾超出容器長(zhǎng)度的元素被刪除
  cout << "l1.resize(5);\t";
  l1.resize(5);
  cout << "l1: ";
  printList(l1);
  cout << "l2.resize(5);\t";
  l2.resize(5);
  cout << "l2: ";
  printList(l2);
  //resize(num, elem);    //重新指定容器的長(zhǎng)度為num，若容器變長(zhǎng)是钥，則以elem值填充新位置
  //                      //如果容器變短掠归，則末尾超出容器長(zhǎng)度的元素被刪除
  cout << "l1.resize(10, 5);\t";
  l1.resize(10, 5);
  cout << "l1: ";
  printList(l1);
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.7.5 list 插入和刪除

函數(shù)原型：

• push_back(elem); //在容器尾部加入一個(gè)元素
• pop_back(); //刪除容器中最后一個(gè)元素
• push_front(elem); //在容器開頭插入一個(gè)元素
• pop_front(elem); //從容器開頭移除第一個(gè)元素
• insert(pos, elem); //在pos位置插入elem元素的拷貝，返回新數(shù)據(jù)的位置
• insert(pos, n, elem); //在pos位置插入n個(gè)elem數(shù)據(jù)悄泥，無返回值
• insert(pos, beg, end); //在pos位置插入 beg end 區(qū)間的數(shù)據(jù)虏冻，無返回值
• clear(); //移除容器的所有數(shù)據(jù)
• erase(beg, end); //刪除 beg end 區(qū)間的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置
• erase(pos); //刪除pos位置的數(shù)據(jù)弹囚，返回下一個(gè)數(shù)據(jù)的位置
• remove(elem); //刪除容器中所有與elem值匹配的元素

示例：

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int> &l) {
  for (auto it : l) { cout << it << " "; }
  cout << endl;
}

void test01() {
  list<int> l;
  for (int i = 0; i < 11; ++i) {
    //push_back(elem);        //在容器尾部加入一個(gè)元素
    l.push_back(i + 1);
  }
  printList(l);
  //pop_back();               //刪除容器中最后一個(gè)元素
  l.pop_back();
  printList(l);
  for (int i = 0; i > -11; --i) {
    //push_front(elem);       //在容器開頭插入一個(gè)元素
    l.push_front(i - 1);
  }
  printList(l);
  //pop_front(elem);          //從容器開頭移除第一個(gè)元素
  l.pop_front();
  printList(l);
  //insert(pos, elem);        //在pos位置插入elem元素的拷貝厨相，返回新數(shù)據(jù)的位置
  auto it = l.begin();
  for (int i = 0; i < 10; ++i) { ++it; }
  l.insert(it, 0);
  printList(l);
  //insert(pos, n, elem);     //在pos位置插入n個(gè)elem數(shù)據(jù)，無返回值
  l.insert(l.begin(), 3, -1000);
  printList(l);
  //insert(pos, beg, end);    //在pos位置插入[beg, end)區(qū)間的數(shù)據(jù)，無返回值
  list<int> l2;
  for (int i = 0; i < 3; ++i) { l2.push_back(1000); }
  l.insert(l.end(), l2.begin(), l2.end());
  printList(l);
  //clear();                  //移除容器的所有數(shù)據(jù)
  cout << "l2:";
  printList(l2);
  l2.clear();
  cout << "l2:";
  printList(l2);
  //erase(beg, end);          //刪除[beg, end)區(qū)間的數(shù)據(jù)蛮穿，返回下一個(gè)數(shù)據(jù)的位置
  it = l.begin();
  for (int i = 0; i < 3; ++i) { ++it; }
  l.erase(l.begin(), it);
  printList(l);
  //erase(pos);               //刪除pos位置的數(shù)據(jù)庶骄，返回下一個(gè)數(shù)據(jù)的位置
  it = l.begin();
  for (int i = 0; i < 10; ++i) { ++it; }
  l.erase(it);
  printList(l);
  //remove(elem);             //刪除容器中所有與elem值匹配的元素
  l.remove(1000);
  printList(l);
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.7.6 list 數(shù)據(jù)存取

函數(shù)原型：

• front(); //返回第一個(gè)元素
• back(); //返回最后一個(gè)元素

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int> &l) {
  for (auto it : l) { cout << it << " "; }
  cout << endl;
}

void test01() {
  list<int> l;
  for (int i = 0; i < 10; ++i) {
    l.push_back(i + 1);
  }
  printList(l);
  //front();    //返回第一個(gè)元素
  cout << "l.front() = " << l.front() << endl;
  //back();     //返回最后一個(gè)元素
  cout << "l.back() = "<< l.back() << endl;
  
  //list迭代器是不支持隨機(jī)訪問的
  list<int>::iterator it = l.begin();
  it++;
  it--; //支持雙向
  //it = it + 1;
}

int main() {
  test01();
  system("pause");
  return 0;
}

總結(jié)：list容器不可以通過[]或者at()方式訪問數(shù)據(jù)

3.7.7 list 反轉(zhuǎn)和排序

函數(shù)原型：

• reverse(); //反轉(zhuǎn)鏈表
• sort() //鏈表排序

#include <iostream>
#include <list>
#include <random>
#include <ctime>

using namespace std;

default_random_engine e(time(nullptr));
uniform_int_distribution<int> d(-500, 500);

void printList(const list<int> &l) {
  for (auto it : l) { cout << it << " "; }
  cout << endl;
}

list<int> &randList() {
  auto *l = new list<int>;
  auto it = l->begin();
  int randNum;
  for (int i = 0; i < 20; ++i) {
    randNum = d(e);
    l->push_back(randNum);
    ++it;
  }
  return *l;
}

bool myCompare(int v1, int v2) {
  //降序：v1>v2
  return v1 > v2;
}

void test01() {
  list<int> l = randList();
  cout << "反轉(zhuǎn)前：";
  printList(l);
  //reverse();    //反轉(zhuǎn)鏈表
  l.reverse();
  cout << "反轉(zhuǎn)后：";
  printList(l);
  //sort()        //鏈表排序
  cout << "排序后：";
  //不支持隨機(jī)訪問迭代器的容器，內(nèi)部會(huì)提供一些對(duì)應(yīng)算法
  l.sort();           //默認(rèn)升序排列
  printList(l);
  l.sort(myCompare);  //降序排列
  cout << "降序排：";
  printList(l);
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.7.8 排序案例

案例描述：將Person自定義數(shù)據(jù)類型進(jìn)行排序践磅，Person中屬性有姓名瓢姻、年齡、身高

排序規(guī)則：按照年齡進(jìn)行升序音诈，如果年齡相同按照身高進(jìn)行降序排序

示例：

#include <iostream>
#include <string>
#include <list>

using namespace std;

class Person {
  public:
  Person(string name, int age, int height) {
    this->m_Name = move(name);
    this->m_Age = age;
    this->m_Height = height;
  }

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

void printList(const list<Person> &l) {
  for (const auto &it:l) {
    cout << it.m_Name << it.m_Age << "歲，" << it.m_Height << "厘米高" << endl;
  }
}

//執(zhí)行排序規(guī)則
bool comparePerson(Person &p1, Person &p2) {
  //年齡升序
  if (p1.m_Age != p2.m_Age)
    return p1.m_Age < p2.m_Age;
  //年齡相同绎狭，身高降序
  else
    return p1.m_Height > p2.m_Height;
}

int main() {
  list<Person> l;
  //準(zhǔn)備數(shù)據(jù)
  Person p1("劉備", 35, 175);
  Person p2("曹操", 45, 180);
  Person p3("孫權(quán)", 40, 170);
  Person p4("趙云", 25, 190);
  Person p5("張飛", 35, 160);
  Person p6("關(guān)羽", 35, 195);
  //插入數(shù)據(jù)
  l.push_back(p1);
  l.push_back(p2);
  l.push_back(p3);
  l.push_back(p4);
  l.push_back(p5);
  l.push_back(p6);
  cout << " -=-=-排序前-=-=-" << endl;
  printList(l);
  //排序
  l.sort(comparePerson);
  cout << endl;
  cout << " -=-=-排序后-=-=-" << endl;
  printList(l);
  
  system("pause");
  return 0;
}

總結(jié)：

• 對(duì)于自定義數(shù)據(jù)類型细溅，必須要指定排序規(guī)則，否則編譯器不知道如何進(jìn)行排序
• 高級(jí)排序只是在排序規(guī)則上再進(jìn)行一次邏輯規(guī)則制定儡嘶，并不復(fù)雜

3.8 set / multiset 容器

3.8.1 set 基本概念

簡(jiǎn)介：

• 所有元素都會(huì)在插入時(shí)自動(dòng)被排序

本質(zhì)：

• set / multiset屬于關(guān)聯(lián)式容器喇聊，底層結(jié)構(gòu)使用二叉樹實(shí)現(xiàn)

set和multiset區(qū)別

• set不允許容器中有重復(fù)的元素
• multiset允許容器中有重復(fù)的元素

3.8.2 set 構(gòu)造和賦值

構(gòu)造：

• set<T> st; //默認(rèn)構(gòu)造函數(shù)
• set(const set &st); //拷貝構(gòu)造函數(shù)

賦值：

• set &operator=(const set &st); //重載等號(hào)操作符

示例：

#include <iostream>
#include <set>

using namespace std;

void printSet(set<int> &s) {
  for (set<int>::iterator it = s.begin(); it != s.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

void test01() {
  //set<T> st;            //默認(rèn)構(gòu)造函數(shù)
  set<int> s1;
  for (int i = 0; i < 10; ++i) {
    //插入數(shù)值，只有insert()方式
    s1.insert(i + 1);
  }
  //遍歷容器
  printSet(s1);
  //所有元素插入的時(shí)候自動(dòng)排序
  //set不允許插入重復(fù)值
  s1.insert(10);
  printSet(s1);

  //set(const set &st);   //拷貝構(gòu)造函數(shù)
  set<int> s2(s1);
  printSet(s2);

  //set &operator=(const set &st);    //重載等號(hào)操作符
  set<int> s3;
  s3 = s2;
  printSet(s2);
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.8.3 set 大小和交換

函數(shù)原型：

• size(); //返回容器中元素的數(shù)目
• empty() //判斷容器是否為空
• swap(st) //交換兩個(gè)集合容器

示例：

#include <iostream>
#include <set>

using namespace std;

ostream &operator<<(ostream &cout, set<int> &s) {
    for (auto &it:s) {
        cout << it << " ";
    }
    return cout;
}

void test01() {
    set<int> s1;
    for (int i = 0; i < 10; ++i) {
        s1.insert(i + 1);
    }
    cout << "s1: " << s1 << endl;
    set<int> s2;
    cout << "s2: " << s2 << endl;
    //size();   //返回容器中元素的數(shù)目
    cout << "s1.size() = " << s1.size() << endl;
    cout << "s2.size() = " << s2.size() << endl;
    //empty()   //判斷容器是否為空
    cout << "s1.empty() = " << s1.empty() << (s1.empty() ? " (True)" : " (False)") << endl;
    cout << "s2.empty() = " << s2.empty() << (s2.empty() ? " (True)" : " (False)") << endl;
    //swap(st)  //交換兩個(gè)集合容器
    s1.swap(s2);
    cout << "-=-=-=-=-交換后-=-=-=-=-" << endl;
    cout << "s1: " << s1 << endl;
    cout << "s2: " << s2 << endl;
}

int main() {
    test01();
    system("pause");
    return 0;
}

3.8.4 set 插入和刪除

函數(shù)原型：

• insert(elem); //在容器中插入元素
• clear(); //清除所有元素
• erase(pos); //刪除pos迭代器所指的元素蹦狂，返回下一個(gè)元素的迭代器
• erase(beg, end); //刪除區(qū)間 beg end 的所有元素誓篱，返回下一個(gè)元素的迭代器
• erase(elem); //刪除容器中值為elem的元素

示例：

#include <iostream>
#include <set>

using namespace std;

ostream &operator<<(ostream &cout, set<int> &s) {
  for (auto &it:s) {
    cout << it << " ";
  }
  return cout;
}

void test01() {
  set<int> s;
  for (int i = 0; i < 10; ++i) {
    //insert(elem);        //在容器中插入元素
    s.insert(i + 1);
  }
  cout << "s: " << s << endl;
  //erase(pos);       //刪除pos迭代器所指的元素，返回下一個(gè)元素的迭代器
  s.erase(s.begin());
  cout << "s: " << s << endl;
  //erase(pos, end);  //刪除區(qū)間[beg, end)的所有元素凯楔，返回下一個(gè)元素的迭代器
  s.erase(++(++s.begin()), --(--s.end()));
  cout << "s: " << s << endl;
  //erase(elem);      //刪除容器中值為elem的元素
  s.erase(10);
  cout << "s: " << s << endl;
  //clear();          //清除所有元素
  s.clear();
  cout << "s: " << s << endl;
}

int main() {
  test01();
  system("pause");
  return 0;
} 

3.8.5 set 查找和統(tǒng)計(jì)

功能描述：

• 對(duì)set容器進(jìn)行查找數(shù)據(jù)以及統(tǒng)計(jì)數(shù)據(jù)

函數(shù)原型：

• find(key); //查找key是否存在窜骄，若存在，返回該鍵的元素迭代器摆屯；若不存在邻遏，返回set.end()
• count(key); //統(tǒng)計(jì)key的元素個(gè)數(shù)

示例：

#include <iostream>
#include <set>
#include <random>
#include <ctime>

using namespace std;

default_random_engine e(time(nullptr));
uniform_int_distribution<int> d(0, 10);

ostream &operator<<(ostream &cout, set<int> &s) {
  for (auto &it:s) { cout << it << " "; }
  return cout;
}

ostream &operator<<(ostream &cout, multiset<int> &s) {
  for (auto &it:s) { cout << it << " "; }
  return cout;
}

void test01() {
  set<int> s;
  for (int i = 0; i < 10; ++i) { s.insert(i + 1); }
  cout << s << endl;

  set<int>::iterator pos = s.find(10);

  if (pos != s.end()) {
    cout << "找到元素 " << *pos << "!" << endl;
  } else {
    cout << "未找到元素." << endl;
  }
}

void test02() {
  set<int> set;
  for (int i = 0; i < 100; ++i) { set.insert(d(e)); }
  multiset<int> multiset;
  for (int i = 0; i < 100; ++i) { multiset.insert(d(e)); }

  cout << "set: " << set << endl;
  cout << "set中有" << set.count(5) << "個(gè)5." << endl;   //對(duì)于set而言，統(tǒng)計(jì)結(jié)果要么是0虐骑，要么是1
  cout << "multiset: " << multiset << endl;
  cout << "multiset中有" << multiset.count(5) << "個(gè)5." << endl;
}

int main() {
  test01();
  test02();
  system("pause");
  return 0;
}

3.8.6 set 和 multiset 區(qū)別

區(qū)別：

• set不可以插入重復(fù)數(shù)值准验，而multiset可以
• set插入數(shù)據(jù)的同時(shí)會(huì)返回插入結(jié)果，表示插入是否成功
• multiset不會(huì)檢測(cè)數(shù)據(jù)廷没，因此可以插入重復(fù)數(shù)據(jù)

示例：

#include <iostream>
#include <set>

using namespace std;

ostream &operator<<(ostream &cout, multiset<int> &s) {
  for (auto &it:s) { cout << it << " "; }
  return cout;
}

void test01() {
  set<int> s;
  pair<set<int>::iterator, bool> ret = s.insert(10);
  cout << "第一次插入" << (ret.second ? "成功糊饱！" : "\u001b[31m失敗\u001b[0m！") << endl;
  ret = s.insert(10);
  cout << "第二次插入" << (ret.second ? "成功颠黎！" : "\u001b[31m失敗\u001b[0m另锋！") << endl;

  multiset<int> ms;
  ms.insert(10);
  ms.insert(10);
  cout << "ms: " << ms << endl;
}

int main() {
  test01();
  system("pause");
  return 0;
}

總結(jié)：

• 如果不允許插入重復(fù)數(shù)據(jù)可以使用set
• 如果需要插入重復(fù)數(shù)據(jù)，利用multiset

3.8.7 pair對(duì)組創(chuàng)建

功能描述：

• 成對(duì)出現(xiàn)的數(shù)據(jù)盏缤，利用對(duì)組可以返回兩個(gè)數(shù)據(jù)

兩種創(chuàng)建方式：

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

示例：

#include <iostream>
#include <string>

using namespace std;

template<typename First, typename Second>
ostream &operator<<(ostream &cout, pair<First, Second> &p) {
  cout << p.first << ", " << p.second;
  return cout;
}

void test01() {
  //pair<type, type> p(value1, value2);
  pair<string, int> p1("張三", 18);
  cout << "p1: " << p1 << endl;
  //pair<type, type> p = make_pair(value1, value2);
  pair<string, int> p2 = make_pair("李四", 19);
  cout << "p2: " << p2 << endl;
}

int main() {
  test01();
  system("pause");
  return 0;
}

3.8.8 set 容器排序

主要技術(shù)點(diǎn)：

• 利用仿函數(shù)砰蠢，可以改變排序規(guī)則

示例一：set存放內(nèi)置數(shù)據(jù)類型

#include <iostream>
#include <set>

using namespace std;

//改變排序規(guī)則
class MyCompare {
  public:
  bool operator()(int v1, int v2) { return v1 > v2; }
};

template<typename Type>
ostream &operator<<(ostream &cout, set<Type> &s) {
  for (auto &it : s) { cout << it << " "; }
  return cout;
}

template<typename Type, typename Rule>
ostream &operator<<(ostream &cout, set<Type, Rule> &s) {
  for (auto &it : s) { cout << it << " "; }
  return cout;
}

void test01() {
  set<int> s1;
  for (int i = 0; i < 10; ++i) {
    s1.insert(i + 1);
  }
  cout << s1 << endl;
  //指定排序規(guī)則為從大到小
  set<int, MyCompare> s2;
  for (int i = 0; i < 10; ++i) {
    s2.insert(i + 1);
  }
  cout << s2 << endl;
}

int main() {
  test01();
  system("pause");
  return 0;
}

示例二：set存放自定義數(shù)據(jù)類型

#include <iostream>
#include <set>

using namespace std;

class Person {
  public:
  Person(string name, int age) {
    this->m_Name = name;
    this->m_Age = age;
  }

  string m_Name;
  int m_Age;
};

class ComparePerson {
  public:
  //按照年齡降序排列
  bool operator()(const Person &p1, const Person &p2) { return p1.m_Age > p2.m_Age; }
};

ostream &operator<<(ostream &cout, set<Person, ComparePerson> &s) {
  for (auto &it : s) { cout << "姓名：" << it.m_Name << "，年齡：" << it.m_Age << endl; }
  return cout;
}

void test01() {
  //自定義數(shù)據(jù)類型唉铜，都會(huì)指定排序規(guī)則
  set<Person, ComparePerson> s;
  //準(zhǔn)備數(shù)據(jù)
  Person p1("劉備", 25);
  Person p2("曹操", 45);
  Person p3("孫權(quán)", 40);
  Person p4("趙云", 20);
  Person p5("張飛", 35);
  Person p6("關(guān)羽", 30);
  //插入數(shù)據(jù)
  s.insert(p1);
  s.insert(p2);
  s.insert(p3);
  s.insert(p4);
  s.insert(p5);
  s.insert(p6);
  cout << s;
}

int main() {
  test01();
  system("pause");
  return 0;
}