STL是什么

STL是标准模板库，包括算法、容器和迭代器。

• 算法：包括排序、复制等常用算法
• 容器：数据存放形式，包括序列式容器和关联式容器，序列式容器就是list,vector，关联式容器就是set,map等
• 迭代器是在不暴露容器内部结构的情况下对容器遍历

迭代器++it和it++哪个好

前者返回一个引用，后者返回一个对象；前者不会产生临时对象，后者产生临时对象，导致效率降低

// ++i实现代码为：
int& operator++()
{

  *this += 1;
  return *this;

} 
//i++实现代码为：                 
int operator++(int)                 
{
int temp = *this;                   

   ++*this;                       

   return temp;                  
} 

迭代器五种成员类型

• value type：表示迭代器所指向的元素类型。
• difference type：表示两个迭代器之间的距离，通常是一个带符号整数。
• pointer：表示迭代器所指向的元素类型的指针类型。
• reference：表示迭代器所指向的元素类型的引用类型。
• iterator category：表示迭代器的类型，包括输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。

STL中的hashtable实现

STL中使用的是开链法解决hash冲突问题。
hashtable中的bucket所维护的list既不是list也不是slist，而是其自己定义的由hashtable_node数据结构组成的linked-list，而bucket聚合体本身使用vector(因为vector自己有动态扩容的能力）进行存储。hashtable迭代器只提供前进操作，不提供后退操作。

• 在hashtable设计bucket的数量上，内置了28个质数[53,97,193…429496729]，创建hashtable的时候根据存入的元素个数选择大于等于元素的个数的质数作为hashtable的容量。

如果插入的hashtable的元素个数超过了bucket容量，就要重建table，也就是找出下一个质数，创建新的buckets vector，重新计算元素在新hashtable的位置。

开链法具体实现

当插入一个元素的时候，先将元素的哈希值对哈希表大小取余得到一个索引值，然后将元素插入到该索引对应的链表中。如果该链表中已经存在一个与该元素关键字相同的元素则将新元素插入到链表头部，成为新的链表头；否则将新的元素插入到链表头部。

• 当查找一个元素时，先根据元素关键字计算哈希值，然后在对应的链表中查找，找到元素则返回元素的地址，否则返回一个空指针。

• 当删除一个元素时，先在对应的链表中查找该元素，如果找到则将该元素从链表中删除。如果删除后链表为空，则将该哈希槽置为空（即指向空指针）。

RAII是什么

资源获取即初始化，也就是在构造函数中申请分配资源，析构函数中释放资源。智能指针就是RAII最具有代表的实现，不用担心忘记delete造成的内存泄漏

STL的两级空间配置器

为什么需要二级空间配置器？

动态开辟内存的时候，需要在堆上申请。但是频繁申请的时候容易造成很多外部碎片，降低效率。于是设置了二级空间配置器：开辟内存小于等于128字节时，开辟小内存

二级空间配置器实现过程

1. 维护16条将链表，从8字节到128字节，传入一个字节参数，然后系统选择相应位置的链表，如果链表不为空，则拔出来。
2. 如果链表为空，查看内存池是否为空，如果不为空，如果剩余空间有20个节点大小（所需内存*20），则从内存池中拿出20个节点大小空间，将其中一个分配给用户使用，另外19个挂在free_list下面；如果不够20个，但是够1个，则拿出一个分配给用户，剩下的空间挂在free_list下面；如果一个节点大小都不满足，则把剩余空间挂在free_list中，然后申请内存
3. 如果内存池为空，使用malloc()从heap上面申请内存【一次所申请的内存大小为2 * 所需节点内存大小（提升后）* 20 + 一段额外空间】，一半拿来使用，一般放在内存池
4. malloc失败，二级空间配置器会从比所需节点空间大的free_list中搜索，拔一个节点来使用，如果还没有找到，那么要使用一级适配器。

释放时调用deallocate函数，如果释放空间大于128，则调用一级空间配置器，否则就直接将内存块挂上自由链表的合适位置。

二级空间配置器缺点

• 造成内部碎片
• 它的实现中所有成员全都是静态的，所以它申请的所有内存只有在进程结束的时候才会释放内存，还给操作系统。如果不断开辟小内存，最后整个堆上的空间都被挂在自由链表上，这个时候如果想开辟大块内存就会失败；若自由链表上挂很多内存块没有被使用当前进程又占着内存不释放，这个时候别的进程在堆上申请不到空间，也不可以使用当前进程的空闲内存，就会引发很多问题。

底层实现

容器内删除元素

顺序容器

erase迭代器不仅使所指向被删除的迭代器失效，而且使被删元素之后的所有迭代器失效（list除外），所以不能使用erase(it++)的方式，但是erase的返回值是下一个有效迭代器；

因为元素在内存中是连续的，删除一个元素会导致这个元素后面所有元素都向前移动一个位置，这样就会导致原本指向后面元素的迭代器指向错误位置。
对于list来说，元素是分散存储的，删除一个元素是不会影响其它元素的位置。

It = c.erase(it);

关联容器

erase迭代器只是被删除元素的迭代器失效，但是返回值是void，所以要采用erase(it++)的方式删除迭代器；
c.erase(it++)

vector

分配空间和底层实现

1. 操作方式与array比较相似，但是vector是维护一块连续的线性空间，空间不足的时候，可以自动扩展空间。
2. 在扩充空间的时候，需要：重新配置空间，移动数据，释放空间。在Windows是扩充为原来的1.5倍，Linux+GCC下是两倍
3. 为什么扩容两倍或者成倍增长？实验得出采用成倍方式扩容，可以保证常数时间复杂度，而增加指定大小容量只能达到O(n)时间复杂度。

释放空间

所有内存空间是在vector析构的时候才被内存回收。如果需要空间动态缩小，可以考虑使用deque。如果想要清空内存，可以使用swap。

clear函数只是清空内容，不能改变容量大小;remove一般也不会改变容器大小。而pop_back()与erase()等成员函数会改变容器大小。如果要改变容量大小可以使用deque

swap

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec1 = {1, 2, 3};
    std::cout << "vec1 size: " << vec1.size() << ", capacity: " << vec1.capacity() << std::endl;

    std::vector<int> vec2 = {4, 5, 6, 7};
    std::cout << "vec2 size: " << vec2.size() << ", capacity: " << vec2.capacity() << std::endl;

    vec1.swap(vec2);

    std::cout << "After swap:" << std::endl;
    std::cout << "vec1 size: " << vec1.size() << ", capacity: " << vec1.capacity() << std::endl;
    std::cout << "vec2 size: " << vec2.size() << ", capacity: " << vec2.capacity() << std::endl;

    return 0;
}

