"Inside STL: The lists" by Raymond Chen
https://devblogs.microsoft.com/oldnewthing/20230804-00/

"The C++ standard library type list represents a doubly-linked list, and
forward_list is a singly-linked list. Fortunately, the implementations
of both of these lists are pretty much what you expect."

Lynn

On Tuesday, 8 August 2023 at 22:38:43 UTC+3, Lynn McGuire wrote:
> "Inside STL: The lists" by Raymond Chen
> https://devblogs.microsoft.com/oldnewthing/20230804-00/
>
> "The C++ standard library type list represents a doubly-linked list, and
> forward_list is a singly-linked list. Fortunately, the implementations
> of both of these lists are pretty much what you expect."
>
Besides the controversial O(N) range splice of list and non-constant time
erase and insert of forward_list these are pretty much what you expect.

On 2023-08-09 11:52 AM, Öö Tiib wrote:
> On Tuesday, 8 August 2023 at 22:38:43 UTC+3, Lynn McGuire wrote:
>> "Inside STL: The lists" by Raymond Chen
>> https://devblogs.microsoft.com/oldnewthing/20230804-00/
>>
>> "The C++ standard library type list represents a doubly-linked list, and
>> forward_list is a singly-linked list. Fortunately, the implementations
>> of both of these lists are pretty much what you expect."
>>
> Besides the controversial O(N) range splice of list and non-constant time
> erase and insert of forward_list these are pretty much what you expect.

In my opinion Raymon Chen is not trying to hide anything. He's just
noting that /given/ the standard's specification, the implementations
are just what you'd expect. I.e. nothing fancy.

Various possible fancy mods have been discussed in this group.

The most basic one, since lists require dynamic allocation of nodes, to
use internal free lists as caches of nodes, to speed things up (O(1)
allocation after a while, in general). A main reason why that's not done
is probably that if you want speed, neither `std::list` nor
`std::forward_list` should be the default choice. Instead, `std::vector`.

- Alf

On Wednesday, 9 August 2023 at 14:38:00 UTC+3, Alf P. Steinbach wrote:
> On 2023-08-09 11:52 AM, Öö Tiib wrote:
> > On Tuesday, 8 August 2023 at 22:38:43 UTC+3, Lynn McGuire wrote:
> >> "Inside STL: The lists" by Raymond Chen
> >> https://devblogs.microsoft.com/oldnewthing/20230804-00/
> >>
> >> "The C++ standard library type list represents a doubly-linked list, and
> >> forward_list is a singly-linked list. Fortunately, the implementations
> >> of both of these lists are pretty much what you expect."
> >>
> > Besides the controversial O(N) range splice of list and non-constant time
> > erase and insert of forward_list these are pretty much what you expect.
~ > In my opinion Raymon Chen is not trying to hide anything. He's just
> noting that /given/ the standard's specification, the implementations
> are just what you'd expect. I.e. nothing fancy.
>
Yes, I did not mean that Raymond Chen was trying to deceive, just that
with C++ some little bear trap should be anticipated everywhere.

> Various possible fancy mods have been discussed in this group.
>
> The most basic one, since lists require dynamic allocation of nodes, to
> use internal free lists as caches of nodes, to speed things up (O(1)
> allocation after a while, in general). A main reason why that's not done
> is probably that if you want speed, neither `std::list` nor
> `std::forward_list` should be the default choice. Instead, `std::vector`.
>
Yes, take vector if there are no solid reason not to take it. Reason like its
insert and erase being expensive or referential stability inexistent. List
does not have those issues. But more often I see (handrolled or boost)
intrusive variants than std::lists.