c++ - 在数组的开头添加一个元素并移动其余元素但保持大小不变

Question

我需要按以下格式创建 vector/数组:

arr[10] = [1, 2, 3, 4, 5, 6, 7, 8, 9 ,10]

我想在开头添加一个新元素，之后所有元素都向右移动，最后一个元素被删除。结果应该是:

arr[10] = [new_int, 1, 2, 3, 4, 5, 6, 7, 8, 9]

我如何在 C++ 中执行此操作？我是否必须编写一个函数，或者已经存在一个函数，例如 .append 或 .pushback？

Answer 1

如果它是一个std::vector，简单的解决方案是:

vec.pop_back();
vec.insert(vec.begin(), new_int);

渐近复杂度与实现此目的的任何其他方法相同(pop_back() 是 O(1)，insert in head 是 O(n)，没有重新分配曾经执行过)但它暂时无缘无故地触及 vector 长度并且总体上做了更多的簿记工作。

一个更好的解决方案(对于 std::vector、std::array 以及 C 风格的数组都很好)是:

std::copy_backward(std::begin(vec), std::end(vec)-1, std::begin(vec)+1);
vec[0] = new_int;

同样，这应该具有 O(n) 复杂度，但“偏移量”较小(它完全按照它需要做的，仅此而已)。

---

现在，如果我们转向不同的数据结构，情况就不同了；使用 std::deque，您可以按照 @JesperJuhl 在他的回答中显示的那样进行操作； deque 两端的压入/弹出成本均摊为 O(1)，因此对于大多数用途来说速度相当快。

不过，如果您的缓冲区大小固定，通常您描述的操作的自然数据结构是固定大小的循环缓冲区；它不是由标准库提供的，但在 Boost 中有一个实现(此外，自己编写它也是一个很好的练习，包括迭代器和所有东西)。