删除元素

动态增长

size和capacity相同的时候，说明vector目前的空间已经被用完了，如果再添加新的元素则会引起vec空间的动态增长。
由于动态增长会引起重新分配空间、拷贝原空间、这些过程会降低效率。所以可以使用reserve(n)预先分配一块较大的指定大小的内存空间，只有当n>capacity的时候，调用reserve(n)才会改变vector容量;当指定大小的内存空间没有使用完的时候，不会重新分配空间。

void resize(size_type __new_size, const _Tp& __x) {
      if (__new_size < size()) 
            erase(begin() + __new_size, end());
      else
            insert(end(), __new_size - size(), __x);
      }

resize和erserver对比

#include <iostream>
#include <vector>

int main() {
  std::vector<int> my_vector;

  // 在插入元素之前，预留 10 个 int 类型的空间
  my_vector.reserve(10);

  for (int i = 0; i < 10; ++i) {
    my_vector.push_back(i);
  }

  std::cout << "Vector size: " << my_vector.size() << '
';//10
  std::cout << "Vector capacity: " << my_vector.capacity() << '
';//10

  return 0;
}

• 空间大小不足的时候，新分配空间大小为原来空间大小的2倍
• 使用reserve预先分配一块内存之后，空间未满情况下不会引起重新分配
• reserve分配的空间比原空间小的时候，不会重新分配
• resize只改变容器数目，不改变容器大小
• 用reserve(size_type)只是扩大capacity值，这些内存空间可能还是“野”的，如果此时使用“[ ]”来访问，则可能会越界。而resize(size_type new_size)会真正使容器具有new_size个对象。

emplace_back

作用是在容器末尾插入一个新的元素，这个元素的值由给定的参数直接在容器内构造而成。
可以直接在容器中构造元素，不需要先创建一个对象然后将其复制到或者移动到容器中，避免移动和复制开销

需要注意的是，emplace_back() 在构造元素时可能会抛出异常，这会导致容器的状态变为未定义，因此在使用 emplace_back() 时需要格外小心，确保提供的参数能够成功构造出一个新的元素。

map和set

底层是红黑树实现的，插入删除操作都是在O(logn)时间之内完成，并且是自动排序的，按照中序遍历会是有序遍历。map是key+value,set是value。

map和set的区别

set只提供一种数据类型的接口，但是会将这一个元素分配到key和value上，而且它的compare_function用的是 identity()函数，这个函数是输入什么输出什么，这样就实现了set机制，set的key和value其实是一样的了。其实他保存的是两份元素，而不是只保存一份元素

