From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <coderodd3@gmail.com>
Received: from mail-oo1-xc31.google.com (mail-oo1-xc31.google.com
 [IPv6:2607:f8b0:4864:20::c31])
 by sourceware.org (Postfix) with ESMTPS id E93B03858C3B
 for <libstdc++@gcc.gnu.org>; Tue, 24 Aug 2021 09:55:14 +0000 (GMT)
DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E93B03858C3B
Received: by mail-oo1-xc31.google.com with SMTP id
 b5-20020a4ac285000000b0029038344c3dso824218ooq.8
 for <libstdc++@gcc.gnu.org>; Tue, 24 Aug 2021 02:55:14 -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:from:date:message-id:subject:to;
 bh=yLOw4w9AdWAqqKMDOhc9GwnnskkMUdxq/CY7OYaN7RQ=;
 b=VpS5T8FPOTR6Bcg6A2HDP4jn5AQjhh/fOWlg87WN/ylYGNbGHmNb+bXYF6SbZrr5JN
 y2RadvdGQVNNtmAVMJ6KAASGBOPXDo3spahWd+wPNp39hSEJarcbv6f9e++3+7R+FSGB
 3ICzAy4U/axnFVcH4yrykwjelaMNlNAO5UPNGjp0fTi1Ij4s3rD4Y5b7xwkv1qNiUaZI
 g1/O9d6xOeMenP0r4hPcbc3SzUybLi4SlcG/2nfuE44i+FqOIV7p8AUeG7bf/OyfZQEV
 ndNmRJkpbD5cxzeSflOSa6qK0o+dmWQjTS9HqjYcF3InumpI34K4ZOlJcqND2A2IIGBq
 lNLw==
X-Gm-Message-State: AOAM530bKsLpw61tqy9ZHIEEpSxs2cfkIlZFsnmpuilKHNh3lqH8Ru7d
 XAHKTJS8C9NiRc9jUY4hmJAk5RGZiAYdJxkiehG9Xf/2MJ8=
X-Google-Smtp-Source: ABdhPJxciaDCR18dQcEjmZC6vwP9PQbW1fhKW9SQYi9/z1vvzscvxLchCoGktO28DyL/qCbxKhDkUdL35yomYShIgMQ=
X-Received: by 2002:a4a:e4ce:: with SMTP id w14mr22885847oov.76.1629798914216; 
 Tue, 24 Aug 2021 02:55:14 -0700 (PDT)
MIME-Version: 1.0
From: Rodion Efremov <coderodd3@gmail.com>
Date: Tue, 24 Aug 2021 12:55:03 +0300
Message-ID: <CADLcvW=oiqGfUFVqyPjhN5_hHv8oaxvu5wTcj495CFXnc0sp1Q@mail.gmail.com>
Subject: Faster indexed heuristic doubly-linked list to STL?
To: libstdc++@gcc.gnu.org
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00, DKIM_SIGNED,
 DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_ENVFROM_END_DIGIT,
 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 09:55:16 -0000

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?

Best regards,
rodde

[1] github.com/coderodde/LinkedList