A fast way to store a variable-sized collection of pointers. More...
#include <pointer_list.h>
Classes | |
| class | allocator |
Allocator for pointer_list, specialized for NELT. More... | |
| class | iterator |
| Forward iterator over the list. More... | |
Public Types | |
|
typedef pointer_list_base::value_type | value_type |
| Stored value type. | |
| typedef allocator | pool_type |
| Alias for allocator. | |
Public Member Functions | |
| pointer_list (pool_type &pool) | |
Constructor. pool gives the allocator for this container. | |
| iterator | begin () |
| Iterator at the beginning of the container. | |
| iterator | end () |
| Iterator at the end of the container. | |
| void | erase (iterator it) |
| Erase one element. O(n). | |
A fast way to store a variable-sized collection of pointers.
If you're growing a variable-sized collection of things, all the STL containers have some performance issues. A std::vector needs to reallocate and copy its data as it grows. The use of variable-sized allocations also means that one cannot use the very efficient fixed-size memory allocators. A std::list incurs a separate memory allocation for each element, and, if the elements are pointers, has a substantial size overhead.
The class here is a compromise, which builds a list consisting of fixed-size chunks.
The operations supported are rather limited. We support forward iteration, push_back, and erase (though the latter can have O(n) complexity).
For best performance, we use our own allocator, an instance of which gets passed to the pointer_list constructor. Memory is not freed until the allocator is destroyed.
This class is templated on the number of elements stored per block. This must be one less than a power of two.
| CxxUtils::pointer_list< NELT >::pointer_list | ( | pool_type & | pool | ) | [inline] |
| void CxxUtils::pointer_list< NELT >::erase | ( | iterator | it | ) | [inline] |
Erase one element. O(n).
| it | The element to erase. |
1.6.1
