Array collection ordering question

PHP
1

I have an associated array being used as a map, as well as using the internal pointer to keep reference of the order of which elements are added - so I can use it as an iterator later (ordering of the elements is important).

The location of the elements obviously move about.


$myArray = ('key1' => 'val1', 'key2' => 'val2');

I want to be able to push in an element before a certain key (e.g. insert before ‘key2’ a new element ‘keyx’ => ‘valx’).

So essentially, (and hopefully), get the position of the key and insert an element into its location shuffling the other elements forward.

I am looking for a suggestion of the most efficient way of managing this collection without necessarily iterating over the collection just to get the pointer in the right place, introducing a different data structure.

Is there are quick way I can do this that is alluding me?

Cheers
Cam

2

A double linked list should do the trick if I understand you correctly:

http://www.php.net/manual/en/class.spldoublylinkedlist.php

3

try array_splice() (see example #1)

4

Thanks for the response (proxi),

Just a quick check (considering the PHP doco looks a little lean), can I prepend an element before a certain index/key, and still then obtain the value directly with a key? Kinda a linked list with some efficient prepend element behaviour and retain a map behaviour…

Cheers

5

Thanks Kalon, how would I obtain the index of the element directly? e.g. obtain the position of the key/index (as it is not numeric, and changes location etc hopefully without the need of iterating to locate its offset)?

If I knew the offset directly I would be able to use this function, but I need to locate the offset/index of the associative key before I could use array_slice/splice/merge (which still might be the answer - but needs something before it).

6

Pulling out the array_keys and then using array_search to find the might do the trick - does array_search iterate I wonder? I guess it seems like the likely answer.

Thanks for the responses.

7

In the end I am deciding to use a bit of a combo of:


// Setup a lookup to avoid iterating over the collection
$keyLocations = array_flip(array_keys($myArray));
// Check the location of the key directly without iterating
$offset = $keyLocations[$key];

// Perform the array_merge(array_slice, array, array_slice);
8

I know I’m late to the party but foreach() with break; and a position tracking variable OR reset() with next(), key(), and a position tracking variable is about the best you can do. array_keys() and array_flip() are creating whole new arrays. You’re iterating over the whole array twice and allocating and cleaning up RAM. Not exactly efficient. But PHP never made any claims to efficient programming in the first place so as long as the solution works. :wink:

9

What’s the actual purpose of this?

as well as using the internal pointer to keep reference of the order of which elements are added

When I read this it sounded like you want to keep track of the order that elements were added to the array, but that happens automatically and clearly that’s not what you’re trying to do. I’d just like to understand your use case better.

10

I have written a routes mapper, and wanted to have an array that you could push different named routes onto. I have used a simple associative array to map the name of the route to a route class which will be iterated over to locate a matching route at execution.

The order in which the routes are added is important as if you wanted one route to be placed in front you would have to locate the named route you wanted and insert above it so it is executed first.

The challenge I guess is that I wanted to remain using the standard internal pointer, and know which named route was inserted before the other, as well as still wanting it to operate as a map so I can easily locate the route by using the name.

Thanks for the help, I will definitely opt for the foreach() break combo. After I wrote it I reflected on it and thought it might look easier to understand but not as efficient - but I think foreach is just as readable in the end… if not more :wink:

11

It seems that SplHeap will do what you are asking for:

http://www.php.net/manual/en/class.splheap.php

There is an example a user provided. If you follow that example, you will need to modify the compare method to match your needs. The only thing is that you will need to figure out some rules as to what value takes a greater presence than another.

The other issue is that you need the value that was inserted. You can do something like this:


class RouteMap extends SplHeap {
    public function compare($value1, $value2) {
        //...
    }

    //SplHeap::insert does not return a value. This works towards your advantage.
    public function insert($node) {
      parent::insert($node);

      return $node;
    }
}

Furthermore, after figuring out how you will compare you can write a search() method in order to find a specific route efficiently.