STL简介

• 编程的抽象发展：面向过程$\to$基于对象$\to$面向对象$\to$泛型

• STL(Standard Template Library)是C++标准库的一部分(80%),采用模板(Template)机制来表达泛型。

STL容器

bitset 位集(位运算)

位运算基础（&、|、^、~、>>、<<）

位运算概述

从现代计算机中所有的数据二进制的形式存储在设备中。即 0、1 两种状态,计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算,即将符号位共同参与运算的运算。

口说无凭,举一个简单的例子来看下 CPU 是如何进行计算的,比如这行代码：

int a = 35;
int b = 47;
int c = a + b;

计算两个数的和,因为在计算机中都是以二进制来进行运算,所以上面我们所给的 int 变量会在机器内部先转换为二进制在进行相加：

35:  0 0 1 0 0 0 1 1
47:  0 0 1 0 1 1 1 1
————————————————————
82:  0 1 0 1 0 0 1 0

所以,相比在代码中直接使用(+、-、*、/)运算符,合理的运用位运算更能显著提高代码在机器上的执行效率。

位运算概览

符号	描述	运算规则
&	与	两个位都为1时,结果才为1
|	或	两个位都为0时,结果才为0
^	异或	两个位相同为0,相异为1
~	取反	0变1,1变0
<<	左移	各二进位全部左移若干位,高位丢弃,低位补0
>>	右移	各二进位全部右移若干位,对无符号数,高位补0,有符号数,各编译器处理方法不一样,有的补符号位（算术右移）,有的补0（逻辑右移）

按位与运算符（&）

定义：参加运算的两个数据,按二进制位进行"与"运算。

运算规则：

0&0=0  0&1=0  1&0=0  1&1=1

总结：两位同时为1,结果才为1,否则结果为0。

例如：3&5 即 0000 0011& 0000 0101 = 0000 0001,因此 3&5 的值得1。

注意：负数按补码形式参加按位与运算。

与运算的用途

• 清零

如果想将一个单元清零,即使其全部二进制位为0,只要与一个各位都为零的数值相与,结果为零。

• 取一个数的指定位

比如取数 X=1010 1110 的低4位,只需要另找一个数Y,令Y的低4位为1,其余位为0,即Y=0000 1111,然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。

• 判断奇偶

只要根据最未位是0还是1来决定,为0就是偶数,为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。

按位或运算符（|）

定义：参加运算的两个对象,按二进制位进行"或"运算。

运算规则：

0|0=0  0|1=1  1|0=1  1|1=1

总结：参加运算的两个对象只要有一个为1,其值为1。

例如：3|5即 0000 0011| 0000 0101 = 0000 0111,因此,3|5的值得7。

注意：负数按补码形式参加按位或运算。

或运算的用途

• 常用来对一个数据的某些位设置为1

比如将数 X=1010 1110 的低4位设置为1,只需要另找一个数Y,令Y的低4位为1,其余位为0,即Y=0000 1111,然后将X与Y进行按位或运算（X|Y=1010 1111）即可得到。

异或运算符（^）

**定义：**参加运算的两个数据,按二进制位进行"异或"运算。

运算规则：

0^0=0  0^1=1  1^0=1  1^1=0

总结：参加运算的两个对象,如果两个相应位相同为0,相异为1。

异或的几条性质:

• 交换律
• 结合律 (a^b)^c == a^(b^c)
• 对于任何数x,都有 x^x=0,x^0=x
• 自反性: a^b^b=a^0=a;

异或运算的用途

• 翻转指定位

比如将数 X=1010 1110 的低4位进行翻转,只需要另找一个数Y,令Y的低4位为1,其余位为0,即Y=0000 1111,然后将X与Y进行异或运算（X^Y=1010 0001）即可得到。

• 与0相异或值不变

例如：1010 1110 ^ 0000 0000 = 1010 1110

• 交换两个数

实例
void Swap(int &a, int &b){
if (a != b){
a ^= b;
b ^= a;
a ^= b;
}
}

取反运算符 (~)

**定义：**参加运算的一个数据,按二进制进行"取反"运算。

运算规则：

~1=0
~0=1

总结：对一个二进制数按位取反,即将0变1,1变0。

异或运算的用途

• 使一个数的最低位为零

使a的最低位为0,可以表示为：a & ~1。~1的值为 1111 1111 1111 1110,再按"与"运算,最低位一定为0。因为" ~"运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。

左移运算符（<<）

**定义：**将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃,右边补0）。

设 a=1010 1110,a = a<< 2 将a的二进制位左移2位、右补0,即得a=1011 1000。

若左移时舍弃的高位不包含1,则每左移一位,相当于该数乘以2。

右移运算符（>>）

**定义：**将一个数的各二进制位全部右移若干位,正数左补0,负数左补1,右边丢弃。

例如：a=a>>2 将a的二进制位右移2位,左补0 或者 左补1得看被移数是正还是负。

操作数每右移一位,相当于该数除以2。

复合赋值运算符

位运算符与赋值运算符结合,组成新的复合赋值运算符,它们是：

&=        例：a&=b    相当于     a=a&b

|=        例：a|=b    相当于     a=a|b

>>=      例：a>>=b   相当于     a=a>>b

<<=      例：a<<=b     相当于      a=a<<b

^=        例：a^=b    相当于   a=a^b

运算规则：和前面讲的复合赋值运算符的运算规则相似。

不同长度的数据进行位运算：如果两个不同长度的数据进行位运算时,系统会将二者按右端对齐,然后进行位运算。

以"与运算"为例说明如下：我们知道在C语言中long型占4个字节,int型占2个字节,如果一个long型数据与一个int型数据进行"与运算",右端对齐后,左边不足的位依下面三种情况补足,

1. 如果整型数据为正数,左边补16个0。
2. 如果整型数据为负数,左边补16个1。
3. 如果整形数据为无符号数,左边也补16个0。

• 如：long a=123；int b=1；计算a& b。
• 如：long a=123；int b=-1；计算a& b。
• 如：long a=123；unsigned intb=1；计算a & b。

