Path: csiph.com!news.mixmin.net!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen
Date: Tue, 15 Aug 2023 08:37:56 -0700
Organization: A noiseless patient Spider
Lines: 16
Message-ID: <86o7j871uz.fsf@linuxsc.com>
References: <uaubnm$3i781$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="4aa43ab23f99b81d777a1b3458fe2d41"; logging-data="3037868"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+u++EaTK2XUeB8V1tW4yX/I9/gLbJdSmc="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:EGePxlzMRCYDKIzBm94TiDf5ZNQ= sha1:1qN2v19g6iZMcTGiBBmGEMQteH8=
Xref: csiph.com comp.lang.c++:91258

Lynn McGuire <lynnmcguire5@gmail.com> writes:

> "Inside STL:  The map, set, multimap, and multiset" by Raymond Chen
>    https://devblogs.microsoft.com/oldnewthing/20230807-00/
>
> "The complexity requirements of the C+ standard library map, set,
> multimap, and multiset basically narrow the possible implementation
> options to AVL trees and red-black trees."

I find this claim hard to believe.  There are other kinds of
balanced trees that offer the same kinds of performance
guarantees that AVL and red-black trees do.  Is there some sort
of unexpected requirement in the C++ standard that would rule out
other balanced tree data structures?  I confess I have not tried
to read the C++ standard looking for such a requirement, but I'm
willing to take a look if someone provides a specific reference.