How to best add element to array at arbitrary index in PHP?

Question

How can I write a solution for which the current PHP interpreter (5.4) is smart enough to simply do about 3-5 copies instead of a full on item-by-item array sort?

Note, I know a few methods to insert an element into an indexed array. However this does not satisfy my understanding. For instance in C++, you can do something using std::copy or make a struct or union as a multi-element array cursor.

So I wonder if I play by PHP's rules somehow, what syntax can one use to have, under the hood, something closer to

Copy the [range of elements from some index to the end of A] into temp C

Copy B into A[Index],

Copy C into A[Index+count(B)]

Than this...

$MasterItemList = $Page[$CurrentPage]->GetItems();   /* Returns an array with 512 Items.         */
$UpdateList = GetUpdatePage();                       /* Returns multi-dimensional array such that: 
                                                        $result[][0]=an index and 
                                                        $result[][1]=a list of items             */

foreach($UpdateList as $Update)
{ foreach($Update as $cursor => $ItemList)
  {
    $cursor=$cursor+0;  //to int..
    $numitems=count($ItemList);

    if($ItemList[0]->NewAddition)
    {
      $BeforeUpdate=array_splice($MasterItemList,0, $cursor, true);
      $AfterUpdate=array_splice($MasterItemList, $cursor+$numitems, 0);
      $MasterItemList=array_merge($BeforeUpdate,$ItemList,$AfterUpdate);

      $Page[$CurrentPage]->OffsetCorrection+=$numitems;
    }
    else
    {
      $i=0;
      foreach($ItemList as $LineItem)
      {
        $MasterItemList[$cursor+$i] = $LineItem;
        $i++;
      }
    }
  }
}

Forgive me if I've a few errors jotting this down, let me know and I'll correct them.

Namely though, I dont think proper referencing and scope are available to the interpreter for it to be able to do the logic directly using this method. It's already a woefully expensive looking thing.. What can be done to do this 'the right way' for PHP?

Examples:

// An Update List

Array(
    [0] => Array(
        [0] => 31
        [1] => Array(
            [1] => stdClass Object 
                (
                    [NewAddition] => false
                    [Name] => "********"
                    [Date] => 1364920943
                    [Active] => 1
                    .
                    .
                    .
                )

            [2] => stdClass Object 
                (
                    [NewAddition] => false
                    [Name] => "********"
                    [Date] => 1364920943
                    [Active] => 1
                    .
                    .
                    .
                )

            [3] => stdClass Object 
                (
                    [NewAddition] => false
                    [Name] => "********"
                    [Date] => 1364920943
                    [Active] => 1
                    .
                    .
                    .
                )

        )                
    )
)

And MasterItemList is simply an array of these same objects (class Item).

A few things to note:

• This data is only accessed in a purely sequential manner anywhere it would matter for this script.
• Only the first item in a newly inserted set needs to be checked for update in this part of the script. All items following in the set will be always be new.
• Items trailing over 512 are auto-adjusted into the next page load. I can adjust size of pages to trade between array sorting performance & data fetch performance (async buffered).

Answer 1

First of all, PHP arrays are not "arrays" in the data structure sense; they are actually hash tables and doubly linked lists rolled into one. When you are indexing into an array e.g. with $list[$i] $i is hashed to find the corresponding element; it's not simple arithmetic as it is in e.g. C++.

Additionally, since arrays are also linked lists the implementation of array_splice is much more efficient than it might appear, at least if the portion being removed is small enough (hashing the new items is normally fast, and interposing items at a certain place of a linked list is constant time).

Of course this means that PHP arrays consume much more memory than a "pure" array would and they are also slower if all you are intending is index-based access. In those situations the SPL offers SplFixedArray which is an implementation of an array in the data structure sense of the word.

In your particular case, array_splice should be your first option; you can insert an array chunk with just one call:

array_splice($MasterItemList, $cursor, 0, $ItemList);