vector

  vector与数组类似,拥有一段连续的内存空间,并且起始地址不变。便于随机访问,时间复杂度为O(1),但因为内存空间是连续的,所以在进入插入和删除操作时,会造成内存块的拷贝,时间复杂度为O(n)。

  此外,当数组内存空间不足,会采取扩容,通过重新申请一块更大的内存空间进行内存拷贝。

List

  list底层是由双向链表实现的,因此内存空间不是连续的。根据链表的实现原理,List查询效率较低,时间复杂度为O(n),但插入和删除效率较高。只需要在插入的地方更改指针的指向即可,不用移动数据。

迭代器支持不同

异:vector中,iterator支持 ”+“、”+=“,”<"等操作。而list中则不支持。

同:vector<int>::iterator和list<int>::iterator都重载了 “++ ”操作。

转:https://www.cnblogs.com/ktao/p/8577700.html

05-08 14:50