C++ 数据结构与算法
C++ 容器与算法
-
vector 容器: 动态数组，可动态扩容，扩容时重新开辟原有长度2倍的长度，然后将原有的数据拷贝过来。
- push_back : O(1)
- insert: O(N)
- 查找: O(1)
- pop_back:O(1)
- erase:O(N)
-
list 容器：list 底层是一个双向链表，而且是一个环状双向链表
- push_back : O(1)
- push_front:O(1)
- insert: O(1)
- 查找: O(1)
- pop_back:O(1)
- pop_front:O(1)
- erase:O(1)
-
deque 容器（双端队列）：
- push_back : O(1)
- push_front:O(1)
- insert: O(N)
- 查找: O(1)
- pop_back:O(1)
- pop_front:O(1)
- erase:O(N)
-
deque 是按页或块来分配存储器的，每页包含固定数目的元素
-
采用一块所谓的 map 作为主控。这里的 map 是一小块连续空间，其中每个元素都是指针，指向另一段连续线性空间
-
stack
- SGI STL 便以 deque 作为缺省情况下的 stack 底部结构
-
queue (单端队列)
- SGI STL 便以 deque 作为缺省情况下的 queue 底部结构
-
priority_queue
深入PriorityQueue底层原理与源码解析- 一个以vector 表现的 complete binary tree.max-heap 实现
- PriorityQueue是一个小顶堆；
- PriorityQueue是非线程安全的；
- PriorityQueue不是有序的，只有堆顶存储着最小的元素；
- 入队就是堆的插入元素的实现；
- 出队就是堆的删除元素的实现
- 时间复杂度
- insert: O(logN)
- pop: O(1)
-
set 、 multiset、map、multmap
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多，map,multimap,set,multiset底层实现都是红黑树。-
multiset, multmap 和 set map实现一致，只是key一致的value 放在一个容器里（网上说是set 但我觉得list 更合适），
-
RB-Tree 红黑数实现
-
插入: O(logN)
-
查看:O(logN)
-
删除:O(logN)
-
-
unordered_map: 就是hash_map，和java的HashMap实现一致
-
插入:O(1)，最坏情况O(N)。
查看:O(1)，最坏情况O(N)。
删除:O(1)，最坏情况O(N)。
-
-
RB-Tree ：近似的平衡二叉树
-
B+树： 减少磁盘IO
-
- 建堆：O(N)
- 重建堆：O(NlogN)
-
STL里resize和reserve的区别:
- resize扩充元素且以0赋值
- reserve扩充容量
-
STL容器利用迭代器删除元素小结
- 关联容器(如map, set, multimap, multiset)：仅仅会使当前的iterator失效，只要在erase时，递增当前的iterator即可
- 序列式容器（如vector，deque，list等）：删除当前的iterator会使后面所有元素的iterator都失效，不过erase方法可以返回下一个有效的iterator
-
STL的allocator：标准库allocator类定义在头文件memory中，它帮助我们将内存分配和对象构造分离开来。它提供一种类型感知的内存分配方法，它分配的内存是原始的、未构造的。https://blog.csdn.net/fengbingchun/article/details/78943527
-
STL内存优化：https://blog.csdn.net/u010183728/article/details/81531392
