面经C++容器和算法

容器和算法

map和set有什么区别，分别怎么实现

map 和 set 在 c++ 中底层都是红黑树实现。他们的区别在于：

map的存储形式是key value的形式，在树中对 key关键字进行排序。而set就是以集合种元素本身作为建立红黑树的关键子，set只存储元素。
对map 迭代时，可以对 value修改，但是不能对key修改，因为红黑树以Key为依据建树，一旦修改红黑树就会自动调整，这时候迭代器的指向顺序就乱了。而同理 set 是直接对集合中的元素建树，所以set迭代时是不可修改的
map 支持下标操作，可以通过关键字访问对应的元素，但是在使用下标访问时，如果map中存在该键就将值返回，否则以默认值新建该键值关系，因此在只需要判断该键存在与否的时候使用 find最好。set 不行。

STL的allocaotr

c++的内存管理使用 new/delete 关键字管理。new/delete的具体执行过程：

new分为两个阶段 : 1. 调用::operator new内存配置 2. 调用构造函数
delete:分为两个阶段： 1. 调用对象析构函数 2. 调用::operator delete释放内存

而 STL 中为了精密分工，将两个阶段（内存配置和对象构造 / 内存释放和对象析构函数）分开操作

alloc::allocate() 内存配置
alloc::deallocate() 内存释放

同时SGI STL采用了两级内存配置，当分配的内存低于128B 时使用内存池技术，通过空闲链表链表管理内存，防止内存碎片化，当分配的内存大于128B时，直接使用malloc realloc free等函数分配一整块内存。

STL 迭代删除元素

主要考虑迭代器失效的问题。

对于序列容器中的vector deque ，删除当前元素，后面的元素都会往前移动一个位置，导致后面的迭代器失效（deque的头尾插除外），而 erase 函数会返回下一个迭代器，因此使用返回值即可。
对于 list 是由双向环形链表构成，因此也只是当前的迭代器失效，不影响后面的。它的erase方法也会返回下一个有效的iterator。
对于关联容器，map 和 set 底层都是红黑树，删除当前元素只是当前迭代元素失效，后面的不影响, 备份即可。

//要求删除键值为偶数的键值对
 map<int, int>::iterator it = m.begin();

 //错误实现：
 while (it != m.end()){
   if(it->second % 2 == 0){
     m.erase(it);
   }
   it++;
 }

 //正确实现：
 while (it != m.end()){
   if(it->second % 2 == 0){
     m.erase(it++); //重点！！！  it++的写法才行不能  m.rease(it); it++;
   }
   else{
     it++;
   }
 }

STL有什么基本组成

容器：STL内部封装好的数据结构，是一种class template，常用的包括vector、list、deque、set、map等
算法：是一种函数模板，常用的有sort、search、copy等，STL中算法与数据相分离（不像面向对象中将算法与数据封装在class中）。
迭代器：类似于泛化的指针，用来访问可迭代序列。
适配器：提供转换操作，有容器适配器、仿函数适配器、迭代器适配器。
分配器：负责空间配置与管理，用以支持容器。是一种class template。
仿函数：行为类似函数，就是使一个类的使用看上去像一个函数。它的具体实现就是通过在类中重载了operator()，使这个类具有了类似函数的行为。

关系：分配器用于给容器分配空间，算法通过迭代器访问容器中的数据从而完成一定的功能，配接器用于适配套接仿函数或容器，或者说通过一定的方法进行封装。例如 queue 和 stack 基本模型都是 deque 通过配接器实现而来。仿函数可以协助算法完成各种操作。

STL中map与unordered_map

底层数据结构不一样，map 是使用红黑数实现，un..使用hash表
因此查询效率等都不一样
map 是有序的 un 是无序的不能迭代访问

vector和list的区别，应用，越详细越好

1、区别：

vector底层实现是数组；list是双向链表。
vector支持随机访问，list不支持。
vector是顺序内存，list不是。
vector在中间节点进行插入删除会导致内存拷贝，list不会。
vector一次性分配好内存，不够时才进行2倍扩容；list每次插入新节点都会进行内存申请。
vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。

