C++ Delete Dupes

Question

I have some code: I need to delete duplicates, I don't really know which step im going wrong at. kinda been losing sleep over this. i feel like im needlessly overcomplicating this but too brain dead atm to see where i went wrong.

STILL HAVING ISSUES =(

I'm making the changes I incoorporated based on suggestions... still running into out of bounds even though my size for the arr is 8... I've tried printing values, it seems to break unexpectedly on the 3rd element but I dont know what to do. any other help would be appreciated...

template <typename T>
void removeDup(std::vector<T> & v)
{
int last = v.size()-1;
for(int i = 0; i <= v.size(); i++)
    {
            if (count(v, i, last, v[i]) > 1){ // if there is more than 1
            v.erase(v.begin()+(i)); // erase it
            }
        }
}


template <typename T>
int count(const std::vector<T> & v, int first, int last, const T& target){

    int index = first;
    int count = 0;

for (index; index < last; index++){
if (v[index] == target){
    count++;
    }
}

return count;
}

template <typename T>
int seqVectSearch(const std::vector<T> & v, int first, int last, const T& target){

    int index = first;
    int returnVal = -1;

for (index; index < last; index++){
if (v[index] == target){
    returnVal = index;
    }
}

return returnVal;
}

template <typename T>
void writeVector(const std::vector<T> & v){
    int i;
    int n = v.size();

    for (i = 0; i < n; i++)
        std::cout << v[i] << ' ';
        std::cout << std::endl;
}

template void removeDup(std::vector<int> & v);
template int seqVectSearch(const std::vector<int> & v, int first, int last, const int& target);
template void writeVector(const std::vector<int> & v);
template int count(const std::vector<int> & v, int first, int last, const int& target);

Output:

Testing removeDup
Original vector is  1 7 2 7 9 1 2 8 9
Vector with duplicates removed is  1 2 7 9 1 2 8 9

1 2 7 9 1 2 8 9
Press any key to continue . . .

Answer 1

If you remove an item, you need to test the next, which now holds the position you where just testing, so updating the index is not right in this case. erase returns an iterator, that can be handy if you want to iterate and conditionally erase some items.
Also note that count is already defined in <algorithm>, you don't need to define your own.

template <typename T>
void removeDup(std::vector<T>& v)
{
    auto iter = v.begin()
    while( iter != v.end() )
    {
        if( std::count(iter, v.end(), *iter) > 1)
            iter = v.erase(iter);
        else
            ++iter;
    }
}

notice however, that this will shuffle a lot of items around, and that the erase-remove idiom might be better suited.

Answer 2

Here is a stable solution (relative order of the elements is preserved) using std::remove_if() from C++'s standard template library. As you can see the actual removal of duplicates only takes ~10 lines of actual code; the rest is (sadly) C++ noise around include files and "pretty" printing a container to stdout.

The core idea is to keep a set of elements that have already been seen inside the predicate; the predicate is a functor that returns true if the element's a duplicate (i.e. can be removed) and false otherwise.

Complexity should be O(n) + O(n log n) - each element needs to be checked once and lookup in the set is O(n log n).

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

template <typename T>
struct remove_dups_predicate {
    typedef std::set<T> unique_values_t;


    // Return true if we've seen this element before
    // note that set.insert(...) returns pair<iterator,bool>
    // with the bool telling wether or not the element was 
    // succesfully inserted, i.e. it should *not* be removed
    bool operator()(const T& element) {
        return !unique_values_seen.insert(element).second;
    }
    unique_values_t  unique_values_seen;
};

int main( void ) {
    std::vector<int>           vi{ 1, 7, 2, 7, 9, 1, 2, 8, 9};

    std::cout << "Before: ";
    std::copy(vi.begin(), vi.end(), std::ostream_iterator<int>(std::cout, ", "));
    std::cout << std::endl;

    // Remove the duplicates
    std::vector<int>::iterator it = std::remove_if(vi.begin(), vi.end(),
                                                   remove_dups_predicate<int>());

    // print to stdout
    std::cout << "After: ";
    std::copy(vi.begin(), it, std::ostream_iterator<int>(std::cout, ", "));
    std::cout << std::endl;

    return 0;
}

Running this gives as output:

Before: 1, 7, 2, 7, 9, 1, 2, 8, 9,
After: 1, 7, 2, 9, 8,

Answer 3

There are some error regarding the algorithm. Mainly, range issues.

v.erase(v.begin()+(i-1));

Your i variable starts at 0, so you don't need to remove the element before it. Just remove begin()+i.

count(v, i, last, i)

You have passed for last argument of count(...) the value of size()-1. So your iteration must be until index <= last, instead of just index < last.

Another problem, the fourth parameter isn't i, is v[i]. Your code only compiles because you is testing with a vector of integers, the same type of the index.

It can have other errors, look carefully to the algorithm and index ranges. A good option is a print on each step of the functions.

Edit: Adding my suggested algorithm

This is the code of the two core methods. Replicate the logic if you want something similar in other tasks.

template <typename T>
void removeDup(std::vector<T> & v) {
    for(int i = 0; i <= v.size(); i++)
    {
            if (count(v, i, v[i]) > 1){ // if there is more than 1
                v.erase(v.begin()+i); // erase it
                i--; // Decrement to stay at the same index.
            }
        }
}

template <typename T>
int count(const std::vector<T> & v, int first, const T& target){
    int count = 0;
    for (int index = first; index < v.size(); index++){
        if (v[index] == target){
            count++;
        }
    }
    return count;
}