map, set, multimap, and multiset采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:

• 插入: O(logN)
• 查看:O(logN)
• 删除:O(logN)

hash_map, hash_set, hash_multimap, and hash_multiset采用哈希表实现，不同操作的时间复杂度为：

• 插入:O(1)，最坏情况O(N)。
• 查看:O(1)，最坏情况O(N)。
• 删除:O(1)，最坏情况O(N)。

vector从名字看，随机访问的复杂度应该是O(1)

• 插入 insert vector O（n）
• 插入 push_back vector O（1）
• 删除 pop_back vector O（1）
• 删除 erase vector O（n）
• 查找特点元素的时间复杂度 O（n）

LinkedList 底层是双链表

• get() 获取第几个元素，依次遍历，复杂度O(n)
• add(E) 添加到末尾，复杂度O(1)
• add(index, E) 添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n)
• remove（）删除元素，直接指针指向操作，复杂度O(1)

说明：
STL中vector，push_back的时间复杂度为常数

因为：假定有 n 个元素,倍增因子为 m。那么完成这 n 个元素往一个 vector 中的push_back​操作，需要重新分配内存的次数大约为 logm(n)，第 i 次重新分配将会导致复制 m^i (也就是当前的vector.size() 大小)个旧空间中元素，因此 n 次 push_back操作所花费的总时间约为 n*m/(m - 1):

那么 n 个元素，n 次操作，每一次操作需要花费时间为 m / (m - 1)，这是一个常量.