位集使用

• C++的 bitset 在 bitset 头文件中,它是一种类似数组的结构,它的每一个元素只能是０或１,每个元素仅用１bit空间。

构造函数

bitset<4> bitset1;	//无参构造,长度为４,默认每一位为０
bitset<8> bitset2(12);	//长度为８,二进制保存,前面用０补充
string s="100101";
bitset<10> bitset3(s);	//长度为10,前面用０补充
cout<<bitset1<<endl;	//0000
cout<<bitset2<<endl;	//00001100
cout<<bitset3<<endl;	//0000100101

注意

• 用字符串构造时,字符串只能包含 ‘0’ 或 ‘1’ ,否则会抛出异常。
• 构造时,需在<>中表明bitset 的大小(即size)。
• 在进行有参构造时,若参数的二进制表示比bitset的size小,则在前面用０补充(如上面的例子)；若比bitsize大,参数为整数时取后面部分,参数为字符串时取前面部分(如下面例子)：

bitset<2> bitset1(12);　　//12的二进制为1100（长度为４）,但bitset1的size=2,只取后面部分,即00
string s="100101";　　
bitset<4> bitset2(s);　　//s的size=6,而bitset的size=4,只取前面部分,即1001
cout<<bitset1<<endl;　　//00
cout<<bitset2<<endl;　　//1001

可用操作符

• bitset有cin和cout
• cin按照二进制输入
• cout输出的是二进制数

bitset<8> foo;
cin>>foo;	//cin>>100
cout<<foo;	//cout<<00000100

• bitset有赋值运算

bitset<8> foo;
foo=15;
cout<<foo;	//cout<<00001111
foo=bitset<8>(string("00000001"));
cout<<foo;	//cout<<00000001;

• bitset对于二进制有位操作符

bitset<4> foo(string("1001"));
bitset<4> bar(string("0011"));
cout<<(foo^=bar)<<endl;       // 1010 (foo对bar按位异或后赋值给foo)
cout<<foo&=bar)<<endl;       // 0010 (按位与后赋值给foo)
cout<<(foo|=bar)<<endl;       // 0011 (按位或后赋值给foo)
cout<<(foo<<=2)<<endl;        // 1100 (左移２位,低位补０,有自身赋值)
cout<<(foo>>=1)<<endl;        // 0110 (右移１位,高位补０,有自身赋值)
cout<<(~bar)<<endl;           // 1100 (按位取反)
cout<<(bar<<1)<<endl;         // 0110 (左移,不赋值)
cout<<(bar>>1)<<endl;         // 0001 (右移,不赋值)
cout<<(foo==bar)<<endl;       // false (0110==0011为false)
cout<<(foo!=bar)<<endl;       // true  (0110!=0011为true)
cout<<(foo&bar)<<endl;        // 0010 (按位与,不赋值)
cout<<(foo|bar)<<endl;        // 0111 (按位或,不赋值)
cout<<(foo^bar)<<endl;        // 0101 (按位异或,不赋值) 

• 可以通过 [ ] 访问元素(类似数组),注意最低位下标为０,如下：

bitset<4> foo("1011");
cout<<foo[0]<<endl;　　//1
cout<<foo[1]<<endl;　　//1
cout<<foo[2]<<endl;　　//0
//当然,通过这种方式对某一位元素赋值也是可以的

可用函数

• bitset还支持一些有意思的函数

bitset<8> foo("10011011");
cout<<foo.count()<<endl;　　//5　　（count函数用来求bitset中1的位数,foo中共有５个１
cout<<foo.size()<<endl;　　 //8　　（size函数用来求bitset的大小,一共有８位
cout<<foo.test(0)<<endl;　　//true　　（test函数用来查下标处的元素是０还是１,并返回false或true,此处foo[0]为１,返回true
cout<<foo.test(2)<<endl;　　//false　　（同理,foo[2]为０,返回false
//test函数会对下标越界作出检查,而通过 [ ] 访问元素却不会经过下标检查,所以,在两种方式通用的情况下,选择test函数更安全一些
cout<<foo.any()<<endl;　　//true　　（any函数检查bitset中是否有１
cout<<foo.none()<<endl;　　//false　　（none函数检查bitset中是否没有１
cout<<foo.all()<<endl;　　//false　　（all函数检查bitset中是全部为１

• 另外,含有一些函数

//同样,如下也都会检查下标是否越界,如果越界就会抛出异常
bitset<8> foo ("10011011");
cout<<foo.flip(2)<<endl;　　//10011111　　（flip函数传参数时,用于将参数位取反,本行代码将foo下标２处"反转",即０变１,１变０
cout<<foo.flip()<<endl;　　 //01100000　　（flip函数不指定参数时,将bitset每一位全部取反
cout<<foo.set()<<endl;　　　　//11111111　　（set函数不指定参数时,将bitset的每一位全部置为１
cout<<foo.set(3,0)<<endl;　　//11110111　　（set函数指定两位参数时,将第一参数位的元素置为第二参数的值,本行对foo的操作相当于foo[3]=0
cout<<foo.set(3)<<endl;　　  //11111111　　（set函数只有一个参数时,将参数下标处置为１
cout<<foo.reset(4)<<endl;　　//11101111　　（reset函数传一个参数时将参数下标处置为０
cout<<foo.reset()<<endl;　　 //00000000　　（reset函数不传参数时将bitset的每一位全部置为０

• 最后,还有一些类型转换的函数

bitset<8> foo ("10011011");
string s = foo.to_string();　　//将bitset转换成string类型
unsigned long a = foo.to_ulong();　　//将bitset转换成unsigned long类型
unsigned long long b = foo.to_ullong();　　//将bitset转换成unsigned long long类型
cout<<s<<endl;　　//10011011
cout<<a<<endl;　　//155
cout<<b<<endl;　　//155

deque 双端队列

• 队首队尾都可以进出的队列
• 在库queue中
• clear 清空
• push_back 入队尾
• push_front 入对头
• pop_back 出队尾
• pop_front 出队头
• back 队尾
• front 队头
• size 大小
• empty 队空

