Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

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> (permalink)
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

Show key headers only | View raw

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.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

"Inside STL: The map, set, multimap, and multiset" by Raymond Chen Lynn McGuire <lynnmcguire5@gmail.com> - 2023-08-08 16:23 -0500
  Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen wij <wyniijj5@gmail.com> - 2023-08-08 17:53 -0700
    Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Paavo Helde <eesnimi@osa.pri.ee> - 2023-08-09 09:26 +0300
      Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Öö Tiib <ootiib@hot.ee> - 2023-08-09 03:08 -0700
        Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-09 13:22 +0200
        Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-09 13:52 +0200
          Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Öö Tiib <ootiib@hot.ee> - 2023-08-09 05:10 -0700
            Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-09 14:52 +0200
          Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen wij <wyniijj5@gmail.com> - 2023-08-09 07:32 -0700
            Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-09 16:36 +0200
      Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen wij <wyniijj5@gmail.com> - 2023-08-09 07:20 -0700
        Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Paavo Helde <eesnimi@osa.pri.ee> - 2023-08-09 20:29 +0300
          Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Öö Tiib <ootiib@hot.ee> - 2023-08-09 21:09 -0700
  Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-15 08:37 -0700

csiph-web