How to remove duplicates from vector by iteratting though?

Question

I'm doing an assignment for my computer engineering class where we have to remove duplicates from a vector. I found solutions elsewhere, but I can't figure out how to iterate through without including the algorithm library

#include <vector>

using namespace std;

vector<int> deleteRepeats(const vector<int>& nums); // Declaration
void print(const vector<int>& nums);

int main() {
    vector<int> nums;
    vector<int> res;
    // Test 1
    nums = {1, 2, 3, 3, 2};
    res = deleteRepeats(nums);
    print(res); // Should print 1, 2, 3
    // Test 2
    nums = {-1, 2, 4};
    res = deleteRepeats(nums); 
    print(res); // Should print -1, 2, 4
    // Test 3
    nums = {42, 42, 42,};
    res = deleteRepeats(nums); 
    print(res); // Should print 42
    // Test 4
    nums = {};
    res = deleteRepeats(nums); 
    print(res); // Should print a blank

    return 0;
}

vector<int> deleteRepeats(const vector<int>& nums) {
    vector<int> res;
    bool foundRepeat;
    //my code here

    return res;
}

void print(const vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++)
        cout << nums[i] << " ";
    cout << endl;
}

So it is just consecutive repeats that you want to remove? What about wjhen there are duplicate values but they aren't consecutive? — Jerry Jeremiah, Nov 02 '21 at 03:18
I would use a for loop with an if statement that uses push_back when the value is different than the last value. — Jerry Jeremiah, Nov 02 '21 at 03:19
@JerryJeremiah my professor wants all duplicate values to be removed. So if the vector is [1, 5, 6, 5, 7] It should print [1, 5, 6, 7] — Devyn Meneses, Nov 02 '21 at 03:19
As this is a homework question, you should really explain why you're stuck on this. There's a naive solution to solve it in `O(n^2)`, and yes, there's faster ways too. — Elliott, Nov 02 '21 at 03:20
@JerryJeremiah, maybe I don't understand you, but I don't think that would work. Consider vector `[0,1,0]`. The previous value is always different. — Elliott, Nov 02 '21 at 03:22
@JerryJeremiah That's only acceptable if you don't have to preserve the order of the vector or if you use the set/map only to decide whether or not to push an entry to the vector. — David Schwartz, Nov 02 '21 at 03:22
I'm pretty new to C++, I have experience in python, but the main reason I'm stuck is because all of the ways I'm learning to remove duplicates is to use the unique function, which we can't use. I just can't wrap my head around how to check if the duplicate exists in the first place — Devyn Meneses, Nov 02 '21 at 03:24
@DevynMeneses, when in doubt, revert back to the basics: `if` statements, loops - that's all you really need. the rest is just sugar. — Elliott, Nov 02 '21 at 03:25
unique works but the vector has to be sorted. unique uses a for loop with an if statement. You can see a sample implementation here: https://en.cppreference.com/w/cpp/algorithm/unique But sorting the vector won't leave it in the original order. — Jerry Jeremiah, Nov 02 '21 at 03:25
Ok, what I would do is: loop through the input vector, check each value whether it can be inserted into a set (because sets don't allow duplciates) and if it can be inserted then push it into the output vector. The set is just used to decide if it is a duplicate - you would have to keep track of that info anyway so you might as well use a standard container. So the whole function is a for loop, an if statement and a push_back. — Jerry Jeremiah, Nov 02 '21 at 03:34
Think of how you would do in manually. Use the simple, if not efficient, approach @Elliot alludes to. Make 2 loops. The first goes from 0 to the second to last element, The second loops from there to the end erasing any duplicates. — doug, Nov 02 '21 at 04:06
Maybe try something like this: https://onlinegdb.com/857mKQVze — Jerry Jeremiah, Nov 02 '21 at 07:43
What do you mean by "the algorithm library"? Just this https://www.cplusplus.com/reference/algorithm/? Because vector's iterators are not part of it. You can use set as suggested, or sort & de-duplicate yourself. — Uri Raz, Nov 02 '21 at 09:06

KuhakuPixel · Answer 1 · 2021-11-02T07:37:52.547

The most simple way to do this is to create a second std::vector then iterate through std::vector that you want to remove duplicate from and add to second std::vector if the item doesn't exist in the second std::vector

#include <stdio.h>
#include <vector>
bool DoesVectorContain(const std::vector<int> &vect, int item)
{
    for (int i = 0; i < vect.size(); i++)
    {
        if (vect.at(i) == item)
            return true;
    }
    return false;
}
std::vector<int> RemoveDuplicate(const std::vector<int> &vect)
{
    std::vector<int> newVect;
    for (int i = 0; i < vect.size(); i++)
    {
        //add to newVect if vect.at(i) doesn't exist in newVect
        if (!DoesVectorContain(newVect, vect.at(i)))
            newVect.push_back(vect.at(i));
    }
    return newVect;
}
int main()
{
    std::vector<int> vect = {0, 2, 4, 4, 3, 4, 4, 8, 8, 10, 12};
    std::vector<int> newVect = RemoveDuplicate(vect);
    for (int i = 0; i < newVect.size(); i++)
        printf("%d\n", newVect.at(i));

    return 0;
}

this prints out

Also you are using the ```````` library. It is a requirement to not use it . . . — A M, Nov 02 '21 at 07:23
@ArminMontigny okay thanks for reminding , i have edited my answer — KuhakuPixel, Nov 02 '21 at 07:38

score 1 · Accepted Answer · answered Nov 02 '21 at 07:44

So, the requirement is to not use the algorithm library and do it manually.

Also no problem, because your teacher gave you already a strong hint by writing:

vector<int> deleteRepeats(const vector<int>& nums) {
    vector<int> res;
    bool foundRepeat;
    //my code here

    return res;
}

You have an input vector nums and a result vector res. Obviously you need to copy values from the input vector to the resulting vector. But no duplicates.

The solution is to

iterate all numbers in the input vector nums
and then compare each number with all numbers in the resulting vector res
and if youd could not find a repeat (foundRepeat), copy the value into the resulting vector.

You need 2 loops. The outer loop will read all values from the input vector nums. Each of this value will be compared with all existing values in the res vector. For this we create an inner llop and iterate over all existing values in the res vector. If the number from the outer loop is equal to the value from the inner loop, then we have obviously a duplicate. We will not add the value. If we do not have a duplicate, then we add the number from the outer loop to the res vector.

This could then look for example like the below:

#include <iostream>
#include <vector>

using namespace std;

vector<int> deleteRepeats(const vector<int>& nums); // Declaration
void print(const vector<int>& nums);

int main() {
    vector<int> nums;
    vector<int> res;
    // Test 1
    nums = { 1, 2, 3, 3, 2 };
    res = deleteRepeats(nums);
    print(res); // Should print 1, 2, 3
    // Test 2
    nums = { -1, 2, 4 };
    res = deleteRepeats(nums);
    print(res); // Should print -1, 2, 4
    // Test 3
    nums = { 42, 42, 42, };
    res = deleteRepeats(nums);
    print(res); // Should print 42
    // Test 4
    nums = {};
    res = deleteRepeats(nums);
    print(res); // Should print a blank

    return 0;
}

vector<int> deleteRepeats(const vector<int>& nums) {
    vector<int> res;
    bool foundRepeat;
    //my code here

    // Iterate over all nums
    for (unsigned int i = 0; i < nums.size(); ++i) {

        // Get current num at index i
        int num = nums[i];

        // Here we will indicate, if we found a duplicate
        foundRepeat = false;

        // Now search, if this num is already in the result vector
        for (unsigned int k = 0; (k < res.size() && !foundRepeat); k++) {

            // This is the number in the res vector at the current index
            int numInRes = res[k];

            // Check for a repeating (duplicate value)
            if (numInRes == num) {

                // Remeber that we found a duplicate and also stop the loop
                foundRepeat = true;
            }
        }
        // If no duplicate has been found, then add the num to the result
        if (!foundRepeat) res.push_back(num);
    }
    return res;
}

void print(const vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++)
        cout << nums[i] << " ";
    cout << endl;
}

