c++ - 为什么在 C++ 中维护有序数组比 Vector 快

Question

我正在创建一个大小为 100 的数组和 vector ，并生成一个随机值，并尝试保持数组和 vector 的排序。 这是我的代码

vector<int> myVector;
int arr[SIZE];
clock_t start, finish;
int random;
for(int i=0; i<SIZE;i++)
{
    myVector.push_back(0);
    arr[i] = 0;
}
    //testing for Array
start = clock(); 
for(int i=0; i<MAX;++i)
{
    random = getRandom(); //returns rand() % 100
    for(int j=0; j<SIZE;++j){
        if(random > arr[j])
        {
            for(int k = SIZE - 1; k > j ; --k)
            {
                arr[k] = arr[k-1];
            }
            arr[j] = random;
            break;
        }
    }
}
finish = clock();
cout << "Array Time " << finish - start << endl;

//Vector Processing
start = clock();
for(int i=0; i<MAX;++i)
{
    random = getRandom(); //returns rand() % 100
    for(int j=0; j<SIZE;++j){
        if(random > myVector[j])
        {
            for(int k = SIZE - 1; k > j ; --k)
            {
                myVector[k] = myVector[k-1];
            }
            myVector[j] = random;
            break;
        }
    }
}
finish = clock();
cout << "Vector Time " << finish - start << endl;

输出如下:

阵列时间:5

vector 时间:83

在这种情况下，我无法理解为什么 vector 比数组慢？ 这是否与优先选择 Vector 而不是 Array 的经验法则相矛盾。

请帮忙!

Answer 1

首先:编程中的许多经验法则不是关于在性能上增加几毫秒，而是关于管理复杂性，从而避免错误。在这种情况下，它是关于执行范围检查，大多数 vector 实现在 Debug模式下都会执行，而数组则不会。它还与动态数组的内存管理有关 - vector 确实管理它的内存本身，而您必须在数组中手动​​执行此操作，冒着引入内存泄漏的风险(永远忘记 delete[] 或使用 delete 代替？我是你有!)。这与易用性有关，例如调整 vector 的大小或在中间插入元素，对于手动管理的数组来说这是一项乏味的工作。
换句话说，性能测量永远不会与经验法则相矛盾，因为经验法则从不以性能为目标。性能测量只是不遵守编码指南的少数可能原因之一。

乍一看，我猜你没有启用优化。 vector 性能损失的主要来源是许多 vector 实现为调试构建启用的索引检查。这些不会在优化构建中发挥作用，因此这应该是您的首要关注点。 经验法则:未启用优化的性能测量毫无意义

如果启用优化仍然显示阵列的更好性能，则还有另一个区别:

数组存储在栈中，因此编译器可以直接使用地址并在编译时计算地址偏移量，而 vector 元素存储在堆中，编译器将不得不取消引用存储在 vector 中的指针。我希望优化器取消对指针的引用一次并计算从该点开始的地址偏移量。尽管如此，与编译时计算的地址偏移量相比，性能可能会有所下降，尤其是在优化器可以稍微展开循环的情况下。 这仍然不与经验法则相矛盾，因为您在这里比较的是苹果和梨。经验法则说，

Prefer std::vector over dynamic arrays, and prefer std::array over fixed arrays.

因此要么使用动态分配的数组(请包括某种delete[])，要么将固定大小的数组与std::array 进行比较。在 C++14 中，您必须考虑游戏中的新候选者，即 std::dynarray 和 C++14 VLA，不可调整大小，运行时长度数组可与 C 的 VLA 相媲美。

更新: 正如评论中指出的那样，优化器擅长识别没有副作用的代码，例如您从未读取过的数组操作。 std::vector 实现非常复杂，优化器通常不会看穿这几层间接寻址并优化所有插入，因此与一些时间相比，您将获得数组的零时间 vector 。在循环之后读取数组内容将禁用这种粗鲁的优化。