欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C++ stl 容器 复杂度

程序员文章站 2024-03-15 22:47:48
...

https://www.cnblogs.com/LloydDracarys/articles/8872804.html

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)。
记住,如果你采用合适的哈希函数,你可能永远不会看到最坏情况。但是记住这一点是有必要的。
相关标签: stl 复杂度