c++标准库包含STL，STL包含六大部件

STL

standard template library 标准模板库

C++的含义：C语言+类+模板

STL有6大组件：

容器、算法、迭代器、适配器、分配器、仿函数

容器（container）

1. 系统封装好的数据结构
   
2. 泛型编程思想，每种数据结构都能装任意类型
   
3. 主要是对数据结构增删改查的操作
   

算法（algorithm）

1. 系统封装好的算法（如sort排序算法）
   
2. 一个算法适用多种容器（泛型编程思想）
   

迭代器（Iterator）

迭代器相当于指针

迭代器告诉算法要执行的范围（在容器中）

分配器（allocator）

对容器的内存进行管理分配（例如vector容器的自动扩充，自动缩容等）

仿函数（functor）

仿函数：结构体或类要实现函数的功能，就要重载function call 操作符 ()

#include <iostream>

usingnamespacestd;

classStu{

public:

   //重载()操作符

   //只有函数返回true时，a的优先级才大于b

   booloperator () (inta,intb){

       

       returna>b; //此时当a>b时返回true，那么数值越大优先级越高

       

       //return a<b; 此时当a<b时返回true，那么数值越小优先级越高

   }

};

intmain()

{

    Stus;

    cout<<s(1,2) <<endl;//0

    cout<<s(2,1) <<endl;//1

   return0;

}

容器（container）

容器类自动申请和释放内存，无需new和delete操作

结构及分类

Sequence Containers

序列式容器：按照放入元素的顺序进行排列

Array：定长数组

Vector：不定长数组

Deque：双端队列

List：双向链表

Forward-List：单向链表

Associative Containers

关联式容器：元素是以键值对的形式存在（key/value），通过key可以快速查找，因此这种容器适合大量查找

关联式容器又分为Ordered Container和Unordered Container，即定序容器和不定序容器

定序容器：元素在容器内的位置是亘古不变的

不定序容器：元素在容器内的位置会随着时间的推移而发生变化

Ordered Container

定序容器：底部是红黑树，一种高度平衡的二分树，避免最差情况的发生（例如退化成链表）

Set：key不可以重复（set的key就是value，value就是key）

Multset：key可以重复

Map：key不可以重复

Multmap：元素可以重复

Unordered Container

不定序容器：底部是HashTable（HashTable中的链表不宜过长，避免查找忒慢）

Unordered Set

Unordered Multset

Unordered Map

Unordered Multmap

所有容器共有的操作

1. 赋值（=）：数组之间不可以赋值，相同类型容器之间可以
   
2. begin()：返回指向开头元素的迭代器
   end()：返回指向末尾的下一个元素的迭代器
   
3. size()：返回容器内元素的个数
   
4. empty()：空返回true，不空返回false
   
5. clear()：清空容器（可以用来初始化）
   

vector（动态数组）

#include<vector>

构造函数

vector();

explicitvector(size_typecount);

vector(size_typecount, constType&value);

template<classInputIterator>

vector(InputIteratorfirst, InputIteratorlast);

vector<int>memo;//无参构造啥都不加

memo=vector<int>(n+1,-1); //初始化n+1个元素，即[0,n]都为-1

vector<string>board(n,string(n,'.'));//初始化n个元素，即[0,n-1]都为n个'.'的字符串

vector<int>v(10);//初始size为10，是动态数组，容量可以改变;int a[10]容量则不可以改变

访问元素

1. 下标
   
2. back()：返回末尾元素的引用
   
3. front()：返回首元素的引用
   

增删改查

push_back()：在末尾插入一个元素

pop_back()：删除末尾元素

insert()：某个迭代器位置插入元素

erase()：删除某个迭代器或者区间的元素，返回最后被删除的迭代器

队列

#include<queue> //包含queue,deque,priority_queue

queue<int>q;

双端队列deque

既可以头出队，也可以尾出队

既可以头入队，也可以尾入队

优先队列

priority_queue<int>q;//默认大的元素先出队

