軟體界一直一種需要可重復利用的東西，C++的泛型編程和面向物件都是為了提高重復率，因此為了建立一種資料結構和演算法的統一標準，于是就有了STL，本節接近一萬五千字的文章將帶你系統走入STL，

目錄

STL的基本概念

STL的基本組件

vector容器

string容器

list容器

stack容器

deque容器

set/multiset容器

queue容器

map/multimap容器

仿函式

謂詞

算術仿函式

關系仿函式

邏輯仿函式

遍歷演算法

查找演算法

算術生成演算法

排序演算法

拷貝和替換演算法

(一）STL的基本概念

1.STL從廣義上可以分為容器，演算法，迭代器

2.容器和演算法之間通過迭代器進行無縫連接

3.STL幾乎所有的代碼都采用了模板型別或者模板函式

（二）STL六大組件：

1.STL的六大組件包括容器 演算法 迭代器 仿函式（多載的小括號也就是行為類似函式） 配置器（修飾容器或者仿函式或者迭代器介面的東西） 空間配置器（負責空間的配置和管理）

2.容器：放資料，運用最廣泛的資料結構實作，

容器分為序列式容器和關聯式容器，

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

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

3.演算法：問題之解法也

質變演算法：運算程序中更改區間中元素的內容，例如拷貝，替換，洗掉等等

非質變演算法：運算程序中不會更改區間中元素的內容，例如查找，遍歷，計數，尋找極值

4.迭代器：容器和演算法之間的粘合劑

提供一種方法，使之能夠依序尋找某個容器所含的各個元素，而又無需暴露容器的內部聯系方式，每個容器都有自己的迭代器，

迭代器使用非常類似于指標，

常用的迭代器型別為雙向迭代器（讀寫操作，并且能夠向前向后操作）和隨機訪問迭代器（讀寫操作，并且可以以任意的方式去訪問任意資料，功能最強）

（三）vector容器

1）vector容器可以理解為陣列，單端陣列，

但是不同之處在于陣列是靜態空間，但是vector是可以動態擴展，動態擴展并不是在原有的空間之后續空間，而是把原有的資料拷貝到新空間里面，釋放原有的空間，

vector容器的迭代器是支持隨機訪問的迭代器

容器：vector
演算法：for_each
迭代器：vector<int>::iterater

void myprint(int val)
{
  cout<<val<<endl;
}

#include<vector>
#include<algorithm>//標準演算法的頭檔案

void test01()
{
  //創建了一個vector容器，認為它是一個陣列
   vector<int>v;

  //向容器中插入資料
  v.push_back(10);
  
  //通過迭代器訪問容器中的資料
   vector<int>::iterator itBegin=v.bagin();//起始迭代器 指向容器中的第一個元素
   vector<int>::iterator itEND=v.end();//結束迭代器 指向容器中的最后一個元素的下一個位置

  //第一種遍歷方式：
   while(itBegin!=itEnd)
   {
     cout<<*itBegin<<endl;
     itBegin++;
   }
 //第二種遍歷：
  for(vector<int>::iterator it=v.begin();it!=v.end;it++)
{
   cout<<*it<<endl;//<>里面是什么資料型別，*it解出來的也是相同的資料型別
}
//第三種遍歷
 for_each(v.begin(),v.end(),myPrint);
}
 

自定義資料型別通過容器訪問內部成員
(*it).m_name;
it->m_name;

2）vector容器中嵌套一個容器（二維陣列）

void test01()
{
  vector<vector<int>>v;

  //創建小容器
  vector<int>v1;
  vector<int>v2;
  vector<int>v3;
  vector<int>v4;
  
 //向小容器添加資料
for(int i=0;i<4;i++)
  {
    v1.push_back(i=1);
    v2.push_back(i=2);
    v3.push_back(i=3);
    v4.push_back(i=4);
 }

 //將小容器插到大容器中去
  v.push_back(v1);
    v.push_back(v2);
        v.push_back(v3);
   v.push_back(v4);
 //通過大容器把所有資料遍歷一遍
   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<<endl;
      }
   }
}

