c++ - 使用 memcpy 提高数组中随机插入的性能

Question

我知道数组提供对其任何元素的恒定时间访问，但是从开始或中间插入或删除元素需要移动后续元素，有时需要调整大小和复制整个数组。这可以在最坏的情况下给出线性复杂度。

我们能否通过使用 memcpy 使数组中的随机插入更有效，如下例所示。

#include <iostream>
#include <cstring>
using namespace std;
int main() {
    // your code goes here
    int arr[16] = {0};
    for ( int i = 0 ; i < 10 ; i++ )
    {
        arr[i] = 1;
    }
    std::cout << std::endl << "INPUT ARR:";
    for ( int i = 0 ; i < 16 ; i++ )
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;


    std::memcpy(arr+9,arr+8,sizeof(int)*2); arr[8] = 9;// std::cout << std::endl << "NO " << *(arr+8);
    for ( int i = 0 ; i < 16 ; i++ )
    {
        std::cout << arr[i] << " ";
    }
    return 0;
}

由于 memcpy 是直接在硬件中使用 DMA 实现的，没有任何 CPU 干扰，这种方法可以加快数组中随机位置的插入或删除。我错了吗？

提前致谢

Answer 1

Since memcpy is implemented directly in hardware using DMA without any CPU interference

这不是真的，至少在现代 x86 CPU 上是这样。参见 x86-64 GNU libc memcpy implementation .

另一个注意事项是 memcpy 不能用于重叠的内存区域。为此需要使用 memmove。