2、应用

vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用vector。
list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。

STL中迭代器的作用，有指针为何还要迭代器

Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。

他本质是类模板，表现的像指针，重载了 ++ – 和 ->等操作，封装了原生指针，更像智能指针，可以根据不同的数据结构类型来实现不同的++ –等操作。迭代器返回的是对象的引用而不是对象的值。

STL迭代器是怎么删除元素

考察的是迭代器失效的问题。

找到数组中每个元素后面比他大的第一个数

单调栈下一个更大元素 II

STL中resize和reserve区别

resize 和 size 参数相关，reserve函数和 capacity参数相关。

size指容器当前拥有的元素个数，它代表的空间是初始化了的可以直接访问
capacity则指容器在必须分配新存储空间之前可以存储的元素总数，只是空间预分配，未初始化，不可访问

调用 resize(n) 函数后，容器的 size = n；如果 n 不超过最大容量capacity，则不需要重新分配内存，capacity不变；反之则重新分配内存 capacity = size；

调用 reserve(n) 函数后，如果 n 不大于 capacity ，capacity不变，否则重新分配 n 的内存使得capcity等于n，同时将之前 size 的内容拷贝过来。

C++ STL 的内存优化

二级配置器结构

STL 内存管理使用二级内存配置器

第一级配置器。当分配的内存数大于128字节时，直接使用 malloc free realloc 等函数执行实际的内存分配，和释放等操作。
第二级配置器，当分配的内存少于128字节时，使用内存池管理。又称之次层配置（sub-allocation）。每次配置一大块内存，并维护对应的16个空闲链表（free-list）。下次若有相同大小的内存需求，则直接从free-list中取。如果有小额区块被释放，则由配置器回收到free-list中。
1. 通过size找到合适的空闲链表，如果链表不为空，则直接返回第一个node
2. 如果链表为空，则使用 blockAlloc 请求分配 node ，即从图中的 start_free-end_free 中的空闲区域再划分出多个连续的node出来。
- 如果有足够一个node 的空间，就尽可能的分配多的node （最多20）个，将一个Node返回，其他的添加到空闲链表中
- 如果一个多的空闲node都没有，再次向操作系统请求分配内存
  - 若分配成功再次使用 b 步骤，分配 block
  - 若分配失败，循环各个自由链表寻找空间，如果寻找到了，再次进行 b 过程，否则抛出异常
用户调用deallocate释放内存空间，如果要求释放的内存空间大于128bytes，直接调用free。否则按照其大小找到合适的自由链表，并将其插入

上述步骤有三个关键函数：

空间配置函数allocate：

检查申请的空间大小，大于128字节就调用一级空间配置器使用malloc分配，否则就调用二级空间配置器，从空闲链表中拿数据块。如果空闲链表为空，则调用 refill 函数重新填充空闲链表。
重新填充空闲链表 refill

在使用 allocate 配置空闲空间时，如果对应的空闲链表中没有可用的块（Node）。那么就会调用该函数充填空闲链表。新的空间取自内存池。默认取出 20 个数据块，如果内存池的空间不够，能取多少取多少。从内存池中取空闲块给空闲链表是由函数 chunk_alloc完成
从内存池取空闲块chunk_alloc

首先根据end_free - start_free来判断内存池中的剩余空间是否足以调出nobjs个大小为size的数据块出去。如果内存连一个数据块的空间都无法供应，需要用 malloc 取堆中申请内存。假如山穷水尽，整个系统的堆空间都不够用了，malloc失败，那么chunk_alloc会从空闲链表中找是否有大的数据块，然后将该数据块的空间分给内存池（这个数据块会从链表中去除）。
空间释放函数 deallocate
首先先要检查释放数据块的大小，如果大于128字节就调用第一级配置器，小于128字节则根据数据块的大小来判断回收后的空间会被插入到哪个空闲链表。