On Fri, Nov 3, 2017 at 9:51 AM, Thomas Hruska <thru...@cubiclesoft.com> wrote:
> I've been wondering for some time why PHP does not have the ability to > efficiently insert string keys before/after an existing string key. > > Let's say I have an array of 10,000 string key/value pairs and I want to > insert five new string key/value pairs at specific positions in the > existing array. Unless I've missed something, despite looking at each of > the array_...() functions, this is not possible in userland without copying > the entire array to insert the new elements It's impossible in user-land because, well, that's just how HashTable works under the hood. Quoting nikic [1]: > The arData array stores the elements in order of insertion. So the first array element will be stored in arData[0], the second in arData[1] etc. This does not in any way depend on the used key, only the order of insertion matters here. That last part is important: the keys from user-land have no bearing on the order in memory. If one wants to effect the in-memory ordering, one must create a new user-land array and insert them in the desired order. As the author of the OrderedHash implementation here: > > https://github.com/cubiclesoft/cross-platform-cpp > > I provide an ordered hash data structure that is similar-ish to the PHP > array implementation, but it also has support for inserting a node anywhere > in the OrderedHash by making a few pointer adjustments. Shifting a few > pointers around is usually magnitudes faster than performing memory > allocations and copying data. Shifting elements in a HashTable.arData would not be cheap. But, honestly I can't think of a scenario where changing the in-memory order would be necessary. If I want an array that traverses in order, I'll insert in order. Otherwise, I'll sort on demand. What seems to matter most is efficiency of lookup by key. > -- > Thomas Hruska > CubicleSoft President > bishop [1]: http://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html
