C++ inserting (and shifting) data into an array

Question

I am trying to insert data into a leaf node (an array) of a B-Tree. Here is the code I have so far:

void LeafNode::insertCorrectPosLeaf(int num)
{
  for (int pos=count; pos>=0; pos--)   // goes through values in leaf node
  {
    if (num < values[pos-1])    // if inserting num < previous value in leaf node
    {continue;}                 // conitnue searching for correct place
    else                        // if inserting num >= previous value in leaf node
    {
      values[pos] = num;        // inserts in position
      break;
    }               
  }
  count++;
} // insertCorrectPos()

Before the line values[pos] = num, I think need to write some code that shifts the existing data instead of overwriting it. I am trying to use memmove but have a question about it. Its third parameter is the number of bytes to copy. If I am moving a single int on a 64 bit machine, does this mean I would put a "4" here? If I am going about this completely wrong any any help would be greatly appreciated. Thanks

Answer 1

The easiest way (and probably the most efficient) would be to use one of the standard libraries predefined structures to implement "values". I suggest either list or vector. This is because both list and vector has an insert function that does it for you. I suggest the vector class specifically is because it has the same kind of interface that an array has. However, if you want to optimize for speed of this action specifically, then I would suggest the list class because of the way it is implemented.

If you would rather to it the hard way, then here goes... First, you need to make sure that you have the space to work in. You can either allocate dynamically:

int *values = new int[size];

or statically

int values[MAX_SIZE];

If you allocate statically, then you need to make sure that MAX_SIZE is some gigantic value that you will never ever exceed. Furthermore, you need to check the actual size of the array against the amount of allocated space every time you add an element.

if (size < MAX_SIZE-1)
{
    // add an element
    size++;
}

If you allocate dynamically, then you need to reallocate the whole array every time you add an element.

int *temp = new int[size+1];
for (int i = 0; i < size; i++)
    temp[i] = values[i];
delete [] values;
values = temp;
temp = NULL;

// add the element
size++;

When you insert a new value, you need to shift every value over.

int temp = 0;
for (i = 0; i < size+1; i++)
{
    if (values[i] > num || i == size)
    {
        temp = values[i];
        values[i] = num;
        num = temp;
    }
}

Keep in mind that this is not at all optimized. A truly magical implementation would combine the two allocation strategies by dynamically allocating more space than you need, then growing the array by blocks when you run out of space. This is exactly what the vector implementation does.

The list implementation uses a linked list which has O(1) time for inserting a value because of it's structure. However, it is much less space inefficient and has O(n) time for accessing an element at location n.

Also, this code was written on the fly... be careful when using it. There might be a weird edge case that I am missing in the last code segment.

Cheers! Ned