3）vector函式的默認構造

vector<T> v;//利用模板實作類實作，默認建構式
vector<v.bagin(),v.end()>//利用v[bagin(),end()]區間的元素拷貝到自身
vector<n,elem>;//建構式把n個elem拷貝給自身
vector<const vector &vec);//拷貝建構式

4）vector的賦值操作

vector <int>v2;
v2=v1;//

vector <int>v3;
v3.assign(v1.begin(),v1.end());//

vector <int>v4;
v4.assign(10,100);//n個elem方式賦值

5）vector的插入和洗掉

v1.push_back(1);//在尾部插入一個1

v1.pop_back();//尾刪

v1.insert(v1.begin(),100);//在頭部插入100 第一個引數是迭代器

v1.insert(v1.begin(),2,1000);//在頭部插入2個1000

v1.erase(v1.begin());//頭刪的引數也是迭代器

v1.erase(v1.begin,v2.end);//清空 只剩換行

v1.clear;//同清空

6）vector的資料存取

v[i];//利用[]來訪問

v.at(i);//利用at來訪問

v1.front;//獲取第一個位置上的元素

v1.end;//獲取最后一個位置的元素

7）vector容器的互換器

v1.swap(v2);
//用swap可以收縮空間大小
vector<int>(v).swap(v);//匿名物件.容器交換

8）vector預留空間

減少vector在動態擴展容量時的擴展次數

reserve(int len);//容器預留len個元素長度，預留位置不初始化，元素不可訪問

9）vector容器的容量和大小

empty();//判斷容器是否為空
capacity();//容器的容量
size();//回傳容器的元素個數
resize(int num);//重新指定容器的長度為num,如果容器變長，則以默認值填充新位置
                //如果容器變短，則末尾超出容器長度的元素被洗掉
resize(int num,elem);//同上只不過靠elem填充新位置

（四）string容器：本質上是一個類

1.string和char*的區別：char*是一個指標.string是一個類，類內封裝了char* ，管理這個字串，是一個char*型別的容器，

2.特點：封裝了很多成員方法：find copy replace insert

3.string的構造方式：

string s1;//默認構造
const char*str="hello world";
string s2(str);//使用字串初始化
string(const string& str);//使用一個string物件初始另一個string物件
  string s3(s2);
string(int n,char c);//使用n個字符初始化

4.string的賦值操作：

void test()
{
  string str1;
  str1="hello";
  
  string str2;
  str2=str1;

  string str3;
  str3='a';

  string str4;
  str5.assign("hello");

  string str5;
  str5.assign("hello",3);//把字串的前3個字符賦值給str5

 string str6;
 str6.assign(str5);

  string str7;
  str7.assign(10,'*');//用10個*
}

5.字串的拼接：

//void test01()
{
  string str1="我";
  str1+="愛你";//追加
 
  str1+=':';

  str2="t";
  str1+=str2;

  string str3="I";
  str3.append("love");

  str3.append("game abbcd",4);//把前四個拼接進去

  str3.append(arr2);
}

void test()
{
 string str1="我“;
 string str2="yyds sdbz";

 str1.append(str2,0,4);//從str的第零個位置截取4個字符
 str1.append(str2,4,4);//從str的第四個位置開始截取四個字符
}

6）string的查找（指定的字串是否存在）和替換（在指定的位置替換字串）

void test01()
{
  string str1="abcdef";
  int pos=str1.find("de");//輸出3 地址從0開始數 地址不存在的時候會回傳-1
  
  int pos2=str1.rfind;//也輸出3
  
  //rfind從右往左查找，find從左往右查找
}
 

void test02()
{
 //從第n個位置起的幾個字符替換成什么樣的字串
 string str1="abcdefg";
 str1.replace(1,3,"1111");//從第一個位置開始數三個字符替換成1111的字串a1111efg
}

7)string字串的比較：比得是字符的ASCII碼值逐個對比

相等回傳0 第一個大的話回傳1 第一個小的話回傳-1

