Standard Library - itzjac/cpplearning GitHub Wiki
| Description | Implementation | Best case | Worst case | Insert | Remove | Look up | |||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| List | Fast insertion and deletion Sequencial access |
Abstraction for a doubly linked list | Good for storing an unpredictable number of items specially if it fluctuates Lots of inserts and deletes Many items unknown amount |
Store small data (a 32 bit integer for example will account for 96 bits in total) Can rapidly lead to bad memory fragmentation If you need constant time random access |
O(1) | O(1) | O(n) | ||||
| Vectors | Fastest iteration Random access |
The default allocator will just double the size of the internal buffer when current capacity is reached Compilers may use different strategies Efficient when pushing back Deleting and removing in the middle of the vector is very expensive Random access and low latency reads |
Consider it when you have a rough idea of the number of items Data can be either added all in one go Access the contents in any order |
Do frequent inserts/deletes anywhere other than the back of the vector Don't know how much data to put in it |
O() | O(1) | |||||
| Dequeu | Dynamic one dimentional array The size of the buffer may possibly be greater than the size of the data Similar to vector Add/Remove from head and tail |
Efficient when appending front or back | Growing the buffer is very costly No mechanism to reserve buffer Internal buffer memory may not shrink when the container is cleared Don't insert in the middle |
O(1) | |||||||
| Map | Sorted associative container that represents an abstraction of an ordered, unique key |
Typically implemented as a binary search tree | Sorted order Sorted inforced real time Filter out duplicates Store data appending to existing data access contents in any orde The need for compatibility with C style arrays Not good when doing frequent inserts or deletes anywhere than back or front |
Size of your data items is very small | O(1) | ||||||
| Multimap | |||||||||||
| Set | Associative container of an ordered unique key. The value is itself the key |
Implemented as a binary tree sparse hash set, dense hast set |
Sorted order Sorted inforced real time Filter out duplicates |
Can't use third party hash Nature of data means doesn't has well (many collisions) The size of your data is very small. Cannot afford to accet the fact that access is not in constant time You can get away with using a has set |
O(log N) | ||||||
| Multiset | |||||||||||
| Queue | |||||||||||
| Stack |