面试浅谈之 C++ STL 篇

一 🏠 概述

HELLO，各位博友好，我是阿呆 🙈🙈🙈

这里是面试浅谈系列，收录在专栏面试中 😜😜😜

本系列将记录一些阿呆个人整理的面试题 🏃🏃🏃

OK，兄弟们，废话不多直接开冲 🌞🌞🌞

二 🏠 核心

1、什么是 STL ？

STL (Standard Template Library) 是 C++ 的标准模板库，主要由container(容器)、algorithm(算法)和iterator(迭代器)三大部分构成：

1、容器 ：存放数据对象（就是一种数据结构，例链表、栈、队列等等）

2、算法 ：操作容器中的数据对象（操作容器数据的模板函数，sort、find、copy、for_each）

3、迭代器 ：访问容器中的数据对象（正向，反向，可读）

剩余三大组件是 ：仿函数、适配器、空间配置器

2、HashMap 和 Map 适用场景

HashMap 底层实现链式哈希表（无序），查找速度快（常量级）

Map 底层实现是红黑树（有序），查找速度相对慢（ log(n) ）

在数据量级高且追求查询性能时，使用 HashMap

在数据量级低且要求内存低消耗时，使用 Map

3、STL HashTable 底层实现

开链法 解决 hash 冲突

4、Vector 底层原理及相关问题

① vector 底层原理

动态数组，包含三个迭代器，start 和 finish 之间是已被使用的空间范围 ，end_of_storage 是整块连续空间包括备用空间尾部

当空间不够装下数据时，会自动申请更大空间，把原来数据拷贝到新内存空间，释放原空间【扩容】

当释放或者删除数据时，内存空间不释放，仅清空数据

任何 Vector 空间重新配置的操作，指向原 Vector 迭代器会失效

② vector reserve 和 resize 区别

reserve 保证空间大小达到参数指定大小，扩充内存空间，解决多次开辟、释放空间问题

resize 涉及成员对象默认初始化，也会改变内存空间大小

③ vector size 和 capacity 区别

size 表示有多少元素（finish - start）

capacity 表示内存空间可容纳多少元素（end_of_storage - start）

④ vector 元素类型可以是引用吗？

vector 元素类型是对象，引用不是对象，没有实际地址

⑤ vector 迭代器失效情况

① 当插入一个元素后，end 返回迭代器失效

② 当插入一个元素后，造成动态扩容，first 和 end 返回迭代器失效

③ 删除操作 （erase，pop_back） ，指向删除点和后面元素的迭代器失效

⑥ 正确释放 vector 内存

vec.clear() ：清空内容，但不释放内存

vector().swap(vec) ：清空内容，且释放内存，得到⼀个空 vector

vec.shrink_to_fit() ：请求容器降低其 capacity 和 size 匹配

vec.clear()，vec.shrink_to_fit() ：清空内容，且释放内存

⑦ vector 扩容为什么 1.5 倍或 2 倍

可能产生堆空间浪费，成倍增长倍数不能太大

⑧ vector 常用函数

vector<int> vec(10,100); //创建10个元素,每个元素值为100
vec.resize(r,vector<int>(c,0)); //⼆维数组初始化
reverse(vec.begin(),vec.end()) //将元素翻转
vec.push_back(val); //尾部插⼊数字
vec.size(); //向量⼤⼩
iterator = vec.erase(iterator) //删除元素find(vec.begin(),vec.end(),1); //查找元素
sort(vec.begin(),vec.end()); //排序，默认升序排列

5、map [ ] 与 find 区别

[] 作用 ：将关键码作为下标执行查找；如果不存在关键码，将⼀个具有该关键码和值类型默认值插入

find 函数：关键码执行查找，找到返回该位置迭代器；不存在这个关键码，返回尾迭代器

6、其它 STL 容器底层实现

参考 C++ 语言专栏中 C++ 浅谈 STL 系列

三 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

各位博友觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