STL算法的精髓在于 算法的 返回值！！！
String:
string是STL的字符串类型，通常用来表示字符串；C语言中一般用char*
char*字符指针;string是类封装了char*,管理这个字符串，是一个char*型的容器；
string不用考虑内存释放和越界，string管理char*所分配的内存。
string提供了一系列字符串操作函数（find,copy,erase,replace,insert）
初始化 ：
string s1 = "abcd"; //重载operator=
string s2("abcd") //有参构造函数
string s3 = s2; //初始化调用的是拷贝构造函数，跟赋值调用operator=()不同
string s1(,'a'); //s1的内容：aaa;将字符复制n份
遍历：
通过数组的方式：
for(int i = ; i < s1.length(); i++)
{
cout << s1[i] << " ";
}
通过迭代器：
for(string::iterator k = s1.begin(); k = s1.end(); k++)
{
cout << *k << " ";
}
通过at()函数：
与数组的[]方法相比，at()可以抛出异常，提示下标越界；而[]不抛出异常直接中断程序。
字符指针和string的转换：
string->char* //生成一个const char*指针，c_str()指向以空字符终止的数组；data()返回的数组不以空字符终止。
string s1 = "aaaaa";
printf("s1 : %s \n",s1.c_str()); s1的指针
char*->string
char buf[]; // char buf[128] = {0}; //c风格字符串
s1.copy(buf,,);//从位置0开始，拷贝3个字符，到buf内；注意自己拷贝\0,不然后面的值都无效。
连接字符串：
string s1 = "aaa";
string s2 = "bbb";
s1 = s1+s2; s1.append(s4); //s1为aaabbb
字符串查找和替换：
string s1 = "jgaaa jjdsj aaa sljf aaa sjfj aaa dfj99";
int index = s1.find("aaa",); //从下标为0开始找aaa，找到后返回下标2，找不到返回-1； 返回当前元素下标
//统计aaa的个数：
int offIndex = s1.find("aaa",);
while(offIndex != string::npos) //npos即-1
{
cout++;
offIndex += ;
offIndex = s1.find("aaa",offIndex);
}
大小写替换：
int offIndex = s1.find("aaa",);
while(offIndex != string::npos) //npos即-1
{
s1.replace(offIndex,,"AAA"); //从offIndex开始，删除3份字符，替换为AAA
offIndex += ;
offIndex = s1.find("aaa",offIndex);
}
字符串的删除和插入：
string s1 = "qbb";
s1.insert(,"aaa"); //qaaabb
s1.insert(,,'c'); //qcccaaabb
s1.insert(s1.length(),"zzz"); //qcccaaabbzzz
string::iterator it = find(s1.begin(),s1.end(),'q'); // 迭代器相关的算法 find 返回指向当前元素的迭代器位置
while(it != s1.end())
{
s1.erase(it); //bb 此时的it已经不存在，erase()会返回指向下一个元素是迭代器位置 it1 = s1.erase(it); //*it == c;
}
s1.erase(s1.begin(),s1.end()); //区间删除：删除整个字符串
字符串相关算法：大小写转换
transform(s1.begin(),s1.end(),s1.begin,toupper); //s1从开始到结尾将小写转大写，并输出到begin的位置（第三个参数）
transform(s1.begin(),s1.end(),s1.begin,tolower);// s1从开始到结尾将小写转大写，并输出到begin的位置（第三个参数）
STL容器简介：
vector:动态数组(尾部添加删除元素)
vector<int>v1;
push_back(); //数组的尾部插入
pop_back(); //删除最后一个元素
v1.front(); //取第一个元素 （其实现返回了一个引用，可以当左值）
v1.back(); //取最后一个元素 （可以当左值）
初始化：
push_back();
vector<int>v2 = v1;
vector<int>v3(v1.begin(),v1.begin()+);
vector<int>v4(,); //
遍历：
vector<int>v1(); //通过数组方式；通过等号操作符需要提前分配内存push_back()在尾部添加元素，新增元素在11号位处
迭代器：（插入，输出，）
begin()指向头元素；end()指向最后一个元素的后面的一个位置
正向迭代器：
for(vector<int>::iterator k = v1.begin(); k = v1.end(); k++)
逆向迭代器： //逆序输出
for(vector<int>::reverse_iterator k = v1.rbegin(); k = v1.rend(); k++)
const迭代器(只读)有2种：（不可当左值）
vector<int>::const_iterator
vector<int>::const_reverse_iterator
《effective STL》建议使用iterator 代替其余三种迭代器；
删除：
vector<int>v1();
v1.erase(); //删除全部
v1.erase(v1.begin(),v1.begin()+); //区间删除：删除2个元素；顺序容器可以调用随机存储器
v1.erase(v1.begin()+); //删除第3个元素
删除某类元素：
for(vector<int>::iterator it = v1.begin(); it = v1.end();)
{
if(*it == )
{
it = v1.erase(it); //删除迭代器位置处的元素，同时指向已删除元素的迭代器也失效了；自增后返回当前位置 也就是说返回当前删除元素的下一个元素的迭代器，如果不用it去保存该位置，原来it++就报错
}
else
{
it++;
}
}
插入：
vector.insert(pos,elem); //pos位置插入一个elem元素的拷贝，返回新元素的位置
vector.insert(pos,n,elem); //无返回值
vector.insert(pos,beg,end); //pos,beg,end均为迭代器的相对位置
eg: vec1.insert(vec1.begin()+,vec2.begin(),vec2.end());
重点：vector中保存对组pair< , >的插入和遍历：
#include <iostream>
#include <vector>
#include <algorithm> using namespace std; bool lessCompare(const pair<string,int>& obj1, const pair<string,int>& obj2)
{
return obj1.second < obj2.second;
}
bool greatCompare(const pair<string,int>& obj1, const pair<string,int>& obj2)
{
return obj1.second > obj2.second;
}
int main()
{ int N, Mode;
cout << "please input N and Mode" <<endl;
while(cin>>N>>Mode)
{
cout << "please input name and age" << endl;
string name;
int age;
vector<pair<string,int>>vec1; //这个地方一旦初始化N了，新插入元素从N+1位置插入
for(int i = ; i < N && cin>>name>>age; ++i)
{
vec1.push_back(make_pair(name,age)); //其他的方法都不成功
}
if(Mode == )
{
stable_sort(vec1.begin(),vec1.end(),lessCompare);
}
if(Mode == )
{
stable_sort(vec1.begin(),vec1.end(),greatCompare);
}
cout << "data after sort: " << endl;
vector<pair<string,int>>::iterator it = vec1.begin();
for( ; it != vec1.end(); ++it)
{
cout << it->first << " " << it->second << endl; //vector放单一变量可以用*it取值，pair应该用这种方法取值
}
/*
for(int i = 0; i < vec1.size(); ++i)
{
cout << vec1[i].first << " " << vec1[i].second << endl; //这个也是可以用的
}*/
} cout << "Hello World!" << endl;
return ;
}
deque：双端数组（头尾插入删除）
插入：
push_front() ,push_back() //注意：插入都是向外扩散的，所以push_front()插入元素显示与插入顺序相反
删除：
pop_front() ;pop_back();
利用迭代器查找元素下标：
deque<int>::iterator it = find(d1.begin(),d1.end(),); //find是算法，要加头文件#include "algorithm"
if(it != d1.end())
{
cout << "元素12的下标是：" << distance(d1.begin(),it) << endl;
}
stack:(先进后出)
push();// 压入一个元素
top();// 获取栈顶元素先进后出
pop();// 弹出栈顶元素
empty();
size();
//容器的值语义。容器是将元素复制了一份到栈，如果是对象的话，其成员有指针就会导致浅拷贝的问题。
queue:(先进先出)
push() front() pop() empty()
list:(双向链表容器)
可高效地进行插入删除元素；
不可以随机存取元素，所以不支持at(pos)函数和[]操作符，迭代器不支持it+5;
注：可以当数组用，此时可以用at()和[]，顺序操作，支持it++和it--等顺序操作
push_back(elem);
push_front(elem);
pop_back();
pop_front();
front();
back();
重要：链表结点index序号从0号位置开始
在3号位置插入，即在原来3号元素的前面插入； // insert(it2,100);
list.clear(); //删除所有数据
list.erase(beg, end); //删除[beg, end)区间的数据，返回下一个数据位置，左闭右开的删除
重要：erase(it1, it2); //it1++;it1++;it2 = it1; 不支持list.begin()+2 //insert(it2,100);
list.erase(pos); //删除pos位置数据，返回下一个数据位置
list.remove(elem); //删除容器中所有与elem值匹配的元素
priority_queue(二叉堆，一种完全二叉树)
#include "queue"
empty();size();top();pop();push(item);
priority_queue<int> p1; //默认情况下是 最大值优先级队列
priority_queue<int, vector<int>, less<int>> p2; //最大值；提前定义好预定义函数 谓词
priority_queue<int, vector<int>, greater<int>> p3; //最小值优先级队列
set/multiset #include "set"
//set是一个集合容器，元素唯一，已排序；默认从小到大
//按照排序规则插入，所以不能指定插入位置；
//不可直接存取元素（不可以使用at(pos)和[]）
//不可以直接修改set/multiset容器中元素值，因为该类容器是自动排序的。可以删除原有元素，再插入新元素。
//采用红黑树变体的数据结构实现。红黑树属于平衡二叉树，插入和删除比vector快；
//multiset支持重复元素；
insert(); empty(); erase(pos);
set<int>::iterator set1; <=> set<int, less<int>>::iterator set2;
set<int, greater<int>>::iterator set3; //由大到小
复杂数据类型，自定义数据类型排序 ==>仿函数 函数对象
伪函数（仿函数）：重载了"()"操作符的普通类对象，从语法上讲，它与普通函数行为类似。
struct FuncStudent
{
bool operator()(const Student& left, const Student& right)
{
if(left.age < right.age)
{
return true;
}
else
{
return false;
}
}
set<Student, FuncStudent>set1;
Student s1("s1",);
Student s2("s2",);
Student s3("s3",);
set1.insert(s1); //...
for(set<Student, FuncStudent>::iterator it = set1.begin();...)
重要：set是有序的，键值唯一，当age相同时，后面的插入失败；即不插入，然后继续插入后面不重复的元素
//insert()源码：F11单步进入 返回类型是 对组 pair<T1, T2>
//typedef pair<iterator, bool> _Pairib;
pair<set<Student, FuncStudent>::iterator, bool> pair1 = set1.insert(s1);
if(pair1.second == true)
{
cout << "插入s1成功" << endl;
}
set的查找：
set.find(elem); //查找elem元素，返回指向该元素的迭代器。
set.count(elem); //元素个数，set为0或1；multiset值可能大于1
set.lower_bound(elem); //返回第一个>=elem的迭代器
set.upper_bound(elem); //返回第一个>elem的迭代器 set.equal_range(elem); //返回=elem的迭代器上下限，[beg, end)，其中*beg>=elem, *end>elem
该函数返回两个迭代器，被封装在pair中。
pair<set<int>::iterator, set<int>::iterator> pair1 = set1.equal_range(elem);
set<int>::iterator it1 = pair1.first; //beg, *beg>=elem
set<int>::iterator it2 = pair1.second; //*end>elem
map/multimap #include "map"
标准的关联式容器。
key唯一；元素按一定顺序排列，插入过程按排序规则插入，不能指定插入位置、
红黑树变体的平衡二叉树，插入和删除比vector快。
map[key] = value;
multimap 相同键可多次出现，不支持[]操作符；
insert:
map<int, string>map1;
map1.insert(pair<int, string>(,"tracher1"));
map1.insert(make_pair(,"tracher2"));
map1.insert(map<int, string>::value_type(,"tracher3"));
map1[] = "teacher4";
前三种方法返回pair(对组)
pair<map<int, string>::iterator, bool> pair1 = map1.insert(make_pair(2,"tracher2"));
重要：
这种方式，插入已经存在的key就不插入；
通过第四种 = 操作，插入已经存在的key就覆盖；
遍历：
迭代器：
for(map<int,string>::iterator it = map1.begin(); it != map1.end(); it++)
{
cout << it->first << "\t" << it->second << endl;
}
删除：
while(!map1.empty())
{
map<int,string>::iterator it = map1.begin(); //erase()后it失效，需要赋新值
map1.erase(it);
}
map1.erase(); //删除全部
map1.erase(v1.begin(),v1.begin()+2); //区间删除：删除2个元素
map1.erase(v1.begin()+3); //删除第3个元素
查找：（判断是否查找成功，即迭代器是否 = map1.end()）
find:
map<int,string>::iterator it = map1.find(100);
首先，接到insert的返回值pair
//equal_range:
pair<map<int>::iterator, map<int>::iterator> pair1 = map1.equal_range(elem); //返回两个迭代器，>=elem 和 >elem
if(pair1.first == map1.end())
{
cout << "第一个迭代器 >= elem 的位置不存在" << endl;
}
else
{
cout << pair1.first->first << "\t" << pair1.first->second << endl;
}
//pair1->first 表示第一个迭代器 ->first表示->key
multimap:
1个key值可以对应多个value =>分组
部门做key，人对象做value；
容器总结：
一、容器的值语意：浅拷贝；
除了queue和stack外，每个容器都提供可返回迭代器的函数，运用返回的迭代器可以访问元素！！！为什么呢？？？（后文解析）
每个容器都提供一个默认构造函数 和 一个默认拷贝构造函数（值语意，浅拷贝）。
当容器存放对象时，如果对象有指针，容器的值语意会造成浅拷贝。
vector.push_back(t1); //此时，C++编译器会调用Teacher类自带的拷贝构造函数，将t1拷贝一份到容器中
//如果不写一个深拷贝的拷贝构造函数，就会造成野指针。
解决办法： 定义自己的拷贝构造函数。
自定义的类中，最好自定义自己的 无参构造函数 拷贝构造函数 和 重载operator=操作符 将浅拷贝扼杀在摇篮里；
至于有参构造函数，根据需要定义。
class Teacher
{
public:
Teacher(char* name, int age)
{
m_name = new char[strlen(name)+];
strcpy(m_name,name);
m_age = age;
}
~Teacher()
{
if(m_name != NULL)
{
delete [] m_name;
m_name = NULL;
m_age = ;
}
}
//自定义拷贝构造函数
Teacher(const Teacher& obj)
{
m_name = new char[strlen(obj.m_name)+];
strcpy(m_name, obj.m_name);
m_age = obj.m_age;
}
//重载operator=操作符(成员函数)
Teacher& operator=(const Teacher& obj)
{
//1.析构左操作数原数据
if(m_name != NULL)
{
delete [] m_name;
m_name = NULL;
m_age = ;
}
//2.根据右操作数，给左操作数申请内存
m_name = new char[strlen(obj.m_name)+];
//3.赋值
strcpy(m_name, obj.m_name);
m_age = obj.age;
//4.返回调用对象
return *this;
}
private:
char* m_name;
int age;
}
二、除了queue和stack外，每个容器都提供可返回迭代器的函数，运用返回的迭代器可以访问元素！！！
分别是vector、list和deque，这三种顺序容器的设计都会设计到迭代器的概念，STL要求任何一种容器都必须内置一个迭代器，如果连迭代器都没有内置，就谈不上”容器“的定义了。所以，stack只是一个容器适配器，并不是一个容器，因为stack不提供迭代器，所以在元素不弹出的前提下不能够遍历内部所有的元素。
另外，queue是在stack基础上做了封装（两个栈怎么实现一个队列），所以也不是一个容器，而叫做容器适配器。
任何提供末端插入(push_back函数)、删除(pop_back函数）、访问(back函数)都能够被stack容器封装与修饰。这里的封装指的是通过stack对象，你不能直接访问被封装的底层容器了，所谓的修饰指的是stack在对底层容器做封装的同时，还提供了必要的接口，以满足用户的需要。我们将被适配器封装的底层容器称为基础容器。
在我们所学过的顺序容器中，只要能够提供末端的插入、删除和访问操作，都可以作为stack适配器的基础容器，所以vector、list和deque都可以作为stack的基础容器，而stack默认的基础容器为deque容器。