priority_queue<int,vector<int>,greater<int>>q;//这样子小的元素先出队

栈stack

#include<stack>

stack<int> s;

1. push()：将新元素进栈
   
2. pop()：弹出栈顶元素
   
3. top()：访问栈顶元素
   

集合set

不含重复元素，默认从小到大排序

#include<set>

增删改查

增删改查时间复杂度都为O(log n)

1. insert()：插入元素
   
2. erase(x)：删除元素
   
3. count()：返回元素数量
   
4. find(x)：在set内存在值为x的元素会返回该元素的迭代器，否则返回end()
   
5. 遍历不能使用下标，要用迭代器

set<int> s;

s.insert(3);

s.insert(2);

set<int>::iterator it;

for (it = s.begin(); it != s.end(); it++)

cout << *it << endl;

映射map

#include<map>

map<string,int> m;

m["string"]=1;//下标为字符串

迭代器（iterator）

迭代器是泛化的指针，每个容器基本都有迭代器

算法通过迭代器知道要处理数据的范围（在容器中）

迭代器实现遍历

int ia[6]={5,1,2,3,1,4};

vector<int> vi(ia,ia+6);

vector<int>::iterator it=vi.begin();

for(;it!=vi.end();++it){

cout << *it << endl;

}

因为每种容器的迭代器实现是不同的，因此我们声明一个迭代器变量的时候需要指明是属于谁的迭代器

vector<int>::iterator it=vi.begin();//it是vector的迭代器

但是这种方式比较麻烦，我们可以使用auto关键字来自动识别迭代器种类

int main()

{

int ia[6]={5,1,2,3,1,4};

vector<int> vi(ia,ia+6);

for(auto a : vi){

cout << a << endl;

}

return 0;

}

谓词（predicate）

谓词就是一个判断，只能返回bool类型

5种谓词模式

1. 函数（function）谓词

/*Function Predicate*/

bool isLarger (const std::string &s1, const std::string &s2) {

return s1.size() > s2.size();

}

......

std::stable_sort(sv.begin(), sv.end(), isLarger);

函数谓词使用时，只需要函数名，函数名代表函数地址，但函数名本质并不是函数地址

2. 函数对象（function object）谓词

函数对象谓词也叫仿函数（functor）谓词：在类或结构体中重载了函数调用符()

/*Function Object*/

class LargerString {

public:

bool operator() (const std::string& a, const std::string& b) {

return a.size() > b.size();

}

};

......

std::stable_sort(sv.begin(), sv.end(), LargerString());

因为他们是仿函数（不是真的函数），因此仿函数谓词在使用时，需要 类名+() 或 结构体名+() 这种格式

3. 库定义的函数对象（library-defined function object）谓词

使用标准库定义的函数对象, 充当算法中的谓词, 包含在#include<functional>中

std::stable_sort(sv.begin(), sv.end(), std::less<std::string>());

4. 函数指针(function pointer)谓词

5. Lambda表达式(lambda expression)谓词

常用的谓词是函数谓词，仿函数谓词（分为自定义的和标准库定义的）

一元谓词与二元谓词

1. 如果operator()接收一个参数，叫一元谓词
   
2. 如果operator()接收两个参数，叫二元谓词
   

//自己定义的一元函数谓词greater2

bool greater2(int a){

return a>2;

}

int main()

{

int ia[6]={5,1,2,3,1,4};

vector<int> vi(ia,ia+6);

cout << count_if(vi.begin(),vi.end(),greater2);//3

return 0;

}

//使用标准库定义好的仿函数谓词greater<int>()

int main()

{

int ia[6]={5,1,2,3,1,4};

vector<int> vi(ia,ia+6);

cout << count_if(vi.begin(),vi.end(),bind2nd(greater<int>(),2));//3

return 0;

}

count_if函数第三个参数需要的是一元谓词，但是greater仿函数是二元谓词，所以我们可以通过function adapter（binder）来绑定第二个参数为2，那么greater<int>()只需要一个参数