数组的时间复杂性
操作时间复杂度访问头插(向量中无此操作) o )1) push_backO(1)1) insertO(n ) n ) eraseO(n ) n )随机o )1)链表的时间复杂度
操作时间复杂度push_front (插头) o )1) push_backO(1)1) insertO(1)1) eraseO(1)1)随机访问
o(n )如何理解vector的erase的时间复杂度是o(n)?
因为向量的底部是连续数组，所以必须在erase之后重新定位区域。 此时间等于删除元素的时间和移动其余元素的时间。
becausevectorsuseanarrayastheirunderlyingstorage， erasingelementsinpositionsotherthanthevectorendcausesthecontainertorelocatealltheelementsafterthesegmenterasedtotheirnewposition inefficientoperationcomparedtotheoneperformedforthesameoperationbyotherkindsofsequencecontainers (
complexity 3360 linearonthenumberofelementserased (destructions ) plusthenumberofelementsafterthelastelementdeleted (移动) )
(删除)析构函数操作)的元素个数；剩馀元素个数；移动操作) )。 那就是o ) n。
英文来源：http://www.cplusplus.com/reference/vector/vector/erase /
如何理解随机访问？
例如vector，iterator i=v.begin () n，得到第N 1个要素的迭代器。 可以直接用n的方法跳到想访问的地方。
另一方面，list不能是n的方法，因为要到达第N 1个元素的位置，而不是随机访问，必须逐个扫描才能找到。 需要使用高级(I，n )的方式。