#include <iostream>
#include <queue>
using namespace std;
int main(){
	deque<int> que;//创建一个int类型双端队列
	int n;
	cin>>n;
	while(n--){
		int p;
		cin>>p;
		que.push_back(p);//入队尾,队头用que.push_front(p);
	}
	while(!que.empty()){//队非空则循环,或while(que.size())
		cout<<que.front()<<' ';//输出队头,队尾用que.back()
		que.pop_front();//队头出队,队尾用que.pop_back()
	}
	return 0;
}

heap 堆

• heap没有对应容器,STL中只有相关算法,由于heap是一种基础数据结构,因此归为容器
• make_heap 建堆
• push_heap 入堆
• pop_heap 出堆
• sort_heap 排序堆
• heap相关算法在algorithm中

void make_heap(first,last,comp)
void push_heap(first,last,comp)
void pop_heap(first,last,comp)
void sort_heap(first,last,comp)
first 堆起始位置 num+i s.begin()
last 堆末尾位置+1 num+n s.end()
comp 自定义比较函数,不填默认大顶堆
除了push_heap,全都是[first,last)
push_heap将last加入堆[first,last-1)

//初始2个数,输入n个数,按堆从大到小排序
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int num[100]={2,1};//默认堆中有2个元素 
	make_heap(num,num+2);//初始化堆 
	int n;
	cin>>n;//入堆n个元素 
	for(int i=0;i<n;i++){
		int p;
		cin>>p;
		num[i+2]=p; 
		push_heap(num,num+2+i);//入堆 
	}
	for(int i=n+1;i>=0;i--){//输出之后排堆的元素少1 
		cout<<num[0]<<' ';
		pop_heap(num,num+i);//出堆 
	}
	return 0;
}

list 双向链表

• 需要库list
• 链表的插入删除效率高于顺序存储容器
• clear 清空
• push_back 入队尾
• push_front 入对头
• pop_back 出队尾
• pop_front 出队头
• back 队尾
• front 队头
• size 大小
• empty 队空

#include <iostream>
#include <list>
using namespace std;
int main(){
	list<int> l;//创建一个int类型双向链表 
	int n;
	cin>>n;
	while(n--){
		int p;
		cin>>p;
		l.push_back(p);//入链尾,链头l.push_front(p);
	}
	list<int> ll(l);//复制l到ll 
	l.merge(ll,less<int>());//将ll合并到l,第二个参数是比较构造函数,不填默认升序 
	while(!l.empty()){//链非空则循环,或while(l.size())
		cout<<l.front()<<' ';//输出链头,链尾用l.back()
		l.pop_front();//删除链头,链尾l.pop_back()
	}
	return 0;
}

map 映射

• #include <map>//映射库
• $x\to y$称之为一个映射,map映射类似于一元函数,不同的$x$可以映射到同一个$y$,但一个$x$不能映射多个$y$
• char类型字符与ASCII值是一个映射关系

#include <map>
map<键的类型,值的类型> 变量名;//map容器类型变量定义
//他做的是键值的映射
//访问map的映射可以采用数组的方式
//变量名[键]==值;
//mp[idx]返回的是值的类型

#include <iostream>
#include <map>
using namespace std;
int main(){
    map<int,char> mp;//创建一个int到char的映射
    //可以重载比较函数改变存储顺序:map<int,char,greater<int> > mp,默认升序
    for(int i=1;i<=26;i++){
        mp[i]='A'+i-1;//使1~26映射为大写字母A~Z
    }
    for(int i=1;i<=26;i++){
        cout<<i<<':'<<mp[i]<<endl;//输出映射关系
    }
    mp[27]='a';//使mp[27]等于小写a
    cout<<mp[27]<<endl;//输出mp[27]
    mp.erase(27);
    if(mp.find(27)==mp.end()){//这是查找27是否存在
        cout<<"键27不存在\n";
    }else{
        cout<<"键27存在\n";
    }
    mp.clear();//清空map
    if(mp.empty()){//判断map空
        cout<<"map为空";
    }
    return 0;
}

multimap 多重映射

• 用法类似于map,但可以存取重复元素
• multimap未重载[]运算符,基元素类型是pair
• 需要库map

#include <iostream>
#include <map>
using namespace std;
int main(){
	multimap<int,char> mp;
	/*
		上句是int到char的多重映射
		multimap存的是一些pair二元组 
		第三个参数是比较函数的重载,不写默认为first键升序 
		降序写法:multimap<int,char,greater<int> > mp; 
	*/
	int n;
	cin>>n;
	while(n--){
		int f;
		char s;
		cin>>f>>s;//输入n对二元组
		mp.insert(pair<int,char>(f,s));//数对的插入 
	}
	cout<<"size:"<<mp.size()<<endl;//求大小 
	for(auto i=mp.begin();i!=mp.end();i++){
		cout<<i->first<<' '<<i->second<<endl;//输出这些二元映射 
	}
	mp.erase(1);//删除键1 
	if(mp.find(1)==mp.end()) cout<<"key 1 not found.";//查找键1 
	else cout<<"key 1 in multimap.";
	mp.clear();//清空multimap 
	return 0;
}

multiset 多重集合

• 可以包含重复元素的集合
• 用法类似于set
• 包含于库set

#include <iostream>
#include <set>
using namespace std;
int main(){
	multiset<int> s;//创建一个int类型的多重集合
	//可以重载比较函数改变存储顺序:multiset<int,greater<int> > s,默认升序
	int n;
	cin>>n;
	while(n--){
		int p;
		cin>>p;
		s.insert(p);//集合插入元素p,若p存在则不插入 
	}
	for(auto i=s.begin();i!=s.end();i++){//迭代器访问形式,set会按照升序输出 
		cout<<*i<<' ';
	}
	cout<<endl; 
	s.erase(2);//删除2
	//查找2,需要使用迭代器判断 
	if(s.find(2)!=s.end()) cout<<"2 is in set";
	else cout<<"2 is not in set";
	return 0;
}

pair 二元组

