On 09/04/2024 17:12, Michael S wrote:
> On Tue, 9 Apr 2024 15:13:54 +0200
> David Brown <david.brown@hesbynett.no> wrote:
>
>> On 09/04/2024 12:27, Michael S wrote:
>>> On Tue, 9 Apr 2024 09:45:08 +0200
>>> David Brown <david.brown@hesbynett.no> wrote:
>>>
>>
>>>> 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.
>>>
>>
>> Perhaps you don't understand about what "real-time" means. Real-time
>> development does not care about theoretical possibilities of
>> different implementations, because you fix your system at /one/
>> implementation. But it /does/ care about theoretical possibilities of
>> what could happen in that one system. I don't care if some
>> implementation uses Pink-Green trees to get O(1) average speed, or
>> another one uses Purple-Brown trees to get O(n ^ 27) space
>> complexity. I only care about the implementation I am using. And I
>> don't care about its average speed, I only care about its worst-case
>> spaces and times.
>>
>> I don't care if it does 99.999% of its operations within 1µs, I care
>> if I can /guarantee/ that /every/ case is completed with 1 second.
>>
>> Sometimes in real-time systems you will prefer a linear search
>> through a list, because it is easier to be sure of your limits and
>> the correctness of the code in all cases - with the simpler code,
>> it's likely that your worst case times are better than many kinds of
>> tree.
>>
>> And the same applies to space considerations - the worst case is the
>> only relevant case.
>>
>
> You continue to argue about unimportant theoretical possibilities.
> std::map is *never* Pink-Green or Purple-Brown, It is either
> Guibas-Sedgewick, better known as red-black or, very rarely,
> Adelson-Velsky-Landis.

There are no guarantees about that at all. I am sure you are correct
that these are the most common types of implementation - or rather, the
implementations used in the most commonly used C++ standard libraries.
But they are not the only possibilities - do you know that these are
what are used by IAR's C++ library, and Metrowerks, and EASTL, and any
other C++ library? No, you do not. You /might/ know that these are
used in gcc's libc++ and llvm's library, because that is publicly
available information. But you don't know that other implementations
might have different implementations due to different requirements, such
as absolute minimum ram space or code space, or maybe a wider B-tree
aimed at improving cache friendliness, or something designed for
parallel access.

But let's assume that the implementation has both amortized and
worst-case complexity O(log n) - that's a reasonable assumption and fits
your insistence that it will be either a type of red-black tree or some
kind of AVL tree. Where does that get us?

Do we have a guarantee on the constant factors for the O(log n)
complexity? No.

Do we have a way to test the worst-case times? No.

Do we know if an insertion or deletion will lead to a memory allocation
or deallocation? No.

Do we have any idea of a worst-case time for such allocations or
deallocations? No.

Do we have a solid upper bound on the time a given operation will take? No.

Can we use a std::map in a hard real-time system without doing a great
deal of work measuring and characterising a particular implementation? No.

That's not theoretical - it's real.

On 4/9/24 11:12, Michael S wrote:
> On Tue, 9 Apr 2024 15:13:54 +0200
> David Brown <david.brown@hesbynett.no> wrote:
....
>> complexity. I only care about the implementation I am using. And I
>> don't care about its average speed, I only care about its worst-case
>> spaces and times.
....
> You continue to argue about unimportant theoretical possibilities.

He's doing the exact opposite of worrying about theorectical
possibilities. He's saying that what the implementation he's using
actually does is more important than your instance that it can only be
doing something else.

On Wed, 10 Apr 2024 02:24:59 -0400
James Kuyper <jameskuyper@alumni.caltech.edu> wrote:

> On 4/9/24 11:12, Michael S wrote:
> > On Tue, 9 Apr 2024 15:13:54 +0200
> > David Brown <david.brown@hesbynett.no> wrote:
> ...
> >> complexity. I only care about the implementation I am using. And
> >> I don't care about its average speed, I only care about its
> >> worst-case spaces and times.
> ...
> > You continue to argue about unimportant theoretical possibilities.
>
> He's doing the exact opposite of worrying about theorectical
> possibilities. He's saying that what the implementation he's using
> actually does is more important than your instance that it can only be
> doing something else.

He can check and see by himself that all toolsets that he uses have
std::map implemented on top of red-black tree. It's easy, sources are
here. But it seems arguing is more fun.
And one of the the posibilities that he mentiond (wider nodes) does not
look like even theoretically possible for C++17 and later, because it
would mess with extract() and the rest of node-based APIs.

