C++中Mergesort的问题

Question

vector<int>& mergesort(vector<int> &a) {
    if (a.size() == 1) return a;
    int middle = a.size() / 2;
    vector<int>::const_iterator first = a.begin();
    vector<int>::const_iterator mid = a.begin() + (middle - 1);
    vector<int>::const_iterator last = a.end();
    vector<int> ll(first, mid);
    vector<int> rr(mid, last);

    vector<int> l = mergesort(ll);
    vector<int> r = mergesort(rr);
    vector<int> result;
    result.reserve(a.size());
    int dp = 0, lp = 0, rp = 0;

    while (dp < a.size()) {
        if (lp == l.size()) {
            result[dp] = (r[rp]);
            rp++;
        } else if (rp == r.size()) {
            result[dp] = (l[lp]);
            lp++;
        } else if (l[lp] < r[rp]) {
            result[dp] = (l[lp]);
            lp++;
        } else {
            result[dp] = (r[rp]);
            rp++;
        }
        dp++;
    }
    a = result;
    return a;
}

它正确编译但在执行时,我得到:

此应用程序已请求运行时以不寻常的方式结束它.

这是一个奇怪的错误.

这些代码是否存在根本错误？

Answer 1

这result.reserve(a.size())只会影响矢量的容量,而不是它的大小.(向量的容量可以说明向量可以增长到哪个大小而无需重新分配和复制所有成员.基本上它只用于优化目的.)在result预留之后,您无法访问任何成员,因为没有任何成员.或者使用result.push_back(...)替代result[dp] = ...或result.resize(a.size())代替result.reserve(a.size()).

我想前者可能更有效.

Answer 2

一个问题是使用reserve()(使用resize()或附加项push_back()而不是访问索引).

if (a.size() == 1) return a;
int middle = a.size() / 2;
vector<int>::const_iterator first = a.begin();
vector<int>::const_iterator mid = a.begin() + (middle - 1);
vector<int>::const_iterator last = a.end();
vector<int> ll(first, mid);
vector<int> rr(mid, last);

这可能是另一个问题.如果大小为2,那么ll最终将成为空向量,并且此函数似乎不会处理此问题.无论如何,似乎没有太多理由从中间减去1.

这也有可能是要复制周围的事物,远远超过需要的:你不应该需要l和r向量(因为他们将只是副本ll和rr),同样地,我不认为你需要的result载体,因为你可以只写合并的结果回到了a.