Faster indexed heuristic doubly-linked list to STL?

[Jonathan Wakely]

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
>