if(str1.compare(str2)==0)
{
  cout<<"str1==str2"<<endl;
}

8)string的字符存取

string的單個字符的存取方式有倆種

//通過[]來訪問單個字符

for(int i=0;i<str.size();i++)
{
   cout<<str[i]<<endl;
}

//通過at的方式來訪問單個字符

for(int i=0;i<str.size();i++)
{
   cout<<str.at(i)<<endl;
}

//修改單個字符
str[0]='a';
str.at(1)='a';

9)string中的插入和洗掉

//插入
 str.insert(1,'111');//在第一個位置插入三個1
//洗掉
 str .erase(1,3)//從第一個位置刪三個

10）string子串——常用介面（從字串中截取想要的子串）

string str1='abcdef';
string str2=str.substr(1,3);//從第一個的位置截取三個bcd

//實用操作 從郵件地址中獲取用戶名資訊
void test02()
{
  string email="zhangsan@sina.com";
  int pos=email.find("@");
  string userName=email.substr(0,pos);
}

(四）deque容器

deque容器：雙端陣列，可以對頭端進行插入和洗掉操作，

和vector的區別：vector對于頭部的插入洗掉效率低，資料量越大，效率越低

deque相對而言，對頭部的插入洗掉速度比vector快

vector訪問元素的速度比deque快，這和倆者的內部實作有關，

//vector的賦值操作
1)等號賦值
 v2=v1;
2)assign賦值
 v3.assign(d1.begin(),d1.end());
3)
 v4=assign(10,100);

//deque的大小操作
 d1.empty();//空為1非空為0
 d1.size();//容器中的元素個數
 deque容器沒有容量的概念
 d1.resize(15,1);//重新指定大小

//deque的洗掉和插入
 //尾插
   d1.push_back(10);
 //頭插
   d1.push_front(10);
 //尾刪
   d1.pop_back()；
 //尾刪
   d1.pop_front();
 //d1.insert(d1.begin(),1000);
   d1.insert(d1.begin(),2,10000);//在頭部插入倆個一萬
 //按照區間來進行插入
   d1.insert(d1.begin(),d2.begin(),d2.end());//在d1的頭部插入d2
 //洗掉
   d1.erase();
 //按照區間來洗掉
   d1.erase(d1.begin(),d1.end());
 //清空
   d1.clear;

//deque的資料存盤
  []訪問
     d[i]
  at訪問
     d.at(i);
  d.front
  d.end

//deque的排序
演算法：sort(d.begin().d.end());//默認從小到大升序排列

對于支持隨機訪問的迭代器容器，都可以利用sort演算法直接對其進行排序，vector也可以用這個方式進行排序，

（五）stack堆疊容器

一種先進后出的資料結構，通常只有一個出口，堆疊不允許有遍歷行為，會有元素的改動，堆疊可以判斷容器是否為空，堆疊可以回傳它的元素個數（入堆疊的時候記錄個數）

#include<iostream>
#include<stack>
using namespace std;

void test01()
{
  stack<int>s;//默認構造
 //入堆疊
  s.push(10);
  s.push(20);
 //只要堆疊不為空，查看堆疊頂，最后執行出堆疊
 while(!s.empty())
  {
    cout<<"堆疊頂元素"<<s.top<<endl;
   //出堆疊
    s.pop();
 }
 cout<<"堆疊的大小"<<s.size<<endl;
}

queue佇列容器：符合先進先出的資料結構，它有倆個出口，隊尾只能進資料，對頭只能出資料，

進叫做入隊（push)，出叫做出隊(pop)，

1)佇列容器允許從一段新增元素，從另一端移除元素

2）佇列中只有頭和尾才能被外部訪問，因此佇列中不允許有遍歷行為

3）佇列不允許遍歷

#include<iostream>
using namespace std;
#include<queue>

class person
{
public:
 person(string name,int age)
  {
    this->m_name=name;
    this->m_age=age;
   }
   int m_age;
   int m_name;
}

