EASTL Modules

Introduction

We provide here a list of all top-level modules present or planned for future presence in EASTL. In some cases (e.g. algorithm), the module consists of many smaller submodules which are not described in detail here. In those cases you should consult the source code for those modules or consult the detailed documentation for those modules. This document is a high level overview and not a detailed document.

Module List

Module	Description
config	Configuration header. Allows for changing some compile-time options.
slist fixed_slist	Singly-linked list. fixed_slist is a version which is implemented via a fixed block of contiguous memory.
list fixed_list	Doubly-linked list.
intrusive_list intrusive_slist	List whereby the contained item provides the node implementation.
array	Wrapper for a C-style array which extends it to act like an STL container.
vector fixed_vector	Resizable array container.
vector_set vector_multiset	Set implemented via a vector instead of a tree. Speed and memory use is improved but resizing is slower.
vector_map vector_multimap	Map implemented via a vector instead of a tree. Speed and memory use is improved but resizing is slower.
deque	Double-ended queue, but also with random access. Acts like a vector but insertions and removals are efficient.
bit_vector	Implements a vector of bool, but the actual storage is done with one bit per bool. Not the same thing as a bitset.
bitset	Implements an efficient arbitrarily-sized bitfield. Note that this is not strictly the same thing as a vector of bool (bit_vector), as it is optimized to act like an arbitrary set of flags and not to be a generic container which can be iterated, inserted, removed, etc.
set multiset fixed_set fixed_multiset	A set is a sorted unique collection, multiset is sorted but non-unique collection.
map multimap fixed_map fixed_multimap	A map is a sorted associative collection implemented via a tree. It is also known as dictionary.
hash_map hash_multimap fixed_hash_map fixed_hash_multimap	Map implemented via a hash table.
intrusive_hash_map intrusive_hash_multimap intrusive_hash_set intrusive_hash_multiset	hash_map whereby the contained item provides the node implementation, much like intrusive_list.
hash_set hash_multiset fixed_hash_set fixed_hash_map	Set implemented via a hash table.
basic_string fixed_string fixed_substring	basic_string is a character string/array. fixed_substring is a string which is a reference to a range within another string or character array. cow_string is a string which implements copy-on-write.
algorithm	min/max, find, binary_search, random_shuffle, reverse, etc.
sort	Sorting functionality, including functionality not in STL. quick_sort, heap_sort, merge_sort, shell_sort, insertion_sort, etc.
numeric	Numeric algorithms: accumulate, inner_product, partial_sum, adjacent_difference, etc.
heap	Heap structure functionality: make_heap, push_heap, pop_heap, sort_heap, is_heap, remove_heap, etc.
stack	Adapts any container into a stack.
queue	Adapts any container into a queue.
priority_queue	Implements a conventional priority queue via a heap structure.
type_traits	Type information, useful for writing optimized and robust code. Also used for implementing optimized containers and algorithms.
utility	pair, make_pair, rel_ops, etc.
functional	Function objects.
iterator	Iteration for containers and algorithms.
smart_ptr	Smart pointers: shared_ptr, shared_array, weak_ptr, scoped_ptr, scoped_array, linked_ptr, linked_array, intrusive_ptr.

Module Behaviour

The overhead sizes listed here refer to an optimized release build; debug builds may add some additional overhead. Some of the overhead sizes may be off by a little bit (usually at most 4 bytes). This is because the values reported here are those that refer to when EASTL's container optimizations have been complete. These optimizations may not have been completed as you are reading this.

