Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #118723

Re: std::map advocacy

From Michael S <already5chosen@yahoo.com>
Newsgroups comp.lang.c++
Subject Re: std::map advocacy
Date 2024-04-09 13:27 +0300
Organization A noiseless patient Spider
Message-ID <20240409132722.0000414d@yahoo.com> (permalink)
References (14 earlier) <uv0dd7$3diif$1@dont-email.me> <uv0jb2$ck7p$3@i2pn2.org> <uv0sd6$3hbhr$1@dont-email.me> <uv1vco$3pmea$1@dont-email.me> <uv2rm5$3g4p$1@dont-email.me>

Show all headers | View raw

On Tue, 9 Apr 2024 09:45:08 +0200
David Brown <david.brown@hesbynett.no> wrote:

> On 09/04/2024 01:42, James Kuyper wrote:
> > On 4/8/24 09:45, David Brown wrote:
> > ...  
> >> The complexity guarantees in the standard are vague - they are
> >> given as an indication of "time and/or space complexity", and I
> >> assume they mean the average or amortized complexity.  
> > 
> > I don't think they are that vague. Some of them are explicitly
> > described as amortized - virtually all of which are "amortized
> > constant time", I would presume that any complexity guarantee not
> > explicitly described as amortized, isn't.  
> 
> I only saw "amortized" used in the context of "amortized constant" 
> complexity.  (I have not read the standards here very thoroughly, so
> I might have missed something.)   I think it is fair to assume that 
> something marked "constant" complexity, without "amortized", really
> is constant - and that will obviously also apply to the worst case.
> 
> Everything else is vague.  That's good enough for most uses, and 
> stricter guarantees would limit implementations too much.  But it is
> not suitable for real-time systems or systems with tight constraints
> on time or space.
> 
> >   
> >> That's fine for general use, but
> >> not for real-time systems.  (Some people distinguish between "hard
> >> real-time" and "soft real-time" - the C++ standard guarantees
> >> /might/ be acceptable for some "soft real-time" uses.)  
> > 
> > The standard's guarantees about complexity are meant to be what
> > developers can portably rely upon. Code that doesn't need to be
> > portable can rely upon more precise specifications of the
> > complexity provided by a particular implementation of C.  
> 
> Sure.  However, I don't think any of the big C++ standard library 
> implementations provide tighter guarantees.  Other implementations of 
> standard library containers, such as the EASTL, might have worst-case 
> guarantees - or they might at least have simple enough source code
> that it is practical to determine the complexity by reading the code.
> 
> Typically, however, small embedded systems and hard real-time systems 
> have little need for things like std::map<> or std::vector<>, so it
> is not much of an issue in practice.  But it is one of the reasons
> why I rule out such containers for use in the code I write.
> 

You're arguing about unimportant theoretical possibilities.

In practice 95% of std::map implementations that you will ever
encounter will be Red-Black Tree and the remaining 5% will be AVL Tree.
All of them will have lookup, insertion and deletion in O(logN), not
amortized, but honest worst case. If you want all three major ops and
if your keys have no special properties than nothing more real-time
friendly than partially balanced binary tree does not exist. Or at least
I never heard about it and I tend to keep my ears open to that sort of
gossips.

All above not considering memory allocation part, but for robustness of
the later there exist several solutions mentioned by several posters in
this sub-thread.

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

