undefined | Better HN

0 pointsmarshray13y ago0 comments

You have a magic allocator for your list nodes that does better than O(1) amortized?

0 comments

4 comments · 2 top-level

spinlocked13y ago· 2 in thread

Do you need magic to create an O(1) allocator for a pool of fixed size objects?

marshrayOP13y ago

Yes, when (as in the general case of std::list) the number of objects is not known in advance.

true. however, libstdc++ implements __pool_alloc for a reason.

Being better than O(n) worst case is the target here, not O(1) amortized. For example, O(1) amortized and O(log n) worst case is a thing.

j / k navigate · click thread line to collapse