CODEWITHSUNDEEP
c++
Zachary Finger
Zachary Finger

Reputation: 1

Deleting duplicates in a vector filled with a pair of two ints

I am having trouble running through a vector of two int pairs and deleting all the duplicates. Right now the vector looks like this:

3, 2
3, 2
3, 2
5, 3
5, 3

And it goes on. I want it to looks like this:

3, 2 
5, 3

Here is my code:

sort(vec3.begin(), vec3.end());
std::vector<std::pair<int, int>> vec4;
int sum = 0;
for(int i = 0; i<vec3.size(); i++){
    for(int j = i+1; j<vec3.size(); j++){
        if(vec3[i] != vec3[j]){
            vec4.push_back(vec3[i]);
            break;
        }
    }
}
for(int i = 0; i< 10; i++){
    cout << vec4[i].first << ", " << vec4[i].second << endl;
}

What I did is I sorted the first vector, which worked, and then I am trying to run through it where after vec3(i) != vec3(j) it breaks out of the inner loops and adds vec3(i) only once to a new vector, essentially deleting the other duplicates. However, this is not working. It is taking forever to run, and I think it has to do with my break not working.

Upvotes: 0

Views: 68

Answers (1)

Remy Lebeau
Remy Lebeau

Reputation: 596317

The problem is that you are not really handling the duplicates correctly at all.

Lets look at the logic using your example:

  • The outer loop starts at vec3[0]. It sees the 1st 3, 2, then the inner loop scans for the next non-duplicate, finding the 1st 5, 3, and so it adds 3, 2 to vec4.

  • Then the outer loop moves on to vec3[1]. It sees the 2nd 3, 2, then the inner loop scans for the next non-duplicate, finding the 1st 5, 3 again, and so it adds 3, 2 to vec4 again.

  • Then the outer loop moves on to vec3[2]. It sees the 3rd 3, 2, then the inner loop scans for the next non-duplicate, finding the 1st 5, 3 again, and so it adds 3, 2 to vec4 again.

  • Then the outer loop moves on to vec3[3]. It sees the 1st 5, 3, then the inner loop scans for the next non-duplicate, finding none, and so it does not add 5, 3 to vec4.

  • Then the outer loop moves on to vec3[4]. It sees the 2nd 5, 3, then the inner loop scans for the next non-duplicate, finding none, and so it does not add 5, 3 to vec4.

See the problem?

Try something more like this instead:

std::sort(vec3.begin(), vec3.end());
std::vector<std::pair<int, int>> vec4;

size_t i = 0;
while (i < vec3.size()) {
    vec4.push_back(vec3[i]);
    // skip any duplicates
    while ((++i < vec3.size()) && (vec3[i] == vec3[i-1]));
}

for(size_t i = 0; i < vec4.size(); ++i) {
    std::cout << vec4[i].first << ", " << vec4[i].second << std::endl;
}

Online Demo

Which can be greatly simplified using std::unique() with vector::erase(), eg:

std::sort(vec3.begin(), vec3.end());
vec3.erase(
    std::unique(vec3.begin(), vec3.end()),
    vec3.end()
);

for(size_t i = 0; i < vec3.size(); ++i) {
    std::cout << vec3[i].first << ", " << vec3[i].second << std::endl;
}

Online Demo

Upvotes: 1

Related Questions