On 10/04/2024 23:07, Michael S wrote:
> On Wed, 10 Apr 2024 02:24:59 -0400
> James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>
>> On 4/9/24 11:12, Michael S wrote:
>>> On Tue, 9 Apr 2024 15:13:54 +0200
>>> David Brown <david.brown@hesbynett.no> wrote:
>> ...
>>>> complexity. I only care about the implementation I am using. And
>>>> I don't care about its average speed, I only care about its
>>>> worst-case spaces and times.
>> ...
>>> You continue to argue about unimportant theoretical possibilities.
>>
>> He's doing the exact opposite of worrying about theorectical
>> possibilities. He's saying that what the implementation he's using
>> actually does is more important than your instance that it can only be
>> doing something else.
>
> He can check and see by himself that all toolsets that he uses have
> std::map implemented on top of red-black tree. It's easy, sources are
> here. But it seems arguing is more fun.

No, it is /not/ easy - sources for big C++ standard libraries are far
from simple to understand. (That is in no way a criticism - I
understand why they are written the way they are.) I could look up
sources and see identifiers or comments saying they use red-black trees,
but as I have already explained several times, knowing that does not
give me anywhere close to the guarantees that are needed before the code
is useable for hard real-time systems. Of course I could study the code
for long enough, and do enough analysis and testing to establish timing
guarantees - but it would be vastly simpler and faster to write my own
data structures from scratch to fulfil real-time requirements. I would
not expect my implementations to be faster on average for general usage
- indeed, I'd expect them to be a lot slower. But /knowing/ the limits
is the important point, not the speed.

If you don't know what real-time requirements are - what the phrase
"real-time" means - that's fine. Most people don't need to know about
it. Even most people who work with small embedded systems as a
profession don't really understand it - most embedded systems don't have
serious real-time requirements. But some do, and the more advanced C++
standard library features are not something that could be considered for
them.

If you are interesting it knowing what real-time means, I can try to
explain. If you'd rather continue playing salesman for C++ standard
library containers, then we'll just have to leave it.

> And one of the the posibilities that he mentiond (wider nodes) does not
> look like even theoretically possible for C++17 and later, because it
> would mess with extract() and the rest of node-based APIs.
>

On Thu, 2024-04-11 at 09:57 +0200, David Brown wrote:
> On 10/04/2024 23:07, Michael S wrote:
> > On Wed, 10 Apr 2024 02:24:59 -0400
> > James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
> >
> > > On 4/9/24 11:12, Michael S wrote:
> > > > On Tue, 9 Apr 2024 15:13:54 +0200
> > > > David Brown <david.brown@hesbynett.no> wrote:
> > > ...
> > > > > complexity.  I only care about the implementation I am using..  And
> > > > > I don't care about its average speed, I only care about its
> > > > > worst-case spaces and times.
> > > ...
> > > > You continue to argue about unimportant theoretical possibilities.
> > >
> > > He's doing the exact opposite of worrying about theorectical
> > > possibilities. He's saying that what the implementation he's using
> > > actually does is more important than your instance that it can only be
> > > doing something else.
> >
> > He can check and see by himself that all toolsets that he uses have
> > std::map implemented on top of red-black tree. It's easy, sources are
> > here. But it seems arguing is more fun.
>
> No, it is /not/ easy - sources for big C++ standard libraries are far
> from simple to understand.  (That is in no way a criticism - I
> understand why they are written the way they are.)  I could look up
> sources and see identifiers or comments saying they use red-black trees,
> but as I have already explained several times, knowing that does not
> give me anywhere close to the guarantees that are needed before the code
> is useable for hard real-time systems.  Of course I could study the code
> for long enough, and do enough analysis and testing to establish timing
> guarantees - but it would be vastly simpler and faster to write my own
> data structures from scratch to fulfil real-time requirements.  I would
> not expect my implementations to be faster on average for general usage
> - indeed, I'd expect them to be a lot slower.  But /knowing/ the limits
> is the important point, not the speed.
>
Yup, the good point of std::list/set/map/... is that users can use it nearly
blindingly. But when you calculate the gains/losses, things are different than
what is usually thought.

> If you don't know what real-time requirements are - what the phrase
> "real-time" means - that's fine.  Most people don't need to know about
> it.  Even most people who work with small embedded systems as a
> profession don't really understand it - most embedded systems don't have
> serious real-time requirements.  But some do, and the more advanced C++
> standard library features are not something that could be considered for
> them.
>
> If you are interesting it knowing what real-time means, I can try to
> explain.  If you'd rather continue playing salesman for C++ standard
> library containers, then we'll just have to leave it.
>
> > And one of the the posibilities that he mentiond (wider nodes) does not
> > look like even theoretically possible for C++17 and later, because it
> > would mess with extract() and the rest of node-based APIs.
> >
>
>

On 11/04/2024 13:25, wij wrote:

> Yup, the good point of std::list/set/map/... is that users can use it nearly
> blindingly. But when you calculate the gains/losses, things are different than
> what is usually thought.
>
Yes, most C++ users can use these standard library containers "blindly".
And for others that have special requirements, things like custom
allocators and other flexibilities can help.