• 可以理解为一对元素组成的数据类型
• 使用pair可以减少结构体数目
• 需要库utility
• first 第一个元素
• second 第二个元素

#include <iostream>
#include <utility>
using namespace std;
int main(){
	pair<int,char> p;//创建一个int与char关联的二元组 
	cin>>p.first;//输入pair的第一个元素
	cin>>p.second;//输入pair的第二个元素
	cout<<p.first<<' '<<p.second;//输出 
	return 0;
}

priority_queue 优先队列

• 优先队列是允许插队的队列,优先权越高越靠前
• 优先队列默认优先权以>运算符识别,即大的在前面
• 可通过重载运算符或传入比较函数改变优先权判定
• 优先队列包含于queue

#include <queue>
priority_queue<int> que;//声明一个int优先队列
/*
	priority_queue<>的原型是priority_queue<type,sequence,comp>
	type表示存储数据类型 
	sequence表示底层容器,不填默认使用vector<type>
	comp是比较函数,比较type的大小,默认升序取大值靠前
	 
	由于大部分的编程语言限制,可选参数只得出现在末尾 
	因此加入比较函数后,sequence不得为空
	int的降序写法是priority_queue<int,vector<int>,greater<int> > que;
	注意上句末尾> >,这是因为>>会被识别为运算符,比如cin>>,加空格得以区分开 
*/ 

优先队列的成员函数

• push 入队
• pop 出队
• top 队头
• size 大小
• empty 队空

#include <iostream>
#include <queue>
using namespace std;
int main(){
	priority_queue<int> que;//声明一个int优先队列
	int n;
	cin>>n;
	while(n--){
		int p;
		cin>>p;
		que.push(p);//将p送入优先队列 
	}
	while(!que.empty()){//队列非空 
		cout<<que.top()<<' ';//输出队头
		que.pop();//出队 
	}
	return 0;
}

queue 队列

• #include <queue>//队列库
• 先进先出(FIFO)的数据容器
• queue
• push 入队
• pop 出队
• empty 队空
• size 队大小
• front 队头

#include <iostream>
#include <queue>
using namespace std;
int main(){
    //queue<数据类型> 变量名;//定义一个队列变量
    queue<int> que;
    
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int p;
        cin>>p;
        que.push(p);//n次输入,每次输入一个p入队
    }
    cout<<"size:"<<que.size()<<endl;//输出队的大小
    
    cout<<"queue:";//输出按序出队
    while(!que.empty()){//队非空时循环
        cout<<que.front()<<' ';//输出队头元素
        que.pop();//出队一个元素
    }
    cout<<endl;
    if(que.empty()) cout<<"queue is empty";//输出队空
    return 0;
}

set 集合

• 集合是无重复元素的数据集
• 需要库set
• insert 插入元素
• erase 删除元素
• find 查找元素

#include <iostream>
#include <set>
using namespace std;
int main(){
	set<int> s;//创建一个int类型的集合
	//可以重载比较函数改变存储顺序:set<int,greater<int> > s,默认升序
	int n;
	cin>>n;
	while(n--){
		int p;
		cin>>p;
		s.insert(p);//集合插入元素p,若p存在则不插入 
	}
	for(auto i=s.begin();i!=s.end();i++){//迭代器访问形式,set会按照升序输出 
		cout<<*i<<' ';
	}
	cout<<endl; 
	s.erase(2);//删除2
	//查找2,需要使用迭代器判断 
	if(s.find(2)!=s.end()) cout<<"2 is in set";
	else cout<<"2 is not in set";
	return 0;
}

stack 栈

• #include <stack>//栈库
• 先进后出(FILO)的数据容器
• stack 栈
• push 入栈
• pop 出栈
• empty 栈空
• size 栈大小
• top 栈顶

#include <iostream>
#include <stack>
using namespace std;
int main(){
    //stack<数据类型> 变量名;//定义一个栈变量
    stack<int> stk;
	
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int p;
        cin>>p;
        stk.push(p);//n次输入,每次输入一个p入栈
    }
    cout<<"size:"<<stk.size()<<endl;//输出栈的大小
    
    cout<<"stack:";//输出按序出栈
    while(!stk.empty()){//栈非空时循环
        cout<<stk.top()<<' ';//输出栈顶元素
        stk.pop();//出栈一个元素
    }
    cout<<endl;
    if(stk.empty()) cout<<"stk is empty";//输出栈空
    return 0;
}

string 字符串

基本字符(char)函数

函数名	返回值类型	参数表	解释	所在库
islower()	int	int _C	判断字符是否为小写字母,是返回2,否返回0	cctype
isupper()	int	int _C	判断字符是否为大写字母,是返回1,否返回0	cctype
isalpha()	int	int _C	判断字符是否为字母,小写返回2,大写返回1,否返回0	cctype
isdigit()	int	int _c	判断字符是否为数字,是返回1,否返回0	cctype
tolower()	int	int _C	转换为小写字母	cctype
toupper()	int	int _C	转换为大写字母	cctype

//输入一个字符c,改变他的大小写
#include <iostream>
#include <cctype>//iostream中已包含cctype,可以不加
int main(){
	char c;
	cin>>c;
	if(islower(c)){
		cout<<toupper(c);
	}else{
		cout<<tolower(c);
	}
	return 0;
}

字符串初步

• #include <string> 字符串库
• string s;//定义一个字符串变量
• string s=“hello”;//字符串变量赋初值
• 字符串可以使用输入流(cin)输出(cout)流

#include <iostream>
#include <string>
using namespace std;
int main(){
	string s1,s2;
	cin>>s1;//cin输入不能读入空格
	getline(cin,s2);
	/*
	getline的注意事项
	1.getline是整行读入函数
	  与cin或scanf输入其他数据类型时有冲突,需要过滤换行符
	  推荐过滤法:getchar()或scanf("\n")
	2.getline位于<cstdio>,自C++11起<iostream>已包含getline
	*/
	cout<<s1<<endl;//cout输出字符串
	return 0;
}

字符串的比较

• == 逻辑等于
• >,<,字符串大于小于比较,大小按照字典序确定,如"a"<“aa”,“ab”<“ac”

