为什么用vector错误用数组就正确？

Question

我做算法题的时候需要数据类型long long类型，数据个数int类型，我用vector总是结果错误，使用数组就可以正确AC，这是不是和vector的某种特性有关呢？
题目：求数组中逆序对的个数
代码（结果错误的，但是我自己测试的是对的）

#include<iostream>
#include<vector>
#include<fstream>
using namespace std;
vector<int>input;
vector<int>now;
long long mergesort(int left, int right) {
    now.clear();
    if (left >= right)return 0;
    int mid = (left + right) / 2;
    long long res = mergesort(left, mid) + mergesort(mid+1, right);
    int i = left,j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (input[i] <= input[j]) {
            now.push_back(input[i]); k++; i++;
        }
        else {
            now.push_back(input[j]);
            k++; j++;
            res += mid - i + 1;
        }
    }
    while (i <= mid) { now.push_back(input[i]); i++; k++; }
    while (j <= right) { now.push_back(input[j]); k++; j++; }
    for (int i = left, j = 0; i <= right&&j<=k; i++, j++) {
        input[i] = now[j];
    }
    return res;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int now;
        scanf("%d", &now);
        input.push_back(now);
    }
    
    
    
    printf("%lld", mergesort(0, n - 1));
    return 0;
}

代码（AC的）

#include<iostream>
#include<vector>
#include<fstream>
using namespace std;
int input[500003];
int now[500003];
long long mergesort(int left, int right) {
    if (left >= right)return 0;
    int mid = (left + right) >> 1;
    long long res = mergesort(left, mid) + mergesort(mid+1, right);
    int i = left,j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (input[i] <= input[j]) {
            //now.push_back(input[i]); k++; i++;
            now[k++]=input[i++];
        }
        else {
            //now.push_back(input[j]);
            now[k++]=input[j++];
            //k++; j++;
            res += mid - i + 1;
        }
    }
    while (i <= mid) { 
        //now.push_back(input[i]); i++; k++; 
        now[k++]=input[i++];
        
    }
    while (j <= right) { 
        //now.push_back(input[j]); k++; j++; 
        now[k++]=input[j++];
    }
    for (int i = left, j = 0; i <= right&&j<=k; i++, j++) {
        input[i] = now[j];
    }
    return res;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d",&input[i]);
    }    
    printf("%lld", mergesort(0, n - 1));
    return 0;
}

Answer 1

在你的代码中，使用 vector 和数组时出现了不同的结果，这主要是由于 vector 的动态特性以及你在处理 vector 时的一些细节问题导致的。下面来分析一下可能的原因：

1、vector 的动态性：与数组不同，vector 在运行时可以改变大小。当你向 vector 中添加元素时，如果当前容量不足以容纳新的元素，vector 会自动重新分配更大的内存空间，并将原有元素复制到新空间中。这个过程可能会导致性能下降，尤其是在频繁添加元素的情况下。
2、vector 的 push_back 方法：每次调用 push_back 时，如果 vector 当前的容量不足以容纳新的元素，它会触发上述的重新分配过程。这不仅消耗时间，还可能导致原有的迭代器、引用和指针失效。在你的代码中，虽然没有直接看到这个问题，但是频繁的 push_back 调用可能会导致不必要的开销。
3、边界条件处理：在使用 vector 的版本中，你在合并排序的过程中使用了 now.push_back(...) 来添加元素，同时也在循环中使用了 k++ 来跟踪索引。而在数组版本中，你直接通过 now[k++] = ... 来添加元素。这两种方法本质上是一样的，但是如果 vector 的 push_back 引发了重新分配，那么 k 的值可能会与实际的 vector 大小不匹配，从而导致错误的结果。
4、初始化和清理：在每次递归调用 mergesort 时，你都调用了 now.clear() 来清空 vector。这会导致 vector 的容量保持不变，但是大小变为0。当再次向 vector 添加元素时，如果之前的容量足够大，就不会触发重新分配，这可能减少了不必要的性能损耗。然而，这也意味着 vector 的内部状态可能会影响程序的行为，特别是在多次递归调用之间。
解决方案
为了确保 vector 版本的代码能够像数组版本一样工作，你可以考虑以下改进：

预分配容量：在开始排序之前，预先分配足够的容量给 vector，以避免在添加元素时触发重新分配。例如，在 main 函数中初始化 now 向量时，可以指定一个合适的初始容量。

now.reserve(n); // 预先分配足够的容量

避免不必要的清理：如果 vector 的容量足够大，可以不必每次都调用 clear 方法。相反，可以使用 resize 方法将 vector 的大小设置为0，这样不会影响其容量。

now.resize(0); // 只重置大小，保留容量

使用数组索引：如果你发现即使做了上述优化，vector 版本仍然不如数组版本稳定，可以考虑在 vector 上使用类似数组的操作，比如直接通过索引来访问和修改元素，而不是使用 push_back。
通过这些调整，你应该能够使 vector 版本的代码表现得与数组版本一样好。如果你尝试了这些解决方案后问题仍然存在，建议仔细检查边界条件和其他潜在的逻辑错误。
如果觉得有用打赏支持一下，你的支持是我最大的动力，造福更多打码人