But people working on real-time systems, high-reliability systems,
safety-related systems, or very resource-constrained systems can't do
/anything/ blindly.

Am 11.04.2024 um 13:47 schrieb David Brown:

> Yes, most C++ users can use these standard library containers "blindly".
>  And for others that have special requirements, things like custom
> allocators and other flexibilities can help.

Custom allocators only make sense with a vector. With all other con-
tainers the standars library does a allocator_traits<X>::rebind_alloc<Y>
to have a different allocator type. F.e. a map never uses the supplied
allocator since the nodes also contain the links. For me the whole
allocator-concept mostly doesn't make sense because of that.

On Thu, 11 Apr 2024 19:25:44 +0800
wij <wyniijj5@gmail.com> wrote:

> Yup, the good point of std::list/set/map/... is that users can use it
> nearly blindingly. But when you calculate the gains/losses, things
> are different than what is usually thought.
>

I can not see a single reason to use std::list. It brings nothing to the
table relatively to my own lists and just reduces flexibility and
transparency.
Associative containers are very different.
Even std::vector is different - while it does not bring to table a lot,
it brings quite enough to prefer std over home-bred.

On Thu, 11 Apr 2024 14:04:47 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:

> Am 11.04.2024 um 13:47 schrieb David Brown:
>
> > Yes, most C++ users can use these standard library containers
> > "blindly". And for others that have special requirements, things
> > like custom allocators and other flexibilities can help.
>
> Custom allocators only make sense with a vector. With all other con-
> tainers the standars library does a
> allocator_traits<X>::rebind_alloc<Y> to have a different allocator
> type. F.e. a map never uses the supplied allocator since the nodes
> also contain the links. For me the whole allocator-concept mostly
> doesn't make sense because of that.
>

I tried to implement custom allocator for std::multiset and actually
succeed. But it was too hard and too ugly. So I happily forgot how to
do it 2 hours later.

Am 11.04.2024 um 15:18 schrieb Michael S:
> On Thu, 11 Apr 2024 14:04:47 +0200
> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>
>> Am 11.04.2024 um 13:47 schrieb David Brown:
>>
>>> Yes, most C++ users can use these standard library containers
>>> "blindly". And for others that have special requirements, things
>>> like custom allocators and other flexibilities can help.
>>
>> Custom allocators only make sense with a vector. With all other con-
>> tainers the standars library does a
>> allocator_traits<X>::rebind_alloc<Y> to have a different allocator
>> type. F.e. a map never uses the supplied allocator since the nodes
>> also contain the links. For me the whole allocator-concept mostly
>> doesn't make sense because of that.
>>
>
> I tried to implement custom allocator for std::multiset and actually
> succeed. But it was too hard and too ugly. So I happily forgot how to
> do it 2 hours later.

To make this work a custom allocator should be rebind<>-able to any
type, thereby having a typed malloc()-like allocator for all types
and sizes.

On Thu, 11 Apr 2024 15:31:21 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:

> Am 11.04.2024 um 15:18 schrieb Michael S:
> > On Thu, 11 Apr 2024 14:04:47 +0200
> > Bonita Montero <Bonita.Montero@gmail.com> wrote:
> >
> >> Am 11.04.2024 um 13:47 schrieb David Brown:
> >>
> >>> Yes, most C++ users can use these standard library containers
> >>> "blindly". And for others that have special requirements, things
> >>> like custom allocators and other flexibilities can help.
> >>
> >> Custom allocators only make sense with a vector. With all other
> >> con- tainers the standars library does a
> >> allocator_traits<X>::rebind_alloc<Y> to have a different allocator
> >> type. F.e. a map never uses the supplied allocator since the nodes
> >> also contain the links. For me the whole allocator-concept mostly
> >> doesn't make sense because of that.
> >>
> >
> > I tried to implement custom allocator for std::multiset and actually
> > succeed. But it was too hard and too ugly. So I happily forgot how
> > to do it 2 hours later.
>
> To make this work a custom allocator should be rebind<>-able to any
> type, thereby having a typed malloc()-like allocator for all types
> and sizes.
>
>

The point is to not be more generic than absolutely necessary for
particular application.

