C++ STL 容器使用的底层数据结构

STL 容器底层数据结构查找插入删除vector动态数组O(1) 随机访问尾部 O(1)均摊中间 O(n)array静态数组O(1)不支持扩容不支持deque分段连续数组Map BlockO(1)两端 O(1)两端 O(1)list双向链表O(n)O(1)O(1)forward_list单向链表O(n)O(1)O(1)set红黑树O(log n)O(log n)O(log n)multiset红黑树O(log n)O(log n)O(log n)map红黑树O(log n)O(log n)O(log n)multimap红黑树O(log n)O(log n)O(log n)unordered_set哈希表平均 O(1)平均 O(1)平均 O(1)unordered_map哈希表平均 O(1)平均 O(1)平均 O(1)unordered_multiset哈希表平均 O(1)平均 O(1)平均 O(1)unordered_multimap哈希表平均 O(1)平均 O(1)平均 O(1)stack默认deque也可vector、list—栈顶 O(1)栈顶 O(1)queue默认deque—尾部 O(1)头部 O(1)priority_queue二叉堆Heap最大值 O(1)O(log n)O(log n)STL 算法底层算法时间复杂度sort()Introsort快速排序 堆排序 插入排序O(n log n)stable_sort()归并排序O(n log n)partial_sort()堆排序O(n log k)nth_element()Introselect快速选择平均 O(n)make_heap()建堆O(n)push_heap()堆上滤O(log n)pop_heap()堆下滤O(log n)binary_search()二分查找O(log n)lower_bound()二分查找O(log n)upper_bound()二分查找O(log n)equal_range()二分查找O(log n)find()顺序查找O(n)find_if()顺序查找O(n)count()顺序遍历O(n)for_each()顺序遍历O(n)transform()顺序遍历O(n)copy()顺序复制O(n)copy_if()顺序复制O(n)remove()双指针快慢指针O(n)unique()双指针O(n)reverse()双指针交换O(n)rotate()三次翻转/循环移动O(n)merge()归并O(n)set_union()双路归并O(n)set_intersection()双路归并O(n)set_difference()双路归并O(n)min_element()顺序扫描O(n)max_element()顺序扫描O(n)accumulate()累加O(n)