From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <jwakely.gcc@gmail.com>
Received: from mail-wr1-x42f.google.com (mail-wr1-x42f.google.com
 [IPv6:2a00:1450:4864:20::42f])
 by sourceware.org (Postfix) with ESMTPS id 8631E3858409
 for <libstdc++@gcc.gnu.org>; Tue, 24 Aug 2021 10:27:23 +0000 (GMT)
DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8631E3858409
Received: by mail-wr1-x42f.google.com with SMTP id e5so13952306wrp.8
 for <libstdc++@gcc.gnu.org>; Tue, 24 Aug 2021 03:27:23 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=8HpgF75mqmfvJ2vUcMXTFgxwS3npcc1DlT10MB4xjeo=;
 b=Mfk8JMCYcy3b178lVzTuDFjtpIeNchM9mOgbgjz5B4OrVV4xedZHt9/kzpg0YZ+SR6
 Zjoe5EktAnOwfQOsf+594Btzq+xcz50d9pONNFg2NYkcJ/FFuKs6qfFTAc4MiEOrZUev
 x/rPdzbjsPbKIyXUai5ywLLb3CHq8NT3eqyT4mvhrdkLWKA+znXkN37jSsKtm4kdBG7S
 6PehRilIMryB55Pt3/FGedZv0XPBqdq9eUxsk1xt4+I9erFWm8weWANT2zmKI3diS4zj
 x3iyGtql/FPJKrtpUY4GgBdmZMDd2Ay+WuJ/xP0bJiqfxhwF2gbu3cInwhanXAeiHx43
 L5IA==
X-Gm-Message-State: AOAM530TmIof0wF0TsUYiStRiPuUtdZhQuGy0l03tI0VwiiyIFa/iqoG
 iRPekfxQ6WsQxgVHkp38jEaqDve06kX5Oa2QHtI=
X-Google-Smtp-Source: ABdhPJxTb384f5SOkpaBfarQi55CJwrIPPSidAjvaL7OHXCe7hJCqelftswXblEFxUnBBcXlErFtnVXqryhPhuGLJ88=
X-Received: by 2002:adf:fd8c:: with SMTP id d12mr14691002wrr.21.1629800842661; 
 Tue, 24 Aug 2021 03:27:22 -0700 (PDT)
MIME-Version: 1.0
References: <CADLcvW=oiqGfUFVqyPjhN5_hHv8oaxvu5wTcj495CFXnc0sp1Q@mail.gmail.com>
In-Reply-To: <CADLcvW=oiqGfUFVqyPjhN5_hHv8oaxvu5wTcj495CFXnc0sp1Q@mail.gmail.com>
From: Jonathan Wakely <jwakely.gcc@gmail.com>
Date: Tue, 24 Aug 2021 11:27:08 +0100
Message-ID: <CAH6eHdTy8RjON5gT1RYq77oSTFKk+AW=j3N2+srxG-XgLcnNxQ@mail.gmail.com>
Subject: Re: Faster indexed heuristic doubly-linked list to STL?
To: Rodion Efremov <coderodd3@gmail.com>
Cc: "libstdc++" <libstdc++@gcc.gnu.org>
X-Spam-Status: No, score=-1.2 required=5.0 tests=BAYES_00, DKIM_SIGNED,
 DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, HTML_MESSAGE,
 RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS,
 TXREP autolearn=ham autolearn_force=no version=3.4.4
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on
 server2.sourceware.org
Content-Type: text/plain; charset="UTF-8"
X-Content-Filtered-By: Mailman/MimeDel 2.1.29
X-BeenThere: libstdc++@gcc.gnu.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Libstdc++ mailing list <libstdc++.gcc.gnu.org>
List-Unsubscribe: <https://gcc.gnu.org/mailman/options/libstdc++>,
 <mailto:libstdc++-request@gcc.gnu.org?subject=unsubscribe>
List-Archive: <https://gcc.gnu.org/pipermail/libstdc++/>
List-Post: <mailto:libstdc++@gcc.gnu.org>
List-Help: <mailto:libstdc++-request@gcc.gnu.org?subject=help>
List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/libstdc++>,
 <mailto:libstdc++-request@gcc.gnu.org?subject=subscribe>
X-List-Received-Date: Tue, 24 Aug 2021 10:27:26 -0000

On Tue, 24 Aug 2021, 10:55 Rodion Efremov via Libstdc++, <
libstdc++@gcc.gnu.org> wrote:

> Hello,
>
> I would like to rewrite my fast linked list in Java [1] to C++ and
> contribute it to STL. If we allow the operation
>
>     iterator at(size_t index) // runs in Theta(sqrt(N))
>
> the data structure in question can add/remove an element also in total
> Theta(sqrt(N)).
>
> What do you think? Can it make it to the library?
>


Probably not.

Libstdc++ is an implementation of the ISO C++ standard library (and related
ISO C++ extensions).

We do have some historical extensions that are not part of the standard,
but they are a maintenance burden and we prefer to avoid adding any more.
We only include things that are in the C++ standard, or are proposed for
inclusion in a future standard.



> Best regards,
> rodde
>
> [1] github.com/coderodde/LinkedList
>