remove duplicates from sorted array, same solution with different code way has different output

Question

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include "hello_world.h"


using namespace std;


class Solution1 {
public:
    int removeDuplicates(vector<int>& nums) {
        return distance(nums.begin(), removeDuplicates(nums.begin(), nums.end(), nums.begin()));
    }
    template<typename InIt, typename OutIt>
    OutIt removeDuplicates(InIt begin, InIt end, OutIt output){
        while(begin != end){
            *output++ = *begin;
            begin = upper_bound(begin, end, *begin);
        }

        return output;
    }

};


class Solution2 {
public:
    int removeDuplicates(vector<int>& nums) {
        vector<int>::iterator output = nums.begin();
        while(nums.begin() != nums.end()){
            *output++ = *nums.begin();
            nums.begin() = upper_bound(nums.begin(), nums.end(), *nums.begin());
        }

        return distance(nums.begin(), output);
    }
};


int main()
{
    //helloworld test;
    //test.print();
    int num[3] = {1,1,2};
    vector<int> nums(num, num + 3);

    Solution2 so;
    int a = so.removeDuplicates(nums);
    cout<<a<<endl;


    return 0;
}

In main function, when i use the class solution1, the code can remove duplicates numbers from the arrary [1 1 2] ,to output [1 2]. In order to simplify the code, I changed the solution1 to solution2, but the solution2 can not execute right output, anybody know the reason?

Answer 1

In this while loop

    while(nums.begin() != nums.end()){
        *output++ = *nums.begin();
        nums.begin() = upper_bound(nums.begin(), nums.end(), *nums.begin());
    }

you are always using the iterator nums.begin() in the condition and in this statement

        *output++ = *nums.begin();

because this statement

        nums.begin() = upper_bound(nums.begin(), nums.end(), *nums.begin());

does not change the iterator returned by a new call of nums.begin().

You need to introduce a variable of the iterator type before the loop like

auto it = nums.begin();

while( it != nums.end()){
    *output++ = *it;
    it = upper_bound( it, nums.end(), *it );
}

Here is a demonstrative program

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main() 
{
    std::vector<int> v = { 1, 2 };

    size_t i = 0;

    while ( v.begin() != v.end() )
    {
        v.begin() = std::upper_bound( v.begin(), v.end(), *v.begin() );

        if ( ++i == 10 ) break;
    }

    std::cout << "i = " << i << '\n';

    i = 0;

    auto it = v.begin();

    while ( it != v.end() )
    {
        it = std::upper_bound( it, v.end(), *it );

        if ( ++i == 10 ) break;
    }

    std::cout << "i = " << i << '\n';

    return 0;
}

Its output is

i = 10
i = 2

To erase duplicates after the loop use the member function erase like

nums.erase( output, nums.end() );

The same can be done using the standard algorithm std::unique. For example

nums.erase( std::unique( nums.begin(), nums.end() ), nums.end() );