Am 11.04.2024 um 15:39 schrieb Michael S:
> On Thu, 11 Apr 2024 15:31:21 +0200
> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>
>> Am 11.04.2024 um 15:18 schrieb Michael S:
>>> On Thu, 11 Apr 2024 14:04:47 +0200
>>> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>>
>>>> Am 11.04.2024 um 13:47 schrieb David Brown:
>>>>
>>>>> Yes, most C++ users can use these standard library containers
>>>>> "blindly". And for others that have special requirements, things
>>>>> like custom allocators and other flexibilities can help.
>>>>
>>>> Custom allocators only make sense with a vector. With all other
>>>> con- tainers the standars library does a
>>>> allocator_traits<X>::rebind_alloc<Y> to have a different allocator
>>>> type. F.e. a map never uses the supplied allocator since the nodes
>>>> also contain the links. For me the whole allocator-concept mostly
>>>> doesn't make sense because of that.
>>>>
>>>
>>> I tried to implement custom allocator for std::multiset and actually
>>> succeed. But it was too hard and too ugly. So I happily forgot how
>>> to do it 2 hours later.
>>
>> To make this work a custom allocator should be rebind<>-able to any
>> type, thereby having a typed malloc()-like allocator for all types
>> and sizes.
>>
>>
>
> The point is to not be more generic than absolutely necessary for
> particular application.
>

A rebind()-able allocator is as generic as possible. There's no way
to have a pool-allocator for a container's given type since the type
is always rebound.

On Thu, 2024-04-11 at 13:47 +0200, David Brown wrote:
> On 11/04/2024 13:25, wij wrote:
>
> > Yup, the good point of std::list/set/map/... is that users can use it nearly
> > blindingly. But when you calculate the gains/losses, things are different than
> > what is usually thought.
> >
> Yes, most C++ users can use these standard library containers "blindly".
>   And for others that have special requirements, things like custom
> allocators and other flexibilities can help.
>
> But people working on real-time systems, high-reliability systems,
> safety-related systems, or very resource-constrained systems can't do
> /anything/ blindly.
>

Understand. People here seemingly do not program hard-wares (thus don't really
understand C, IMO). I quit hard-ware things (and C) for a long time. But, for
embedded systems, esp. real real-time systems, my first choice was Assembly..
I am not aware whether C++ is suitable for real real-time systems or not.

I had encountered programming for buggy hardwares (sound efffect chips, and some
badly designed hard-wares, because the company wanted to save money) where
some pins had to be read/written in a peculiar way (language optimization will
be a problem here). And, an embedded system that had to simulate UART where
timeing is really critical in order to communicate with other devices (every
machine tick counts). And a system that uses two DOS machines to work as one
machine where COM1 is set to the highest priority to provide basic
synchronization mechanism...
And, for embedded systems, RAM/pins is money, related to survival of product.
Average people don't understand this.

High-level languages normally involves more supporting tools, all these need
update and learning, not necessarily good.

On 11/04/2024 16:40, wij wrote:
> On Thu, 2024-04-11 at 13:47 +0200, David Brown wrote:
>> On 11/04/2024 13:25, wij wrote:
>>
>>> Yup, the good point of std::list/set/map/... is that users can use it nearly
>>> blindingly. But when you calculate the gains/losses, things are different than
>>> what is usually thought.
>>>
>> Yes, most C++ users can use these standard library containers "blindly".
>>   And for others that have special requirements, things like custom
>> allocators and other flexibilities can help.
>>
>> But people working on real-time systems, high-reliability systems,
>> safety-related systems, or very resource-constrained systems can't do
>> /anything/ blindly.
>>
>
> Understand. People here seemingly do not program hard-wares (thus don't really
> understand C, IMO). I quit hard-ware things (and C) for a long time. But, for
> embedded systems, esp. real real-time systems, my first choice was Assembly.
> I am not aware whether C++ is suitable for real real-time systems or not.
>

C++ is fine for hard real-time and safety-critical systems - as long as
you use an appropriate subset of the features, and as long as your
development process is suitable. It's not any different from any other
language in that respect. And I'd rate C++ above C, and C above
assembly, for suitability.

> I had encountered programming for buggy hardwares (sound efffect chips, and some
> badly designed hard-wares, because the company wanted to save money) where
> some pins had to be read/written in a peculiar way (language optimization will
> be a problem here).

You need to know how to access the hardware properly, and how to work
with the language and the tools to achieve that. Sometimes this can be
a bit fiddly, but it is entirely possible to do in a solid and reliable way.

> And, an embedded system that had to simulate UART where
> timeing is really critical in order to communicate with other devices (every
> machine tick counts). And a system that uses two DOS machines to work as one
> machine where COM1 is set to the highest priority to provide basic
> synchronization mechanism...
> And, for embedded systems, RAM/pins is money, related to survival of product.
> Average people don't understand this.
>
> High-level languages normally involves more supporting tools, all these need
> update and learning, not necessarily good.
>

Sure. (But don't update the build tools for a project - they are part
of the project.)

11.04.2024 16:13 Michael S kirjutas:

> I can not see a single reason to use std::list. It brings nothing to the
> table relatively to my own lists and just reduces flexibility and
> transparency.

You are right, but for wrong reasons. There is usually little reason to
use std::list because std::vector or std::deque is almost always a
better choice.

std::list might be occasionally useful for holding a bunch of entity
objects whose addresses must remain unchanged.