在C++的STL中,我们有一个模板类
一个解释是,如果我们想要在vector的前面推入/弹出元素,则必须将数组中的每个元素向前移动一步,这将花费
但是我认为这并非总是如此。考虑到如果我们使用循环数组来实现
<vector>
。我们知道它支持O(1)
的随机访问和尾部修改。我的问题是为什么我们不在<vector>
中定义push_front或pop_front?一个解释是,如果我们想要在vector的前面推入/弹出元素,则必须将数组中的每个元素向前移动一步,这将花费
O(n)
的时间。但是我认为这并非总是如此。考虑到如果我们使用循环数组来实现
<vector>
,我们可以从向量的前面和尾部同时实现O(1)
的推入/弹出,而不会失去O(1)
随机访问的能力。因此,我个人无法想到任何原因,除了轻微的开销外,不实现<vector>
的push_front
/pop_front
。您有什么想法?