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

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	2023-08-15 08:37 -0700
Organization	A noiseless patient Spider
Message-ID	<86o7j871uz.fsf@linuxsc.com> (permalink)
References	<uaubnm$3i781$1@dont-email.me>

Show all headers | 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