//字符串大小比较
#include <iostream>
#include <string>
using namespace std;
int main(){
	string s1,s2;
	cin>>s1>>s2;
	if(s1<s2) cout<<s1<<'<'<<s2;
	else if(s1>s2) cout<<s1<<'>'<<s2;
	else cout<<s1<<'='<<s2;
	//s1=="hello"可以判断是s1是否是hello字符串
	//s1==""可以判断s1是否为空字符串
	return 0;
}

字符串的成员函数

• 成员函数的访问方式:

• 若fun()为变量s的成员函数,则fun访问方式为s.fun();

• 字符串常用成员函数

函数名	返回值类型	参数表	解释	所属类
find(str)	int	string(或char) str	查找str第一次出现的下标,不存在则返回-1	string
find(str,pos)	int	string(或char) str,int pos	查找从pos下标开始,str第一次出现的下标,不存在则返回-1	string
insert(pos,str)	string	int pos,string str	在字符串下标pos处添加字符串str,返回值为修改后的字符串	string
erase(pos)	string	int pos	删除字符串从pos处开始到字符串尾的字符,返回值为修改后的字符串	string
erase(pos,len)	string	int pos,int len	删除字符串从pos处开始的n个字符,返回值为修改后的字符串	string
size()	int		返回字符串的长度	string
substr(pos)	string	int pos	返回从pos开始到字符串尾的子字符串,不改变原字符串	string
substr(pos,len)	string	int pos,int len	返回从pos开始长度为len的子字符串,不改变原字符串	string
appen(str)	string	string str	在字符串末尾添加字符串str,可用s=s+str代替	string
at(idx)	char	int idx	返回字符串下标为idx的字符,可用s[idx]代替	string
clear()	void		清空字符串,可用s=""代替	string
compare(str)	int	string str	使字符串s与参数str比较,s>str返回1,s<str返回-1,s==str返回0,可用>,<,==替代	string
empty()	bool		判断字符串为空?,可用s==""代替	string
length()	int		返回字符串的长度	string

字符串的运算符

操作符	返回值类型	使用示例	解释
=	string	s=“abc”;	字符串赋值
+	string	s=s1+s2;	拼接字符串s2到s1的末尾
+=	string	s+=“abc”;s+=‘a’;	在字符串末尾添加字符串或字符
==	int	s==s1	逻辑比较两个字符串是否相等
>	int	s>s1	逻辑比较字符串s>s1是否成立
>=	int	s>=s1	逻辑比较字符串s>=s1是否成立
<	int	s<s1	逻辑比较字符串s<s1是否成立
<=	int	s<=s1	逻辑比较字符串s<=s1是否成立
[idx]	char	s[0]=‘0’;	访问字符串下标为idx的字符,可以进行赋值

字符串示例

//把字符串的大小写倒置
#include <iostream>
#include <string>
using namespace std;
int main(){
	string s;
	getline(cin,s);
	for(int i=0;i<s.size();i++){
		if(islower(s[i])){
			s[i]=toupper(s[i]);
		}else{
			s[i]=tolower(s[i]);
		}
	}
	s="大小写倒置后:"+s;
	cout<<s;
	return 0;
}

vector 向量

• 可以把vector理解成STL顺序表(动态数组),适合顺序访问,慢于数组
• 需要库vector
• push_back 末尾添加元素
• pop_back 删除末尾元素
• insert 添加元素
• clear 清空
• size 大小
• empty 判断为空

#include <iostream>
#include <vector>
using namespace std;
int main(){
	vector<int> vec;//声明一个int类型vector 
	int n;
	cin>>n;//输入n个数 
	while(n--){
		int p;
		cin>>p;
		vec.push_back(p);//存入p 
	}
	for(int i=0;i<vec.size();i++){
		cout<<vec[i]<<' ';//依次输出vec元素 
	}
	cout<<endl<<"size:"<<vec.size();
	vec.pop_back();//删除末尾元素 
	cout<<endl<<"size:"<<vec.size()<<endl;
	vec.insert(vec.begin()+1,2);//在1处插入2  
	for(int i=0;i<vec.size();i++){
		cout<<vec[i]<<' ';//依次输出vec元素 
	}
	return 0;
}

unordered 无序容器

• 无序容器不是一个具体的容器,而是一类容器
• 无序容器基于哈希表
• 有序容器擅长大量遍历容器的操作,无序容器擅长通过键获取对应值

无序容器	所在库	对应容器
unordered_map	unordered_map	map
unordered_multimap	unordered_map	multimap
unordered_set	unordered_set	set
unordered_multiset	unordered_set	multiset

• • 无序容器用法可以直接参考对应容器,如下是unordered的一个简单例子

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
    //创建并初始化一个 unordered_map 容器，其存储的 <int,char> 类型的键值对
    unordered_map<int,char> umap;
    for(int i=1;i<=26;i++){
    	umap[i]='a'+i-1;
	}
    //使用迭代器遍历哈希容器，效率不如关联式容器
    for (auto i=umap.begin();i!=umap.end();i++)
    {
        //pair类型键值对分为2部分
        cout<<i->first<<" "<<i->second<<endl;
    }
    return 0;
}

STL算法

binary_search 二分查找

binary_search 二分查找

• 查找目标值是否在数组中，返回$bool$

#include <iostream>
#include <algorithm>//需要算法库
using namespace std;
int main(){
    /*
    	返回值:bool 整数类型数组地址(没找到返回last)或iterator迭代器(s.begin(),s.begin+i,s.end()代表查找失败)
    	binary_search(first,last,value,comp)
    	first 查找起始位置 num+i s.begin()
    	last 查找末尾位置+1 num+n s.end()
    	value 查找值
    	comp 自定义比较函数,不填默认升序
    */
	int num[5]={1,2,3,4,5};
	cout<<binary_search(num,num+5,3);//输出3是否在此区间 
	return 0;
} 

lower_bound和upper_bound 二分查找下标

• lower_bound 查找第一个大于等于value的位置
• upper_bound 查找第一个大于value的位置