Thank you so much! The syntax of c++ really trips me up. What does the "unsigned" part of the for loop do? — Devyn Meneses, Nov 03 '21 at 23:39
````Unsigned```` means that the variable will contain only positive numbers. Normal ````int```` integers can have positive and negative values. And since ````size()```` returns only ````unsigned```` numbers, which is logical, because the size cannot be negative, I used also ````unsigned int```` variables. To make your life easier, simply delete the word ````unsigned```` — A M, Nov 04 '21 at 11:25

score 0 · Answer 3 · answered Nov 02 '21 at 07:39

0

You can use an unordered_set object, which allows insertion of an element only if it doesn't exist. After the insertion you can convert the set into a vector.

This solution has an average complexity of O(N) (but not in the worst case)

#include <vector>
#include <unordered_set>

std::vector<int> deleteRepeats(const std::vector<int>& nums) {
    std::unordered_set<int> uniq_set;

    for (const auto& element : nums) {
        uniq_set.insert(element);
    }

    return std::vector(uniq_set.begin(), uniq_set.end());
}

answered Nov 02 '21 at 07:39

user107511

772
3
23

2

Like that, order is not preserved. – Jarod42 Nov 02 '21 at 09:42
1

@Jarod42 That isn't mentioned as one of the requirements – user107511 Nov 02 '21 at 09:51
2

It was, but in comment part... (*"We need to preserve the order @JerryJeremiah"* – Devyn Meneses) – Jarod42 Nov 02 '21 at 09:54

How to remove duplicates from vector by iteratting though?

3 Answers3