自学内容网 自学内容网

性能&设计模式

class Singleton {
public:
static Singleton& getInstance() {
    static Singleton instance; // 局部静态变量
    return instance;
}
private:
    Singleton() {}
    Singleton(const Singleton&) = delete; // 禁止拷贝
    Singleton& operator=(const Singleton&) = delete; // 禁止赋值
};

容器类型

插入性能

删除性能

查找性能

随机访问性能

内存使用情况

底层实现

std::vector

末尾 O(1),其他 O(n)

末尾 O(1),其他 O(n)

O(n)

O(1)

紧凑(数组式存储)

动态数组

std::deque

前后 O(1)

前后 O(1)

O(n)

O(1)

较紧凑

分块数组

std::list

O(1)

O(1)

O(n)

O(n)

高(每个元素有指针)

双向链表

std::forward_list

O(1)

O(1)

O(n)

O(n)

较低

单向链表

std::map

O(log n)

O(log n)

O(log n)

O(log n)

较高(树结构)

红黑树

std::unordered_map

O(1) 均摊,最坏 O(n)

O(1) 均摊,最坏 O(n)

O(1) 均摊,最坏 O(n)

不支持

较高(哈希表开销)

哈希表

std::set

O(log n)

O(log n)

O(log n)

O(log n)

较高(树结构)

红黑树

std::unordered_set

O(1) 均摊,最坏 O(n)

O(1) 均摊,最坏 O(n)

O(1) 均摊,最坏 O(n)

不支持

较高(哈希表开销)

哈希表

std::stack

O(1)

O(1)

不支持

不支持

与底层容器相同

deque / vector

std::queue

O(1)

O(1)

不支持

不支持

与底层容器相同

deque

std::priority_queue

O(log n)

O(log n)

O(1)

不支持

与底层容器相同

堆结构

  • mapmap 中的元素是按 键值的升序 存储的。由于底层使用了红黑树结构,每次插入元素时会自动对元素进行排序。你可以在遍历时按键值的顺序访问元素。

  • unordered_mapunordered_map 中的元素 没有特定的顺序。哈希表不维护元素的顺序,元素的插入顺序和访问顺序没有特定规则,完全取决于哈希值的分布。


原文地址:https://blog.csdn.net/Algo_x/article/details/142568722

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!