Why is my code skipping some elements of this vector?

Question

So it's my first semester on computer science, learning about vectors. For this assignment I had to write a code that read the vector and "eliminated" any repeated elements, then wrote down the results on the same vector.

So, on my limited time and experience, I tried something which is kinda like bubble sort, which yes I know it's terrible and inefficient, but it's just one vector for a first semester assignment.

The logic would go like this: I'd assign a variable called "temp" to have the same value as the first item on the list. Then, I'd compare it with the second item. If they're different, just skip it. If they're equal, then replace the first item with the second, the second with the third, and so forth, always replacing the repeated element with the one after it. After the code is done comparing the temp variable with every other item on the list, it starts all over again but with the temp variable with the same value as the second element, and then the third, and so on. This way the code is kind of "pulling" the list on top of every repeated term.

But I guess I must've done something wrong in the maths of the "for" statements, because the code is skipping some elements, and increasing the size of the vector double confirms it.

#include <cstdlib>
#include <iostream>
#include <fstream>
#define tam 10
using namespace std;

int main(int argc, char** argv) {
    
    int vet[tam] = {1, 2, 3, 5, 7, 11, 3, 0, 7, 17};
    int temp, 
    t = tam;
    int j = 0;
    
    for (int i = 0; i < t; i++)
    {
        temp = vet[i];
        for (int n = 1; n < t; n++)
        {
            if (temp == vet[i+n])
            {
                t--;
                j++;
                vet[i+n] = vet[i+n+j];
            }
        }
        cout << vet[i] << endl;
    }
    
    return 0;
}

I've tried removing the j and t variables since on hindsight they're probably wholly unecessary but I couldn't find a better logic to replace them, even though I'm preeetty sure they're the main cause of the problem. May need to do more flowcharts in the future.

Edit: So I tried rewriting the code, but couldn't debug or test since VScode isn't cooperating. Could this work?

#include <cstdlib>
#include <iostream>
#include <fstream>
#define tam 20
using namespace std;

int main(int argc, char** argv) {
    
    int vet[tam] = {1, 2, 3, 5, 7, 11, 3, 0, 7, 17, 2, 4, 5, 1, 65, 23, 3, 9, 0, 74};
    int temp;

    for(int i = 0, j = tam; i <= j; i++)
    {
        temp = vet[i];
        for(int n = 1; n <= j;)
        {
            if(temp == vet[i+n])
            {
                vet[i+n] = vet[i+n+1];
                n++;
                j--;
            }
        }
        cout << vet[i] << endl;
    }

    return 0;
}

