STL中map和set异同点

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

STL迭代器删除元素

  1. 对于序列容器vector、deque而言，使用erase(iterator)后，后边的每个元素的迭代器都会失效，但是后边每个元素都会往前移动一个位置，但是erase会返回下一个有效的迭代器
  2. 对于关联容器map、set而言，使用erase(iterator)后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素的不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可
  3. 对于list来说，list使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上述两种正确的方法都可以使用。
  4. STL由容器、迭代器、仿函数、算法、分配器、配接器几部分组成。
    他们之间的关系：分配器给容器分配存储空间、算法通过迭代器获取容器中的内容，仿函数可以协助算法完成各种操作，配接器用来套接适配仿函数。

vector与list的区别

  1. vector:
    连续存储的容器，动态数组，在堆上分配空间
    底层实现：数组
    两倍容量增长
    vector插入新元素时，如果未超过当时的容量，则还有剩余空间，那么直接添加到最后（插入指定位置），然后调整迭代器。
    如果没有剩余空间了，则会重新配置原有元素个数的两倍，然后将原空间元素通过复制的方式初始化新空间，再向新空间增加元素，最后析构并释放原空间，之前的迭代器都会失效。
    性能：
    访问：O（1） 插入：在最后插入(空间够)：很快
    在最后插入(空间不够)：需要内存申请与释放，以及对之前数据进行拷贝
    在中间插入(空间够)：内存拷贝
    在中间插入(空间不够)：需要内存申请与释放，以及对之前数据进行拷贝
    删除：在最后删除：很快
    在中间删除：内存拷贝
    适用场景：经常随机访问，且不经常对非尾节点进行插入和删除
  2. list：
    动态链表，在堆上分配空间，每插入一个元素都会分配空间，每删除一个元素都会释放空间
    底层：双向链表
    性能：
    访问：随机访问能力很差，只能快速访问头尾结点
    插入：很快，一般是常数开销
    删除：很快，一般是常数开销
    适用场景：经常插入删除大量数据
  3. vector与list区别：
    （1）vector底层实现是数组，list是双向链表
    （2）vector支持随机访问，list不支持
    （3）vector是顺序内存，list不是
    （4）vector在中间结点插入或删除会导致内存拷贝，list不会
    （5）vector一次性分配好内存，不够时才进行2倍扩容，list每次插入新节点都会进行内存申请
    （6）vector随机访问性能好，插入删除性能差，list随机访问性能差，插入删除性能好
  4. 二者应用：
    （1）vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随机访问，而不在乎插入和删除的效率，使用vector
    （2）list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关系随机访问，则应使用list

STL中的迭代器的作用

  1. iterator迭代器模式又叫做cursor游标模式，用于提供一种方法顺序访问一个聚合对象中的各个元素，而又不需暴露该对象的内部表示，也可以叫做：iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序(由iterator提供的方法)访问聚合对象中的各个元素。
  2. 由于iterator模式与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如STL中的list、vector、statck等容器类及ostream_iterator等扩展iterator。
  3. 迭代器和指针的区别：
    （1）迭代器不是指针，是类模板，表现得像指针。他只是模拟了指针的一些功能，通过重载了指针的一些操作符，->、*、++、–等。迭代器封装了指针，是一个“可遍历STL容器内全部或部分元素”的对象，本质是封装了原生指针，是指针概念的一种提升，提供了比指针更高级的行为，相当于一种智能指针，它可以根据不同的数据结构来实现不同的++、–等操作。
    （2）迭代器返回的是对象的引用而不是对象的值，所以cout只能输出迭代器使用*取值后的值而不能直接输出其自身。
  4. 迭代器产生的原因：
    iterator类的访问方式就是把不同的集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。

STL中resize和reserve的区别

  1. resize():改变当前容器内含有元素的数量(size())，eg: 
     vector<int> v;
 v.resize(len);

    v的size变成len，如果原先的size小于len，那么容器新增len-size个新元素，元素的值默认为0，当v.push_back(3)后，3放在下标为len的位置，此时size为len+1

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