Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite

i've made a little function for eliminate continuous duplicate from a std::vector. i have to use c++03!

for example if a vector of int is composed of: 1,1,2,3,,3,1,1,2 my function shoul return 1,2,3,1,2. i've tried to use templates (i've just began to use c++) and made it as fast as possible! here it is:

template<class T>
vector<T> remove_duplicate(vector<T>& vec) {
    int length = vec.size();
    vector<T> result(length);
    result[0] = vec[0];
    int last = 0;
    for(int i=0; i<length; i++)
        if(vec[i] != result[last]){
            last++;
            result[last] = vec[i];
        }
    result.resize(last+1);
    return result;
}

and here a simple test case:

static
void test_remove_duplicate() {
    vector<int> v;
    v.push_back(1); //123131
    v.push_back(1);
    v.push_back(2);
    v.push_back(2);
    v.push_back(3);
    v.push_back(1);
    v.push_back(3);
    v.push_back(3);
    v.push_back(1);
    v.push_back(1);

    vector<int> v1;
    v1 = remove_duplicate(v);
    for(int i=0; i<v1.size(); i++) {
        cout << v1[i];
    } cout << endl;
}

what do you think about it?

share|improve this question

1 Answer

up vote 5 down vote accepted

Let's go through mechanical errors:

  1. use size_t instead of int

    int length = vec.size();

  2. what if there is no zero element?

    result[0] = vec[0];

  3. the same as first:

    int last = 0;

  4. the same as 1, 3:

    for(int i=0; i<length; i++)

Optimization errors:

  1. Is there any reason why do you need to return a COPY of vector? If you need return copy, so why do you pass it by reference?

  2. Extra resize of vector is extremely heavy and slow operation.

    result.resize(last+1);

  3. Prefer pre-increment to post-increment

  4. use reserve and push_back, instead of resize and []. In you case result.size() <= v.size(). So, make following:

    std::vector<T> result;
result.reserve(v.size);
result.push_back( vec[0] );

    In the loop:

    result.push_back( vec[i] );

So, including all comments above:

template<class T>
std::vector<T> remove_duplicate(const std::vector<T>& vec)
{
    std::vector<T> result;

    if(!vec.empty())
    {
        result.reserve(vec.size());
        result.push_back(vec.front());

        for(size_t i = 0; i< vec.size(); ++i)
            if(vec[i] != result.back())
                result.push_back( vec[i] );
    }

    return result;
}
share|improve this answer
whithout last resize if i try to use the vector with a for loop ended in size() it continue with some trail 0.. – nkint Feb 25 '12 at 17:57
resize() to a smaller size than capacity does not have any nasty side-effects only that current size will be reduced. But I agree that I would prefer to use reserve() and push_back() instead. – Loki Astari Feb 26 '12 at 4:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.