Question

问几个vector 容器的问题

1.vector 容器用下标找到元素，是不是和数组一样是复杂度都是o(1)的，如果不是...这是怎么实现的..复杂度多少？
2.vector 容器把某一个元素删掉，后面的元素向前移，这个复杂度是多少？实现跟链表类似的还是和数组类似的？

Answer 1

1, vector内部是用堆数组实现的，下标引用操作和普通数组是一样的，常数时间o(1);

2:因为底层是数组，所以删除元素效率很低，比链表慢得多，复杂度是O(n);

Answer 2

1. 是O(1)
2. 复杂度是O(n)

Answer 3

vector是数组和 链表的组合，集成了他们的 优点