删除:O(1)，最坏情况O(N)。
Vector
vector（连续的( )空间存储，可以使用[ ]操作符）可以快速的访问随机的元素，快速的在末尾插入元素，但是在序列中间随机的插入、删除元素要慢。而且，如果一开始分配的空间不够时，有一个重新分配更大空间的过程。
连续存储结构，每个元素在内存上是连续的；支持高效的随机访问和在尾端插入/删除操作，但其他位置的插入/删除操作效率低下；相当于一个数组，但是与数组的区别为：内存空间的扩展。vector支持不指定vector大小的存储，但是数组的扩展需要程序员自己写。
STL内部实现时，首先分配（assign）一个非常大的内存空间预备进行存储，即capacity（）函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储
扩充空间（不论多大）都应该这样做：
（1）配置一块新空间
（2）将旧元素一一搬往新址
（3）把原来的空间释放还给系统
insert和erase时间复杂度O(1)
Deque
连续存储结构，即其每个元素在内存上也是连续的，类似于vector，不同之处在于，deque提供了两级数组结构， 第一级完全类似于vector，代表实际容器；另一级维护容器的首位地址。这样，deque除了具有vector的所有功能外，还支持高效的首/尾端插入/删除操作。在deque中不存在容量的概念，因为它维护的是一段动态的存储空间
deque 采用一块连续的空间存放指针，每个指针都指向一个连续的存储空间，成为缓冲区，这些缓冲区才是元素真正存储的空间。每个缓冲区的大小是相同的，所以当计 算deque的size时，不需要一个一个遍历（traverse）元素，是需要计算指针数组中一共使用了多少个指针，和最后一个指针指向缓冲区使用的个数数组和链表的区别，就可以计算出来。
deque中的元素就存在于这一段一段的缓冲区中。如果当存放指针的连续空间不足时，就需要像操作vector空间不足一样，开辟一段更大的内存空间，将原来的指针数组 拷贝到新的空间中去。
insert操作和erase操作相似，首先检查插入或者删除的位置，如果前面的元素较少，那么向前方扩张（收缩）；如果后面元素较少，反之。假设想前方扩张（收缩），将之前的元素一一移动，如果是插入，将插入的元素赋值给腾出的空间，若是删除，则pop_front第一个元素即可。
deque 双端队列 double-end queue
deque是在功能上合并了vector和list。
优点：
(1) 随机访问方便，即支持[ ]操作符和vector.at()
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop
缺点：
占用内存多使用区别：
（1）如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
（2）如果你需要大量的插入和删除，而不关心随机存取，则应使用list
（3）如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque
List
C++11中，针对顺序容器(如vector、deque、list)，新标准引入了三个新成员：emplace_front、emplace和emplace_back，这些操作构造而不是拷贝元素。这些操作分别对应push_front、insert和push_back，允许我们将元素放置在容器头部、一个指定位置之前或容器尾部。
当调用push或insert成员函数时，我们将元素类型的对象传递给它们，这些对象被拷贝到容器中。而当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素。
非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针，开销也比较大。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
Insert erase O（1）
优点：
(1) 不使用连续内存完成动态操作。
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop
缺点：
(1) 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()
(2) 相对于verctor占用内存多
使用区别：
（1）如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
（2）如果你需要大量的插入和删除，而不关心随机存取，则应使用list
（3）如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque
vector VS. list VS. deque：
a、若需要随机访问操作，则选择vector；
b、若已经知道需要存储元素的数目，则选择vector；
c、若需要随机插入/删除（不仅仅在两端），则选择list
d、只有需要在首端进行插入/删除操作的时候，还要兼顾随机访问效率，才选择deque，否则都选择vector。
e、若既需要随机插入/删除，又需要随机访问，则需要在vector与list间做个折中-deque。
f、当要存储的是大型负责类对象时数组和链表的区别，list要优于vector；当然这时候也可以用vector来 存储指向对象的指针，
同样会取得较高的效率，但是指针的维护非常容易出错，因此不推荐使用。
Free和delete区别
free释放内存的和delete可以说是两套代码，它们的逻辑不同，不能混用。用new申请的就yu要用delete翻译，用malloc申请的就要用free释放。
free 只是告诉操作系统回收recycle内存，而delete会先调用类的析构函数，然后才告诉操作系统回收内存。
首先, C++中的explicit关键字只能用于修饰只有一个参数的类构造函数, 它的作用是表明该构造函数是显示的, 而非隐式的, 跟它相对应的另一个关键字是implicit, 意思是隐藏的,类构造函数默认情况下即声明为implicit(隐式).
Implicit type conversion
递归
优点：
1. 简洁
2.在树的前序，中序，后序遍历算法中，递归的实现明显要比循环简单得多。
缺点：
1.递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间。->效率
2.递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如fibonacci斐波那契数列的递归实现。->效率
3.调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。->性 能
size_t是一种数据相关的无符号类型，它被设计得足够大以便能够内存中任意对象的大小在C++中，设计 size_t 就是为了适应多个平台的 。size_t的引入增强了程序在不同平台上的可移植性。
动态规划和贪心算法都是一种递推算法均用局部最优解来推导全局最优解不同点：
贪心算法：
1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解 推导下一步的最优解，而上一部之前的最优解则不作保留。
2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。
动态规划算法：
1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解
2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解
3.边界条件：即最简单的，可以直接得出的局部最优解
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。红黑树能自平衡
● 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。
● 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。
● 变色：结点的颜色由红变黑或由黑变红。
左旋–只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。
右旋–只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。
所以旋转操作是局部的。另外可以看出旋转能保持红黑树平衡的一些端详了：当一边 子树的结点少了，那么向另外一边子树“借”一些结点；当一边子树的结点多了，那么向另外一边子树“租”一些结点。
红黑树插入：插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。查找插入的父结点很简单。
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号 从1至n的结点一一对应时称之为完全二叉树。
满二叉树
该节点要么是叶子结点，要么是有两个字节点的节点。
完全二叉树
对于一颗二叉树，假设其深度为d（d>1）。除第d层外的所有节点构成满二叉树，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
平衡二叉树（AVL）
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树。
红黑树
红黑树是一颗特殊的二叉查找树，除了二叉查找树的要求外，它还具有以下特性：
每个节点或者是黑色，或者是红色。
根节点是黑色。
每个叶子节点（NIL）是黑色。[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
如果一个节点是红色的，则它的子节点必须是黑色的。
从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
B树
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构
B+
B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使 得B+树每个非叶子节点所能保存的关键字大大增加；
B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
最后，大佬的这份技术岗面试笔记还包含了网络、设计模式、编程语言和其它技术类面试的众多知识点，总结得非常详细，一共有60多页，满满的都是干货！如果有需要的同学，欢迎大家关注【校招巴士】公众号后，后台回复关键字：【技术岗面试笔记】，获取该面试笔记的完整pdf！！！
近期热门名企内推
点击文字，查看内推详情
||
|||
||||
||||
———END———
限 时 特 惠：本站每日持续更新海量各大内部创业教程，一年会员只需128元，全站资源免费下载点击查看详情
站 长 微 信：jiumai99
×