Thread

Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-04 20:11 +0200
  Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-04 21:55 +0300
    Re: Ain't that beautiful ? Sam <sam@email-scan.com> - 2024-04-04 20:00 -0400
      Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-05 00:21 +0000
        Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-05 17:44 +0300
          Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-05 17:27 +0200
            Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-05 18:37 +0300
              Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-05 18:04 +0200
                Re: Ain't that beautiful ? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-04-06 15:55 -0700
                Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 08:28 +0200
                Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-07 15:51 +0000
                Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 19:35 +0200
                Re: Ain't that beautiful ? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-04-07 12:21 -0700
    Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-05 05:05 +0200
      Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-05 17:52 +0300
        Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-05 17:26 +0200
          Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-05 20:00 +0000
            Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-05 22:29 +0200
              Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-05 21:29 +0000
                Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-06 09:06 +0200
                Re: Ain't that beautiful ? Paavo Helde <eesnimi@osa.pri.ee> - 2024-04-06 17:29 +0300
                Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-06 14:56 +0000
                Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-06 18:34 +0200
                Re: Ain't that beautiful ? wij <wyniijj5@gmail.com> - 2024-04-07 03:00 +0800
                Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 08:28 +0200
                Re: Ain't that beautiful ? wij <wyniijj5@gmail.com> - 2024-04-08 07:47 +0800
                Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-07 15:25 +0300
                Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-07 16:00 +0300
                Re: Ain't that beautiful ? David Brown <david.brown@hesbynett.no> - 2024-04-07 16:06 +0200
                Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-07 18:37 +0300
                Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-07 15:58 +0000
                Re: Ain't that beautiful ? David Brown <david.brown@hesbynett.no> - 2024-04-07 18:00 +0200
                Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 19:38 +0200
                std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-07 18:38 +0300
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-07 18:06 +0200
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-07 19:35 +0300
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-08 11:29 +0200
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-08 13:34 +0300
                Re: std::map advocacy wij <wyniijj5@gmail.com> - 2024-04-08 19:18 +0800
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-08 16:32 +0300
                Re: std::map advocacy wij <wyniijj5@gmail.com> - 2024-04-09 08:40 +0800
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 12:48 +0300
                Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-09 13:16 +0200
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-08 15:30 +0200
                Re: std::map advocacy scott@slp53.sl.home (Scott Lurndal) - 2024-04-08 17:19 +0000
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 00:47 +0300
                Re: std::map advocacy scott@slp53.sl.home (Scott Lurndal) - 2024-04-08 23:00 +0000
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 02:20 +0300
                Re: std::map advocacy scott@slp53.sl.home (Scott Lurndal) - 2024-04-09 15:22 +0000
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-09 09:11 +0200
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 13:12 +0300
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-09 15:01 +0200
                Re: std::map advocacy Richard Damon <richard@damon-family.org> - 2024-04-08 07:10 -0400
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-08 15:45 +0200
                Re: std::map advocacy James Kuyper <jameskuyper@alumni.caltech.edu> - 2024-04-08 19:42 -0400
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-09 09:45 +0200
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 13:27 +0300
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-09 15:13 +0200
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 18:12 +0300
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-09 18:22 +0200
                Re: std::map advocacy James Kuyper <jameskuyper@alumni.caltech.edu> - 2024-04-10 02:24 -0400
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-11 00:07 +0300
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-11 16:18 +0300
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-11 16:39 +0300
                Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-11 16:21 +0200
                Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-11 15:31 +0200
                Re: std::map advocacy wij <wyniijj5@gmail.com> - 2024-04-11 22:40 +0800
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-11 16:55 +0200
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-11 16:13 +0300
                Re: std::map advocacy Paavo Helde <eesnimi@osa.pri.ee> - 2024-04-11 18:18 +0300
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-11 09:57 +0200
                Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-11 13:47 +0200
                Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-11 14:04 +0200
                Re: std::map advocacy wij <wyniijj5@gmail.com> - 2024-04-11 19:25 +0800
                Re: std::map advocacy scott@slp53.sl.home (Scott Lurndal) - 2024-04-07 16:09 +0000
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-07 19:48 +0300
                Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 19:45 +0200
                Re: std::map advocacy Paavo Helde <eesnimi@osa.pri.ee> - 2024-04-08 16:37 +0300
                Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 19:44 +0200
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-08 11:15 +0300
                Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-08 14:09 +0200
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-08 16:26 +0300
                Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-08 16:54 +0200
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-08 20:52 +0300
                Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 00:17 +0300
                Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-09 07:34 +0200
                Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 16:39 +0200
                Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-07 18:41 +0300
                Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 19:36 +0200
                Re: Ain't that beautiful ? Paavo Helde <eesnimi@osa.pri.ee> - 2024-04-07 18:25 +0300

csiph-web