c++ - 为什么 vector 迭代器指向越界？

Question

我正在研究一种递归合并排序算法，一个迭代器越界。我很肯定我的问题的根源是我的算法有缺陷，但我花了好几天时间研究它，我就是看不到我的失误。我不知道该往哪个方向走。比我更有经验/更聪明的人可以看看吗？ (带驱动程序的完整程序可在 Github here 上获得。)

输出是:

before: 50 5 40 10 30 15 20 20 10 25 
after : -1808873259 5 10 10 15 20 20 25 30 40 50 
/*      ^  
 *      Extra recursive call, and out-of-bounds.
 */

明确地说，我只能返回一个 T 类型的 vector ，在本例中为 int，但我从 this post 了解到使用 void 函数更好。

template <typename T>
vector<T> mergesort(typename vector<T>::iterator begin, typename vector<T>::iterator end){
    vector<T> newVector;
    if (begin!=end){
        vector<T> tmp1;
        vector<T> tmp2;
        typename vector<T>::iterator mid1 = begin;
        typename vector<T>::iterator mid2 = begin;

        long origDistance = distance(begin,end);
        long endOfRange1 = origDistance/2;
        long begOfRange2 = endOfRange1+1;

        advance(mid1,endOfRange1);
        advance(mid2,begOfRange2);

        tmp1 = mergesort<T>(begin,mid1);
        tmp2 = mergesort<T>(mid2,end);

        //"merge()" is from the STL, link in comments. 
        merge(tmp1.begin(),tmp1.end(),tmp2.begin(),tmp2.end(), back_inserter(newVector));

    } else {
        newVector.push_back(*begin);
    }
    return newVector;
}

Answer 1

当 begin == end 时，您取消引用 begin。那是未定义的行为。可能您需要 if (origDistance == 1) 然后 push_back 单个元素并返回。