C++中list、vector、map、set的区别

一句话不看版:list封装了链表,vector封装了数组,map和set是标准关联容器,内部使用了红黑树。

vector使用连续内存,list是以链表形式存在的,vector支持[],list不支持[]。

vector对于随机访问速度很快,对于头插入很慢,对于尾插入很快。list对于随机访问速度很慢,但是对于插入速度很快,不需要拷贝和移动数据,只需要移动指针就行了。

Map,Set属于标准关联容器,使用了非常高效的平衡检索二叉树:红黑树,他的插入删除效率比其他序列容器高是因为不需要做内存拷贝和内存移动,而直接替换指向节点的指针即可。

Set和Vector的区别在于Set不包含重复的数据。Set和Map的区别在于Set只含有Key,而Map有一个Key和Key所对应的Value两个元素。

Map和Hash_Map的区别是Hash_Map使用了Hash算法来加快查找过程,但是需要更多的内存来存放这些Hash桶元素,因此可以算得上是采用空间来换取时间策略。

comments powered by Disqus