use*_*042 1 c++ performance list vector
有人知道为什么在列表中间插入一个元素比在向量中间插入一个元素要快吗？
我更喜欢使用矢量,但如果可以的话我被告知使用列表.任何人都能解释为什么？是否始终建议使用列表而不是向量？
如果我逐字地提出问题,找到数组的中间(std :: vector)是一个简单的操作,你将长度除以2,然后向上或向下舍入以获得索引.找到双向链表(std :: list)的中间部分需要遍历所有元素.即使你知道它的大小,你仍然需要走过一半的元素.因此std :: vector比std :: list快,换句话说,一个是O(1),而另一个是O(n).
插入已知位置需要对数组的相邻元素进行混淆,并且仅在另一个节点中链接以获得双向链表,正如其他人在此处所解释的那样.因此,带有O(1)的std :: list比带有O(n)的std :: vector快.
一起,为了插入正确的中间,我们有数组的O(1)+ O(n)和双链表的O(n)+ O(1),使得插入中间O(n)容器类型.所有这些都省去了CPU缓存和分配器速度之类的事情,它只是比较了"简单"操作的数量.总之,您需要了解如何使用容器.如果你真的在随机位置插入/删除很多,std :: list可能会更好.如果你很少这样做,然后只读取容器,std :: vector可能会更好.如果你只有十个元素,那么所有的O(x)都可能毫无价值,你应该选择你最喜欢的元素.