#include <iostream>
#include <algorithm>//需要算法库
using namespace std;
int main(){
    /*
    	返回值:int* 整数类型数组地址(没找到返回last)或iterator迭代器(s.begin(),s.begin+i,s.end()代表查找失败)
    	lower_bound(first,last,value,comp)
    	upper_bound(first,last,value,comp)
    	first 查找起始位置 num+i s.begin()
    	last 查找末尾位置+1 num+n s.end()
    	value 查找值
    	comp 自定义比较函数,不填默认升序
    */
	int num[5]={1,2,3,4,5};
	cout<<lower_bound(num,num+5,3)-num;//输出第一个大于等于3的下标
	return 0;
} 

copy 复制

• 某一个数组或容器复制到另一个数组或容器

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	/*
		返回值为目标数组指针或迭代器 
		copy(first,last,out)
		[first1,last1)是参与复制的数组或容器范围
		out是存储结果的数组或迭代器 
		copy的前三个参数均使用数组指针或迭代器 
	*/
	int a[4]={1,2,4,0},
		b[5];
	copy(a,a+4,b);//将[a,a+4)和[b+1,b+4)插入c 
	for(int i=0;i<4;i++) cout<<b[i]<<' ';
	return 0;
}

count 计算个数

• count可以统计first到last中值value的个数
• count 在algorithm库中

#include <iostream>
#include <algorithm>//需要算法库
using namespace std;
int main(){
    /*
	    int 整数返回值
    	count(first,last,value)
    	first 统计起始位置 num+i s.begin()
    	last 统计末尾位置+1 num+n s.end()
    	value 值,类型同数组或容器内元素类型
    */
	int num[5]={1,1,2,2,9};
    //计算num[0]~num[5-1]中2的个数
    cout<<count(num,num+5,2);
	return 0;
} 

count_if 计算满足条件的个数

• count_if可以统计first到last中满足条件的值的个数

• count_if在algorithm中

  #include <iostream>
  #include <algorithm>//需要算法库
  using namespace std;
  int cmp(int n){
  	return n<4;//条件为n<4 
  }
  int main(){
  	/*
  	    int 整数返回值
      	count_if(first,last,comp)
      	first 统计起始位置 num+i s.begin()
      	last 统计末尾位置+1 num+n s.end()
      	comp 条件函数,非空
      */
  	int num[5]={1,1,2,2,9};
      cout<<count_if(num,num+5,cmp);//统计num[0]~num[5-1]中小于4的元素个数
  	return 0;
  } 

element 区间元素

max_element 区间最大

• 查找数组或迭代器特定区间的最大值

#include <iostream>
#include <algorithm>//需要使用算法库
using namespace std;
int main(){
	/*
	返回值为数组指针或迭代器
	max_element(first,last,comp);
    first 查找起始位置 num+i s.begin()
    last 查找末尾位置+1 num+n s.end()
    comp 比较函数,不写默认从小到大
    */
    
    int num[9]={1,3,4,5,2,6,7,8,9};
    //输出最大
    int idx=max_element(num,num+9);
    cout<<num[idx];
    return 0;
}

min_element 区间最小

• 查找数组或迭代器特定区间的最小值

#include <iostream>
#include <algorithm>//需要使用算法库
using namespace std;
int main(){
	/*
	返回值为数组指针或迭代器
	min_element(first,last,comp);
    first 查找起始位置 num+i s.begin()
    last 查找末尾位置+1 num+n s.end()
    comp 比较函数,不写默认从小到大
    */
    
    int num[9]={1,3,4,5,2,6,7,8,9};
    //输出最小
    int idx=min_element(num,num+9);
    cout<<num[idx];
    return 0;
}

nth_element 区间第n小

• nth_element使用快速排序的原理,如果求第n小,则只保证下标n左侧的元素小于等于s[n],下标n右侧的元素大于等于s[n]

#include <iostream>
#include <algorithm>//需要使用算法库
using namespace std;
int main(){
	/*
	void 无返回值
	nth_element(first,nth,last,comp);
    first 排序起始位置 num+i s.begin()
    nth 第k大的位置 num+k s.begin()+k
    last 排序末尾位置+1 num+n s.end()
    comp 比较函数,不写默认从小到大
    输出第k小 cout<<num[k],k从0开始
    */
    
    int num[9]={1,3,4,5,2,6,7,8,9};
    //输出第3大
    nth_element(num,num+2,num+9);
    cout<<num[2];
    return 0;
}

permutation 全排列

• next_permutation 数组或容器全排列的下一次组合
• prev_permutation 数组或容器全排列的上一次组合

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	/*
		int 返回值,0、1
		next_permutation(first,last,comp)
		prev_permutation(first,last,comp)
		两个permutation会改变数组,如果下一次排列存在,则返回1,否则返回0,返回0会回到初始第一个排列
		comp比较函数,默认为空按照升序排列
	*/
    int num[3]={1,2,3};
    do{
        for(int i=0;i<3;i++){
            cout<<num[i]<<' ';
        }
        cout<<endl;
    }while(next_permutation(num,num+3));
	return 0;
}

fill 填充

• 填充数组或容器的值

#include <iostream>
#include <algorithm>//需要算法库
using namespace std;
int main(){
	/*
  		void 无返回值
		fill(first,last,value)
		first 填充起始位置 num+i s.begin()
		last 填充末尾位置+1 num+n s.end()
		value 填充值
    */
	int num[5];
	fill(num,num+5,4);//填充num[0]~num[5-1]为4
	for(int i=0;i<5;i++){
		cout<<num[i]<<' ';//输出填充后的数组
	}
	return 0;
} 

reverse 逆置

• 数组或容器逆置

#include <iostream>
#include <algorithm>//需要算法库
int main(){
	/*
	void 无返回值
	reverse(first,last)
	first 逆置起始位置 num+i s.begin()
	last 逆置末尾位置+1 num+n s.end()
	*/
	int num[5]={1,1,2,2,9};
	cout<<reverse(num,num+5);//逆置num[0]~num[5-1]
	for(int i=0;i<5;i++){
		cout<<num[i]<<' ';//输出逆置后的数组
	}
	return 0;
}

