C++ STL 复*总结

发布于:2021-10-21 19:32:56

STL 复*
1.STL概述
1.1 六大组件

容器 算法 迭代器 仿函数 适配器 空间配置器

1.2 容器 Container

序列式容器
关联式容器 //Key和Val

1.3 算法 algorithm

质变算法
非质变算法

1.4 迭代器 iterator

双向 //支持++ --
随机访问 (功能最强,可以支持跳跃式访问)//支持+1 2 3

1.5 优点

直接使用 高复用性 高性能 高移植性 数据和算法分离,利用迭代器进行沟通

2.String容器

char *是一个指针 String是一个类 封装了char*不用考虑内存越界等
string s1
string s2(s1)//拷贝构造
string s3("aaa");string s4(10,"a")//有参构造
s1.assign("abc",n)//前n字符个赋值
s1.assign("abc",n,m);//从第n个开始m个字符赋值
[] 和 s.at(i) 取值 //[]访问越界会down at越界抛出异常 out_of_range
s1 +=s2; s1.append(s2)//拼接
s1.find("a")//返回位置,否则-1 第二个默认参数0为起始查找位置
s1.rfind("a")//从右往左找
s1.replace(pos,n,"aaa")//从pos开始n个字符替换为aaa n不是截取aaa的个数是原字符串替换掉的个数
s1.compare(s2)//比较 0为= 正数为s1>s2 负数为s1s1 = s2.substr(pos,n)//从第pos开始截取n个
s1.insert(pos,"aa")//插入
s1.erase(pos,n)//删除pos开始的n个字符
char * str; string s(str);//char *转换为string 调用函数时可以隐式的抓换string
const char * str = s.c_str();//string转char * 不会隐式转换char *
toupper(s[i]) tolower(s[i])//转换大小写
当字符串内存重新分配时 原指针无效

3.vector容器

单端开口 Array静态空间 vector动态 动态空间大小是重新开辟空间并将原先数据拷贝至新内存,所以原有迭代器失效
v.capacity()//容器容量 扩展不是成倍扩展
vector v
vector v(10,100)//10个100有参构造
vector v(v1.begin(),v1.end());//end指向最后的下一位 左开右闭
v1.swap(v)//元素交换
v.resize(n)//重新指定容器长度 长增长默认0填充 短删除超出元素
v.resize(n,10)//第二个参数默认填充值
at []同string
v.front() v.back()//第一个和最后一个元素
v.insert(itreator,x)//插入 第一个迭代器 x为值
v.insert(itreator,n,x)//插入 第一个迭代器 n个数
v.pop_back()//尾删
v.erase(v.begin()) v.erase(v.begin(),v.end()) //删除
v.clear();v.erase(v.begin(),v.end())//清空
vector(v).swap(v);//利用swap收缩空间 利用拷贝构造初始匿名对象并交换 匿名对象自动释放 v指向新的收缩后内存
v.reserve(10000)//预留空间 减少因空间不足动态增加产生的操作消耗
vector::reverse_iterator it = v.rbegin();//逆序迭代器
vector::iterator it = v.begin(); it = it + i;//支持随机访问

4.deque容器

双端开口 可以头尾两端进行插入删除操作
没有容量概念 动态的以连续分段空间组合而成 中*鱇ey 缓冲区Val
deque d;
d.push_back(i)//尾插
d.push_front(i)//头插
d.pop_back()//删除最后一个数据
d.pop_front()//删除第一个数据

5.stack容器

//先进后出 不允许遍历 没有迭代器
stack s
s.empty() 是否为空
s.size() 大小
s.push(a) 入栈
s.pop() 弹出栈顶元素
s.top() 栈顶

6.queue容器

//队列 先进先出 不允许遍历 没有迭代器
queue q;
q.push(i)//入队
q.pop()//出队
q.front()//队头元素
q.back()//队尾元素
q.empty()

7.list容器

list对于vector对空间运用更精准 动态存储分配一次开辟一个 不会造成浪费和溢出
插入删除方便只需要修改指针 是一个循环的双向链表
链表灵活 但时间空间浪费较大(指针)
插入删除不会造成迭代器失效(vector内存重新分配会失效)
不支持随机访问
list l;
l.push_back(i);l.push_front(i);reverse_iterator it = l.begin();l.insert(l.begin(),i);
l.remove(elem)//删除所有与elem匹配的元素
l.reverse();//反转 逆序遍历是非质变的 反转质变
l.sort()// 所有系统提供的标准算法 使用的容器提供的迭代器必须支持随机访问 (这个是list容器自带的sort)
l.sort(myfunc())//myfunc()提供一个回调函数 对于自定义的类型 必须指定排序规则

8.set容器和multiset容器

关联式容器 会根据元素的键值自动排序
set的元素既是键值又是实值 所以不能通过set的迭代器(const_iterator)随意修改set元素值 因为有默认排序规则
set不允许有两个元素有相同键值
set和list某些相同 插入删除后 之前的迭代器依然有效
multiset容器 和set用法相同 底层都是红黑树 但允许键值重复
set s;
s.insert(i);//插入数据 内部自动排好序 唯一插入方式
s.erase(elem);//删除elem的元素
s.find(elem);//存在返回对应元素的迭代器(*pos可以取找到的值) 不存在返回end()迭代器
s.count(elem);//找elem个数 对于set要么1 要么0
set::iterator res = s.lower_bound(elem);//返回第一个key>=elem元素的迭代器
set::iterator res = s.upper_bound(elem);//返回第一个key>elem元素的迭代器
pair::iterator,set::iterator> res = s.equal_range(elem);//返回容器中key与elem相等的上下限的两个迭代器(对组)
res.first//lower_bound迭代器
res.second//upper_bound迭代器
pair::iterator,bool> res = s.insert(i);//res.second为bool体现是否插入成功

