STL标准模板库
软件界一直一种需要可重复利用的东西，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>::iteratervoid 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="[email protected]";
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的替换成3000swap:互换俩个容器中的元素
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());
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
二维码