void test()
{
  queue<person> q;
 
  person p1("tt",19);
  q.push(p1);

 //只要佇列不為空，查看隊頭和隊尾，出隊
 while(!q.empty())
  {
   cout<<q.front().m_Name<<q.front().m_Age<<endl;//查看隊頭
   q.pop();//出隊
  }
}

（六）list容器：

將資料進行鏈式存盤

鏈表是一種物理存盤單元上非連續的存盤結構，資料元素的邏輯順序是通過鏈表中的指標實作的，鏈表是由結點組成的，每個結點是由指標域和資料域組成的，

優點：可以對任意的位置進行快速插入或者洗掉元素

缺點：對容器中元素的遍歷速度較慢，占用的空間大于陣列

STL中的鏈表是一種雙重回圈鏈表：每一個結點都記錄著前面和后面的指標域，最后一個結點指向第一個結點，第一個指向最后一個，

鏈表的存盤方式并不是連續的記憶體空間，因此鏈表list中的迭代器只支持前移和后移，屬于雙向迭代器，

//list建構式
list<T>int;
list(begin,end);
list(n,elem);


list<int>l2(l1.begin(),l1.end());//區間構造

list(const list &lst);//拷貝構造
list<int>l3(l2);

//list的賦值和交換
#include<iostream>
#include<list>

void test01()
{
 list<int>L1;
   //插入
 L1.push(10);
 L1.push(20);

 list<int>L2；
   L2=L1;//賦值
   L2.assign(L2.begin(),L2.end());
   L2.assign(10,100);

 //交換
  L1.swap(L2);
};

//list容器中的大小操作
size()
emptu()
resize(n,elem);
resize(n);

//List的插入和洗掉
  //在pos位置插入elem元素
   insert(pos.elem);
  //在pos位置插入n個elem
   insert(pos,n,elem);
  //移除容器中的所有資料
   clear();
  //刪掉（begin,end)區間的資料
  erase(begin,end);
  //洗掉pos位置的資料，回傳下一個資料
  erase(pos);
  //洗掉容器中和elem匹配的元素
  remove（elem);

list資料的存盤
front();//回傳第一個元素
back();//回傳最后一個元素

//驗證迭代器是不支持隨機訪問的 支持雙向的
list<int>::iterator it=li.begin();
it--;
it++;//但是it=it+1 +2……會報錯

//list的反轉和排序
//把容器中的元素反轉，以及對容器中的資料進行排序
  reverse();
  sort();

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

void test()
{
  list<int>l1;
  l1.push_back(10);
  l1.push_back(20);
  l1.reverse();
  sort(l1.begin(),l2.end);//err 所有不支持隨機訪問迭代器的容器，不支持標準演算法
  //不支持隨機訪問迭代器的容器內部會提供一些對應的演算法
  l1.sort();//默認從小到大
}

//從大到小排序
bool myCompare(int v1,int v2)
{
  //降序讓第一個數大于第二個數
   return v1>v2;
}

l1.sort(mycompare);//sort是成員函式

（七）set/multiset容器：

所有元素都會在插入的時候自動被排序

本質：set/multiset屬于關聯式的容器，就是結構是用二叉樹實作的，

set不允許資料中有重復存在，multiset允許資料的重復存在，

//構造：
set<T>s;
set s1(const set& s2);
//插入
s1.insert(10);
//大小
size();
empty();
//交換
swap(st);
//插入
insert(elem);
//洗掉
clear();
//洗掉pop所指的元素，回傳下一個元素的迭代器
erase(pop);
//洗掉begin,end的元素，回傳下一個元素的迭代器
erase(begin,end);
//洗掉容器中為elem的元素
erase(elem);
//查找key是否存在，存在就回傳該鍵元素的迭代器，不存在就回傳set.end()
find(ket);
//統計key元素的個數
count(key);

隊組：成對出現的資料，利用隊組可以回傳倆個資料

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

//pair對組的創建
void test01()
{
  //第一種方式
  pair<string,int>p("Tom",20);
  cout<<p.first<<p.second<<endl;
  //第二種方式
  pair<string,int>p2=make_pair("jerry",18);
}

