目录
一、STL概述
二、STL基本概念
三、STL六大组件
四、string（类）容器
1.string容器基本概念
2.string容器常用操作
五、vector（类模板）容器
1.vector的概述
2.vector的数据结构
3..vector常用的API操作
六、deque容器
1.deque容器基本概念
2.deque容器实现原理
3.deque常用API
七、stack容器
1.stack容器的基本概念
2.stack常用API
八、queue容器
1.queue容器的基本概念
2.queue常用API
九、list容器
1.list容器的基本概念
2.list常用API
十、set/multiset容器
1.set/multiset容器的基本概念
2.set/multiset常用API
3.对组（pair）
十一、map/multimap容器
1.map/multimap容器的基本概念
2.map/multimap常用API
3.multimap案例
STL（Standard Template Library标准模版库），是惠普实验室开发的一系列软件的统称。
为了建立数据结构和算法的一套标准，降低它们之间的耦合关系，以提升各自的独立性、弹性、交互操作性（相互合作性，interoprrability），诞生了ST
其实就是提高 代码复用性，制造出可重复运用的代码，而不需要自己再去写已经存在的代码。
二、STL基本概念STL从广义上分为：容器（container）、算法（alhorithm）、迭代器（iterator）
【容器和算法之间通过迭代器进行无缝连接，算法 其实是 通过迭代器 操作 容器数据】
容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器
STL的一个重要特性是 将数据和操作分离，数据由 容器类别 加以管理，操作则由 特定算法 完成。
1.容器：存放数据
2.算法：操作数据
算法分为 质变算法 和 非质变算法。
质变算法：运算过程中，会更改区间内的元素内容。例如拷贝、替换、删除等等。
非质变算法：运算过程中，不会更改区间内元素内容。例如查找、计数、遍历、寻找极值等。
3.迭代器：算法 只能借助迭代器 操作容器数据（容器和迭代器一一对应）。
4.仿函数:为算法提供更多策略
eg：排序函数默认是从小到大排序，用仿函数让它可以从大到小排序，提供更多的策略。
5.适配器（配接器）:为算法提供更多参数的接口
eg：函数默认是传1个参数，用适配器让它可以传2个参数，这样的
6.空间配置器:为算法和容器 动态分配、管理空间
最常用的容器是 vector 和 lis t容器。
四、string（类）容器 1.string容器基本概念c字符串是 以空字符结尾的字符数组，不适合大程序开发，所以c++标准库定义了一种string类。
【查找find，拷贝copy，删除delete，替换replace，插入insert】
【string管理char*所分配的内存，每一次string的复制、取值都由string类负责维护，不用担心复制越界和取值越界等 】
2.string容器常用操作（以下都是函数定义。string&是返回值，调用的时候用的是函数名，也就是operator、assign这样的，懂吧）
【不管什么容器，看到assign就是赋值，operator是运算符重载】
【3.[ ]越界不会抛出异常，at方法会】
【5.find返回第一次出现位置，rfind返回最后一次出现位置，没找到返回-1；没传pos默认从头开始找】
#include#include//string.h是c的头文件，string是类的
using namespace std;
#include//input output manipulator:输入输出格式控制
void test1()
{
string str;//1.1
cout<< str<< endl;
string str1("hello");//1.3
cout<< str1<< endl;
string str2(5, 'A');//1.4
cout<< str2<< endl;
string str3=str2;//1.2 拷贝构造
cout<< str3<< endl;
string str4;
str4 = "hello";//2.1
cout<< str4<< endl;
str4.assign("world");//2.4
cout<< str4<< endl;
str4 = "W";//2.3
cout<< str4<< endl;
str4.assign("hello",3);//2.5
cout<< str4<< endl;
string str5 = "hello";
str4.assign(str5, 2, 2);//2.8
cout<< str4<< endl;
}
void test2()
{
//3.1+3.2
string str1 = "hello";
cout<< str1[1]<<" "<0)
cout<< "大于"<< endl;
else if (str1.compare(str2)< 0)
cout<< "小于"<< endl;
//>、=、<重载
if (str1==str2)
cout<< "相等"<< endl;
else if (str1>str2)
cout<< "大于"<< endl;
else if (str1 vector和array的数据安排和操作方式非常相似，两者的唯一差别在于空间运用的灵活性。 array是静态空间，vector随元素的加入，内部会自动扩充空间，以容纳新元素。
v.begin()：获取容器的起始迭代器（指向第0个元素）
v.end() ：获取容器的结束迭代器（指向最后一个元素的下一个位置）
只能尾插尾出
线性连续空间
一旦满载，vector会开辟 现有空间容量两倍大小的空间（未雨绸缪机制），将原内容复制到新空间内
3..vector常用的API操作
#includeusing namespace std;
#includevoid test1()
{
//类的类型是类，类模板的类型是<类型>vectorv1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
v1.push_back(40);
v1.push_back(50);
//遍历该容器
//定义一个迭代器iterator 保存起始迭代器
vector::iterator it = v1.begin();
for (; it != v1.end(); it++)
{
//*it==int
cout<< *it<< " ";
}
cout<< endl;
}
void test2()
{
vectorv1;
//可以事先预留足够空间，省的多次开辟
v1.reserve(1000);//3.6
cout<< "容量："<::iterator it;
int i = 0;
int count = 0;
for (i = 0; i< 1000; i++)
{
v1.push_back(i);
if (it != v1.begin())//如果开辟空间，v1.begin指向新空间，迭代器仍指向旧空间，v1.begin和迭代器不相等。可以通过这个来判断是否开辟了空间。
{
count++;
cout<< "第"<< count<< "次开辟空间容量："<< v1.capacity()<< endl;
it = v1.begin();
}
}
}
void printVectorInt(vector& v)
{
vector::iterator it = v.begin();
for (; it != v.end(); it++)
cout<< *it<< " ";
cout<< endl;
}
void test3()
{
vectorv1(5,100);//1.3
printVectorInt(v1);
vectorv2(v1.begin(), v1.end());//1.2
printVectorInt(v2);
vectorv3;//1.1
//v3=v2; //2.3
//v3.assign(v2.begin(),v2.end()); //2.1
v3.assign(10, 10);
printVectorInt(v3);
v3.swap(v2);//2.4
printVectorInt(v2);
printVectorInt(v3);
vectorv4;
if (v4.empty())//3.2
{
cout<< "空"<< endl;
}
else
cout<< "非空"<< endl;
vectorv5(10,30);
cout<< "容量："<< v5.capacity()<< " 大小："<< v5.size()<< endl;//3.5 3.1
printVectorInt(v5);
//v5.resize(15);//过大 补零 3.3
v5.resize(15, 2);//过大 补二 3.4
v5.resize(5);//过小 删除多余
printVectorInt(v5);
}
void test4()
{
vectorv1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
v1.push_back(40);
v1.push_back(50);//10 20 30 40 50
cout<< "头元素："<< v1.front()<< " 尾元素："<v1;
v1.reserve(1000);
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
v1.push_back(40);
cout<< "容量："<< v1.capacity()<< " 大小："<< v1.size()<< endl;
//resize只能修改大小，不能修改容量
//v1.resize(4);
vector(v1).swap(v1);//vector(v1)为匿名对象，发生拷贝构造，用旧对象v1给新对象赋值（只有size大小的被赋值过去了，而不是capacity大小），
//和v1 swap后，v1指向匿名对象的size大小空间
cout<< "容量："<< v1.capacity()<< " 大小："<< v1.size()<< endl;
}
void test6()
{
vectorv1(5, 10);
vectorv2(5, 100);
vectorv3(5, 1000);
//定义一个vector容器存放v1 V2 V3
vector>v;
v.push_back(v1);
v.push_back(v2);
v.push_back(v3);
//遍历
vector>::iterator it = v.begin();
for (; it != v.end(); it++)
{
//*it==vectorvector::iterator mit = (*it).begin();
for (; mit != (*it).end(); mit++)
{
cout<< *mit<< " ";
}
cout<< endl;
}
}
#include;
void test7()
{
vectorv1;
v1.push_back(20);
v1.push_back(60);
v1.push_back(50);
v1.push_back(30);
v1.push_back(40);
v1.push_back(10);
printVectorInt(v1);
//排序算法
sort(v1.begin(), v1.end());
printVectorInt(v1);
}
#includeclass Person
{
friend bool comparePerson(Person ob1, Person ob2);
friend void printVectorPerson(vector&v);
private:
int num;
string name;
float score;
public:
Person() {}
Person(int num, string name, float score)
{
this->num = num;
this->name = name;
this->score = score;
}
};
void printVectorPerson(vector&v)
{
vector::iterator it = v.begin();
for (; it != v.end(); it++)
{
//*it==Person
cout<< (* it).num<< " "<<(*it).name<<" "<<(*it).score<v1;
v1.push_back(Person(100,"lucy",77.7f));
v1.push_back(Person(103, "bob", 77.7f));
v1.push_back(Person(101, "tom", 77.7f));
v1.push_back(Person(104, "德玛", 77.7f));
v1.push_back(Person(105, "小法", 77.7f));
printVectorPerson(v1);
//对自定义类型的vector类型排序，需要修改排序规则
sort(v1.begin(),v1.end(),comparePerson);
printVectorPerson(v1);
}
int main(int argc,char *argv[])
{
test8();
return 0;
} double ended queue，双端队列
vector与deque容器的大差异:
（1）deque允许在 头尾两端 分别做元素的插入和删除操作,且 所用时间 仅 常数项时间。
【vector也可以头部插入，但效率太低】
（2）没有容量的概念。它是动态的，以 分段定量连续空间 组合而成，随时可以增加一段新的空间并连接起来，不存在容量限制。
【也就是说，
像vector那样 “空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间” 的事情在deque这不存在。
因此deque不需要空间保留（reserve）功能，虽然deque容器也提供了Random Access Iterator，但它的迭代器并不是普通的指针，其复杂度和vector不是一个量级。
因此，除非有必要，尽量使用vector而不是deque。
对deque进行排序操作，为了提高效率。可以将deque完整复制到一个vector中，对vector容器进行排序，再复制回deque。】
array无法扩张
vector尾端假扩张：申请更大空间-->原数据复制新空间-->释放原空间
deque双端真扩张
deque采取一块map作为主控（注意不是STL的map容器，是一小段连续的内存空间），其中每一个元素（结点）都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间主体。
Deque由一段段定量连续空间构成。当在deque前端或尾端增加新空间时，便串接一段连续定量的空间。
deque避开了重新配置空间、复制、释放的轮回，代价就是复杂的迭代器架构和数据结构设计。
#includeusing namespace std;
#includevoid printDequeInt(deque& d)
{
deque::iterator it = d.begin();
for (; it != d.end(); it++)
{
cout<< *it<< " ";
}
cout<< endl;
}
void test1()
{
dequed1;
d1.push_back(1);//4.1
d1.push_back(2);
d1.push_back(3);
d1.push_front(4);//4.2
d1.push_front(5);
d1.push_front(6);
printDequeInt(d1);
cout<< "大小："<< d1.size()<< endl;
d1.pop_front();//4.4
printDequeInt(d1);
d1.pop_back();//4.3
printDequeInt(d1);
d1.insert(d1.begin() + 1, 3, 100);//6.2
printDequeInt(d1);
}
//8
#include#include
class Person
{
public:
string name;
float score;
public:
Person() {}
Person(string name, float score)
{
this->name = name;
this->score = score;
}
};
void createPerson(vector& v)
{
string tmpName = "ABCDE";
int i = 0;
for (i = 0; i< 5; i++)
{
string name = "选手";
name += tmpName[i];
v.push_back(Person(name, 0.0f));
}
}
void showPerson(vector&v)
{
vector::iterator it = v.begin();
for (; it != v.end(); it++)
{
//*it==Person
cout<< (*it).name<< " "<< (*it).score<< endl;
//以下写法也可以，但是是把迭代器看成了指针,容易出错,其他迭代器上可能就不能用了。
//cout<< it->name<< " "<< it->score<< endl;
}
}
void playGame(vector&v)
{
//每人逐个比赛
vector::iterator it = v.begin();
for (; it != v.end(); it++)
{
//定义一个deque容器存放10个评委的分数
dequed;
int i = 0;
for (i = 0; i< 10; i++)
{
d.push_back((float)(rand() % 41 + 60));//rand() % 41:生成0-41间的一个随机数。
}
//对deque排序
sort(d.begin(), d.end());
//去掉最低最高分
d.pop_back();
d.pop_front();
//求平均分
(*it).score = (float)accumulate(d.begin(), d.end(),0)/d.size();
}
}
#includevoid test2()
{
vectorv;
//srand设置随机数种子
srand(time(NULL));
//创建五名选手
createPerson(v);
//比赛
playGame(v);
//显示选手成绩
showPerson(v);
}
int main(int argc, char* argv[])
{
test2();
return 0;
} stack是一种 先进后出 的数据结构，stack容器只能 新增、删除、取得 栈顶元素。
stack不允许 遍历，没有迭代器。【只有一个出口，除了最顶端外，没有其他方法可以存取stack的其他元素】
queue是一种 先进先出 的数据结构，允许元素从队尾新增入队，从队头移除出队。
list容器是一个双向链表。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
插入和删除元素是常数时间，无需像静态链表（数组）那样移动大量元素。
采用动态存储分配。灵活，但消耗了空间和时间。
十、set/multiset容器 1.set/multiset容器的基本概念list容器的迭代器是双向迭代器，
- 不支持 +2 这种（随机访问迭代器支持，像vector的），支持++（因为++运算符可以重载）；
- 不支持 STL提供的算法（STL提供的算法（像sort）只支持随机访问迭代器）
【可以写(对象)h1.sort();】
特征：set的所有元素会根据 键值 自动排序。
因为set插入元素就自动排序好了，所以没有push_back/push_front这种。
修改排序规则：
- 应该在定义类对象时修改，set
【先定义类对象，再插入元素。因为插入时就自动排序了，所以应该在插入之前修改排序规则，也就是在定义类对象时修改】
- 因为在尖括号内，排序规则须是一个类，同时也是一个函数，所以我们用 仿函数 来写规则。
【仿函数：重载函数调用运算符（）的类】
- set存放自定义数据必须修改排序。
【同vector实操最后面出现的。自定义类型不指定排序规则的话，sort不知道你是依据哪个成员变量来排序】
将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公用属性 first 和 second 。
模板：template
void test()
{
//方式一：
pairp1(10086,"移动");
pairp2(10010,"联通");
pairp3(10000,"电信");
//方式二：（推荐）
pairp4=make_pair(9527,"星爷");
cout< 
multimap和map唯一区别在于，multimap键值可重复。
map和multimap都是以 红黑树 为底层实现机制。
2.map/multimap常用API
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