max 求最大

type max(type a,type b,comp);//返回a和b最大的一个
//comp 比较函数,可以为空

max_element 求区间最大

merge 合并

• 合并两个数组或容器
• 合并方式为循环从两个数组或容器的起始位置取最小值往目标数组或容器进行尾插,直到其中一个数组或迭代器取到末尾则将其余数据拼接到目标数组或容器

合并示例

将a={1,2,4,0}和b{2,3,1}合并到c{}
1.取得左端最小是a[0]=1,插入c={1},更新a={2,4,0},此时b={2,3,1}
2.取得左端最小是a[0]=2,插入c={1,2},更新a={4,0},此时b={2,3,1}
3.取得左端最小是b[0]=2,插入c={1,2,2},更新b={3,1},此时a={4,0}
4.取得左端最小是b[0]=3,插入c={1,2,2,3},更新b={1},此时a={4,0}
5.取得左端最小是b[0]=1,插入c={1,2,2,3,1},更新b={},此时a={4,0}
6.b为空,将a={4,0}插入c={1,2,2,3,1,4,0}

代码示例

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	/*
		返回值为目标数组指针或迭代器 
		merge(first1,last1,first2,last2,out,comp)
		[first1,last1)是参与合并的一号数组或容器范围 
		[first2,last2)是参与合并的二号数组或容器范围 
		out是存储结果的数组或迭代器 
		comp是比较函数,不填默认升序比较
		merge的前四个参数均使用数组指针或迭代器 
	*/
	int a[4]={1,2,4,0},
		b[5]={0,2,3,1,2},
		c[9];
	merge(a,a+4,b+1,b+1+3,c);//将[a,a+4)和[b+1,b+4)插入c 
	for(int i=0;i<7;i++) cout<<c[i]<<' ';
	return 0;
}

min 求最小

type min(type a,type b,comp);//返回a和b最小的一个
//comp 比较函数,可以为空

sort 排序

• 对数组或容器进行排序

//数组升序排序
sort(num+i,num+j);//使num下标从i到j-1的数据升序排列
int cmp(int a,int b){
	return a>b;
}

sort(num+i,num+j,cmp);//使num下标从i到j-1的数据降序排列,注意cmp没有括号()

//字符串升序排列
sort(s.begin(),s.end());

//字符串降序排列
int cmp(char a,char b){
	return a>b;
}
sort(s.begin(),s.end(),cmp);

swap 交换

• 交换两个变量的值

void swap(type a,type b);//交换a,b的值,a,b同类型

unique 去重

• 排序后去除重复元素
• unique去除的是相邻的相同元素

#include <iostream>
#include <algorithm>//需要使用算法库
using namespace std;
int main(){
	/*
		返回值:int* 整数类型数组地址或iterator迭代器,是去重后的新末尾地址
		unique(first,last,comp)
		first 去重起始位置 num+i s.begin()
		last 去重末尾位置+1 num+n s.end()
		comp 自定义比较函数,已知数据类型且有==比较符可以不填
    */
    
    int n=8;
	int num[8]={1,1,2,3,3,2,4,5};
	n=unique(num,num+8)-num;//-num才是去重后的长度
	for(int i=0;i<n;i++){
		cout<<num[i]<<' ';//输出去除相邻元素后的数组
	}
    return 0;
}

STL迭代器

• 除了少数重载过[]运算符的容器,要访问顺序容器和关联容器中的元素,需要通过"迭代器(iterator)"进行。迭代器是一个变量,相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素,通过迭代器就可以读写它指向的元素。从这一点上看,迭代器和指针类似。

四大迭代器

如下是迭代器的变量或常量定义方式
容器类名:iterator 迭代器名//正向迭代器
容器类名:const_iterator 迭代器名//正向常量迭代器
容器类名:reverse_iterator 迭代器名//逆向迭代器
容器类名:const_reverse_iterator 迭代器名//逆向常量迭代器

例如声明一个vector<int>的正向迭代器
vector<int>::iterator i;

C++11 auto语法糖

• auto代表自动数据类型,即自动识别数据类型,初始化时需要赋值才会识别类型

auto i=1;//i被识别为int型
auto j="1";//j被识别为string型
string s="111";
auto k=s.begin();//k被识别为string的正向迭代器

• 使用auto语法糖,可以简化迭代器声明的冗长前缀

迭代器用法示例

• 通过迭代器可以读取它指向的元素,*迭代器名就表示迭代器指向的元素。通过非常量迭代器还能修改其指向的元素。

• 迭代器都可以进行++操作

• • 对正向迭代器进行++操作时,迭代器会指向容器中的后一个元素
• • 对反向迭代器进行++操作时,迭代器会指向容器中的前一个元素

• 下面的程序演示了如何通过迭代器遍历一个 vector 容器中的所有元素

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> v;  //v是存放int类型变量的可变长数组，开始时没有元素
    for(int n=0;n<5;++n)
        v.push_back(n);  //push_back成员函数在vector容器尾部添加一个元素
    vector<int>::iterator i;  //定义正向迭代器
    for(i=v.begin();i!=v.end();++i) {  //用迭代器遍历容器
        cout<<*i<<" ";  //*i 就是迭代器i指向的元素
        *i*=2;  //每个元素变为原来的2倍
    }
    cout<<endl;
    //用反向迭代器遍历容器
    for(vector<int>::reverse_iterator j=v.rbegin();j!=v.rend();++j)
        cout<<*j<<" ";
    return 0;
}

提示1

• 对于如map容器来说,所存储的数据类型是pair,*迭代器名取得的是pair数据,若需输出键值可采用两种方法:

//假设存在map<int,char> mp,让i指向mp的begin元素
map<int,char>::iterator i=mp.begin();
cout<<(*i).first<<' '<<(*i).second;//方法1
cout<<i->first<<' '<<i->second;//方法2
//(*i).data和i->data即指针访问数据的两种方式,数据可以是常量变量也可以是函数

提示2

