火花机 东莞网站建设,兰州网站建设哪家公司好,宜都网站seo,安能物流网站C STL standard template libaray 标准模板库 目录 C STL standard template libaray 标准模板库 一、标准容器顺序容器vectordequelistvector deque list对比 容器适配器stackqueuepriority_queue 关联容器(1)无序关联容器unordered_setunordered_multisetunordered_mapunorde…C STL standard template libaray 标准模板库 目录 C STL standard template libaray 标准模板库 一、标准容器顺序容器vectordequelistvector deque list对比 容器适配器stackqueuepriority_queue 关联容器(1)无序关联容器unordered_setunordered_multisetunordered_mapunordered_multimap (2)有序关联容器setmultisetmapmutimap 二、迭代器iterator和const iteratorreverse_iterator和const_reverse_iterator 三、函数对象四、泛型算法 一、标准容器
顺序容器
vector
底层数据结构动态开辟的数组每次以原来空间大小的2倍进行扩容开辟两倍大小的新数组拷贝构造原数组对象析构原数组对象回收原数组内存
vectorint vec; 增加 vec.push_back(20); 末尾添加元素 O(1) 导致容器扩容 vec.insert(it,20); it迭代器指向的位置添加一个元素20 O(n) 导致容器扩容 删除 vec.pop_back(); 末尾删除元素 O(1) vec.erase(it); 删除it迭代器指向的元素 O(n) 查询 operator[] 下标的随机访问 vec[5] O(1) iterator 迭代器进行遍历 findfor_each foreach 底层通过iterator来实现的 常用方法介绍: size() empty() reserve(20)vector预留空间的 只给容器底层开辟指定大小的内存空间并不会添加新的元素 resize(20)容器扩容用的 不仅给容器底层开辟指定大小的内存空间还会会添加新的元素 swap两容器进行元素交换
注意1resize和reserver的区别 reserve预留空间 只给容器底层开辟指定大小的内存空间并不会添加新的元素 resize容器扩容 不仅给容器底层开辟指定大小的内存空间还会添加新的元素 vectorint ve;ve.reserve(20);//预留内存空间 coutve.empty()endl;//输出 1 coutve.size()endl;//输出 0ve.push_back(1); ve.push_back(2); ve.push_back(3); for(int x:ve) coutx ;//输出 1 2 3vectorint ve;ve.resize(10);//开辟空间 添加元素coutve.empty()endl;//输出 0 coutve.size()endl;//输出 10 ve.push_back(1); ve.push_back(2); ve.push_back(3); for(int x:ve) coutx ;//输出 0 0 0 0 0 0 0 0 0 0 1 2 3注意2vector调用clear()或者size(0),会清除容器内的所有元素但是不会释放内存,如果想释放内存需要调用shrink_to_fit()函数 vectorint ve{1,2,3,4,5,6,7,8,9,10};coutve.size()endl;//输出10 coutve.capacity()endl;//输出10ve. clear(); //ve.resize(0);coutve.size()endl;//输出0 coutve.capacity()endl;//输出10coutve[2]ve[2]endl;//输出3 因为元素清空了 内存没有清空 ve.shrink_to_fit();coutve.size()endl;//输出0 coutve.capacity()endl;//输出0注意3对容器进行连续插入或者删除操作(insert/erase)一定要更新迭代器否则第一次insert或者erase完成迭代器就失效了比如下面代码经典错误
#include iostream
#include vector
using namespace std;
int main() {vectorint ve{1,2,3,4,5,6,7,8,9,10};//把容器中所有的偶数删除auto it ve.begin();for(;it!ve.end();it) {if(*it%20){ve.erase(it);//错误迭代器已经失效了 }}for(int x:ve){coutx ;//输出为空}return 0;
}正确写法
#include iostream
#include vector
using namespace std;
int main() {vectorint ve{1,2,3,4,5,6,7,8,9,10};//把容器中所有的偶数删除auto it ve.begin();while(it!ve.end()){if(*it%20){it ve.erase(it);//删除之后返回迭代器位置 }else//迭代器指向的不是偶数才后移 {it;}}for(int x:ve){coutx ;//输出1 3 5 7 9 }coutendl;//给vector容器中所有的奇数前面都添加一个小于奇数1的偶数 for(itve.begin();it!ve.end();it){if(*it%2!0){it ve.insert(it,*it-1);//插入之后返回新的迭代器位置 it;//迭代器需要向后多移动一次保证不重复插入 }}for(int x:ve){coutx ;//输出0 1 2 3 4 5 6 7 8 9 }return 0;
}deque
底层数据结构动态开辟的二维数组二维双端队列一维数组从大小2开始以2倍的方式进行扩容每次扩容后原来的二维数组(固定长度)从新的第一维数组的下标oldsize/2开始存放上下都预留相同的空行方便支持deque的首尾元素添加
注意deque底层每一个第二维本身是连续的但是所有的二维不是连续的是重新new出来的(分段连续)
底层原理 一般编译器默认大小 #define MAP_SIZE 2 第一维度大小 #define QUE_SIZE 4096/sizeof(T) 第二维度大小 T为数据类型
1.初始的队头队尾指针在队列中间双端队列方便两头都可以插入删除 2.随着元素的插入队头队尾指针移动 3.当队列满的时候开辟新的二维空间 4.当所有队列满的时候进行2倍扩容(二维会放在一维中间位置) 操作 dequeint deq; 增加 deq.push_back(20); 从末尾添加元素 O(1) 可能扩容 deq.push_front(20);从首部添加元素 O(1) 可能扩容 deq.insert(it,20); it指向的位置添加元素 O(n) 可能扩容
删除: deq.pop_back(); 从末尾删除元素 O(1) deq.pop_front(); 从首部删除元素 O(1) deq.erase(it); 从it指向的位置删除元素 O(n)
查询搜索 iterator 连续的insert和erase一定要考虑迭代器失效的问题
list
底层数据结构双向的循环列表
list mylist; 增加 mylist.push_back(20); 从末尾添加元素 O(1) 可能扩容 mylist.push_front(20);从首部添加元素 O(1) 可能扩容 mylist.insert(it,20); it指向的位置添加元素 O(1) 可能扩容 往往需要先query查询操作 对于链表来说查询操作效率就比较慢
删除: mylist.pop_back(); 从末尾删除元素 O(1) mylist.pop_front(); 从首部删除元素 O(1) mylist.erase(it); 从it指向的位置删除元素 O(1)
查询搜索 iterator 连续的insert和erase一定要考虑迭代器失效的问题
vector deque list对比
vector特点动态数组内存连续2倍的方式进行扩容 deque特点动态开辟的二维数组空间第二维是固定长度的数组空间扩容的时候(第一维的数组进行2倍扩容) list特点双向循环链表
vector和deque之间的区别 1.底层数据结构 2.前中后插入删除元素的时间复杂度中间O(n)末尾都是O(1) 前插deque O(1) vector O(n) 3.对于内存的使用效率vector需要的内存空间必须连续deque可以分块进行数据存储不需要内存必须连续 4.在中间进行insert或者erase虽然时间复杂度都是O(n),但是vector都是连续空间比较方便deque的第二维内存空间不是连续的所以在deque中间进行元素的inset或者erase指令肯定更多造成元素移动的时候比vector要慢 deque和list比vector容器多出来的增加删除函数接口push_front() pop_front() vector和list之间的区别 数组和链表的区别 数组增加删除O(n) 查询O(n) 随机访问O(1) 链表增加删除O(1) 查询(n)
容器适配器
怎么理解适配器 1.适配器底层没有自己的数据结构它是另一个容器的封装它的方法全部由底层依赖的容器进行实现 2.没有实现自己的迭代器
底层实现
templatetypename T,typename ContainerdequeT
class Stack
{
public:void push(const T val){con.push_back(val);}void pop(){con.pop_back();}T top()const{return con.back();}
private:Container con;
};stack
先进后出 push():入栈 pop():出栈 top():查看栈顶元素 empty():判断栈空 size():返回元素个数
queue
先进先出 push():入队 pop():出队 front():查看队头元素 back():查看队尾元素 empty():判断队空 size():返回队列元素个数
priority_queue
底层数据结构大根堆 push():入队 pop():出队 top():查看队顶元素 empty():判断队空 size():返回元素个数
面试问题 stack和queue底层依赖deque为什么不依赖vector? 1.vector的初始内存使用效率太低了没有deque好(vector需要二倍扩容,deque初始二维就开辟了1024个数组空间) 2.对于queue来说需要支持尾部插入头部删除O(1)如果queue依赖vector其出队效率很低 3.vector需要大片连续内存而deque只需要分段的内存当存储大量的数据时显得deque对于内存的利用率更好一些 priority_queue底层依赖vector为什么不依赖deque? 底层默认把数据组成一个大根堆结构在一个内存连续的数组上构建一个大根堆和小根堆(父子节点需要通过下标计算) 关联容器
(1)无序关联容器
底层数据结构链式哈希表 增删查O(1)
unordered_set
#includeunordered_set 增加insert(val) 遍历iterator自己搜索调用find成员方法 删除erase(key) erase(it) 存在count()
unordered_multiset
#includeunordered_set #includeunordered_set 增加insert(val) 遍历iterator自己搜索调用find成员方法 删除erase(key) erase(it) 个数count()
unordered_map
#includeunordered_map
unordered_multimap
#includeunordered_map
#includeiostream
#includeunordered_map
#includestring
using namespace std;
/*map存储的是pair对象
class pair
{first;second;
}
*/
int main()
{unordered_mapint,string map;//插入 map.insert(make_pair(1000,张三));map.insert({1010,李四});map[1020] 王五;coutmap.size()endl;map.erase(1020);//删除 //查询 方式1 coutmap[1020]endl;//查询 方式2 auto it map.find(1000);if(it!map.end()){cout key:it-first value:it-second;}//遍历方式一 for(const pairint,string p:map){cout key:p.first value:p.second;} //遍历方式二 it map.begin();for(;it!map.end();it){cout key:it-first value:it-second;} return 0;
} 注意 1.map的operator[]不仅有查询功能如果key不存在它会插入一对数据[key,type()] 2.map存储的是pair对象
(2)有序关联容器
底层数据结构红黑树 增删查 O(log2n) n是底数(树的层数 树的高度)
set
multiset
#include 增加insert(val) 遍历iterator自己搜索调用find成员方法 删除erase(key) erase(it)
注意自定义类型需要重载运算符
#includeiostream
#includeset
#includemap
#includestring
using namespace std;
class Student
{
public:Student(int id,string name):_id(id),_name(name){}//重载小于运算符 bool operator(const Student stu)const{return _idstu._id;}
private:int _id;string _name; friend ostream operator(ostream out,const Student stu);
};
ostream operator(ostream out,const Student stu)
{outid:stu._id name:stu._nameendl;return out;
}
int main()
{setStudent set;set.insert(Student(1020,李四));set.insert(Student(1000,张文));for(auto itset.begin();it!set.end();it){cout*itendl;}return 0;
} map
#include
mutimap
#include
注意使用operator[]需要提供默认参数构造函数
#includeiostream
#includeset
#includemap
#includestring
using namespace std;
class Student
{
public:Student(int id0,string name):_id(id),_name(name){}
private:int _id;string _name; friend ostream operator(ostream out,const Student stu);
};
ostream operator(ostream out,const Student stu)
{outid:stu._id name:stu._nameendl;return out;
}
int main()
{mapint,Student mp;mp.insert({1000,Student(1000,张文)});mp.insert({1020,Student(1000,李广)});mp.insert({1030,Student(1000,高阳)});coutmp[1020]endl;//使用[]需要提供默认参数构造函数 (因为可能查询的key不存在则会构造一个新的对象)auto it mp.begin();for(;it!mp.end();it){coutkey:it-first value:it-second;} return 0;
} 二、迭代器
iterator和const iterator
const_iterator:常量的正向迭代器 只能读不能写 iterator:普通的正向迭代器
两种迭代器其实是继承关系class const_iterator{public:const T operator*(){//返回常引用 所以不能赋值 return *_ptr;}};class iterator : public const_iterator{public:T operator*(){//返回普通引用 可以赋值 return *_ptr;}}vectorint const_iterator it vec.begin();//子类的值赋值给父类 没毛病reverse_iterator和const_reverse_iterator
reverse_iterator:普通的反向迭代器 const_reverse_iterator:常量的反向迭代器 只能读不能写
#includeiostream
#includevector
using namespace std;
int main()
{vectorint vec;for(int i0;i20;i){vec.push_back(i);}//rbegin():返回的是最后一个元素的反向迭代器表示//rend():返回的是首元素前驱位置的迭代器的表示 auto rit vec.rbegin();for(;rit!vec.rend();rit){cout*rit ;}return 0;
} 三、函数对象
(1)什么是函数对象 把有operator()小括号运算符重载函数的对象称作为函数对象或者称为仿函数 (小括号运算符重载函数一个参数叫一元函数对象二个参数叫二元函数对象)
C语言实现两数之和
int sum(int a,int b)
{return ab;
}
int ret sum(10,20);C实现两数之和函数对象
class Sum
{
public:operator()(int a,int b){return ab;}
};
Sum sum;
int ret sum(10,20);(2)为什么使用函数对象 假如我们要实现比较两个数的大小使用C语言实现
templatetypename T
bool greater(T a,T b)
{return ab;
}
templatetypename T
bool less(T a,T b)
{return ab;
}
coutgreater(10,20)endl;
coutless(10,20)endl;使用函数指针实现
templatetypename T
inline bool mygreater(T a,T b)
{return ab;
}templatetypename T
inline bool myless(T a,T b)
{return ab;
}templatetypename T,typename Compare
bool compare(T a,T b,Compare comp)//第三个参数接收函数指针
{//通过函数指针调用函数是没有办法内联的效率很低因为有函数调用开销 return comp(a,b);
}
int main()
{coutcompare(10,20,mygreaterint)endl;coutcompare(10,20,mylessint)endl;return 0;
} 使用C函数对象的版本实现
templatetypename T
class mygreater
{
public:bool operator()(T a,T b){return ab;}
};
templatetypename T
class myless
{
public:bool operator()(T a,T b){return ab;}
};
templatetypename T,typename Func
bool compare(T a,T b,Func fun)//第三个参数为函数对象
{return fun(a,b);
}
int main()
{coutcompare(10,20,mygreaterint())endl;//第三个参数为函数对象 coutcompare(10,20,mylessint())endl;return 0;
} 1.通过函数对象调用operator()可以省略函数的调用开销比通过函数指针调用函数(不能够inline内联调用)效率高 2.因为函数对象是用类生成的所以可以添加相关的成员变量用来记录函数对象使用时的更多信息
(3)STL函数对象的使用 greater函数对象 从大到小 less函数对象 从小到大
举例1priority_queue 模板类原型第一个参数为类型第二个参数为容器第三个参数为函数对象(默认less)
//默认大根堆 从小到大排序 priority_queueint queMax;for(int i0;i10;i){queMax.push(rand()%1001);}while(!queMax.empty()){coutqueMax.top() ;queMax.pop(); }//小根堆 从大到小排序 using MinHeap priority_queueint,vectorint,greaterint;MinHeap queMin; for(int i0;i10;i){queMin.push(rand()%1001);}while(!queMin.empty()){coutqueMin.top() ;queMin.pop(); }举例2set模板类原型第一个参数是类型第二个参数是函数对象(默认less)第三个参数是容器空间配置器 setint,greaterint set;//小根堆 从大到小排列 for(int i0;i10;i){set.insert(rand()%100);}for(int v:set){coutvendl;}四、泛型算法
泛型算法 template 迭代器 函数对象 特点一泛型算法的参数接收的都是迭代器 特点二泛型算法的参数还可以接收函数对象(C函数指针)
绑定器 bindlst把二元函数对象的operator()(a,b)的第一个形参绑定起来 bind2nd把二元函数对象的operator()(a,b)的第二个参数绑定起来
sort
sort(vec.begin(),vec.end());//从小到大排序
sort(vec.begin(),vec.end(),greaterint());//从大到小排序 find 遍历查找 O(n) auto it1 find(vec.begin(),vec.end(),43);if(it1!vec.end()){cout43存在endl;}binary_search 有序容器二分查找 O(log2n) if(binary_search(vec.begin(),vec.end(),21)){cout52存在endl;}for_each 可以遍历容器的所有元素可以自行添加合适的函数对象对容器的元素进行过滤
//输出所有偶数 for_each(vec.begin(),vec.end(),[](int val)-void{if(val%20){coutval ;}});测试代码
#includeiostream
#includevector
#includealgorithm
using namespace std;int main()
{int arr[] {12,4,78,9,21,43,56,52,42,31};vectorint vec(arr,arrsizeof(arr)/sizeof(arr[0]));for(int v:vec){coutv ;} sort(vec.begin(),vec.end());//从小到大排序 for(int v:vec){coutv ;} //有序容器二分查找 O(log2n)if(binary_search(vec.begin(),vec.end(),21)){cout52存在endl;}//遍历查找 O(n)auto it1 find(vec.begin(),vec.end(),43);if(it1!vec.end()){cout43存在endl;}sort(vec.begin(),vec.end(),greaterint());//从大到小排序 for(int v:vec){coutv ;} //输出所有偶数 for_each(vec.begin(),vec.end(),[](int val)-void{if(val%20){coutval ;}});}
