Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:101042 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 77774 invoked from network); 3 Nov 2017 14:47:10 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 3 Nov 2017 14:47:10 -0000 Authentication-Results: pb1.pair.com header.from=bishop.bettini@gmail.com; sender-id=pass Authentication-Results: pb1.pair.com smtp.mail=bishop.bettini@gmail.com; spf=pass; sender-id=pass Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.213.45 as permitted sender) X-PHP-List-Original-Sender: bishop.bettini@gmail.com X-Host-Fingerprint: 209.85.213.45 mail-vk0-f45.google.com Received: from [209.85.213.45] ([209.85.213.45:46310] helo=mail-vk0-f45.google.com) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id 9F/EA-09857-A618CF95 for ; Fri, 03 Nov 2017 09:47:09 -0500 Received: by mail-vk0-f45.google.com with SMTP id k123so1898739vkb.3 for ; Fri, 03 Nov 2017 07:47:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:reply-to:sender:in-reply-to:references:from:date :message-id:subject:to:cc; bh=mOogYMqxkaLr6K9JxajWzB94t9VMc498geAP4H2cICM=; b=EOz7SBs82WWnulFDpJSTaJcZVWSIjcFH9HTVsZQWjpSsUedL9q25sXB/puTXaTlSFC R8qrLYNwkVt8ZXp5qwYyGIrM//J4H850okGDDs4k89z/5f0zMrhr4ANXEZNb2SjVuDsI 0qLdJL+dDsdROP/NXyarULzOcNoIcxpyrzbj6ayj1faM8ABYxNhWRmaEL00jMNZ5+RML dkqEfxFUbWOWtOV90CPozF+DSI7JbojialT4fy8HJfUucFBqRoxS1WLtnkRGwk95rU/p MomXQOIkFsIXZLElvELEvpejxXGyiIfdmpgm79K43Ju0Zg85lFrZf2AAT4kiQam43Kzi 5vdQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:reply-to:sender:in-reply-to :references:from:date:message-id:subject:to:cc; bh=mOogYMqxkaLr6K9JxajWzB94t9VMc498geAP4H2cICM=; b=MPthpSrQRPgrcly9kVE6xM1uj/FomAdnYOjh0GjP7klDW/N0FNNv67YqXQIx99Q/X7 KqLgB2ww68WNKG4zk9xkxJni47oixPg4o71A1Q+SuqZlEziBLUzm9/xwBImZHoilgb4R rSJtB4x7OwBj7Kx8cT0fsTXEZeBnxpESKQ0gPJaz7xmYWGFZ1lJeYyoqD8u91nJJMd7M cDglY6T1Lhz0wUhlopivE4blE9yrHWBLin1N8d5nS/op/34L6hBnqTnUZBCa9tNFJiAy rMQQYmdVCKBLyzAgQTR1r6yjGuHymojVFe5kIPaNcIjUQ2Hq9cOwhF7oPN7GoT8js/Nl QXKQ== X-Gm-Message-State: AMCzsaVejcIN+bFVE8qeJoSUpVxPICZ/WR5+dgk1NfCj2E+iezaa5o3a IxIJTNuCq5axFcloNo/DjLbbL8/LDjlfm194i7eDnOga X-Google-Smtp-Source: ABhQp+QrWXXhvPaVfuuiqVdtn4/lZZT8sOISK/GKj2PpUGuQTT81K5pJpDeNwcV6Sb3WHI/7Zd9F9IUsmLt8pATRwgA= X-Received: by 10.31.205.4 with SMTP id d4mr5699481vkg.198.1509720423795; Fri, 03 Nov 2017 07:47:03 -0700 (PDT) MIME-Version: 1.0 Reply-To: bishop@php.net Sender: bishop.bettini@gmail.com Received: by 10.103.11.4 with HTTP; Fri, 3 Nov 2017 07:46:33 -0700 (PDT) In-Reply-To: References: Date: Fri, 3 Nov 2017 10:46:33 -0400 X-Google-Sender-Auth: zDFRH0wxY1Aqk1cwPRva-oQqHx4 Message-ID: To: Thomas Hruska Cc: PHP Development Content-Type: multipart/alternative; boundary="001a114dde969226cd055d152db3" Subject: Re: [PHP-DEV] Inserting string keys in arrays at any position From: bishop@php.net (Bishop Bettini) --001a114dde969226cd055d152db3 Content-Type: text/plain; charset="UTF-8" On Fri, Nov 3, 2017 at 9:51 AM, Thomas Hruska 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 --001a114dde969226cd055d152db3--