3 ms·
You have a magic allocator for your list nodes that does better than O(1) amortized?
by marshray 14y ago
You have a magic allocator for your list nodes that does better than O(1) amortized?
- spinlocked 14y agoDo you need magic to create an O(1) allocator for a pool of fixed size objects?
- marshray 14y agoYes, when (as in the general case of std::list) the number of objects is not known in advance.
- deleted 14y ago[deleted]
- deleted 14y ago[deleted]
- spinlocked 14y agotrue. however, libstdc++ implements __pool_alloc for a reason.
- shrughes 14y agoBeing 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.