• 容器适配器stack,que和priority_queue没有迭代器,但有一些成员函数用来对元素进行访问。

提示3

• STL在重载++运算符时,后置形式比前置形式慢,循环次数很多时,++i和i++会有可观的运行时间差别。因此,应该养成写++i循环的习惯。

迭代器的功能分类

• 不同容器的迭代器，其功能强弱有所不同。容器的迭代器的功能强弱，决定了该容器是否支持 STL 中的某种算法。例如，排序算法需要通过随机访问迭代器来访问容器中的元素，因此有的容器就不支持排序算法。

• 常用的迭代器按功能强弱分为输入,输出,正向,双向,随机访问五种，这里只介绍常用的三种。

1. 正向迭代器。假设 p 是一个正向迭代器，则 p 支持以下操作：++p，p++，*p。此外，两个正向迭代器可以互相赋值，还可以用==和!=运算符进行比较。
2. 双向迭代器。双向迭代器具有正向迭代器的全部功能。除此之外，若 p 是一个双向迭代器，则–p和p–都是有定义的。–p使得 p 朝和++p相反的方向移动。
3. 随机访问迭代器。随机访问迭代器具有双向迭代器的全部功能。若 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作

• p+=i：使得 p 往后移动 i 个元素。
• p-=i：使得 p 往前移动 i 个元素。
• p+i：返回 p 后面第 i 个元素的迭代器。
• p-i：返回 p 前面第 i 个元素的迭代器。
• p[i]：返回 p 后面第 i 个元素的引用。

• 此外,两个随机访问迭代器p1,p2还可以用<,>,<=,>=运算符进行比较。p1<p2的含义是:p1经过若干次(至少一次)++操作后,就会等于p2。其他比较方式的含义与此类似。
• 对于两个随机访问迭代器p1,p2,表达式p2-p1也是有定义的,其返回值是p2所指向元素和 p1所指向元素的序号之差(也可以说是 p2 和 p1 之间的元素个数减一)。
  |容器|迭代器功能|
  |:-😐:-😐
  |vector|随机访问|
  |deque|随机访问|
  |list|双向|
  |set/multiset|双向|
  |map/multimap|双向|
  |stack|不支持迭代器|
  |queue|不支持迭代器|
  |priority_queue|不支持迭代器|

• 在 C++ 中，数组也是容器。数组的迭代器就是指针，而且是随机访问迭代器。例如，对于数组 int a[10]，int * 类型的指针就是其迭代器。则 a,a+1,a+2 都是 a 的迭代器。

迭代器的辅助函数

• STL 中有用于操作迭代器的三个函数模板
• • advance(p, n):使迭代器p向前或向后移动n个元素
• • distance(p, q):计算两个迭代器之间的距离，即迭代器p经过多少次++操作后和迭代器q相等。如果调用时p已经指向q的后面，则这个函数会陷入死循环
• • iter_swap(p, q):用于交换两个迭代器 p,q 指向的值
• 要使用上述模板，需要包含头文件algorithm

#include <list>
#include <iostream>
#include <algorithm> //要使用操作迭代器的函数模板，需要包含此文件
using namespace std;
int main()
{
    int a[5]={1,2,3,4,5};
    list<int> lst(a,a+5);
    list<int>::iteratorp=lst.begin();
    advance(p,2);  //p向后移动两个元素，指向3
    cout<<"1)"<<*p<<endl;  //输出 1)3
    advance(p,-1);  //p向前移动一个元素，指向2
    cout<<"2)"<<*p<<endl;  //输出 2)2
    list<int>::iterator q=lst.end();
    q--;  //q指向5
    cout<<"3)"<<distance(p, q)<<endl;  //输出 3)3
    iter_swap(p,q); //交换2和5
    cout<<"4)";
    for(p=lst.begin();p!=lst.end();++p)
        cout<<*p<< " ";
    return 0;
}

STL仿函数

• 仿函数被设计为搭配STL算法的函数对象,虽然函数指针也能作为算法参数,但函数指针不能满足STL对抽象性的要求。

• 所谓仿函数,即函数被设计为一个结构体或类,但是这个结构体或类被重载了()运算符,可以以匿名结构体或匿名类的()函数形式被调用。

自制仿函数

• 此处涉及C++模板编程及C++面向对象编程,仅作了解

#include <iostream>
using namespace std;

template<typename T>//模板制作仿函数
struct add{
	operator ()(T a,T b){//重载a+b 
		return a+b;//返回a+b 
	}
};

int main(){
	cout<<add<int>{}(1,3);//调用仿函数输出1+3 
	return 0;
}

• 由上述代码可知,仿函数的调用方法为函数名<模板类型表>{}(参数表)

STL仿函数

• 位于库functional
• algorithm已包含functional
• 仅介绍常用仿函数,用于作为算法的自定义函数参数

函数名	解释
equal_to	等于
not_equal_to	不等于
greater	大于
less	小于
greater_equal	大于等于
less_equal	小于等于

调用STL仿函数

#include <iostream>
#include <functional> 
using namespace std;
int main(){
	if(greater<int>{}(1,2)){//比较1>2 
		cout<<"1>2";
	}else{
		cout<<"1<2";
	}
	return 0;
}

使用STL仿函数作为参数

• 使得sort排序为降序的代码如下

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int num[5]={1,2,5,3,2};
	sort(num,num+5,greater<int>());
	//使用greater_equal有细微差别,结构体排序有影响
	for(int i=0;i<5;i++)
		cout<<num[i]<<' ';//输出排序结果 
	return 0;
}

参考文献

C++迭代器（STL迭代器）iterator详解(http://c.biancheng.net/view/338.html)

C++ STL无序容器（哈希容器）是什么？(http://c.biancheng.net/view/7230.html)

位运算（&、|、^、~、>>、<<）(https://www.runoob.com/w3cnote/bit-operation.html)

C++ bitset 用法(https://www.cnblogs.com/magisk/p/8809922.html)

STL之仿函数实现详解(https://blog.csdn.net/u010710458/article/details/79734558)

---

cout0于2021在重庆完成