STL Flashcards
vector和list的区别
从概念上来说，vector是一个顺序表，它的物理存储方式是一片连续的内存空间，而list是一个链表，是不连续的内存空间
从底层实现上来说，vector是由用动态数组实现的，而list是用带头双向链表实现的，vector在插入新元素的时候，如果元素数量没有超过capacity，就是还有剩余空间的话会直接添加元素，如果没有剩余空间，则会重新开辟一块原有容量几倍大小的空间，这里的话vs是1.5倍，g++是两倍，然后将原空间元素复制到新空间，再在新空间里增加元素，之后再释放原空间。而list是每插入一个元素就分配一个节点的空间，没删除一个元素就释放一个节点的空间
从性能上来说，因为vector是数组，支持随机访问，所以访问元素是O(1)的复杂度，尾插也是O(1)，除了尾插之外的插入需要把插入位置后面的元素依次向后挪一位，所以复杂度是O(n)，但是增加元素的时候如果容量不够了就要进行内存申请、拷贝和释放，删除同理，尾删是O(1)，除了尾删都要把后面元素往前挪。而list不支持随机访问，所以除了头尾节点都需要遍历访问，但是list的元素插入删除操作就都是O(1)的复杂度了
所以，从使用上来说，vector适用于需要经常随机访问，并且不会有太多对非尾节点进行插入或删除操作的场景，而list适用于不需要随机访问但是需要经常插入或删除数据，还有就是vector使用的时候很容易就会造成严重的迭代器失效问题，list的迭代器失效问题则没那么复杂
迭代器失效问题
迭代器失效分成两种类型的问题，一种是由于插入或删除元素，导致容器中的元素整体发生移动导致存放容器元素的原空间不再有效，从而导致指向原空间的迭代器失效，另一种是由于删除元素导致原本指向改元素的迭代器失效
vector中的迭代器失效问题
vector中上述两种迭代器失效问题都存在，比如第一种，有一个vector迭代器it，当我们使用insert操作时，可能会导致增容，增容后it还指向原来的空间，但原来的空间已经被释放了，第二种比如我们用v.erase(it)删除掉it位置的数据，这样就会导致it迭代器失效，此时我们再访问it，对它解引用，就是访问非法内存了
list中的迭代器失效问题
list的迭代器失效问题就只有第二种，删除掉一个节点后，原本指向该节点的迭代器就失效了，因为list的存储空间不是连续的所以不会有第一种的问题
deque中的迭代器失效问题
deque也会出现这两种迭代器失效的问题，但是deque在头部或者尾部插入元素不会使迭代器失效，头部或尾部删除元素只会出现第二种失效，而在中间插入或删除就会出现第一种迭代器失效问题
set和map中的迭代器失效问题
和list相同，插入或删除元素不会使其它迭代器失效，只会在删除时导致被删除的元素的迭代器失效
讲一下map
map是一个关联式容器，它的每一个元素是一个键值对，也就是key和value，它会按照key的大小由小到大的对元素进行排序，并且在map中key是唯一的，不会出现两个相同的key，它的底层实现通常是红黑树
map相同key是否覆盖问题
当key已经存在的情况下，用insert插入相同key，value还是原来的value，但是用中括号插入key，value会变成新value
讲一下multimap
multimap也是一个关联式容器，它和map一样都会按key的顺序存储key和value映射得到的键值对，但是和map不同的地方在于，map不允许key重复而multimap允许key重复，multimap底层也是通过红黑树实现
讲一下set
set也是一种关联式容器，它的底层实际存放的是键和值都是value的键值对，但是我们使用的时候只用插入value，每个value都必须是唯一的，并且是const修饰的，不能在容器中修改元素，但是可以插入或删除，它的元素也会由小到大排序，底层是用红黑树实现
讲一下multiset
multiset和set的区别在于multiset中的元素可以重复，而set中value是唯一的
map和set的区别
map和set都是C++的关联式容器，其底层实现都是红黑树，它们的区别在于
首先map在使用时插入的元素是一个key-value键值对，而set在使用时插入的则只有value，但是其实set的底层也是有键值对的，只不过它的键和值都是value
第二点是在map中只能修改元素的value而不能修改元素的key，但是set的元素是const修饰的，不能进行修改，只能删除再重新插入
还有就是map支持中括号重载的下标操作，在中括号里放入key就能找到对应的元素，如果key不存在还能直接插入非常方便，但是set就不支持
讲一下deque
deque是一个双端队列，一般是由动态数组实现，与vector相比，deque在头部和尾部进行数据插入删除操作时会更加高效，它的内部实现原理比vector复杂，它不能保证所有的元素存储在连续的空间中。deque一般用的比较少，简单存储元素一般就用vector，插入或者删除操作比较多就用list，所以很少用deque，它最大的应用就是作为标准库中stack和queue的底层结构
为什么选择deque作为stack和queue的底层默认容器？
- stack和queue不需要遍历，只需要在固定的一端或者两端进行操作
2. 在stack中元素增长时，deque比vector效率高，queue中元素减少时deque效率高，而且内存使用率高
vector的底层实现和vector的扩容机制
vector通过一个动态数组实现，在初始化的时候会在堆上给它分配一块空间，同时设定一个capacity，以及一个size，size描述vector中真正有几个元素，而capacity则描述这片空间最大能存放的元素个数，每增加或者删除元素的时候，size也会增加或者减少，当发现size等于capacity的时候就说明原有空间已经存满了，这时就会重新开辟一块内存空间，把capacity增长到1.5倍或者2倍这样子，然后把原有的元素复制新的空间，再在新空间里增加刚插入的元素，之后再释放原来的空间
vs 下(PJ版本STL)capacity是1.5倍增长的，g++(SGI版本STL)是按2倍增长的
vector迭代器失效问题
vector在使用的过程中可能会出现一个迭代器失效的问题，可能会引起vector底层空间改变的操作都会导致迭代器失效，例如erase、push_back、insert、resize、reserve这些。比如说，有一个vector迭代器it，我们用v.erase(it)删除掉it位置的数据，这样就会导致it迭代器失效，此时我们再访问it，对它解引用，就是访问非法内存了。还有就是insert操作也可能导致迭代器失效，因为insert可能会导致增容，增容后it还指向原来的空间，但原来的空间已经被释放了
我们可以通过使用erase和insert的返回值来解决迭代器失效的问题，erase的返回值是删除元素的下一个元素的位置，insert的返回值是新插入的元素的位置，当我们对一个迭代器进行erase或者insert操作之后，不要立即使用原来的迭代器，把erase或者insert的返回值赋给原迭代器，再对迭代器进行操作就可以了
list迭代器失效问题
list在插入元素时不会导致迭代器失效，在删除元素时，只会导致当前迭代器失效，其它迭代器不受影响
