A container is a
holder object that stores a collection of other objects (its elements). They
are implemented as class templates, which allows a great flexibility in the
types supported as elements.
Container class templates
Sequence containers: (Elements in sequence
containers are ordered in a strict linear sequence. Individual elements are
accessed by their position in this sequence.)
- array - Array class vector
- Vector
- Deque -Double ended queue
- forward_list
- List
Container adaptors:
- Stack - LIFO stack
- Queue -FIFO queue
- priority_queue -Priority queue
Associative containers: (Elements in
associative containers are referenced by their key and not by their absolute
position in the container.)
- set
- Multiset-Multiple-key set
- map
- Multimap-Multiple-key map
Unordered associative containers:
- unordered_set
- unordered_multiset
- unordered_map
- unordered_multimap
Array
- Arrays are fixed-size sequence containers: they hold a specific number of elements ordered in a strict linear sequence.
- The elements are stored in contiguous memory locations, allowing constant time random access to elements.
- The container uses implicit constructors and destructors to allocate the required space statically. Its size is compile-time constant.
Complexity :
- Almost all the operations are O(1)
- Remove/Insert operations that handles element between elements require O(n),because the elements need to be shifted.
Note!
Hence, an array as a data structure is used where remove/insert operations are
not required.
Vector
- Vectors are sequence containers representing arrays that can change in size.
- Vectors use contiguous storage locations for their elements.
- vectors use an array as their underlying storage
- size can change dynamically, with their storage being handled automatically by the container.
- If a reallocation happens, all iterators, pointers and references related to the container are invalidated,
- vector containers may allocate some extra storage to accommodate for possible growth.
vectors
consume more memory than arrays in exchange for the ability to manage storage
and grow dynamically in an efficient way.
Complexity :
- Accessors : [], at, size,empty, begin,end,front,back,capacity - Constant time
- Modifiers : pushback (ammortized),popback - constant time
insert,assign,erase
- Linear
Deque
- sequence containers with dynamic sizes that can be expanded or contracted on both ends
- provide a functionality similar to vectors, but with efficient insertion and deletion of elements also at the beginning of the sequence, and not only at its end.
- Generally implemented as a dynamic array. (Vector of vectors)
- unlike vectors, deques are not guaranteed to store all its elements in contiguous storage locations
- vectors use a single array that needs to be occasionally reallocated for growth, the elements of a deque can be scattered in different chunks of storage, with the container keeping the necessary information internally to provide direct access to any of its elements in constant time and with a uniform sequential interface (through iterators).
Complexity :
- Accessors : [], at, size,empty, begin,end,front,back - Constant time
- Modifiers : pushback (ammortized),pushpopback - constant time
insert,assign,erase
- Linear
List
- Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.
- List containers are implemented as doubly-linked lists;
- contain in different and unrelated storage locations.
- Each element keeps information on how to locate the next and the previous elements, allowing constant time insert and erase operations before or after a specific element (even of entire ranges), but no direct random access.
- Lists perform generally better in inserting, extracting and moving elements in any position within the container for which an iterator has already been obtained, and therefore also in algorithms that make intensive use of these, like sorting algorithms.
- they lack direct access to the elements by their position
- They also consume some extra memory to keep the linking information associated to each element
Complexity :
- Accessors : begin,end, empty, front,back - Constant time
Size
-Linear
- Modifiers :popfront, pushfront, popback, pushback - constant time
insert,
erase - Linear
-------------------------------------------------------------------------------------------------------------
Stack
- Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.
- The container shall support the following operations:
- empty
- size
- back
- push_back
- pop_back
- The standard container classes vector, deque and list fulfill these requirements. By default, if no container class is specified for a particular stack class instantiation, the standard container deque is used.
Complexity : Operations on the underline
container class will be called and complexity depend on them. (Constant)
Queue:
- queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.
- This underlying container shall support at least the following operations:
- empty
- size
- front
- back
- push_back
- pop_front
- The standard container classes deque and list fulfill these requirements. By default, if no container class is specified for a particular queue class instantiation, the standard container deque is used.
Complexity : Operations on the underline
container class will be called and complexity depend on them. (Constant)
Priority Queue
- Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion.
- Elements are popped from the "back" of the specific container, which is known as the top of the priority queue.
- The underline container shall be accessible through random access iterators and support the following operations:
- empty()
- size()
- front()
- push_back()
- pop_back()
- The standard container classes vector and deque fulfill these requirements. By default, if no container class is specified for a particular priority_queue class instantiation, the standard container vector is used.
Complexity : top, size, empty - Operations on
the underline container class will be called and complexity depend on them.
(Constant)
push, pop - log n
----------------------------------------------------------------------------------------------------------------------
Set / MultiSet
- Unique keys - No two elements in the container can have equivalent keys. (only in set)
- Ordered - The elements in the container follow a strict order at all times.
- Associative - Elements in associative containers are referenced by their key and not by their absolute position in the container.
- Sets are typically implemented as binary search trees.(balanced binary search trees, typically red-black trees) Thus, they provide logarithmic storage and retrieval times.
- MultiSet -multiple elements can have equivalent values.
Complexity : size, empty, begin, end - Constant
insert,
erase - log n
clear
- Linear
Map:
- Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order.
- key values - sort and uniquely identify the elements
- mapped values - store the content associated to this key.
- implemented as binary search trees.
Complexity : size, empty, begin, end - Constant
[],
at, insert, delete,find,upper bound ,lower bound - log n
Clear
- linear
References
No comments:
Post a Comment