`vet[i+n]` accesses an index out of bounds, whereupon the program exhibits undefined behavior. I'm not sure what you are trying to achieve, but your index arithmetic doesn't make any sense to me. — Igor Tandetnik, Jun 07 '23 at 00:50
You mention vectors, but you are using C-style arrays. If this is C++, use [`std::vector`](https://en.cppreference.com/w/cpp/container/vector) instead. — heap underrun, Jun 07 '23 at 00:53
Unrelated: With the line-feed preserved, something you can't do in a comment `int temp, t = tam;` is deceptive. I'd split this up into two distinct definitions. — user4581301, Jun 07 '23 at 01:01
If your build tools have sanitizers you can save yourself a lot of work: https://godbolt.org/z/dM5PPjGrM . If your tools don't have sanitizers, consider getting some that do. Even if you have to submit code compiled with toolchain X, you can learn a lot form seeing how toolchain Y looks at your code, backport what you find, and generally live a simpler, more satisfying life. — user4581301, Jun 07 '23 at 01:07
You have two reasonable options now. You can learn how to [run your code in a debugger](https://stackoverflow.com/questions/25385173) (because this code certainly has bugs) or you can use a pencil-and-paper to follow your code by hand until you notice Something Bad happening. — Drew Dormann, Jun 07 '23 at 01:10
The downside of pen-and-paper debugging is any incorrect assumptions you made while writing the program will most likely follow through into your debugging of it. The debugger, on the other hand, doesn't give a about your assumptions. It shows you exactly what your code has been interpreted by the compiler to do. Ego-bruising, but very efficient. — user4581301, Jun 07 '23 at 01:14

Chris · Answer 1 · 2023-06-07T04:41:49.353

If you're trying to implement a bubble sort, this is a well-understood algorithm. You compare two elements at a time, looping over the array. If the first one is bigger, you swap them. By doing this across the entire array once from the beginning, the largest value will be pushed to the end of the array. You need to repeat this loop, but you don't need to go to the end each time. You can iterate to one less index each time.

For your example:

{1, 2, 3, 5, 7, 11, 3, 0, 7, 17}
 <-->
{1, 2, 3, 5, 7, 11, 3, 0, 7, 17}
    <-->
{1, 2, 3, 5, 7, 11, 3, 0, 7, 17}
       <-->
{1, 2, 3, 5, 7, 11, 3, 0, 7, 17}
          <-->
{1, 2, 3, 5, 7, 11, 3, 0, 7, 17}
             <--->
{1, 2, 3, 5, 7, 11, 3, 0, 7, 17} SWAP
                <--->
{1, 2, 3, 5, 7, 3, 11, 0, 7, 17} SWAP
                   <--->
{1, 2, 3, 5, 7, 3, 0, 11, 7, 17} SWAP
                      <--->
{1, 2, 3, 5, 7, 3, 0, 7, 11, 17}
                         <---->

Next outer loop:

{1, 2, 3, 5, 7, 3, 0, 7, 11, 17}
 <-->
{1, 2, 3, 5, 7, 3, 0, 7, 11, 17}
    <-->
{1, 2, 3, 5, 7, 3, 0, 7, 11, 17}
       <-->
{1, 2, 3, 5, 7, 3, 0, 7, 11, 17}
          <-->
{1, 2, 3, 5, 7, 3, 0, 7, 11, 17} SWAP
             <-->
{1, 2, 3, 5, 3, 7, 0, 7, 11, 17} SWAP
                <-->
{1, 2, 3, 5, 3, 0, 7, 7, 11, 17}
                   <-->
{1, 2, 3, 5, 3, 0, 7, 7, 11, 17}
                      <--->

Then:

{1, 2, 3, 5, 3, 0, 7, 7, 11, 17}
 <-->
{1, 2, 3, 5, 3, 0, 7, 7, 11, 17}
    <-->
{1, 2, 3, 5, 3, 0, 7, 7, 11, 17}
       <-->
{1, 2, 3, 5, 3, 0, 7, 7, 11, 17} SWAP
          <-->
{1, 2, 3, 3, 5, 0, 7, 7, 11, 17} SWAP
             <-->
{1, 2, 3, 3, 0, 5, 7, 7, 11, 17}
                <-->
{1, 2, 3, 3, 0, 5, 7, 7, 11, 17}
                   <-->

Then:

{1, 2, 3, 3, 0, 5, 7, 7, 11, 17}
 <-->
{1, 2, 3, 3, 0, 5, 7, 7, 11, 17}
    <-->
{1, 2, 3, 3, 0, 5, 7, 7, 11, 17}
       <-->
{1, 2, 3, 3, 0, 5, 7, 7, 11, 17} SWAP
          <-->
{1, 2, 3, 0, 3, 5, 7, 7, 11, 17}
             <-->
{1, 2, 3, 0, 3, 5, 7, 7, 11, 17}
                <-->

Then:

{1, 2, 3, 0, 3, 5, 7, 7, 11, 17}
 <-->
{1, 2, 3, 0, 3, 5, 7, 7, 11, 17}
    <-->
{1, 2, 3, 0, 3, 5, 7, 7, 11, 17} SWAP
       <-->
{1, 2, 0, 3, 3, 5, 7, 7, 11, 17}
          <-->

Then:

{1, 2, 0, 3, 3, 5, 7, 7, 11, 17}
 <-->
{1, 2, 0, 3, 3, 5, 7, 7, 11, 17} SWAP
    <-->
{1, 0, 2, 3, 3, 5, 7, 7, 11, 17}
       <-->

Then:

{1, 0, 2, 3, 3, 5, 7, 7, 11, 17} SWAP
 <-->
{0, 1, 2, 3, 3, 5, 7, 7, 11, 17}
    <-->

Then:

{0, 1, 2, 3, 3, 5, 7, 7, 11, 17}
 <-->

And we can see that the result is sorted.

So we need two nested loops. Within the inner loop we compare adjacent ints in the array and swap if necessary.

for (int i = 0; i < tam - 1; i++) {
    for (int j = 0; j < tam - 1 - i; j++) {
        if (vet[j] > vet[j+1]) {
            int temp = vet[j];
            vet[j] = vet[j+1];
            vet[j+1] = temp;
        }
    }
}

Oh, I'm not exactly doing bubble sort, it's just that the way my program was supposed to compare each item to the rest of the list vaguely resembles that. But thanks anyway. What I'm actually trying to do is too have the program check each item on the list for repeats, and if they find any, erase them. Since I don't know any better ways at the moment, I'm trying to do that by replacing each following item with the rest of the list. I tried rewriting it with a slightly better logic to see if it works now, but VScode isn't cooperating so I couldn't debug it just yet. — Socks, Jun 07 '23 at 01:43
@Socks VS Code can be a pain to configure. My recommendation is to exterminate all organic life. Whoops. Used AI to generate that recommendation. My real recommendation is to spend the time [fighting through it](https://code.visualstudio.com/docs/cpp/launch-json-reference) or switch to a different tool like Visual Studio Community that's easier to set up. There's also https://www.onlinegdb.com/ for the small stuff. Should be able to handle your program without breathing too hard. — user4581301, Jun 07 '23 at 01:48
Just don't use ALL those pointers, just use `vet[j]` and `vet[j+1]` and don't worry about "optimization" the compiler is very good at finding invariants in a scope and keeping them in registers (as long as they fit). And for swapping values there is `std::swap`. Use `std::array` for the array and replace `tam` with `vet.size()-1` — Pepijn Kramer, Jun 07 '23 at 03:09
Pepijn's not kidding. Compilers are written by humans and the patterns the humans recognize tend to be handled very well by compilers. CPUs also like to go in nice, predictable lines, so given the choice between something stupid-and-repetitive and something smart-and chaotic, give stupid a shot and see what happens. — user4581301, Jun 07 '23 at 03:19
Regarding setting up VS Code, you can also use a text editor as a text editor and compile in your terminal. It's a time-tested method and works very nicely for the kind of small programs you will write lots of at this stage of your learning. — Chris, Jun 07 '23 at 04:44

Why is my code skipping some elements of this vector?

1 Answers1