[kentonv]

Agreed that std::list is never the best solution. In every case where I want linked list semantics, it's because I want to be able to dynamically add and remove objects from the list without any allocations at all. The only way to achieve that is an intrusive linked list design, which std::list is not...

[inetknght]

> I want to be able to dynamically add and remove objects from the list without any allocations at all. The only way to achieve that is an intrusive linked list design

No it isn't.

    std::array<std::optional<std::pair<T, std::pair<std::size_t /* prev index */, std::size_t /* next index */>>>, 256U /* or whatever your maximum size is \*/>.

Indexing does come with a wart: you'd need a sentry value for a "no prev" or "no next" value, I'd just use std::numeric_limits<size_t>::max() for that. And of course when you move objects within the container you'd need to update the indices.

If you don't know your upper size bound at compile time, then replace `array` with `vector`, and reserve your runtime-known upper bound. As long as you never violate your upper bound then no (re-)allocations occur (unless T's constructor allocates).

[kentonv]

In most (quite possibly all) cases I don't know the upper bound even at runtime. So, this ends up requiring allocation.

[inetknght]

You don't think it's useful to calculate some reasonable upper bound if only to avoid resource exhaustion?

[kentonv]

Not really:

* In my experience arbitrary limits intended to prevent "resource exhaustion" tend to lead to incidents where the limit was hit but resources weren't really exhausted, so it just caused failures for no reason. Very common example is the ulimit on open file descriptors. The default limits feel like they were set last century and haven't been updated to account for the fact that we have way more memory these days. We should really just be enforcing an overall limit on memory usage (per-user or per-cgroup) and expect that to include the file descriptor table.

* If I did choose a limit, it would be quite high (to avoid aforementioned unnecessary incidents), but in practice most of the lists I'm thinking of would never get near that size, so pre-allocating arrays would waste a lot of memory.

[inetknght]

So you don't know how much to allocate and you also don't want to allocate too much.

It sounds like you want something built on top of std::vector but with your own rules about when to reserve() and how much.

[kentonv]

No, for the use cases I'm thinking of, I really do just want an intrusive linked list. Why would I want to invent a convoluted way to adapt std::vector when an intrusive linked list does exactly what I want?

(Example use case: Some number of objects want to register themselves as observers on some event, and unregister themselves later, in arbitrary order. The same object may register and unregister itself many times. std::unordered_set<Observer*> would be the best fit if performance doesn't matter but an intrusive linked list requires no allocation at all on behalf of the list.)