CPP vector concatenation in recursive function

Question

I have this recursive function, which does not compile giving errors at vector concatenation lines.

    vector<int> binaryInsert(vector<int> subArray, int subArraySize, int nextVal) {
    if(subArraySize == 1)
    {
        if(nextVal >= subArray[0]) subArray.insert(subArray.begin()+1, nextVal);
        else subArray.insert(subArray.begin(), nextVal);
        return subArray;
    }
    else if(subArraySize == 2)
    {
        if(nextVal >= subArray[0]) {
            if(nextVal >= subArray[1]) subArray.insert(subArray.begin()+2, nextVal);
            else subArray.insert(subArray.begin()+1, nextVal);
        }
        else subArray.insert(subArray.begin(), nextVal);
        return subArray;
    }
    else
    {
        if(subArraySize%2 == 1)
        {
            int halfPoint = (subArraySize-1)/2;
            vector<int> leftSubArray(subArray.begin(), subArray.begin()+halfPoint);
            vector<int> rightSubArray(subArray.begin()+halfPoint, subArray.end());
            vector<int> newVec;
            if(nextVal <= leftSubArray[halfPoint-1]) {
                newVec = binaryInsert(leftSubArray, halfPoint, nextVal);
                return newVec.insert(newVec.end(), rightSubArray.begin(), rightSubArray.end());
            }
            else
            {
                newVec = binaryInsert(rightSubArray, halfPoint+1, nextVal);
                return leftSubArray.insert(leftSubArray.end(), newVec.begin(), newVec.end());
            }
            
        }
        else
        {
            int halfPoint = (subArraySize)/2;
            vector<int> leftSubArray(subArray.begin(), subArray.begin()+halfPoint);
            vector<int> rightSubArray(subArray.begin()+halfPoint, subArray.end());
            vector<int> newVec;
            if(nextVal <= leftSubArray[halfPoint-1]) {
                newVec = binaryInsert(leftSubArray, halfPoint, nextVal);
                return newVec.insert(newVec.end(), rightSubArray.begin(), rightSubArray.end());
            }
            else
            {
                newVec = binaryInsert(rightSubArray, halfPoint, nextVal);
                return leftSubArray.insert(leftSubArray.end(), newVec.begin(), newVec.end());
            }
        }      
    }  
}

The line return newVec.insert(newVec.end(), rightSubArray.begin(), rightSubArray.end()); gives below error.

could not convert ‘newVec.std::vector::insert<__gnu_cxx::__normal_iterator<int*, std::vector > >(__gnu_cxx::__normal_iterator<const int*, std::vector >(newVec.std::vector::end()), rightSubArray.std::vector::begin(), rightSubArray.std::vector::end()’ from ‘std::vector::iterator {aka __gnu_cxx::__normal_iterator<int*, std::vector >}’ to ‘std::vector’

Same for return leftSubArray.insert(leftSubArray.end(), newVec.begin(), newVec.end()); too.

I am certain the method I use for vector concatenation is the most reliable and better method, yet I can't figure out what causes the error. Is there something wrong I'm doing here?

Answer 1

Calling std::vector::insert returns an iterator, not the modified vector. So the return statement will try to convert an iterator to a vector, giving the compiler error that you see.

You can solve this by simply breaking up the return statement into 2 lines:

newVec.insert(newVec.end(), rightSubArray.begin(), rightSubArray.end());
return newVec;

You need to do a similar thing for your other return statements as well.