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

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

Re: std::map advocacy

From Michael S <already5chosen@yahoo.com>
Newsgroups comp.lang.c++
Subject Re: std::map advocacy
Date 2024-04-07 19:35 +0300
Organization A noiseless patient Spider
Message-ID <20240407193505.00004d17@yahoo.com> (permalink)
References (8 earlier) <uurm8q$24ka4$1@dont-email.me> <20240407160050.00004370@yahoo.com> <uuu98b$2qou0$1@dont-email.me> <20240407183854.00000797@yahoo.com> <uuuga5$2s7td$2@dont-email.me>

Show all headers | View raw

On Sun, 7 Apr 2024 18:06:29 +0200
David Brown <david.brown@hesbynett.no> wrote:

> On 07/04/2024 17:38, Michael S wrote:
> > On Sun, 7 Apr 2024 16:06:02 +0200
> > David Brown <david.brown@hesbynett.no> wrote:
> >   
> >>
> >> Different people have different needs from C++, and use different
> >> features.  If I were programming on a PC, I'd happily use
> >> std::map<> and the like.  But I don't program on PC's, and I don't
> >> use std::map<>.  If I needed something like that, I'd make my own
> >> class that fitted my requirements tightly - a factor of 10
> >> inefficiency is often fine on big systems, but not on the devices
> >> I work with.
> >>
> >> But that's all fine - use whatever you find useful from the
> >> language.
> >>
> >>  
> > 
> > Factor of 5-10 (mentioned in my other post) is quite rare and mostly
> > applies not to std::map vs custom implementation of RB or AVL tree,
> > but to std::map vs some form of hash, esp. when the nature of the
> > key is such that relatively simple hash function happens to have
> > good collision avoidance properties and when the database is huge,
> > so O(1) vs O(logN) starts to be significant.
> >   
> 
> Sure.
> 
> But remember, for small embedded systems you don't have dynamic
> memory - or if you do, you use it in limited and tightly controlled
> manner.  And in a real-time system, it is the worst-case time that
> matters, unlike PC's where you are generally looking for average or
> amortized times.  So a data structure which allocates and deallocates
> memory unpredictably, can use complex tree structures with little
> control of their worst-case times - no thanks!

As said in post above, in C++17 when the max size of map is known
during initialization, allocation and de-allocation can be solved by
std::map:extract in the same manner you do it for simpler containers:
you push the required number of nodes into std::map then immediately
extract and store in the simple structure, typically managed like a
stack, but probably not using std::stack. Then during main runtime,
in very typical "embedded" manner, you pop nodes that you want to
insert from stack and push extracted nodes back to stack. No malloc, no
free.
It was possibly to achieve similar effect before C++17 as well, but it
required use of custom allocators which are, IMHO, too hard to use.

> 
> (And again, that does not mean these containers are not great choices 
> for all kinds of other uses.)
>

Partially balanced binary trees, like those used by std::map and by its
relatives, are among the most predictable data structures out here.
Certainly they are far more predictable than generic hash that in the
worst case degenerates into O(N).
OTOH, in std::map of given size the difference in worst access time
between perfectly balanced case and most unbalanced case is only
2x. And that applies not just for lookup, but for insertion and
deletion as well.

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