（八）map/multimap容器：

map中的所有元素都是pair

pair中的第一個元素是key(鍵值），起到索引的作用，第二個元素是實值value

所有元素都會根據鍵值自動排序，

map本質上也是關聯式的容器，底層結構是用二叉樹實作的，

優點：可以根據key快速找到value

缺點：（1）map不允許有重復的key

(2)multimap允許出現重復的key

//構造
map<T1,T2>mp;
map(const map& mp);
//賦值
map& operator=(const map &mp);
//大小
size()
empty()
swap(st);
//插入
insert(item);
//清除
clear();
//洗掉pos迭代器所指的元素，回傳下一個元素的迭代器
erase(pos);
//洗掉區間
erase(begin,end);
//洗掉容器中值為key的元素
erase(key);
//查找
find(key);
//統計
count(key);

map容器中的排序

#include<iostrean>
using namespace std;
#include<map>


class compare
{
public:
  bool operator()(int v1,int v2)
  { 
      return v1>v2;
  }
}

void test01()
{
  map<int,int,compare>m;
  m.insert(make_pair(1,10));
  m.insert(make_pair(2,20));

 for(map<int,int>::iterator it=m.begin;it!=m.end;it++)
  {
    cout<<it->first<<it->second<<endl;
  }

（九）函式物件（仿函式）是一個類，而不是一個函式，

概念：

多載函式呼叫運算子的類，其物件稱為函式物件

函式物件使用多載的（）時候，行為類似函式呼叫，也叫做仿函式，

函式物件在使用的時候，可以像普通函式那樣呼叫，可以有引數和回傳值

int operator()(int v1,int v2)
{
  return v1+v2;
}

myprintf()
{
  this->count=0;
  this->count++;
}
int operator()(int v1,int v2)
{
  return v1+v2;
}

int count;//查看呼叫次數

函式物件可以作為引數傳遞

void doprint(myprint &mp,string test)
{
   mp(test);
}

void test03()
{
   myprint my;
   doprint(my,"hello");
}

（十）謂詞：回傳bool型別的仿函式

如果operator（）接受一個引數，那么叫做一元謂詞

如果operator()接受倆個引數，那么叫做二元謂詞

class over
{
  public:
     bool operator()(int val)
     {
         return val>5;
     }
};


void test01()
{
  vector<int>v1;
  int i=0;
  for(;i<10;i++)
   {
     v.push_back(i);
   }
  //查找容器中是否有大于5的數字 over()匿名函式物件
  vector<int>::iterator it=find_if(v1.begin,vi.end,over());
  if(it==v.end())
   {
     cout<<"未找到”<<endl;
   }
  else
   {
     cout<<*it<<endl;
   }
}

二元謂詞

bool operator()(int val1,int val2)
{
  return val1>val2;
}

（十一）算術仿函式

功能：實作四則運算

plus minus multiplies divides modulus negate//取反
#include<functional>

void test()
{
  negate<int>(n);
  n(50);
}

void test()
{
  plus<int>p
  p(10,20);
}

（十二）關系仿函式

功能：實作關系對比

equal not_equal greater greater_equal less less_equal//
sort(v.begin,v.end,greater<int>());//greater<int><>內建函式物件

（十三） 邏輯仿函式

功能：實作邏輯運算

logical_and與 logical_or或 logic_not非
//把v1容器中的資料搬到v2，并且執行取反操作

vector<bool>v1
vector<bool>v2;
v2.resize(v.size());

transform(v.begin(),v.end(),v2.begin(),logical_not<bool>())

（十四）遍歷演算法

//for_each遍歷

#include<vector>
#include<algorithm>

class print{
 public:
   void operator()(int val)
    {
      cout<<val<<endl;
     }
}


void test01()
{
  vector<int>v;
  for(int i=0;i<10;i++)
   {
      v.push_back(i);
   }
  for_each(v.begin(),v.end(),print());
}

//transform的遍歷
class transform()
{
  public:
    int operator()(int val)
     {
       return val+10000;
     }
};

void test01()
{
  vector<int>v;
  for(int i=0;i<10;i++)
   {
      v.push_back(i);
   }
  vector<int>v1;
  v1.resize(v.size());
 transform(v.begin(),v.end(),v1.begin(),transform());
}

（十五）常用查找演算法：

find：查找指定元素，查到的話回傳指定元素的迭代器，找不到的話回傳最后元素的迭代器end()
 vector<int>::iterator it=find(v.begin(),v.end(),5);
 if(it==v.end)
  cout<<"沒有找到"<<endl;
 else{
   cout<<*it<<endl;
  }

//遇到自定義型別的時候需要多載==
class person{
 public:
   person(string name,int age)
   { 
      this->m_name=name;
      this->m_age=age;
    }
   string m_name;
   int m_age;
//多載==
   bool operator==(const person& p)
   {
       if(this->m_name==p.m_name&&this->m_name==p.m_name)
           return true;
       else return false;
   }
}
 

find_if（起始，最后，仿函式）：按條件查找元素

按照值去查找元素，找到的話就回傳指定位置迭代器，找不到的話回傳結束迭代器，

vector<int>::iterator it=find_if(v.begin(),v.end(),overfive());

adjacent_find(起始，最后）：查找相鄰元素

如果查到相鄰元素了，就回傳相鄰元素的第一個的迭代器

vector<int>::iterator pos=adjacent_find(v.begin(),v.end());

binary_search：查找指定的元素是否存在(必須是一個有序序列）

bool ret=binary_search(v.begin(),v.end(),9);

count:統計元素的個數

int num=count(v.begin(),v.end(),40);

count_if：按照條件來統計元素個數

class over5()
{
  public:
   bool operator()(int val)
    {
       return val>20;
    }
};

int num=count_if(v.begin(),v.end(),over5());

（十六）常用排序演算法：

sort 對容器元素進行排序

sort(v.begin(),v.end(),greater<int>());

random_shuffle 洗牌 在指定范圍內的元素隨機調整次序

void test()
{
  srand((unsigned int)time(NULL));
}

random_shuffle(v.begin()<v.end());

merge：容器元素合并 并且存盤到另一個容器中 倆個容器必須是有序的

//提前給目標容器分配空間
vtarget.resize(v1.size()+v2.size());
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),vtarget.begin());

reverse：反轉指定范圍內的元素

reverse(v.begin(),v.end());

（十七）常用的拷貝和替換演算法：

.copy:容器中指定范圍的元素拷貝到另一個容器中

v2.resize(v1.size());
copy(v1.begin(),v1.end,v2.begin());

replace：將容器中指定范圍內的舊元素修改為新元素

replace(v1.begin(),v1.end(),20,2000);//把20替換成2000

.replace_if:容器內指定范圍滿足條件的元素替換為新元素

class greater30
{
  public:
    bool operator()(int val)
     {
         return val>=30;
     }
};
replace_if(v.begin(),v.end(),greater30,3000);//把大于等于30的替換成3000

swap:互換倆個容器中的元素

swap(v1,v2);

（十八）常用的算術生成演算法#include<numeric>

accumulate:計算容器元素累計總和

int total=accumulate(v1.begin(),v1.end(),val);//val是初始值

fill：向容器中添加元素

fill(v.begin(),v.end(),100);

常用集合演算法

求倆個容器的交集

//目標容器需要提前開辟空間，倆個容器取小的
vtarget.resize(min(v1.size(),v2.size());
vector<int>::iterator it
=set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),vtarget.begin());

求倆個容器的并集：倆個集合必須是有序的序列

vtarget.resize(v1.size()+v2.size());
vector<int>::iterator it
=set_union(v1.begin(),v1.end(),v2.begin(),v2.end(),vtarget.begin());

求倆個容器的差集：從某個容器中看和另一個容器中不同的部分

vtarget.resize(max(v1.size(),v2.size());
vector<int>::iterator it=set_difference(v1.begin(),v1.end(),v2.begin(),v2.end(),vtarget());