STL的基本组成

STL主要由以下几部分组成:容器、迭代器、仿函数、算法、分配器和配接器。

Map和 Set的实现与区别

map和set都是C++的关联容器，其底层实现都是红黑树(RB-Tree) 。由于map和set所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的map和set的操作行为，都只是转调RB-tree 的操作行为。

区别

  1. map中的元素是key-value (关键字一值)对:关键字起到索引的作用，值则表示与索引相关联的数据; Set 与之相对就是关键字的简单集合，set 中每个元素只包含-一个关键字。
  2. set的迭代器是const的，不允许修改元素的值; map 允许修改value,但不允许修改key。其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map 和set的结构，导致iterator 失效，不知道应该指向改变前的位置， 还是指向改变后的位置。所以STL中将set的迭代器设置成const,不允许修改迭代器的值;而map的迭代器则不允许修改key值，允许修改value值。
  3. map支持下标操作，set 不支持下标操作。map可以用key做下标，map 的下标运算符[ ]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中，因此下标运算符[ ]在map应用中需要慎用，const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用，mapped_type类型没有默认值也不应该使用。如果find能解决需要，尽可能用find

注：unordered_map的底层实现是hash表。

STL中的allocator

STL的分配器用于封装STL容器在内存管理上的底层细节。在C++中，其内存配置和释放如下:

  1. new运算分两个阶段:(1)调用::operatornew配置内存;(2)调用对象构造函数构造对象内容。
  2. delete运算分两个阶段: (1) 调用对象希构函数; (2)掉员 工: :operator delete 释放内存。
  3. 为了精密分工，STL allocator将两个阶段操作区分开来:内存配置有alloc: :allocate()负责，内存释放由alloc: : deallocate()负责;对象构造由: : construct()负责，对象析构由: :destroy()负责。

  4. 同时为了提升内存管理的效率，减少申请小内存造成的内存碎片问题，STL采用了两级配置器，当分配的空间大小超过128B 时，会使用第一级空间配置器;当分配的空间大小小于128B时，将使用第二级空间配置器。第一级空间配置器直接使用malloc()、reealloc()、 free()函数进行内存空间的分配和释放，而第二级空间配置器采用了内存池技术，通过空闲链表来管理内存。

    STL中迭代器的作用，指针与迭代器

    迭代器

    Iterator (迭代器)模式又称Cursor (游标)模式，用于提供一种方法顺序访问 一个聚合对象中各个元素，而又不需暴露该对象的内部表示。或者这样说可能更容易理解:Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序(由iterator提供的方法)访问聚合对象中的各个元素。由于Iterator模式的以上特性:与聚合对象耦合， 在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如STL的list、vector、stack 等容器类及ostream_ iterator 等扩展iterator.

    迭代器和指针的区别

    迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的-些功能，通过重载了指针的一些操作符,一>、 、++、—等。迭代器封装了指针，是一个“ 可遍历STL( Standard Template Library)容器内全部或部分元素”的对象，本质 是封装了原生指针，是指针概念的一种提升(lift) ，提供了比指针更高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，— 等操作。迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。

    迭代器产生原因

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

    STL里resize和reserve的区别

    resize()

    改变当前容器内含有元素的数量(size()), eg: vectorv; v. resize(len) ;v的size变为len,如果原来v的size小于len,那么容器新增(len-size) 个元素，元素的值为默认为0.当v. push_ back(3);之后，则是3是放在了v的末尾，即下标为len,此时容器是size
    为len+1;

    reserve()

    改变当前容器的最大容量(capacity)，它不会生成元素，只是确定这个容器允许放入多少对象，如果reserve(len)的值大于当前的capacity()，那么会重新分配一块能存len个对象的空间，然后把之前v. size()个对象通过copy construtor 复制过来，销毁之前的内存。

    STL迭代器删除元素

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

  5. 对于序列容器vector, deque来说，使用erase(itertor)后，后边的每个元素的迭代器都会失效，但是后边每个元素都会往前移动一个位置，但是erase会返回下一个有效的迭代器;

  6. 对于关联容器map set 来说，使用了erase(iterator)后， 当前元素的迭代器失效，但是其结构是红黑树，删除当前元素的，不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一一个元素的迭代器即可。
  7. 对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator,因此上面两种正确的方法都可以使用。

    epoll原理

    调用顺序:
    1. int epoll_ create(int size) ;
    2. int epoll_ ctl (int epfd, int op, int fd, struct epoll_ event *event) ;
    3. int epoll_ wait(int epfd, struct epoll_ event *events, int maxevents, int timeout) ;

首先创建一个epoll对象，然后使用epoll ctl 对这个对象进行操作，把需要监控的描述添加进去，这些描述如将会以epoll event 结构体的形式组成一颗红黑树 ，接着阻塞在epoll_ wait,进入大循环，当某个fd上有事件发生时，内核将会把其对应的结构体放入到一个链表中，返回有事件发生的链表。