性能设计模式
class Singleton {
public:
static Singleton& getInstance() {static Singleton instance; // 局部静态变量return instance;
}
private:Singleton() {}Singleton(const Singleton&) = delete; // 禁止拷贝Singleton& operator=(const Singleton&) = delete; // 禁止赋值
};| 容器类型 | 插入性能 | 删除性能 | 查找性能 | 随机访问性能 | 内存使用情况 | 底层实现 |
|
| 末尾 O(1)，其他 O(n) | 末尾 O(1)，其他 O(n) | O(n) | O(1) | 紧凑（数组式存储） | 动态数组 |
|
| 前后 O(1) | 前后 O(1) | O(n) | O(1) | 较紧凑 | 分块数组 |
|
| O(1) | O(1) | O(n) | O(n) | 高（每个元素有指针） | 双向链表 |
|
| O(1) | O(1) | O(n) | O(n) | 较低 | 单向链表 |
|
| O(log n) | O(log n) | O(log n) | O(log n) | 较高（树结构） | 红黑树 |
|
| O(1) 均摊，最坏 O(n) | O(1) 均摊，最坏 O(n) | O(1) 均摊，最坏 O(n) | 不支持 | 较高（哈希表开销） | 哈希表 |
|
| O(log n) | O(log n) | O(log n) | O(log n) | 较高（树结构） | 红黑树 |
|
| O(1) 均摊，最坏 O(n) | O(1) 均摊，最坏 O(n) | O(1) 均摊，最坏 O(n) | 不支持 | 较高（哈希表开销） | 哈希表 |
|
| O(1) | O(1) | 不支持 | 不支持 | 与底层容器相同 |
|
|
| O(1) | O(1) | 不支持 | 不支持 | 与底层容器相同 |
|
|
| O(log n) | O(log n) | O(1) | 不支持 | 与底层容器相同 | 堆结构 |
-
map：map中的元素是按 键值的升序 存储的。由于底层使用了红黑树结构，每次插入元素时会自动对元素进行排序。你可以在遍历时按键值的顺序访问元素。 -
unordered_map：unordered_map中的元素 没有特定的顺序。哈希表不维护元素的顺序，元素的插入顺序和访问顺序没有特定规则，完全取决于哈希值的分布。