CODEWITHSUNDEEP
c++sortingvectormergesort
samuraiseoul
samuraiseoul

Reputation: 2967

c++ merge sort won't merge?

Im trying to make this mergesort function to sort a vector or word nodes (contains word length, number of occurences, and the word itsself) It seems to enter the merge function once, then the program fails, any ideas?

bool Utility::mergeSort_occurences(vector<Word> &invector){
    if (invector.size() <= 1){
        return true;
    }
    vector<Word> left, right;
    int middle = (invector.size()/2);
    for(int i = 0 ; i < middle ; i++){
        left.push_back(invector[i]);
    }
    for(int i = middle ; i < invector.size() ; i++){
        right.push_back(invector[i]);
    }
    mergeSort_occurences(left);
    mergeSort_occurences(right);
    invector = mergeOccurences(left, right);
    return true;
}

vector<Word> Utility::mergeOccurences(vector<Word> &left, vector<Word> &right){
    vector<Word> mergelist;
    while(left.size() > 0 || right.size() > 0){
        if(left.size() > 0 && right.size() > 0){
            if(left[0].getOccurences() <= right[0].getOccurences()){
                mergelist.push_back(left[0]);
                left.erase(left.begin());
            }else{
                mergelist.push_back(right[0]);
                right.erase(right.erase(right.begin()));
            }
        }
        else if(left.size() > 0){
           mergelist.push_back(left[0]);
           left.erase(left.begin()); 
        }
        else if(right.size() > 0){
           mergelist.push_back(right[0]);
           right.erase(right.erase(right.begin()));            
        }
    }
    return mergelist;
}

Upvotes: 0

Views: 240

Answers (1)

Kaz
Kaz

Reputation: 58510

Your right.erase(right.erase(right.begin())); code looks dodgy. The erase function returns an iterator to the successor of the element which was deleted, which is the end() if you deleted the last element.

You're guarding this code with right.size() > 0 which only guarantees there is one item. You have two erase operations.

Have you looked into the consequences of doing erase on right.end()?

Upvotes: 1

Related Questions