Container	Stores	Container Overhead (32 bit)	Container Overhead (64 bit)	Node Overhead (32 bit)	Node Overhead (64 bit)	Iterator category	size() efficiency	operator[] efficiency	Insert efficiency	Erase via Iterator efficiency	Find efficiency	Sort efficiency
slist	T	8	16	4	8	f	n	-	1	1	n	n+
list	T	12	24	8	16	b	n	-	1	1	n	n log(n)
intrusive_slist	T	4	8	4	8	f	n	-	1	1	n	n+
intrusive_list	T	8	16	8	16	b	n	-	1	1	n	n log(n)
array	T	0	0	0	0	r	1	1	-	-	n	n log(n)
vector	T	16	32	0	0	r	1	1	1 at end, else n	1 at end, else n	n	n log(n)
vector_set	T	16	32	0	0	r	1	1	1 at end, else n	1 at end, else n	log(n)	1
vector_multiset	T	16	32	0	0	r	1	1	1 at end, else n	1 at end, else n	log(n)	1
vector_map	Key, T	16	32	0	0	r	1	1	1 at end, else n	1 at end, else n	log(n)	1
vector_multimap	Key, T	16	32	0	0	r	1	1	1 at end, else n	1 at end, else n	log(n)	1
deque	T	44	84	0	0	r	1	1	1 at begin or end, else n / 2	1 at begin or end, else n / 2	n	n log(n)
bit_vector	bool	8	16	0	0	r	1	1	1 at end, else n	1 at end, else n	n	n log(n)
string (all types)	T	16	32	0	0	r	1	1	1 at end, else n	1 at end, else n	n	n log(n)
set	T	24	44	16	28	b	1	-	log(n)	log(n)	log(n)	1
multiset	T	24	44	16	28	b	1	-	log(n)	log(n)	log(n)	1
map	Key, T	24	44	16	28	b	1	log(n)	log(n)	log(n)	log(n)	1
multimap	Key, T	24	44	16	28	b	1	-	log(n)	log(n)	log(n)	1
hash_set	T	16	20	4	8	b	1	-	1	1	1	-
hash_multiset	T	16	20	4	8	b	1	-	1	1	1	-
hash_map	Key, T	16	20	4	8	b	1	-	1	1	1	-
hash_multimap	Key, T	16	20	4	8	b	1	-	1	1	1	-
intrusive_hash_set	T	16	20	4	8	b	1	-	1	1	1	-
intrusive_hash_multiset	T	16	20	4	8	b	1	-	1	1	1	-
intrusive_hash_map	T (Key == T)	16	20	4	8	b	1	-	1	1	1	-
intrusive_hash_multimap	T (Key == T)	16	20	4	8	b	1	-	1	1	1	-

- means that the operation does not exist.
1 means amortized constant time. Also known as O(1)
n means time proportional to the container size. Also known as O(n)
log(n) means time proportional to the natural logarithm of the container size. Also known as O(log(n))
n log(n) means time proportional to log(n) times the size of the container. Also known as O(n log(n))
n+ means that the time is at least n, and possibly higher.
Iterator meanings are: f = forward iterator; b = bidirectional iterator, r = random iterator.
Overhead indicates approximate per-element overhead memory required in bytes. Overhead doesn't include possible additional overhead that may be imposed by the memory heap used to allocate nodes. General heaps tend to have between 4 and 16 bytes of overhead per allocation, depending on the heap.
Some overhead values are dependent on the structure alignment characteristics in effect. The values reported here are those that would be in effect for a system that requires pointers to be aligned on boundaries of their size and allocations with a minimum of 4 bytes (thus one byte values get rounded up to 4).
Some overhead values are dependent on the size_type used by containers. size_type defaults to size_t, but it is possible to force it to be 4 bytes for 64 bit machines by defining EASTL_SIZE_T_32BIT.
Inserting at the end of a vector may cause the vector to be resized; resizing a vector is O(n). However, the amortized time complexity for vector insertions at the end is constant.
Sort assumes the usage of the best possible sort for a large container of random data. Some sort algorithms (e.g. quick_sort) require random access iterators and so the sorting of some containers requires a different sort algorithm. We do not include bucket or radix sorts, as they are always O(n).
Some containers (e.g. deque, hash*) have unusual data structures that make per-container and per-node overhead calculations not quite account for all memory.

End of document