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。
注意:负数按补码形式参加按位或运算。
或运算的用途
比如将数 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)即可得到。
例如: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型数据进行"与运算",右端对齐后,左边不足的位依下面三种情况补足,
- 如果整型数据为正数,左边补16个0。
- 如果整型数据为负数,左边补16个1。
- 如果整形数据为无符号数,左边也补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 头文件中,它是一种类似数组的结构,它的每一个元素只能是0或1,每个元素仅用1bit空间。
构造函数
bitset<4> bitset1;
bitset<8> bitset2(12);
string s="100101";
bitset<10> bitset3(s);
cout<<bitset1<<endl;
cout<<bitset2<<endl;
cout<<bitset3<<endl;
注意
- 用字符串构造时,字符串只能包含 ‘0’ 或 ‘1’ ,否则会抛出异常。
- 构造时,需在<>中表明bitset 的大小(即size)。
- 在进行有参构造时,若参数的二进制表示比bitset的size小,则在前面用0补充(如上面的例子);若比bitsize大,参数为整数时取后面部分,参数为字符串时取前面部分(如下面例子):
bitset<2> bitset1(12);
string s="100101";
bitset<4> bitset2(s);
cout<<bitset1<<endl;
cout<<bitset2<<endl;
可用操作符
- bitset有cin和cout
- cin按照二进制输入
- cout输出的是二进制数
bitset<8> foo;
cin>>foo;
cout<<foo;
bitset<8> foo;
foo=15;
cout<<foo;
foo=bitset<8>(string("00000001"));
cout<<foo;
bitset<4> foo(string("1001"));
bitset<4> bar(string("0011"));
cout<<(foo^=bar)<<endl;
cout<<foo&=bar)<<endl;
cout<<(foo|=bar)<<endl;
cout<<(foo<<=2)<<endl;
cout<<(foo>>=1)<<endl;
cout<<(~bar)<<endl;
cout<<(bar<<1)<<endl;
cout<<(bar>>1)<<endl;
cout<<(foo==bar)<<endl;
cout<<(foo!=bar)<<endl;
cout<<(foo&bar)<<endl;
cout<<(foo|bar)<<endl;
cout<<(foo^bar)<<endl;
- 可以通过 [ ] 访问元素(类似数组),注意最低位下标为0,如下:
bitset<4> foo("1011");
cout<<foo[0]<<endl;
cout<<foo[1]<<endl;
cout<<foo[2]<<endl;
可用函数
bitset<8> foo("10011011");
cout<<foo.count()<<endl;
cout<<foo.size()<<endl;
cout<<foo.test(0)<<endl;
cout<<foo.test(2)<<endl;
cout<<foo.any()<<endl;
cout<<foo.none()<<endl;
cout<<foo.all()<<endl;
bitset<8> foo ("10011011");
cout<<foo.flip(2)<<endl;
cout<<foo.flip()<<endl;
cout<<foo.set()<<endl;
cout<<foo.set(3,0)<<endl;
cout<<foo.set(3)<<endl;
cout<<foo.reset(4)<<endl;
cout<<foo.reset()<<endl;
bitset<8> foo ("10011011");
string s = foo.to_string();
unsigned long a = foo.to_ulong();
unsigned long long b = foo.to_ullong();
cout<<s<<endl;
cout<<a<<endl;
cout<<b<<endl;
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 n;
cin>>n;
while(n--){
int p;
cin>>p;
que.push_back(p);
}
while(!que.empty()){
cout<<que.front()<<' ';
que.pop_front();
}
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)
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int num[100]={2,1};
make_heap(num,num+2);
int n;
cin>>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--){
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 n;
cin>>n;
while(n--){
int p;
cin>>p;
l.push_back(p);
}
list<int> ll(l);
l.merge(ll,less<int>());
while(!l.empty()){
cout<<l.front()<<' ';
l.pop_front();
}
return 0;
}
map 映射
- #include <map>//映射库
-
x
→
y
x \to y
x→y称之为一个映射,map映射类似于一元函数,不同的
x
x
x可以映射到同一个
y
y
y,但一个
x
x
x不能映射多个
y
y
y
- char类型字符与ASCII值是一个映射关系
#include <map>
map<键的类型,值的类型> 变量名;
#include <iostream>
#include <map>
using namespace std;
int main(){
map<int,char> mp;
for(int i=1;i<=26;i++){
mp[i]='A'+i-1;
}
for(int i=1;i<=26;i++){
cout<<i<<':'<<mp[i]<<endl;
}
mp[27]='a';
cout<<mp[27]<<endl;
mp.erase(27);
if(mp.find(27)==mp.end()){
cout<<"键27不存在\n";
}else{
cout<<"键27存在\n";
}
mp.clear();
if(mp.empty()){
cout<<"map为空";
}
return 0;
}
multimap 多重映射
- 用法类似于map,但可以存取重复元素
- multimap未重载[]运算符,基元素类型是pair
- 需要库map
#include <iostream>
#include <map>
using namespace std;
int main(){
multimap<int,char> mp;
int n;
cin>>n;
while(n--){
int f;
char s;
cin>>f>>s;
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);
if(mp.find(1)==mp.end()) cout<<"key 1 not found.";
else cout<<"key 1 in multimap.";
mp.clear();
return 0;
}
multiset 多重集合
- 可以包含重复元素的集合
- 用法类似于set
- 包含于库set
#include <iostream>
#include <set>
using namespace std;
int main(){
multiset<int> s;
int n;
cin>>n;
while(n--){
int p;
cin>>p;
s.insert(p);
}
for(auto i=s.begin();i!=s.end();i++){
cout<<*i<<' ';
}
cout<<endl;
s.erase(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;
cin>>p.first;
cin>>p.second;
cout<<p.first<<' '<<p.second;
return 0;
}
priority_queue 优先队列
- 优先队列是允许插队的队列,优先权越高越靠前
- 优先队列默认优先权以>运算符识别,即大的在前面
- 可通过重载运算符或传入比较函数改变优先权判定
- 优先队列包含于queue
#include <queue>
priority_queue<int> que;
优先队列的成员函数
- push 入队
- pop 出队
- top 队头
- size 大小
- empty 队空
#include <iostream>
#include <queue>
using namespace std;
int main(){
priority_queue<int> que;
int n;
cin>>n;
while(n--){
int p;
cin>>p;
que.push(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<int> que;
int n;
cin>>n;
for(int i=0;i<n;i++){
int p;
cin>>p;
que.push(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 n;
cin>>n;
while(n--){
int p;
cin>>p;
s.insert(p);
}
for(auto i=s.begin();i!=s.end();i++){
cout<<*i<<' ';
}
cout<<endl;
s.erase(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<int> stk;
int n;
cin>>n;
for(int i=0;i<n;i++){
int p;
cin>>p;
stk.push(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 |
#include <iostream>
#include <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;
getline(cin,s2);
cout<<s1<<endl;
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;
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 n;
cin>>n;
while(n--){
int p;
cin>>p;
vec.push_back(p);
}
for(int i=0;i<vec.size();i++){
cout<<vec[i]<<' ';
}
cout<<endl<<"size:"<<vec.size();
vec.pop_back();
cout<<endl<<"size:"<<vec.size()<<endl;
vec.insert(vec.begin()+1,2);
for(int i=0;i<vec.size();i++){
cout<<vec[i]<<' ';
}
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> umap;
for(int i=1;i<=26;i++){
umap[i]='a'+i-1;
}
for (auto i=umap.begin();i!=umap.end();i++)
{
cout<<i->first<<" "<<i->second<<endl;
}
return 0;
}
STL算法
binary_search 二分查找
binary_search 二分查找
- 查找目标值是否在数组中,返回
b
o
o
l
bool
bool
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int num[5]={1,2,3,4,5};
cout<<binary_search(num,num+5,3);
return 0;
}
lower_bound和upper_bound 二分查找下标
- lower_bound 查找第一个大于等于value的位置
- upper_bound 查找第一个大于value的位置
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int num[5]={1,2,3,4,5};
cout<<lower_bound(num,num+5,3)-num;
return 0;
}
copy 复制
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int a[4]={1,2,4,0},
b[5];
copy(a,a+4,b);
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 num[5]={1,1,2,2,9};
cout<<count(num,num+5,2);
return 0;
}
count_if 计算满足条件的个数
#include <iostream>
#include <algorithm>
using namespace std;
int cmp(int n){
return n<4;
}
int main(){
int num[5]={1,1,2,2,9};
cout<<count_if(num,num+5,cmp);
return 0;
}
element 区间元素
max_element 区间最大
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
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(){
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(){
int num[9]={1,3,4,5,2,6,7,8,9};
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 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(){
int num[5];
fill(num,num+5,4);
for(int i=0;i<5;i++){
cout<<num[i]<<' ';
}
return 0;
}
reverse 逆置
#include <iostream>
#include <algorithm>
int main(){
int num[5]={1,1,2,2,9};
cout<<reverse(num,num+5);
for(int i=0;i<5;i++){
cout<<num[i]<<' ';
}
return 0;
}
max 求最大
type max(type a,type 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(){
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);
for(int i=0;i<7;i++) cout<<c[i]<<' ';
return 0;
}
min 求最小
type min(type a,type b,comp);
sort 排序
sort(num+i,num+j);
int cmp(int a,int b){
return a>b;
}
sort(num+i,num+j,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);
unique 去重
- 排序后去除重复元素
- unique去除的是相邻的相同元素
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n=8;
int num[8]={1,1,2,3,3,2,4,5};
n=unique(num,num+8)-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;
auto j="1";
string s="111";
auto k=s.begin();
迭代器用法示例
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
for(int n=0;n<5;++n)
v.push_back(n);
vector<int>::iterator i;
for(i=v.begin();i!=v.end();++i) {
cout<<*i<<" ";
*i*=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>::iterator i=mp.begin();
cout<<(*i).first<<' '<<(*i).second;
cout<<i->first<<' '<<i->second;
提示2
- 容器适配器stack,que和priority_queue没有迭代器,但有一些成员函数用来对元素进行访问。
提示3
- STL在重载++运算符时,后置形式比前置形式慢,循环次数很多时,
++i
和i++
会有可观的运行时间差别。因此,应该养成写++i
循环的习惯。
迭代器的功能分类
-
不同容器的迭代器,其功能强弱有所不同。容器的迭代器的功能强弱,决定了该容器是否支持 STL 中的某种算法。例如,排序算法需要通过随机访问迭代器来访问容器中的元素,因此有的容器就不支持排序算法。
-
常用的迭代器按功能强弱分为输入,输出,正向,双向,随机访问五种,这里只介绍常用的三种。
- 正向迭代器。假设 p 是一个正向迭代器,则 p 支持以下操作:++p,p++,*p。此外,两个正向迭代器可以互相赋值,还可以用==和!=运算符进行比较。
- 双向迭代器。双向迭代器具有正向迭代器的全部功能。除此之外,若 p 是一个双向迭代器,则–p和p–都是有定义的。–p使得 p 朝和++p相反的方向移动。
- 随机访问迭代器。随机访问迭代器具有双向迭代器的全部功能。若 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);
cout<<"1)"<<*p<<endl;
advance(p,-1);
cout<<"2)"<<*p<<endl;
list<int>::iterator q=lst.end();
q--;
cout<<"3)"<<distance(p, q)<<endl;
iter_swap(p,q);
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){
return a+b;
}
};
int main(){
cout<<add<int>{}(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)){
cout<<"1>2";
}else{
cout<<"1<2";
}
return 0;
}
使用STL仿函数作为参数
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int num[5]={1,2,5,3,2};
sort(num,num+5,greater<int>());
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在重庆完成
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)