map则提供两种数据类型的接口，分别放在key和value的位置上，他的比较function采用的是红黑树的comparefunction（），保存的确实是两份元素。

map实现原理

一旦map的key确定了，那么是无法修改的，但是可以修改这个key对应的value，因此map的迭代器既不是constant iterator，也不是mutable iterator。
map底层也是红黑树，构造的时候默认采用递增排序key，也是用alloc配置器配置空间大小。需要注意的是在插入元素时，调用的是红黑树中的insert_unique()方法，而非insert_euqal()（multimap使用）

下标操作

需要注意的是subscript（下标）操作既可以作为左值运用（修改内容）也可以作为右值运用（获取实值）。
首先根据键值和实值做出一个元素，这个元素的实值未知，因此产生一个与实值型别相同的临时对象替代，再将这个对象插入到map中，并返回一个pair，pair第一个元素是迭代器，指向当前插入的新元素，如果插入成功返回true，此时对应左值运用，根据键值插入实值。插入失败（重复插入）返回false，此时返回的是已经存在的元素，则可以取到它的实值。由于这个实值是引用传递，所以作为左值或者右值都可以。

map是怎么扩容的

首先申请一块更大的内存空间，然后将原有的元素逐个复制到新的内存空间中。复制的过程中，会按照红黑树的中序遍历顺序，将每个元素的键值对存储到新的位置，释放旧的空间。

set 底层与迭代器

• 底层是红黑树，几乎所有操作都是转调用红黑树的操作行为。
• set不允许迭代器修改元素的值，迭代器是一种constance iterators。

unordered_map和unordered_set

都是无序的，既不会按照大小来排序，也不会按照插入顺序来排序。unordered_map底层是hash_table.

hash_table表格内的元素称为桶，选择vector作为存放桶元素的基础容器，因为vector容器本身具有动态扩容的能力。
为什么sunordered_set不是按照插入顺序排序的？因为是按照散列值哈希值组织到桶中，以便于快速访问某个元素

multimap、unordered_multimap 和multiset 、unordered_multiset

mutimap：底层为红黑树，可以重复
unordered_mutimap：底层为哈希表，无序，可以重复
mutiset:底层为红黑树，有序，可重复
unordered_mutiset：底层为哈希表，无序，可以重复

unordered_map和map应用场景

map适用于有序数据的应用场景，unordered_map适用于高效查询的应用场景

list和slist

list

list不仅是一个双向链表，而且还是一个环状双向链表，所以只需要一个指针。
list是双向迭代器：Bidirectional iterators。

空间管理

默认采用alloc作为空间配置器，为了方便的以节点大小为配置单位，还定义了一个list_node_allocator函数可以一次性配置多个节点空间。

slist

slist是单向链表，迭代器是forward iterator，所耗用的空间更小，操作更快。forward_list在C++11中出现，与slist的区别是没有size()方法。C++标准委员会没有采用slist的名称。

deque

deque的数据结构如下

class deque
{
    ...
protected:
    typedef pointer* map_pointer;//指向map指针的指针
    map_pointer map;//指向map
    size_type map_size;//map的大小
public:
    ...
    iterator begin();
    iterator end();
    ...
}

deque内部有一个指针指向map，map是一小块连续的空间，其中每一个元素称为一个节点node，每一个node都是一个指针，指向另一段较大的连续空间，称为缓冲区，==这就是deque中实际存放数据的区域，默认大小是512bytes。

deque迭代器的数据结构如下

struct __deque_iterator
{
    ...
    T* cur;//迭代器所指缓冲区当前的元素
    T* first;//迭代器所指缓冲区第一个元素
    T* last;//迭代器所指缓冲区最后一个元素
    map_pointer node;//指向map中的node
    ...
}

零拷贝

通常情况下，我们需要将数据从一个应用程序的内存空间复制到操作系统的内核空间，然后再将数据从内核空间复制到另一个应用程序的内存空间。这种复制过程会产生很大的开销，因为每次复制都需要耗费时间和内存资源。

零拷贝技术可以采用以下几种方式

1. 使用内存映射文件（mmap）技术，将文件映射到内存中，避免了文件复制的过程。
2. 使用数据包直接内存访问（DMA）技术，将数据从网络设备的缓冲区直接传输到内存中，避免了数据复制的过程。
3. 使用共享内存（shared memory）技术，将数据共享到多个应用程序中，避免了数据复制的过程。

在C++中，STL也支持零拷贝

• std::vector 的 reserve() 成员函数可以预留一定的容量，从而避免了在插入元素时不必要的扩容和数据复制。
• std::string 的 substr() 成员函数可以返回一个指向原字符串中一段子串的指针，避免了字符串的复制。