C++中为何std::vector删除首元素不是O(1)操作？

这问题问到点子上了，本质是没搞清楚std::vector的核心设计定位——它是连续存储的动态数组，所有行为都围绕这个核心规则展开，随便改首指针会直接打破它的设计逻辑：

• 破坏连续存储的语义约定：C++标准明确要求vector的元素必须在内存中连续排布，data()返回的指针必须指向第一个有效元素，operator[]的索引是从首元素开始的偏移量。如果只是把首指针后移，原来的首元素还占着内存空间，此时vector的内存块里前面会有一段“无效”区域，这会导致所有依赖连续存储的操作出错——比如用std::copy复制vector内容时，会把那段无效区域也包含进去；或者其他代码直接用data()指针做C风格数组操作时，拿到的是错误的起始地址。

• 内存与对象管理混乱：vector会自动管理元素的生命周期和内存分配。如果只是移动首指针，被“跳过”的首元素（如果是类对象）不会被调用析构函数，会造成资源泄漏；而且vector内部记录的内存起始地址还是原来的位置，后续调用clear()、resize()或者析构vector时，会错误地释放整个内存块，包括那段被跳过的区域，很可能导致重复释放或者内存泄漏。

• 容器状态不一致：vector的size()表示有效元素数量，capacity()表示已分配的总内存容量。如果指针后移，你需要手动调整size()，但capacity()的计算是基于初始内存块的大小，这会导致size()和capacity()的关系完全混乱——比如当你调用push_back()时，vector会以为当前内存还剩capacity() - size()的空间，但实际上前面已经浪费了一段，很可能在不需要扩容的时候错误扩容，或者在需要扩容时计算错误。

• 这其实是另一种容器的思路：如果想要O(1)删除首元素的功能，C++标准库已经提供了std::deque（双端队列，首尾操作都是O(1)，内存分段连续）或者std::list（双向链表，首尾删除O(1)但不连续）。vector的定位就是牺牲首尾插入删除的效率，换取随机访问和连续存储的优势，这是设计取舍的结果。

内容的提问来源于stack exchange，提问作者ritvix