CODEWITHSUNDEEP
c++arrays
Staypuft
Staypuft

Reputation: 129

Insert into a desired element of an array and push all other elements one spot over in c++

Having some issues with one small function I'm working on for a homework assignment.

I have a static array size of 20 (shelfSize), however, I only need to use a max of 10 elements. So I don't have to worry about out of bounds etc (the entire array of 20 is initialized to 0).

What I am looking to do is insert an integer, booknum, into an element of an array it receives as input.

This my current logic:

void insert_at(int booknum, int element){
for(int i=element+1; i < shelfSize; i++)
    bookshelf[i+1]=bookshelf[i]
bookshelf[element]=booknum;
}

so let's say I have the this array:

[5,4,3,1,7]

I want to insert an 8 at element 1 and have the array turn to:

[5,8,4,3,1,7]

Technically, everything after the final element 7 is a 0, however, I have a separate print function that only prints up to a certain element.

No matter how many times I take some pencil and paper and manually write out my logic, I can't get this to work.

Any help would be appreciated, thanks.

Upvotes: 0

Views: 741

Answers (3)

Tamer Shlash
Tamer Shlash

Reputation: 9523

You should start from the end of the array, this should word for you:

void insert_at(int booknum, int element)
{
    for (int i = shelfsize-1;i>element;i--)
        bookshelf[i] = bookshelf[i-1];
    bookshelf[element] = booknum;
}

Also I recommend that you get used to handling illegal values, for example, what if a user entered 21?

The optimized code would be:

bool insert_at(int booknum, int element)
{
    if (element>=shelfsize-1)
        return false;
    for (int i = shelfsize-2;i>element;i--)
        bookshelf[i] = bookshelf[i-1];
    bookshelf[element] = booknum;
    return true;
}

Upvotes: 1

Simon Buchan
Simon Buchan

Reputation: 13245

Just noticed, you are copying up, this means your function does this:

 [5,4,3,1,7]
    --^
 [5,4,4,1,7]
      --^
 [5,4,4,4,7]
        --^
 [5,4,4,4,4]
          --^
 [5,4,4,4,4,4]

For moving values in an array, you always want to copy in the opposite direction to which you are moving, so to move up, you want to copy each item up from the top down:

 [5,4,3,1,7]
          --^
 [5,4,3,1,7,7]
        --^
 [5,4,3,1,1,7]
      --^
 [5,4,3,3,1,7]
    --^
 [5,4,4,3,1,7]

And then you can overwrite the index you freed up.

Upvotes: 1

Shirik
Shirik

Reputation: 3701

If your example is correct, then you're assuming 1-based indices instead of 0-based. Use the following instead:

void insert_at(int booknum, int element){
for(int i=element; i < shelfSize; i++)
    bookshelf[i]=bookshelf[i-1];
bookshelf[element-1]=booknum;
}

However, I would prefer you just use the same code, and change "at element 2" in your example to "at element 1". Always remember C++ arrays are 0-based.

That being said, please tell your professor that this is why vectors (and other standard containers) were made, and that C++ arrays are evil.

http://www.parashift.com/c++-faq-lite/containers.html#faq-34.1

Upvotes: 1

Related Questions