网站收录有什么好处,成都网站公司建设,河北建设工程信息网官网入口,比较大的做网站的公司文章目录 零、标准模板库 STL一、容器 (Container)1.序列式容器(1)vector2.五种遍历10.vector的迭代器失效问题 (2)deque(3)list 2.关联式容器(1)set4.set的查找(2)find() 8.set中存储自定义类型#xff1a;三种方法 (2)multiset7.multiset的特殊操作#xff1a;bound系列函数… 文章目录 零、标准模板库 STL一、容器 (Container)1.序列式容器(1)vector2.五种遍历10.vector的迭代器失效问题 (2)deque(3)list 2.关联式容器(1)set4.set的查找(2)find() 8.set中存储自定义类型三种方法 (2)multiset7.multiset的特殊操作bound系列函数 (3)map(4)multimap(5)关联式容器总结 3.无序关联式容器(0)哈希(1)unordered_set6.unordered_set针对自定义类型的改写 (2)unordered_multiset(3)unordered_map(4)unordered_multimap(5)无序关联式容器总结 4.容器的选择 二、迭代器 (iterator)1.概念2.迭代器产生的原因3.迭代器的类型(1)双向迭代器(2)随机访问迭代器 4.流迭代器(1)输出流迭代器(2)输入流迭代器 三、算法1.概念(1)概述(2)头文件(3)分类(4)一元函数、一元断言/一元谓词 2.copy3.for_each的使用4.lambda表达式匿名函数 (lambda函数)5.remove_if的使用 四、适配器1.迭代器适配器(1)反向迭代器reverse_iterator(2)迭代器适配器三组插入迭代器是特殊的输出迭代器 2.容器适配器(1)stack (栈)(2)queue (队列)(3)priority_queue (优先级队列) 3.函数适配器(1)函数绑定器bind1st、bind2nd、bind①bind1st和bind2nd的使用②bind函数的使用7.占位符 function (2)mem_fun 五、函数对象六、空间配置器 (allocator) 【面试加分项】1.概述2.四个函数3.两级空间配置器(1)一级空间配置器(2)二级空间配置器 4.空间配置器的源码剖析(1)allocate()(2)deallocate()(3)construct()(4)destroy() C编程思想 1.C语言的面向过程编程 2.C的面向对象编程 3.STL的泛型编程 零、标准模板库 STL
STL六大组件按顺序分别是 ①容器Containers数据结构用于存储和组织数据。 ②算法Algorithms操作容器中的元素的函数如排序、搜索等。 ③迭代器Iterators用于遍历容器中的元素。 ④仿函数Functors行为类似函数的对象通常用于自定义算法中的操作。 ⑤适配器Adapters修改容器、迭代器或仿函数行为的工具。 ⑥分配器Allocators负责内存分配和管理。
1.容器用来存放数据也称为数据结构。 ①序列式容器vector、list、deque ②关联式容器set、map ③无序关联式容器unordered_set、unordered_map
2.迭代器泛型指针用来访问容器中的元素。存在失效的情况。
3.算法用来操纵容器中的元素。在STL中这些算法都是普通函数(非成员函数)
4.适配器当算法和容器不匹配时用适配器进行匹配。起到适配的效果。 ①容器的适配器stack、queue、priority_queue ②迭代器的适配器 ③函数适配器bind、mem_fn、bind1st、bind2nd
5.函数对象 (仿函数)类重载了函数调用运算符()对象就可以像函数一样使用。起到定制化操作。比如删除器deleter对于智能指针可以定制删除器去回收FILE *
6.空间配置器 Allocator进行申请和释放空间。所有与空间相关的操作都在该类中。(用法原理源码) 一、容器 (Container)
1.序列式容器
三种序列式容器 vector(动态数组)、deque(双端队列)、list(双向链表) ①初始化容器对象都支持五种初始化方式 ②遍历容器中的元素vector、deque支持三种遍历list支持两种遍历。list不支持下标访问。 ③在容器的尾部进行插入和删除都支持 push_back 和 pop_back ④在容器的头部进行插入和删除仅deque和list支持vector不支持 ⑤在容器的任意位置插入和删除vector、deque、list都支持四种insert()。对于list每次插入完成后迭代器都只与结点有关deque要看插入的是前一半还是后一半因为元素挪动是不一样的迭代器还指向原位置可能*it输出不同对于vector插入时底层可能发生扩容造成迭代器失效进而产生bug。 ⑥清空元素clear()。三者都有 ⑦获取元素个数size()三者都有。 获取容器空间大小capacity()只有vector有。 ⑧回收多余空间shrink_to_fit()只有vector和deque有。 ⑨交互容器中的内容swap()。vector、deque、list都支持swap函数只能用于相同类型的STL容器。 ⑩更改容器的大小resize()。vector、deque、list都支持 11.获取第一个元素front() 获取最后一个元素end() 12.emplace系列函数直接在容器中生成对象(只有一次构造)避免创建临时对象后再拷贝到容器中 (一次构造一次拷贝) (1)vector
1.初始化容器对象(五种)创建vector
//1.vector的创建和初始化
//1.创建无参对象
vectorint vec;//2.count个value
vectorint vec2(3,6);//3.迭代器范围
vectorint vec3(vec2.begin(), vec2.end()); //[,)左闭右开的区间//4.拷贝构造或移动构造函数
vectorint vec4 vec3;
vectorint vec44 std::move(vec4); //move后,vec4为空//5.初始化列表 { }
vectorint vec5{10,9,8,7,6}; //直接初始化
vectorint vec55 {10,9,8,7,6}; //拷贝初始化vec4 {10,9,8,7}; //赋值操作必须用等号2.五种遍历
(1)下标
//1.下标
for(size_t idx 0; idx ! number.size(); idx){cout number[idx] ;
}
cout endl;(2)迭代器
//2.迭代器
vectorint::iterator it; //未初始化迭代器
for(it number.begin(); it ! number.end(); it){cout *it ;
}
cout endl;vectorint::iterator it2 number.begin(); //初始化迭代器
for( ; it2 ! number.end(); it2){cout *it2 ;
}
cout endl;for(auto it3 number.begin(); it3 ! number.end(); it3){ //初始化迭代器cout *it3 ;
}
cout endl;(3)增强for循环
//3.增强for循环
for(auto elem : vec){ //引用:避免拷贝cout elem ;
}
cout endl;变成函数 (函数模板)
template typename Container
void display(const Container con){for(auto elem : con){cout elem ;}cout endl;
}(4)输出流迭代器
using std::ostream_iterator;//4.第四种遍历方式:利用输出流迭代器 (遍历容器中的元素)
copy(vec.begin(), vec.end(), ostream_iteratorint(cout, )); //右值临时对象
cout endl;(5)for_each() lambda表达式
//5.第五种遍历: for_each() lambda表达式 //头文件algorithm
for_each(vec.begin(), vec.end(), [](int value){ cout value ; }); //只用for_each,没配合lambda表达式就比较麻烦了。
void func(int value){cout value ;
}void test(){vectorint vec {1,4,7,9,5,2};for_each(vec.begin(), vec.end(), func); cout endl;
}3.尾部进行插入和删除 (三种序列式容器都支持) push_back() pop_back() 4.头部进行插入和删除 (仅deque、list支持vector不支持头部增删) push_front() pop_front()
因为vector只有一段是开口的内部是连续的若在内部增删则所有元素都需要向前或向后移动时间复杂度为O(n)。
插入还可以用插入迭代器 5.vector的底层实现 三个指针 ( sizeof(vec) 等于 24 ) _M_start指向第一个元素的位置 _M_finish指向最后一个元素的下一个位置 _M_end_of_storage指向当前分配空间的最后一个位置的下一个位置 6.vector的源码 vector的下标访问运算是不安全的有越界的风险但是at函数可以防止越界。所以vector中 下标访问
at函数
push_back 扩容2倍 pop_back 7.获取vector第一个元素的首地址 8.vector的自动扩容一个一个插入时size()超过capacity()时会两倍扩容。
9.在任意位置插入insert() (1)迭代器指向位置不变所以输出的*it会改变。 (2)若发生了自动扩容it还是指向旧空间导致*it输出可能是负数。这就是vector的迭代器失效问题。 (3)vector的insert的扩容同resize() ①插入后 size() capacity()不需要扩容 ②插入后 capacity() size() 2*capacity()两倍扩容 ③插入后 size() 2*capacity()则capacity()扩容到和size()一样大 10.vector的迭代器失效问题
1.vector的迭代器失效问题 vector在进行插入后底层发生了自动扩容。导致此时vector的内容已经转移到另一片空间vector.end()已经改变。而其迭代器 vector::iterator it还指向原本的旧空间就发生了迭代器失效的问题。
2.解决方案每次插入后或每次使用迭代器之前重置迭代器。
it vec.begin();
it 2;举例
解决重置迭代器
#include iostream
#include vector
using std::cout;
using std::endl;
using std::vector;void test(){vectorint vec;vec.reserve(2);vec.push_back(111);vec.push_back(222);bool flag true;for(auto it vec.begin(); it ! vec.end(); it){cout *it ;//打印出第一个数后进入插入发生扩容重置迭代器。然后it打印第二个数if(flag){ cout push_back(333) endl;vec.push_back(333); //发生扩容,则迭代器失效flag false;it vec.begin(); //重置迭代器}}cout endl;
}int main()
{test(); return 0;
} 11.vector的删除erase() (重要) vector的erase()只有两种没有set的删除指定元素。 erase(it)删除一个元素时后面的元素会自动前移。 举例vector删除连续重复元素
//题意删除vector中所有值为4的元素。
vectorint vec {1, 3, 5, 4, 4, 4, 4, 7, 8, 4, 9};
for (vectorint::iterator it vec.begin(); it ! vec.end(); it){if(4 *it){vec.erase(it);}
}
//发现删除后有些4没有删除掉,可以推测出是什么原因吗是那些4没有删除呢
//答案:是因为vector删除的时候,后面的元素会自动前移一格。这时候再it,
//就会漏掉删除位置后面的那个元素//正确解法
for (auto it vec.begin(); it ! vec.end();){if (4 *it){vec.erase(it);}else{it;}
}12.vector的元素清空clear() 13.vector的回收多余空间shrink_to_fit() 将capacity()减少到和size()相等。 14.交互两个vector中的内容swap() deque和list也支持swap()。 swap函数只能用于相同类型的STL容器。 15.vector更改容器的大小resize() deque、list也有resize() resize()比capacity()大时底层会发生扩容。 小于2倍capacity()则两倍。大于两倍则resize()。 16.vector的尾部插入自定义类型对象emplace_back() emplace_back()比起push_back()少一次拷贝构造直接在容器内部构造对象避免了临时对象的创建和拷贝操作。 一般情况是构造临时对象、拷贝构造 emplace_back()的情况是在容器内部直接构造对象。只有一次构造没有拷贝。 deque、list也有emplace_back() 17.vector获取容器的第一个元素front() vector获取容器的最后一个元素back() (2)deque
经测试发现deque的初始化、遍历、尾部插入和删除和vector相同。deque还支持头部增删。
1.deque的五种创建和初始化
//1.创建无参对象
dequeint dq;//2.count个value
dequeint dq2(3,6);//3.迭代器范围
dequeint dq3(dq2.begin(),dq2.end());//4.拷贝构造或移动构造函数
dequeint dq4 dq3;
dequeint dq44 std::move(dq4); //move后dq4为空//5.初始化列表 { }
dequeint dq5{11,12,13,14,15}; //直接初始化
dequeint dq55 {15,14,13,12,11}; //拷贝初始化dq4 dq5;
dq4 {20,20,20}; //直接赋值必须用赋值号5.deque的底层实现 deque是由多个片段组成的片段内部是连续的但是片段之间不连续的分散的多个片段被一个称为中控器的结构控制所以说deque是在物理上是不连续的但是逻辑上是连续的。 从继承图中可以看到 (1)中控器其实是一个二级指针 _Tp** _M_map指向一个指针数组(即中控器数组)每个指针指向一个片段 (缓冲区)。size_t _M_map_size表示中控器数组的大小。中控器数组满了也会扩容。 (2)deque的迭代器也不是一个简单类型的指针其迭代器是一个类类型deque有两个迭代器指针一个指向第一个小片段一个指向最后一个小片段。 其结构图如下
_Tp** _M_map;
size_t _M_map_size;deque逻辑上是连续的物理上片段是分散的 6.deque的源码 7.deque在中间位置插入 在前面一半移动前一半。 在后面一半移动后一半。 迭代器指向是可能改变的*it可能会变。 8.deque的元素清空clear() 9.deque的回收多余空间shrink_to_fit() deque没有capacity()函数 10.deque的emplace插入自定义类型对象少一次拷贝构造 ①emplace() 对应于 insert() ②emplace_back() 对应于 push_back() ③emplace_front() 对应于 push_front() (3)list
list是双向链表。
经测试发现list的构建、头部增删和vector相同。list支持头部增删。
特殊点对于list不支持下标访问运算符[]。
1.list的五种创建和初始化
//1.创建无参对象
listint ls;//2.count个value
listint ls2(5,6);//3.迭代器范围
listint ls3(ls2.begin(),ls2.end());//4.拷贝构造或移动构造
listint ls4 ls3;
listint ls44 std::move(ls4);//5.初始化列表 { }
listint ls5{1,2,3,4,5}; //直接初始化
listint ls55 {5,4,3,2,1}; //构造初始化2.list的删除 (1)erase() ①删除单个元素
iterator erase(iterator pos);②删除一个范围内的元素
iterator erase(iterator first, iterator last);(2)remove()删除所有等于指定值的元素
void remove(const T value);举例删除连续重复函数
//list的删除
void test2()
{//删除连续重复元素:删除list中所有的2listint ls {1,2,2,2,3,4,5,2,2,2,6,7,8,2,2,9};#if 0for(auto it ls.begin(); it ! ls.end(); ){if(*it 2){it ls.erase(it);}else{it;}}#endifls.remove(2);display(ls);
}3.在容器的任意位置插入在中间任意位置插入insert()
插入完成后list的迭代器指向不变还是最初的元素。
//list的插入:尾部插入、首部插入、4种中间插入
void test(){listint ls {4,5,6,7};//尾部插入ls.push_back(8);//头部插入ls.push_front(1);//遍历打印display(ls); //1 4 5 6 7 8//四种中间插入:insert()//1.第一种中间插入:找一个迭代器位置,插入一个元素auto it ls.begin();it; //4ls.insert(it, 2);display(ls);cout *it *it endl;//2.第二种中间插入:找一个迭代器位置,插入count个元素ls.insert(it, 2, 3);display(ls);cout *it *it endl;//3.第三种中间插入:找一个迭代器位置,插入迭代器范围的元素vectorint vec {999,1111};ls.insert(it, vec.begin(), vec.end());display(ls);cout *it *it endl;//4.第四种中间插入:找一个迭代器位置,插入大括号范围内的元素it ls.begin();it; //2ls.insert(it, {500, 400, 300});display(ls);cout *it *it endl;
}4.list的迭代器是双向迭代器不是随机访问迭代器只能it不支持it 2。只能一次一次偏移。 5.list清空函数clear() 6.list没有shrink_to_fit()list也没有capacity()。因为有size()。 7.list的特殊操作 (1)反转reverse()
listint ls{1,2,3,4,5,6};
ls.reverse(); //list反转
display(ls); //6,5,4,3,2,1(2)排序sort()
ls.sort(); //无参,默认从小到达
ls.sort(std::lessint()); //从小到大。要加小括号代表是创建一个对象
ls.sort(std::greaterint()); //从大到小。要加小括号代表是创建一个对象函数参数里传的是对象模板参数里传的是类型 加小括号代表是创建一个对象。
自定义比较逻辑 (3)去除连续重复元素unique() 直接使用只能去除连续重复的元素。间隔的重复元素无法去除。 若想要去除所有重复元素需要先排序。
ls.sort();
ls.unique();(4)合并链表merge() 如果要求合并后自动有序(升序)则要求两个链表合并前也各自有序(升序)。 两个链表合并之后被合并的链表就为空了。 (5)移动元素splice() ①全部移动
number.splice(it, other); //1.全部移动②移动一个元素
number.splice(it, other, it2); //2.移动一个指定位置的一个元素③将迭代器范围内的元素进行移动
number.splice(it, other, it2, it3); //左闭右开 [,),右边取不到举例LRU算法可以直接使用splice()
代码链接https://github.com/WangEdward1027/STL/blob/main/list/list_splice.cpp 8.list的底层实现 9.总结 ①对于vector而言前后元素的地址是完全连续的。 ②对于deque而言前后两个元素是逻辑上连续物理上不连续 ③对于list而言前后两个元素是不连续的。 2.关联式容器
(1)set
#include set
using std::set;//set的类模板共有3个模板参数,后两个模板参数有默认值
template class Key,
class Compare std::lessKey,
class Allocator std::allocatorKey
class set1.四种初始化方式。 比起vector少了第二种插入count个相同元素。因为set会去重。 2.两种遍历方式 比起vector少了第一种。set不支持取下标。 3.set的特点 ①去重key值唯一 ②按key值升序排序 ③set的底层实现红黑树 4.set的查找
(1)count() 返回set中该元素的个数为0或1
(2)find()
若能找到该元素返回指向它的迭代器。 若找不到返回尾后迭代器。
auto it myset.find(7);
if(it ! myset.end()){cout 查找成功 *it endl;
}else{cout 查找失败,该元素不在set中 endl;
}5.set的插入insert() 三种插入比起vector少了插入count个元素
①set插入一个元素
pairsetint::iterator, bool ret s.insert(7);
if(ret.second){cout 插入成功: *ret.first endl;
}else{cout 插入失败,该元素存在set中 endl;
}②set插入迭代器范围的元素
//2.插入迭代器范围的元素
cout set迭代器范围的元素 endl;
vectorint vec{8,9,10};
s.insert(vec.begin(), vec.end());
display(s);③set插入大括号范围的元素
s.insert({11,12,13,14,15});多个返回结果tuple (可变参数) 6.set的三种删除erase() ①删除指定元素
s.erase(10); //删除元素10②删除迭代器指定位置
s.erase(it);③删除迭代器范围的元素
s.erase(it,it2);代码链接https://github.com/Edward/STL/blob/main/set/set_insert.cpp 7.set不支持下标访问不支持通过*it 进行修改。 因为set的底层是红黑树。 (RBT是一个稳定的数据结构为了维持稳定性所以不支持修改read-only) 报错太多可以使用错误重定向然后搜索error 错误重定向2 8.set中存储自定义类型三种方法
方法一模板的特化版本模板特化 优先于方法二 方法二运算符重载的版本重载operator运算符可以比较Point类型 方法三函数对象的版本自己写Compare类创建set的的时候里需要写第二个模板参数。若传第二个参数则一定走方法三若不传则一定不走。 代码链接https://github.com/WangEdward1027/STL/blob/main/set/set_custom_type.cpp
方法一 写库的人写法
特化写法
//方法一:模板特化的版本:模板特化
//如果第二个模板参数不传,走std::less,则模板特化的优先级高于重载operator//库里的std::less源码是这样写的
/* namespace std{ */
/* templateclass T */
/* struct less */
/* { */
/* bool operator()(const T lhs, const T rhs) const{ */
/* return lhs rhs; */
/* } */
/* }; */
/* } *///我们对其进行类模板特化:类模板的全特化
namespace std{
template
struct lessPoint
{bool operator()(const Point lhs, const Point rhs) const{/* return lhs rhs; */cout template struct lessPoint endl;if(lhs.getDistance() rhs.getDistance()){return true;}else if(lhs.getDistance() rhs.getDistance()){if(lhs.getX() rhs.getX()){return true;}else if(lhs.getX() rhs.getX()){if(lhs.getY() rhs.getY()){return true;}else{return false;}}else{return false;}}else{return false;}}
};
}方法二重载operator运算符
//方法二:运算符重载的版本:重载operator运算符可以比较Point类型
//全局普通函数声明为友元形式重载operator
bool operator(const Point lhs, const Point rhs){cout bool operator endl;//先比距离,再比横坐标,再比纵坐标if(lhs.getDistance() rhs.getDistance()){return true;}else if(lhs.getDistance() rhs.getDistance()){if(lhs._ix rhs._ix){return true;}else if(lhs._ix rhs._ix){if(lhs._iy rhs._iy){return true;}else{return false;}}else{return false;}}else{return false;}
}hypot可以直接得到两个数的平方和再开根
#include math.hfloat getDistance() const{return hypot(_ix, _iy); //求点到原点的距离
}方法三自定义比较类型
//方法三:函数对象的版本:自己写Compare类
struct ComparePoint{bool operator()(const Point lhs, const Point rhs) const {cout struct ComparePoint endl;if(lhs.getDistance() rhs.getDistance()){return true;}else if(lhs.getDistance() rhs.getDistance()){if(lhs._ix rhs._ix){return true;}else if(lhs._ix rhs._ix){if(lhs._iy rhs._iy){return true;}else{return false;}}else{return false;}}else{return false;}}
};void test(){/* setPoint number { */setPoint, ComparePoint number { Point(1,0),Point(0,1),Point(1,1),Point(1,1),Point(2,0),};display(number);
}(2)multiset
#include set
using std::multiset;1.四种创建 和set一样
2.两种遍历
3.特点 ①multisetkey值可以重复的set ②multiset不支持下标底层是红黑树
4.查找 ①count() ②find()
5.插入insert() 必定成功返回值就是迭代器
6.删除erase()
7.multiset的特殊操作bound系列函数
①lower_bound()返回第一个大于等于(不小于)所给定的key值的迭代器 ②upper_bound()返回第一个大于所给的的key值的迭代器 ③equal_range()返回等于给的key值的范围。是两个迭代器返回一个 std::pair其中包含两个迭代器first指向第一个大于等于(不小于) value 的元素。second指向第一个大于 value 的元素。即pairlower_bound(),upper_bound()。
8.针对于自定义类型的写法 对于multiset而言也需要实现第二个模板参数Compare实现方法与set完全一样。即三种形式模板的特化、运算符重载、函数对象。 (3)map
1.四种创建map
(1)三种构建pair的方法 ①大括号
{1,beijing};②pair , ( ) 直接构建临时pair对象
pairint,string(4,wd);③make_pair
make_pair(2,wuhan);2.map的特征 ①存放的是key-value类型 ②key值唯一会进行去重 ③按照key值进行升序排列 ④map的底层也是红黑树 降序排序 mapint,string,std::greaterint number { }; 3.查找 ①count() ②find() 4.插入 (1)三种insert (和set一致) ①插入一个元素返回值是pair ②插入迭代器范围内的元素返回值是迭代器 ③插入大括号范围内的元素返回值是迭代器 (2)emplace插入 5.map的删除操作 ①按键删除 (erase(const Key key)) ②按迭代器删除 (erase(iterator position)) ③按迭代器范围删除 (erase(iterator first, iterator last)
// 删除键为banana的元素
int numRemoved wordFrequency.erase(banana);// 删除指向banana的迭代器所指向的元素
auto it wordFrequency.find(banana);
if (it ! wordFrequency.end()) {wordFrequency.erase(it);
}// 删除从banana到date之前的元素
auto first wordFrequency.find(banana);
auto last wordFrequency.find(date);
if (first ! wordFrequency.end() last ! wordFrequency.end()) {wordFrequency.erase(first, last);
}6.map的下标操作 (1)取下标mymap[key]得到value (2)key值存在就是查找。key值不存在就会插入key和空的value (3)可以根据下标进行修改 (4)map的下标操作只重载了非const版本的operator[]。则const Map无法使用下标访问。
number test2; //修改运算符重载本质
number[6] test2; //修改
number.operator[](6).operator(test2);7.mapKey,Value 若Key是自定义类型Key不能进行比较大小则和set针对自定义类型一样用三种方法进行改写模板特化、运算符重载、传函数对象 (4)multimap
1.multimapKey值不唯一可以重复
2.与map的不同 (1)插入必定成功 (2)因为Key值不唯一故无法通过Key值取下标。 (5)关联式容器总结
1.元素是有序的。 2.底层使用的都是红黑树查找的时间复杂度为O(logn)。 3.set与map中的key是唯一的不能重复。 multiset、multimap中的key是不唯一的可以重复。 4.关联式容器中只有map支持下标访问而set、multiset、multimap不支持下标访问。 map下标传递的是Key类型返回值是Value类型。并且下标访问运算符没有重载const版本。 5.关联式容器对自定义类型的改写 ①模板的特化 ②函数对象的形式 ③重载operator 3.无序关联式容器
(0)哈希
1.哈希函数 通过key值计算出位置值
size_t index H(key)//由关键字获取所在位置 2.哈希函数的构建方式
定址法: H(key) a * key b
平方取中法: key^2 1234^2 1522756 ------227
数字分析法: H(key) key % 10000
除留取余法: H(key) key mod p (p m, m为表长)3.哈希冲突 就是对于不一样的key值可能得到相同的地址,即:H(key1) H(key2)
H(key1) H(key2), key1 ! key24.解决哈希冲突 ①线性探测再散列法 ②平方探测法 ③拉链法(链地址法也是STL中使用的方法) 5.装填因子 (load factor) (1) 装载因子 α ( 实际装载数据的长度 n ) / ( 表长 m ) 装载因子 α (实际装载数据的长度n) / (表长m) 装载因子α(实际装载数据的长度n)/(表长m) 【装载因子 元素的个数 / 表的长度一般α在50%-75%比较完美】 (2)装填因子大则元素个数多冲突的概率高但空间的利用率也比较高 装载因子小则元素个数少冲突的概率低但空间的利用率也比较低
6.哈希表的设计思想 用空间换时间注意数组本身就是一个完美的哈希所有元素都有存储位置没有冲突空间利用率也达到极致。 (1)unordered_set
1.unordered_set的基本特征 (1)存放的是key类型key值唯一不可重复 (2)key值没有顺序 (3)底层使用的是哈希表
2.查找 (和set一致) (1)count() (2)find()
3.插入 (和set一致)
4.删除 (和set一致) (1)删除一个元素 (2)删除迭代器范围
5.unordered_set不支持下标。不支持用迭代器修改元素。 6.unordered_set针对自定义类型的改写
unordered_set的第二个模板参数Hash如果针对的是自定义类型需要进行自己改写改写的方式是模板的特化、函数对象的形式。
没有对std::hashKey进行特化改写Hash和KeyEqual 方法一模板特化 方法二重载运算符 方法三函数对象 一、Hash的改写两种方法 (1)方法一Hash用模板特化
(2)方法二Hash用函数对象 二、KeyEqual的改写三种方法 unordered_set的第三个模板参数KeyEqual如果针对的是自定义类型需要进行自己改写改写的方式是模板的特化、函数对象的形式、运算符的重载。 (1)方法一模板特化
(2)方法二重载运算符
(3)方法三函数对象 传参数 (2)unordered_multiset
1.unordered_multiset的基本特征 (1)存放的是key类型key值不唯一可以重复 (2)key值是没有顺序的 (3)底层使用的是哈希。查找的时间复杂度为O(1)。
2.其他功能 unordered_multiset的查找
3.针对自定义类型 和unordered_multiset的改写方式一样对第二个模板参数Hash(两种方法)、第三个模板参数KeyEqual(三种方法)进行改写。 (3)unordered_map
1.unordered_map的特征 (1)存放的是key-value类型key值唯一不能重复 (2)key值没有顺序 (3)底层使用的是哈希 2.其他操作 (1)unordered_map的初始化、遍历、查找count find、插入insert、删除操作erase、取下标与map完全相同。 (2)unordered_map也支持下标操作通过下标访问、不存在则直接插入通过下标进行修改。仅支持非const版本的operator[]。 3.unordered_map针对自定义类型 (4)unordered_multimap
1.unordered_map的特征 (1)存放的是key-value类型key值不是唯一的可以重复 (2)key值没有顺序 (3)底层使用的是哈希
2.其他操作 unordered_multimap不支持下标访问 (5)无序关联式容器总结
1.元素是没有顺序的 2.底层使用的都是哈希表查找的时间复杂度为O(1) 3.基本操作 4.无序关联式容器对自定义类型的改写 ①模板的特化 ②重载运算符 ③函数对象的形式 4.容器的选择
1.元素是不是有序的 (1)元素有顺序 ①首先选择的是关联式容器。 ②最不应该选择无序关联式容器。 ③其次选择序列式容器list有成员函数sort、vector与deque在算法库algorithm.h中也有sort函数进行排序。序列式容器可以保留插入时的顺序。 2.容器能不能取下标 (1)可以取下标的 ①序列式容器vector、deque ②关联式容器map ③无序关联式容器unordered_map
(2)不能取下标 ①list ②除了map的关联式容器 ③除了unordered_map的无序关联式容器 ④优先级队列只能取top() 3.容器中的元素的查找的时间复杂度 (1)序列式容器O(n) (2)关联式容器O(log₂n)红黑树 (3)无序关联式容器O(1)哈希表 4.迭代器的类型不同 (1)随机访问迭代器vector、deque 【可以用下标随机访问、一次移动多格 、-】 (2)双向迭代器list、4种关联式容器 【只能、–】 (3)前向迭代器4种无序关联式容器【只能】 5.元素是否可以重复 (1)元素要求可以重复序列式容器、multi系列容器 (2)元素要求不可以重复set、map、unordered_set、unordered_map 6.使用场景 (1)vector (向量) 适用场景尾部插入删除随机访问。
(2)deque (双端队列) 适用场景首尾插入删除随机访问
(3)list (双向链表) 适用场景容器中间插入删除不需要随机访问
(4)set (集合) 适用场景存储不重复元素快速查找。唯一键值集合。
(5)multiset (多重集合)
(6)map (映射) 适用场景存储键值对快速查找。需要保证键的唯一性。
(7)multimap
(8)unordered_set (无序集合)
(9)unordered_multiset
(10)unordered_map (无序映射)
(11)unordered_multimap 二、迭代器 (iterator)
1.概念
迭代器可以理解为广义的直至具备指针的功能可以进行移动、可以解引用获取内容 迭代器(iterator)模式又称为游标(Cursor)模式用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解Iterator模式是运用于聚合对象的一种模式通过运用该模式使得我们可以在不知道对象内部表示的情况下按照一定顺序由iterator提供的方法访问聚合对象中的各个元素。 2.迭代器产生的原因
更好地访问容器中的元素 Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来使得不用暴露集合内部的结构而达到循环遍历集合的效果。 3.迭代器的类型
1.迭代器的分类 ①输入迭代器(InputIterator)输入流迭代器 ②输出迭代器(OutputIterator)输出流迭代器 ③前向迭代器(ForwardIterator) ④双向迭代器(BidirectionalIterator) ⑤随机访问迭代器(RandomAccessIterator)。
2.每个迭代器类型对应的操作 3.五种迭代器的关系图继承图 (1)双向迭代器
1.典型的双向迭代器包括:list、set和map的迭代器。
2.双向迭代器Bidirectional Iterator
3.双向迭代器允许在容器中进行双向遍历即可以向前和向后遍历。双向迭代器支持以下操作 ①递增iter 或 iter将迭代器移动到下一个元素。 ②递减–iter 或 iter–将迭代器移动到上一个元素。 ③解引用*iter访问迭代器当前指向的元素。 ④比较操作符 和 !检查两个迭代器是否相等。 (2)随机访问迭代器
1.典型的随机访问迭代器包括vector、deque和原生数组的迭代器。
2.随机访问迭代器Random Access Iterator
3.随机访问迭代器除了支持双向迭代器的所有操作外还支持在常数时间内进行任意位置的访问。随机访问迭代器支持以下额外的操作 ①加法iter n将迭代器向前移动n个位置。 ②减法iter - n将迭代器向后移动n个位置。 ③迭代器差iter1 - iter2计算两个迭代器之间的距离。 ④关系操作符、、 和 比较两个迭代器的位置。 ⑤下标操作符iter[n]访问迭代器当前位置偏移n个位置的元素。 4.流迭代器
流迭代器与输入输出流进行交互的迭代器。 流迭代器是特殊的迭代器可以将输入/输出流作为容器看待。
(1)输出流迭代器
输出流迭代器ostream_iterator 输出流迭代器就是输出迭代器
#include iterator
using std::ostream_iterator;//遍历容器中的元素
//1.创建左值对象
ostream_iteratorint osi(cout, ); //创建一个输出流迭代器将数据写入std::cout
copy(vec.begin(), vec.end(), osi); //使用标准库算法将容器内容写入输出流//2.创建右值临时对象
copy(vec.begin(), vec.end(), ostream_iteratorint(cout, ));copy的源码里的operator里有输出流运算符。会把容器遍历。相当于第四种遍历方法。 把元素复制到第三个参数中 (2)输入流迭代器
输入流迭代器istream_iterator 输入流迭代器就是输入迭代器
vectorint vec;
istream_iteratorint isi(cin);
copy(isi, istream_iteratorint(), std::back_inserter(vec));三、算法
1.概念
(1)概述
算法中包含很多对容器进行处理的算法使用迭代器来标识要处理的数据或数据段、以及结果的存放位置有的函数还作为对象参数传递给另一个函数实现数据的处理。这些算法可以操作在多种容器类型上,所以称为“泛型”泛型算法不是针对容器编写而只是单独依赖迭代器和迭代器操作实现。而且算法库中的算法都是普通函数自由函数。
(2)头文件
泛型算法不针对一种容器
#include algorithm //泛型算法
#include numeric //泛型算术算法(3)分类
1.非修改式的算法不改变容器的内容count()、find()、for_each() 等。 2.修改式的算法可以修改容器中的内容如copy()、swap()、unique()、remove_if()、transform()、random_shuffle()等。 3.排序函数**sort()**等。 4.二分搜索lower_bound、upper_bound 5.集合操作set_intersection、set_union 6.堆相关的操作push_heap、make_heap 7.取最值max、min 8.数值操作acculate、计算两个容器的内部乘积等 9.未初始化的内存操作uninitialized_copy (4)一元函数、一元断言/一元谓词
①一元函数函数的参数只有一个 ②一元断言/一元谓词函数的参数只有一个并且返回类型是bool类型。 ③二元函数函数的参数有两个 ④二元断言/二元谓词函数的参数两个并且返回类型是bool类型。
//一元断言/一元谓词
bool func(int value)
{return value 5;
}
//一元函数
void func(int value)
{cout value ;
}2.copy 3.for_each的使用
templateclass InputIt, class UnaryFunction
UnaryFunction for_each( InputIt first, InputIt last, UnaryFunction f )
{for( ; first ! last; first){f(*first);}return f;
}第五种遍历
#include algorithm //for_each的头文件void func(int value){cout value ;
}void test(){vectorint vec {1,3,5,7,9};//将for_each函数中的第一个参数到第二个参数范围中的元素传入到第三个参数中for_each(vec.begin(), vec.end(), func);cout endl;
}4.lambda表达式匿名函数 (lambda函数)
1.lambda表达式的形式[](){} ①[ ]捕获列表捕获外部变量。只读属性非要修改需要加。 多个特定变量用,分割 全局变量不需要捕获直接使用 []按值捕获所有变量 []按引用捕获所有变量 [,x]混合捕获按引用捕获所有变量特定变量x按值捕获 [this]捕获当前类的this指针 ②( )函数的参数列表。没有参数的lambda表达式可以省略 ( )。 ③{ }函数的函数体
[capture](params) opt - returnType
{body;
}2.提出原因 为了避免func和for_each不在同一个文件C为了避免这种跨文件查询的麻烦提出了lanmda表达式。lambda表达式可以看作是仿函数。
//1.引入lambda表达式的好处:原本的函数指针,现在声明和实现可以写在一起
//2.lambda表达式的形式: [](){}#include iostream
#include vector
#include algorithm
using std::cout;
using std::endl;
using std::vector;void func(int value){cout value ;
}void test(){vectorint vec {1,3,5,7,9};for_each(vec.begin(), vec.end(), func);cout endl;
}//为了避免func在不同的文件中,考虑用lambda表达式,就可以把声明和实现写在一起了
void test2(){vectorint vec {2,4,6,8,10};//将func用lambda表达式实现for_each(vec.begin(), vec.end(), [](int value){ cout value ; });cout endl;
}int main()
{test(); test2(); return 0;
}3.demo //lambda.cpp
(1)捕获按值捕获、按引用捕获
(2)lambda表达式中捕获的是const版本的变量若要修改 ①按引用捕获可在lambda表达式内修改原变量的值 ②加mutable关键字可在lambda表达式内修改副本
(3)函数的返回类型 4.lambda表达式的接收 使用变量接收lambda表达式以期可以在别处调用lambda表达式
5.捕获类中的数据成员 6.lambda表达式本质是仿函数
还原网址把代码还原成编译器的角度 5.remove_if的使用
1.函数原型
//remove_if()的第三个参数传一元断言
template class ForwardIterator, class UnaryPredicate
ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, UnaryPredicate pred);
{first std::find_if(first, last, p);if (first ! last)for(ForwardIt i first; i ! last; )if (!p(*i))*first std::move(*i);return first;
}2.应用remove_if erase (1)原理符合条件的就前移不符合条件的进行覆盖。最后扫描到末尾返回待删除元素的首迭代器把后面的元素都删掉。 (2)效果将满足第三个参数(一元断言)的元素都删除 (3)优势(不管是什么容器)速度快底层是覆盖不需要移动元素
auto it remove_if(vec.begin(), vec.end(), [](int value)-bool{return value 5;});
vec.erase(it, vec.end());//lambda表达式可省略函数返回值类型,编译器会根据return语句自动推导
auto it remove_if(vec.begin(), vec.end(), [](int value){ return value % 2 0; });
vec.erase(it, vec.end());四、适配器
1.迭代器适配器
迭代器适配器(Iterator Adapters) ①reverse_iterator反向迭代器。 ②back_insert_iterator通过push_back插入元素。 ③front_insert_iterator通过push_front插入元素。 ④insert_iterator通过insert插入元素。
(1)反向迭代器reverse_iterator
rbegin()指向最后一个元素 rend()指向第一个元素的前面一个位置 举例反向遍历vector
//反向迭代器
void test2(){vectorint vec {1,2,3,4,5,6,7,8,9};vectorint::reverse_iterator rit vec.rbegin();for( ; rit ! vec.rend(); rit){cout *rit ;}cout endl;
}(2)迭代器适配器三组插入迭代器是特殊的输出迭代器
1.back_inserter是函数模板返回类型是back_insert_iterator而back_insert_iterator是类模板底层调用了push_back函数来插入元素。 2.front_inserter是函数模板返回类型是front_insert_iterator而front_insert_iterator是类模板底层调用了push_front函数来插入元素。 3.inserter是函数模板返回类型是insert_iterator而insert_iterator是类模板底层调用了insert函 数来插入元素。 举例copy函数 插入迭代器也实现了容器的插入。
1.插入尾部back_inserter()
void test(){vectorint vec {1,2,3,4,5};listint ls {6,7,8,9,10};//将list中的元素插入到vector的尾部copy(ls.begin(), ls.end(), back_inserter(vec));//用输出流迭代器对容器进行输出copy(vec.begin(), vec.end(), ostream_iteratorint(cout, ));//创建临时对象cout endl;
}2.插入头部front_inserter()
void test2(){vectorint vec {1,2,3,4,5};listint ls {6,7,8,9,10};//将vector中的元素插入到list的头部: 头插,会形成逆序的效果copy(vec.begin(), vec.end(), front_inserter(ls));//用输出流迭代器对容器进行输出copy(ls.begin(), ls.end(), ostream_iteratorint(cout, ));//创建临时对象cout endl;
}3.插入中间inserter()
//插入中间
void test3(){vectorint vec {9,7,5,3,1};setint st {10,8,6,4,2}; //将vector中的元素插入到setauto it st.begin();copy(vec.begin(), vec.end(), inserter(st, it));//用输出流迭代器对容器进行输出copy(st.begin(), st.end(), ostream_iteratorint(cout, ));//创建临时对象cout endl;
}2.容器适配器
容器适配器(Container Adapters) ①stack栈后进先出LIFO。 ②queue队列先进先出FIFO。 ③priority_queue优先队列元素按优先级排序。
容器适配器没有迭代器。
(1)stack (栈)
vector、deque、list都可以 (2)queue (队列)
1.特点 要求头部可以删除deque、list可以vector不可以
先进先出队列 queue
2.接口 (3)priority_queue (优先级队列)
1.模板参数 要求随机访问迭代器vector、deque可以list不可以 2.操作 (1)初始化无参构造、拷贝或移动构造、迭代器范围。不支持用大括号。 (2)遍历不支持下标访问、不支持迭代器、不支持增强for循环。只能不停的top()和pop()直至为空。
while(!pque.empty()){cout pque.top() ;pque.pop();
}(3)top()值最大的元素 3.优先级队列的底层实现大顶堆采用堆排序 当有新元素插入时会将堆顶与新插入的元素进行比较。 如果堆顶比新插入元素要小即满足std::less那么会进行置换将新的元素作为新的堆顶。 若堆顶比新插入的元素要大即不满足std::less就不会进行置换。 3.函数适配器
函数适配器(Function Adapters) (1)函数绑定器 ①bind1st绑定二元函数的第一个参数已在 C11 中被弃用。 ②bind2nd绑定二元函数的第二个参数已在 C11 中被弃用。 ③bind通用的参数绑定器用于绑定任意数量的参数推荐在现代 C 中使用。
(2)函数对象(仿函数)适配器 ①not1一元仿函数取反。 ②not2二元仿函数取反。 ③ptr_fun将普通函数指针转换为函数对象。【函数指针适配器】 ④mem_fun将成员函数指针转换为函数对象。【成员函数适配器】 ⑤mem_fun_ref与 std::mem_fun 类似但适用于对象的引用。 (1)函数绑定器bind1st、bind2nd、bind
①bind1st和bind2nd的使用
1.头文件
#include functional2.模板形式
template class F, class T std::binder1stF bind1st( const F f, const T x );
template class F, class T std::binder2ndF bind2nd( const F f, const T x );模板形式中两个函数绑定器的第一个参数就是一个函数第二个参数就是一个数字如果F是一个二 元函数(普通二元函数或者二元谓词)我们可以绑定F的第一个参数(bind1st)或者第二个参数(bind2nd)达到我们想要的效果(使用二元谓词的效果) 3.问题提出 如果remove_if的第三个参数是二元断言如何解决二元断言转一元断言需要固定一个参数 4.解决 (1)bind1st固定二元函数对象的第一个参数 (2)bind2nd固定二元函数对象的第二个参数 ReturnValue Func(Args1, Args2);//要删除所有大于5的元素
//bind1st:固定住第一个参数
auto it remove_if(vec.begin(), vec.end(), bind1st(std::lessint(), 5));
vec.erase(it, vec.end());//要删除所有大于5的元素
//bind2nd:固定住第二个参数
auto it remove_if(vec.begin(), vec.end(), bind2nd(std::greaterint(), 5));
vec.erase(it, vec.end());断言放第三个参数相当于条件。满足条件的返回值为true。再配合remove_if()进行删除。 ②bind函数的使用
1.bind的作用 创建一个新的可调用对象该对象将某些参数绑定到一个已有函数或函数对象上。 std::bind 允许你绑定函数的一部分参数生成新的函数对象该对象可以在需要的地方调用。 2.作用 (1)可变参数可以绑定n元函数对象。 (2)bind函数的使用相比于bind1st以及bind2nd更加的具有通用性因为后者只能绑定一个参数而bind可以绑定任意个参数。 (3)bind可以绑定到普通函数、成员函数、数据成员。 3.bind与bind1st、bind2nd的关系 bind1st、bind2nd在C11中被废弃转而采用更为强大灵活的bind。 4.bind的头文件
#include functional
using std::bind;5.引用折叠 F是既可以传左值又可以传右值 如果F写左值则没有引用折叠只能传左值不能传右值。 C11之前没有右值引用解决方法是 const 类型 既可以传左值又可以传右值。 6.实例 (1)bind绑定普通函数
//测试一个三元函数
int multiply(int x, int y, int z){cout multiply(int x, int y, int z) endl;return x * y * z;
}//bind绑定普通函数
void test4(){//bind: 固定第一个参数,并保留两个占位符auto func bind(multiply, 100, _1, _2);cout func(10,1) endl;
}(2)bind绑定成员函数
class Example
{
public://成员函数的第一个参数,是隐藏的this指针, Example * const thisint add(int x, int y){cout int Example::add(int,int) endl;return x y;}
};//bind可以绑定一元函数、二元函数、甚至n元函数
//既可以绑定普通函数,也可以绑定成员函数
void test(){//1.bind绑定二元普通函数auto f bind(add, 1 , 2);cout f() f() endl;//2.bind绑定三元普通函数auto f2 bind(multiply, 3, 4, 5);cout f2() f2() endl;//3.bind绑定成员函数(三元函数)Example ex;auto f3 bind(Example::add, ex, 10, 20); //成员函数就必须加引用cout f3() f3() endl;//占位符using namespace std::placeholders;functionint(int,int) f4 bind(add, _2, 100); //尽量用_1,需要多写参数,而且没用cout f4() f4(1,2) endl;functionint(int) f5 bind(add, _1, 100); cout f5() f5(6) endl;
}(3)bind还可以绑定数据成员类的数据成员可以提升为函数 C11可以直接将数据成员在声明时进行初始化 7.占位符
1.头文件
#include functional // 包含 std::bind 和 std::placeholders
using std::bind;
using namespace std::placeholders; // 使用占位符2.占位符 占位符的位置(占位符整体)是形参的位置。 占位符的数字是对应的实参的位置。
bind()绑定某个函数只绑定一部分。 占位符_1,_2,_3。对应实参对应的位置。 3.bind 默认采用的是值传递而不是引用传递。即使func的参数使用的是引用。 可以使用std::ref 或 std::cref这两个引用包装器传递引用。 4.bind绑定后会改变函数的类型
函数的类型函数的返回类型 函数的参数列表 add的第一个参数绑定为100第二个参数用占位符_1为f的第一个实参 function
头文件
#include functional
using std::function;5.用function类模板来接收bind的返回类型。 function可以存放函数类型所以将function称为函数包装器(函数的容器)
functionint(int) f bind(add, _1 , 999);
f(100);6.this指针也可以用占位符替代 8.bind绑定成员函数的时候传参传递对象和传递地址的区别 传ex和ex在语法上都是一个效果但是有些区别 ①ex传的是一个指针的大小但ex是传一个对象的大小。 ②ex若是多线程可能ex已经销毁ex就成了空指针。但传ex就没问题已经复制了一次对象。
void test()
{Example ex;functionint() f bind(Example::add, ex, 10, 20); //this指针对应位置传递 ex (传递指针,对象的地址)cout f() f() endl;cout endl;functionint() f2 bind(Example::add, ex, 30, 40); //this指针对应位置传递 ex (值传递,拷贝对象)cout f2() f2() endl;
}9.尽量用_1。不然会造成参数浪费。 10.lambda表达式的返回结果也可以用function进行接收 11.注意若lambda表达式捕获了声明周期不存在的引用会发生错误。 不要捕获局部变量的引用因为当变量离开作用域的时候就是捕获了声明周期不存在的引用。
vectorfunctionvoid(const string ) vec;void test()
{int num 100;string name(wangdao);/* functionvoid(const string ) f */ /* [num, name](const string value){ *//* cout num num endl; *//* cout name name endl; *//* cout value value endl; *//* }; *///局部变量的引用。在该作用域之外调用,进行捕获,会发生错误vec.push_back([num, name](const string value){cout num num endl;cout name name endl;cout value value endl;});
} void test2(){for(auto func : vec){func(wuhan);}
}12.std::bind std::function结合使用实现静态多态 (1)面向对象的方式继承 虚函数(纯虚函数)可以体现多态动态多态 基于对象的方式std::bind std::function也可以实现多态静态多态
(2)std::bind改变函数的形态。 用std::function进行接收
(3)头文件
#include functional
using std::bind;
using std::function;cb 是一个右值引用参数。然而虽然它是右值引用类型但在函数体内cb 本身被视为左值。这是因为在C中所有的命名变量包括右值引用都是左值。 4_figure.cc function可以接收右值并把右值转为左值
Figure fig;
/* functionvoid() f bind(Rectangle::display, rectangle, 100); */
/* fig.setDisplayCallback(std::move(f)); */
fig.setDisplayCallback(bind(Rectangle::display, rectangle, 100));赋值改为初始化 cb是左值但是可以用右值引用 (2)mem_fun
mem_fn是成员函数适配器成员函数调用for_each()需要使用mem_fn进行适配。 //使用for_each进行打印
for_each(vec.begin(), vec.end(), mem_fn(Number::print));成员函数写法
bind写法
using namespace std::placeholders;
/* functionvoid(Number *) f bind(Number::print, _1); */ //function传指针是错的
functionvoid(Number ) f bind(Number::print, _1); //必须传对象
for_each(vec.begin(), vec.end(), f);
/* for_each(vec.begin(), vec.end(), bind(Number::print, _1)); */ //上面两行可以合为这一行传ex和ex则function里不同 五、函数对象
1.狭义的函数对象 重载了函数调用运算符的类的对象称为函数对象。这使得函数对象可以像函数一样被调用。
2.广义的函数对象所有可以与小括号进行结合展示出函数含义的都可以称为函数对象。 (1)重载了函数调用运算符()的类创建的对象 (狭义的函数对象) (2)普通函数名 (3)函数指针 (指向函数的指针)、函数引用 (4)lambda表达式 (5)function
3.举例 1.list
2.set 六、空间配置器 (allocator) 【面试加分项】
1.概述
1.空间配置器的概述 先申请空间然后在在该空间上构建对象。将空间的申请与对象的创建分离开。
2.特点 (1)可以感知类型的空间分配器 (2)将内存的开辟/释放与对象的创建/销毁分开 3.头文件
#include memory
template class T struct allocator;
template struct allocatorvoid;4.对于STL的容器而言一般都是申请一大块空间然后在申请的空间上构建对象。如果每创建一个对象的同时申请一块空间效率较低时间复杂度高。 2.四个函数
1.allocate申请空间 申请一块原始的、未初始化的空间 const void*。底层用的malloc。
2.construct创建对象 源码void constrct(pointer _p,const _Tp _val) { new§ _Tp()_val}; 底层用的new
3.destroy销毁对象 源码void destroy(pointer __p) { __p-~_Tp()};
4.deallocate释放空间 底层用的free
//申请空间:申请的是原始的未初始化的空间
T* allocate( std::size_t n );//释放空间
void deallocate( T* p, std::size_t n );//构建对象:在指定的未初始化的空间上构建对象使用的是定位new表达式
void construct( pointer p, const_reference val );//销毁对象
void destroy( pointer p );2.STL中为何将对象的构建与空间的申请分开 (1)因为在STL中对象的创建并不是一个有可能一次要创建多个对象。如vectorPointvec2(vec)。 ①如果创建一个对象就要申请一块空间则空间的申请就非常的频繁。 ②而且多次申请的空间可能是不连续的从而产生内存碎片。 (2)若销毁一个对象就释放一块空间则空间的释放也会非常频繁。 3.两级空间配置器
1.源码 ①第一个分支(一级空间配置器)底层直接走malloc申请空间【若编译时加了宏】 ②第二个分支(二级空间配置器)若申请空间大小n大于128字节底层还是会走malloc申请空间。若n128执行16维的自由链表内存池。
2.数据结构 ①16维的自由链表下面可以挂接内存块。 ②内存池用两个指针进行控制。
3.对于空间配置器而言所申请的空间在内存的哪个位置 答堆空间 (1)一级空间配置器
一级空间配置器要有宏
#ifdef __USE_MALLOC第一级空间配置器使用类模板malloc_alloc_template 其底层使用的是malloc/free进行空间的申请与释放。 (2)二级空间配置器
1.二级空间配置器分两个分支的设计目的 ①小空间进行频繁malloc申请会在内核态与用户态之间进行频率切换导致系统效率低。 ②防止多次申请空间导致的内存碎片问题多次申请的空间不连续会造成内存外部碎片。 二级空间配置器默认情况没有宏的情况。
二级空间配置器使用类模板default_alloc_template其底层根据申请空间大小有分为两个分支进行 ①第一分支是当申请的空间大于128字节的时候还是走__malloc_alloc_template ②当申请的空间小于128字节的使用使用16维自由链表内存池的结构进行。 128/8 16下标从0到15。 if(n128) {malloc;} else {16维自由链表 S_freelist内存池}
函数调用过程 ①allocate()对外暴露的申请空间的接口但其不是直接申请空间会调用_S_refill()。 ②_S_refill()①会调用_S_chunk_alloc()申请空间。②以n为单位对返回的空间进行切割然后挂接在对应的自由链表下。 ③_S_chunk_alloc()真正申请空间 (递归调用)。可能将会将申请的结果一分为二一部分进行返回另一部分放入内存池由两个指针_S_start_free、_S_end_free进行控制。 ④_S_freelist_index()自由链表取下标 ⑤_S_round_up()以8的整数倍向上取整 ⑥_S_start_free控制堆空间中内存池的开头 ⑦_S_end_free控制堆空间中内存池的结尾 _S_round_up() 4.空间配置器的源码剖析 查看源码我们知道空间配置器会分为两级即两级空间配置器 (1)第一级空间配置器使用类模板malloc_alloc_template 其底层使用的是malloc/free进行空间的申请与释放。 (2)二级空间配置器使用类模板default_alloc_template其底层根据申请空间大小又分为两个分支第一分支是当申请的空间大于128字节的时候还是走malloc_alloc_template 当申请的空间小于128字节的使用使用内存池16个自由链表的结构进行。 也就是由一个16维的数组组成每一维会按照8的整数倍申请空间比如下标为3也就是会按照32字节为基本单位申请空间每次申请空间的大小都是32字节而且每次申请的时候一次申请很大一片空间然后按照32字节为一个等分分成多个等分然后挂接在下标为3的下面形成链表形式这样以后需要32字节的时候直接在下标为3的下面取出一个节点就是32字节即可。其他下标的处理方式完全一致。 (1)allocate()
一级空间配置器底层调用malloc 二级空间配置器两个分支
void* __default_alloc_template::_S_refill(size_t __n)
{int __nobjs 20; //第一次总是申请20倍的char* __chunk _S_chunk_alloc(__n, __nobjs);_Obj* __STL_VOLATILE* __my_free_list;_Obj* __result;_Obj* __current_obj;_Obj* __next_obj;int __i;举例 //1、如果想申请32字节的时候堆空间与内存池是充足的 //2、如果想申请64字节的时候堆空间与内存池是充足的 //3、如果想申请96字节的时候堆空间与内存池是充足的 //4、如果想申请72字节的时候堆空间与内存池没有连续的72字节 //5、如果想申请64字节内存池里有72字节则会把64字节分配出来不足64倍数的8字节会留在内存池。 //6、如果想申请64字节内存池里有130字节则会把128字节从内存池取出64分配给申请者64挂在自由链表下不足64倍数的2字节会留在内存池。 //7、如果想申请64字节内存池里不足64字节。则会优先向堆空间申请进行malloc。若堆空间内存不足导致malloc失败则会沿着自由链表向后借。 1.申请32字节 向上取整得到8的整数倍。
申请32字节实际申请1280字节其中640切割为20个32字节的挂接在自由链表下另外640字节在堆区作为内存池。 2.申请64 先返回内存池中的640B进行分割
堆空间内存池的640B被全部用完 3.申请96B
1920被切割为20等份(20*96 1920)后挂在自由链表下2000B在内存池。 4.申请72字节。假设此时内存池(为0)和堆空间都内存不足没有连续的72字节。 循环向后遍历自由链表向后面更大的借内存空间。比如这次申请72B但是往后借到了96B。 然后进行分割分割出72B剩下的24B由_S_start_free和_S_end_free进行控制丢入内存池。 (2)deallocate()
一级空间配置器 二级空间配置器 用头插法将要delete的结点重新链接回自由链表下进行重复使用。 (3)construct() (4)destroy()
对象的销毁就是执行析构函数