利用仿函数(普通回调函数只是指针 不能作为类型套入模板函数)指定排序规则//对自定义数据类型使用set时同样在插入之前指定排序规则
set s;
实现MyCompare类
class MyComapre
{
public:
bool operator()(const int a,const int b)
{
return a>b;
}
}
迭代器修改为 set::iterator it = begin();

9.map/multimap容器

同时拥有键值和实值 可以有两个相同实值不可以相同的键值 multimap可以重复
其他同set 底层红黑树
map m;
//插入
m.insert(pair(1,10));
m.insert(make_pair(2,20));
m.insert(map::value_type(3,30));
m[4] = 40;
//读取
map::iterator it = m.begin();
it->first 或者(*it).first

m.erase(key)//按照key删除
map::iterator pos = m.find(key)//返回迭代器 pos != end() 则查到

map::iterator res = m.lower_bound(key);//返回第一个容器中key>=key元素的迭代器
map::iterator res = m.upper_bound(key);//返回第一个容器中key>key元素的迭代器
pair::iterator,map::iterator> res = m.equal_range(key);//返回容器中key与key相等的上下限的两个迭代器(对组)
res.first//lower_bound迭代器 值为res.first->first
res.second//upper_bound迭代器 ......

指定排序规则
map m;//同set

10.STL使用时机

类型内存结构
vector单端数组 deque双端数组 list双向链表 set map二叉树
可以随机存取 vector deque //map的key而言不可以
元素查找速度 数组较慢 链表最慢 二叉树快
插入速度 vector尾插快 deque头尾快 list任何位置都快 二叉树不可以随意插入
vector 用于查找历史记录且不修改 deque 头尾修改方便
//vector的at效率高因为at(0)是固定的 释放效率也高 deque优点头部快速插入与移除
list 随机修改频繁
set 排序数据的存储
map 键值对应大量数据

11.函数对象(仿函数)

重载()运算符 使得类对象可以像函数一样使用 因此可以拥有自己的状态
函数对象可以作为函数的参数传递
函数对象可以内联编译(空间换时间)普通函数不行
可以配合模板使用set s;

12.谓词

普通函数或者仿函数返回值是bool类型 这样的称为谓词

13.内建函数对象

//#include sort(v.begin(),v.end(),greater());大于
//negate n;n(1);取反仿函数
//plus p;p(1,1);加法仿函数

14.适配器
14.1 函数对象适配器

bind2nd(MyPrint(),num)(顺序一致)和bind1st将两个参数绑定
继承binary_function<类型1,类型2,返回值类型>
加const

14.2 取反适配器

一元取反 not1
继承 unary_function<类型1,返回值类型>
加const
二元取反 not2

14.3 函数指针适配器

ptr_fun 将函数指针适配为函数对象

14.4 成员函数适配器

mem_fun_ref(&Person::showPerson()) 存放对象本体
mem_fun 存放对象指针

15.常用遍历算法

#include
for_each(v.begin(),v.end(),MyPrint)//回调函数
for_each(v.begin(),v.end(),MyPrint())//仿函数

transform(v1.begin(),v1.end(),v2.begin(),MyTransform())//v1-->v2 MyTransform()仿函数 需要提前重置v2的容器大小

16.常用查找算法

vector::iterator it = find(v.begin(),v.end(),elem);//查找元素elem 返回位置
对于自定义数据类型 重载 == 运算符//让编译器知道如何对比
find_if//按条件查找
adjacent_find(v.begin(),v.end())//查找第一个相邻的重复元素位置
bool ret = binary_search(v.begin(),v.end(),2)//二分查找法 无序序列不可以使用
int num = count(v.begin(),v.end(),elem)//按值统计个数
int num = count_if(v.begin(),v.end(),MyCompared());//按条件 调用仿函数

17.常用排序算法

#include
merge(v1.begin(),v1.end(),v2.begin(),v2.end());//首先对目标容器扩容 有序合并算法 前提两个有序的
sort(v.begin(),v.end(),greater())//默认内建函数 或者仿函数 回调函数
random_shuffie(v.begin(),v.end())//洗牌打乱函数 加随机种子 srand(unsigned int)time(NULL);
reverse(v.begin(),v.end())//反转

18.常用拷贝和替换算法

copy(v.begin(),v.end(),vTarget.begin())//拷贝
replace(v.begin(),v.end(),oldelem,newelem)//将old值替换为new值
replace_if(v.begin(),v.end(),MyCompare(),newelem)//按条件替换 (return val >elem)
swap(v1,v2)//互换

19.常用算数生成算法

#include
int num = accumulate(v.begin(),v.end(),0);//计算容器元素累加总和 第三个参数是起始累加值
fill(v.begin(),v.end(),elem)//向容器中添加元素 填充elem

20.常用集合算法

set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),vTarget.begin())//交集 根据目标集合大小提前扩容
set_union//并集
set_difference//差集

相关推荐

最新更新

猜你喜欢