C++基础之STL

本文主要是介绍C++基础之STL，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

以下自己整理的东东很多参考[如下链接]，如果雷同，纯属抄袭…

1，STL介绍(空间配置器详解)
标准模板库，C++的标准库之一。
STL包含6大部件：容器、迭代器、算法、仿函数、适配器和空间配置器。
容器：容纳一组元素的对象。
迭代器：提供一种访问容器中每个元素的方法。
函数对象：一个行为类似函数的对象，调用它就像调用函数一样。
算法：包括查找算法、排序算法等等。
适配器：用来修饰容器等，比如queue和stack，底层借助了deque。
空间配置器：负责空间配置和管理。对象构造钱的空间配置和对象析构后的空间释放。
要考虑如下问题：
- 向system heap要空间

• 考虑多线程状态
• 考虑内存不足
• 考虑小型区块可能造成的内存碎片问题
  对于内存破碎问题，SGI使用了双层级配置器
• 第一级直接使用allocate()调用malloc()、deallocate()调用free()，使用类似new_handler机制解决内存不足（抛出异常），配置无法满足的问题（如果在申请动态内存时找不到足够大的内存块，malloc 和new 将返回NULL 指针，宣告内存申请失败）。
• 第二级视情况使用不同的策略，当配置区块大于128bytes时，调用第一级配置器，当配置区块小于128bytes时，采用内存池的整理方式：配置器维护16个（128/8）自由链表，负责16种小型区块的此配置能力。内存池以malloc配置而得，如果内存不足转第一级配置器处理。

但SGI也存在一些问题

• 自由链表所挂区块都是8的整数倍，因此当我们需要非8倍数的区块，往往会导致浪费。
• 由于配置器的所有方法，成员都是静态的，那么他们就是存放在静态区。释放时机就是程序结束，这样子会导致自由链表一直占用内存，自己进程可以用，其他进程却用不了。

2，各种容器的特点和适应情况

3，vector二三事

- vector底层实现原理
动态数组，三个迭代器。[start, finish]是已经被使用的范围，[start, end_of_storage]整块连续存储空间。
当内存不足时，自动申请1.5倍或2倍更大的空间，然后将原来的拷贝到新的空间中，接着释放原来空间。【vector内存增长机制】
vec.clear时，存储空间不释放，仅仅是清空数据而已。因此一旦空间配置，所有的迭代器都会失效。
- vector中reserve和resize的区别
resize：改变当前容器内含有元素的数量。
reserve：改变的是capacity的量。
- size和capacity的区别
- 元素类型可以是引用吗

• 引用并不分配实际地址，元素不可是引用
  - 正确释放内存
    vec.clear()：清空内容，但是不释放内存。
    vector().swap(vec)：清空内容，且释放内存，想得到一个全新的vector。
    vec.shrink_to_fit()：请求容器降低其capacity和size匹配。
    vec.clear();vec.shrink_to_fit();：清空内容，且释放内存。
  - 为什么要以1.5或2倍扩容
  算法啊。。。
• 常用函数

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

3，List二三事

• list的底层实现原理
  双向链表
• 常用函数

list.push_back(elem)	在尾部加入一个数据
list.pop_back()	        删除尾部数据
list.push_front(elem)	在头部插入一个数据
list.pop_front()	    删除头部数据
list.size()	            返回容器中实际数据的个数
list.sort()             排序，默认由小到大 
list.unique()           移除数值相同的连续元素
list.back()             取尾部迭代器
list.erase(iterator)    删除一个元素，参数是迭代器，返回的是删除迭代器的下一个位置

4，deque二三事

• 底层实现原理
  
  -双端队列
• 常用函数

deque.push_back(elem)	在尾部加入一个数据。
deque.pop_back()	    删除尾部数据。
deque.push_front(elem)	在头部插入一个数据。
deque.pop_front()	    删除头部数据。
deque.size()	        返回容器中实际数据的个数。
deque.at(idx)	        传回索引idx所指的数据，如果idx越界，抛出out_of_range。

5，priority_queue

• 底层实现原理
  有先队列—待补充

priority_queue<int, vector<int>, greater<int>> pq;   最小堆
priority_queue<int, vector<int>, less<int>> pq;      最大堆
pq.empty()   如果队列为空返回真
pq.pop()     删除对顶元素
pq.push(val) 加入一个元素
pq.size()    返回优先队列中拥有的元素个数
pq.top()     返回优先级最高的元素

