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

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

Re: std::map advocacy

From David Brown <david.brown@hesbynett.no>
Newsgroups comp.lang.c++
Subject Re: std::map advocacy
Date 2024-04-09 09:45 +0200
Organization A noiseless patient Spider
Message-ID <uv2rm5$3g4p$1@dont-email.me> (permalink)
References (13 earlier) <20240407193505.00004d17@yahoo.com> <uv0dd7$3diif$1@dont-email.me> <uv0jb2$ck7p$3@i2pn2.org> <uv0sd6$3hbhr$1@dont-email.me> <uv1vco$3pmea$1@dont-email.me>

Show all headers | View raw

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.

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