高频考点
6，map 、set、multiset、multimap
（1）map 、set、multiset、multimap的底层原理
底层实现都是红黑树，
红黑树–待补充
本质都是对红黑树特性的应用和转换
（2）map 、set、multiset、multimap的特点
可不可以重复。
（3）为何map和set的插入删除效率比其他序列容器高，而且每次insert之后，以前保存的iterator不会失效？
因为每次存储的都是节点，不需要内存拷贝和移动。
（4）为何map和set不能像vector一样有个reserve函数来预分配数据?
map和set内部存储的不是元素本身，而是包含元素的节点。
（5）map 、set、multiset、multimap的常用函数
// 待补充

it map.begin() 　        返回指向容器起始位置的迭代器（iterator） 
it map.end()             返回指向容器末尾位置的迭代器 
bool map.empty()         若容器为空，则返回true，否则false
it map.find(k)           寻找键值为k的元素，并用返回其地址
int map.size()           返回map中已存在元素的数量
map.insert({int,string}) 插入元素
for (itor = map.begin(); itor != map.end();)
{
    if (itor->second == "target")
        map.erase(itor++) ; // erase之后，令当前迭代器指向其后继。
    else
        ++itor;
}

7，stl迭代器是怎样删除元素的
主要考察迭代器实效问题。
（1）vector和deque，使用erase，后面的元素都会实效，但是后面元素都会向前移动一个位置。erase会返回下一个有效迭代器。
（2）对于map和set，使用erase后，在调用erase之前，记录下一个元素的迭代器即可。
（3）对于list来说，使用不连续分配 的内存，上面两个都可以用。
8，vector和list的区别
从数组和链表的本质去讲。
9，unordered_map、unordered_set
（1）unordered_map、unordered_set的底层原理
unordered_map的底层是哈希表。
（2）哈希表的实现
（3）unordered_map 与map的区别？使用场景？
构造函数：unordered_map需要hash，map只需要比较函数
存储结构：unordered_map使用hash表，mao使用红黑树。
查找速度:unordered_map一般要快。unordered_map是用内存要消耗速度，且构造速度比较慢
（4）unordered_map、unordered_set的常用函数

unordered_map.begin() 　　  返回指向容器起始位置的迭代器（iterator） 
unordered_map.end() 　　    返回指向容器末尾位置的迭代器 
unordered_map.cbegin()　    返回指向容器起始位置的常迭代器（const_iterator） 
unordered_map.cend() 　　   返回指向容器末尾位置的常迭代器 
unordered_map.size()  　　  返回有效元素个数 
unordered_map.insert(key)  插入元素 
unordered_map.find(key) 　 查找元素，返回迭代器
unordered_map.count(key) 　返回匹配给定主键的元素的个数 

10，stl中map的数据存放形式
11，介绍stl中的allocator
12，迭代器的底层机制和实效的问题
（1）迭代器种类
输入迭代器：是只读迭代器，在每个被遍历的位置上只能读取一次。例如上面find函数参数就是输入迭代器。

输出迭代器：是只写迭代器，在每个被遍历的位置上只能被写一次。

前向迭代器：兼具输入和输出迭代器的能力，但是它可以对同一个位置重复进行读和写。但它不支持operator–，所以只能向前移动。

双向迭代器：很像前向迭代器，只是它向后移动和向前移动同样容易。

（2）迭代器实效问题

• 插入
  对于vector和string，如果容器内存被重新分配，iterators,pointers,references失效；如果没有重新分配，那么插入点之前的iterator有效，插入点之后的iterator失效；

对于deque，如果插入点位于除front和back的其它位置，iterators,pointers,references失效；当我们插入元素到front和back时，deque的迭代器失效，但reference和pointers有效；

对于list和forward_list，所有的iterator,pointer和refercnce有效。

• 删除
  对于vector和string，删除点之前的iterators,pointers,references有效；off-the-end迭代器总是失效的；

对于deque，如果删除点位于除front和back的其它位置，iterators,pointers,references失效；当我们插入元素到front和back时，off-the-end失效，其他的iterators,pointers,references有效；

对于list和forward_list，所有的iterator,pointer和refercnce有效。

对于关联容器map来说，如果某一个元素已经被删除，那么其对应的迭代器就失效了，不应该再被使用，否则会导致程序无定义的行为。

13，容器的线程安全性
（1）线程安全
多个读取者是安全的。多线程可能同时读取一个容器的内容，这将正确地执行。当然，在读取时不能 有任何写入者操作这个容器；

对不同容器的多个写入者是安全的。多线程可以同时写不同的容器。
（2）线程不安全
在对同一个容器进行多线程的读写、写操作时；

在每次调用容器的成员函数期间都要锁定该容器；

在每个容器返回的迭代器（例如通过调用begin或end）的生存期之内都要锁定该容器；

在每个在容器上调用的算法执行期间锁定该容器。

这篇关于C++基础之STL的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！