Module 4 : STL Containers

C ++ Standard Template Library Container

Container is an object that is used to store a collection of other objects (called elements in the container) and manage their storage space. In C ++, container is implemented as a template class, so that there are functions to access its elements.

std::array

Example of complete implementation of std::array

Do you still remember Array? std::array is a type of data structure that holds elements sequentially with a fixed size (fixed-size). Operations on std::array:

• operator [] - Accesses the element at a specific position.
• at() - Accesses the element at a specific position while checking the array size limit. Returns the same value as operator []''. The difference is when the index of the element to be accessed exceeds the array size limit. On `at (),` the program will throw an `out_of_range` error when running. On the operator []``, this causes an undefined behavior.
• front() - Accesses the first position element.
• back() - Accesses the element in the last position.
• begin() - An iterator for the start of the sequence.
• end() - An iterator for the element after the end of the sequence.
• size() - Get the number of elements.
• max_size() - Get the maximum number of elements the array can hold. Returns the same value as size ().
• empty() - Checks whether the array is empty or not. If array size is 0, returns true. Otherwise, returns the value false.
• swap() - Swaps all elements in an array with all elements in another array that have the same data type and size.
• fill() - Fills all the elements in the array with a specific value.

std::vector

Example of complete implementation of std::vector

Do you still remember Dynamic Array? std::vector is a type of data structure that represents an array with the ability to change size (capacity) dynamically according to the amount of data entered. Operations on std::vector:

• operator[] - Accesses the element at a specific position.
• at() - Accesses element in specific position while checking vector size limit. Returns the same value as the operator []. The difference is when the index of the element to be accessed exceeds the vector size limit. On at (), the program will throw an out_of_range error when running. On the operator[], this causes an undefined behavior.
• front() - Accesses the first position element.
• back() - Accesses the element in the last position.
• begin() - An iterator for the start of the sequence.
• end() - An iterator for the element after the end of the sequence.
• size() - Get the number of elements.
• max_size() - Get the maximum number of elements the vector can hold.
• resize() - Resizes a vector to a specified number of elements. resize () can also be accompanied by specifying a specific value, but it will not change an element that has a previous value (as opposed to assign ()).
• empty() - Checks whether the vector is empty or not. If the vector size is 0, returns true. Otherwise, returns the value false.
• assign() - Set the vector size to be a certain number of elements with a certain value on all elements.
• push_back() - Adds the element at the last position.
• pop_back() - Deletes the last element.
• insert() - Inserts a value at a specific position (or range).
• erase() - Deletes the value at a specific position (or range).
• clear() - Removes all elements, so the vector size is 0.
• swap() - Swaps all elements in a vector with all elements in another vector that have the same data type (size can be different).
• sort(first, last) - Sorts the elements in the array by descending in the range (first, last).
• lower_bound(first, last, val) - Returns an iterator that points to the smallest element not less than $ val $ in the range (first, last). If it doesn't exist, it returns the last iterator.
• upper_bound(first, last, val) - Returns an iterator that points to the smallest element that is more than $ val $ in the range (first, last). If it doesn't exist, it returns the last iterator.

std::list

Example of complete implementation of std::list

Do you still remember Linked List? std::list is a type of data structure that holds elements sequentially and is capable of performing insert ()and erase ()operations constant time. Operations on std::list:

• front () - Accesses the first position element.
• back () - Accesses the element in the last position.
• begin () - An iterator for the start of the sequence.
• end () - An iterator for the element after the end of the sequence.
• size () - Get the number of elements.
• max_size () - Get the maximum number of elements the list can hold.
• resize () - Resizes the list to a specified number of elements. resize () can also be accompanied by specifying a specific value, but it will not change an element that has a previous value (as opposed to assign ()).
• empty () - Checks whether the list is empty or not. If list size is 0, returns true. Otherwise, returns the value false.
• assign () - Set the size of the list to be the number of certain elements with a certain value on all elements.
• push_front () - Adds the element in the first position.
• pop_front () - Removes the element in the first position.
• push_back () - Adds the element at the last position.
• pop_back () - Removes the element in the last position.
• insert () - Inserts a value at a specific position (or range).
• erase () - Deletes the value at a specific position (or range).
• clear () - Deletes all elements, bringing the list size to 0.
• swap () - Swaps all elements in a list with all elements in another list that have the same data type (size can be different).
• reverse () - Reverses the order in which the elements are positioned.
• sort () - Sorts all elements in ** ascending ** (** default **, can be changed).
• merge () - Moves all elements in a list to another list, provided that both lists are ordered, so that all elements in the destination list are ordered.
• splice () - Move all elements or certain elements at a specific position in that list or another list.
• unique () - Removes duplicate elements from a list, leaving a list of unique elements.
• remove () - Removes an element with a specified value. Unlike erase () which removes based on the position of the element, remove () removes the element based on its value.
• remove_if () - Removes elements with a specific value that meet certain conditions.

std::stack

Example of complete implementation of std::stack

Do you still remember Stack? std::stack is a type of dynamic data structure that follows the principle of Last In First Out (LIFO). Operations on std::stack:

• top () - Accesses the first position element.
• size () - Get the number of elements.
• empty () - Checks whether the stack is empty or not. If the stack size is 0, returns true. Otherwise, returns the value false.
• push () - Adds the element in the first position.
• pop () - Removes the element in the first position.
• swap () - Swaps all elements on a stack with all elements on another stack that have the same data type (size can be different).

std::queue

Example of complete implementation of std::queue

Do you still remember Queue? std::queue is a type of dynamic data structure that follows the First In First Out (FIFO) principle. Operations on std::queue:

• front () - Accesses the first position element.
• back () - Accesses the element in the last position.
• size () - Get the number of elements.
• empty () - Checks whether the queue is empty or not. If queue size is 0, returns true. Otherwise, returns the value false.
• push () - Adds the element in the first position.
• pop () - Removes the element in the last position.
• swap () - Swaps all elements in a queue with all elements in another queue that have the same data type (size can be different).

std::deque

Example of complete implementation of std::deque

Do you still remember [Deque] (https://github.com/AlproITS/StrukturData/wiki/Modul-1-(Deque))? std::deque (double-ended queue) is a type of dynamic data structure that can add data or subtract data in both the start and end positions. Operations on std::deque:

• operator [] - Accesses the element at a specific position.
• at () - Access the element at a specific position while checking the deque size limit. Returns the same value as the operator []. The difference is when the index of the element to be accessed exceeds the deque size limit. On at (), the program will throw an out_of_range error when running. On the operator [], this causes an undefined behavior.
• front () - Accesses the first position element.
• back () - Accesses the element in the last position.
• begin () - An iterator for the start of the sequence.
• end () - An iterator for the element after the end of the sequence.
• size () - Get the number of elements.
• max_size () - Get the maximum number of elements that can be accommodated by deque.
• resize () - Resizes the deque to a specified number of elements. resize () can also be accompanied by specifying a specific value, but it will not change an element that has a previous value (as opposed to assign ()).
• empty () - Checks whether the deque is empty or not. If deque size is 0, returns true. Otherwise, returns the value false.
• assign () - Set the deque size to be the number of certain elements with a certain value on all elements.
• push_front () - Adds the element in the first position.
• pop_front () - Removes the element in the first position.
• push_back () - Adds the element at the last position.
• pop_back () - Removes the element in the last position.
• insert () - Inserts a value at a specific position (or range).
• erase () - Deletes the value at a specific position (or range).
• clear () - Erases all elements, bringing the deque size to 0.
• swap () - Swaps all elements in a deque with all elements in another deque that have the same data type (sizes can be different).

std::priority_queue

Example of complete implementation of std::priority_queue

Do you still remember Priority Queue? std::priority_queue is a type of dynamic data structure that can automatically accommodate elements in an ordered order descending (default, can be changed). Operations on std::priority_queue:

• top () - Accesses the first position element.
• size () - Get the number of elements.
• empty () - Checks whether the priority queue is empty or not. If the priority queue size is 0, returns true. Otherwise, returns the value false.
• push () - Adds the element in the first position.
• pop () - Removes the element in the last position.
• swap () - Swaps all elements in a priority queue with all elements in another priority queue that have the same data type (size can be different) .cpp)

std::map

Example of complete implementation of std::map

std::map is an associative container that holds elements in the form key - value. Operations on std::map:

• operator [] - Accesses the value of a key.
• begin () - An iterator for the start of the sequence.
• end () - An iterator for the element after the end of the sequence.
• size () - Get the number of elements.
• max_size () - Get the maximum number of elements the map can hold.
• empty () - Checks whether the map is empty or not. If map size is 0, returns true. Otherwise, returns the value false.
• insert () - Inserts a value at a specific position (or range).
• erase () - Deletes the value at a specific position (or range).
• clear () - Deletes all elements, bringing the map size to 0.
• swap () - Swap all elements on a map with all elements in another map that have the same data type (size can be different).
• find () - Finds elements by ** key **.
• count () - Finds the number of elements with the same value.

std::set

Example of complete implementation of std::set

std::set is an associative container that holds elements in the form key - value, where the value is the key, so that each element is a unique element. Operations on std::set:

• begin () - An iterator for the start of the sequence.
• end () - An iterator for the element after the end of the sequence.
• size () - Get the number of elements.
• max_size () - Get the maximum number of elements the set can hold.
• empty () - Checks whether the set is empty or not. If set size is 0, returns true. Otherwise, returns the value false.
• insert () - Inserts a value at a specific position (or range).
• erase () - Deletes the value at a specific position (or range).
• clear () - Deletes all elements, so the size is set to 0.
• swap () - Swaps all elements in a set with all elements in another set that have the same data type (size can be different).
• find () - Finds elements by key.
• count () - Finds the number of elements with the same value. Since each element in the set is a unique element, if the element is found it will return the value 1, while if not found it will return the value 0.
• lower_bound (val) - returns an iterator pointing to the smallest value key not less than $val$. If it doesn't exist, it returns the end () iterator.
• upper_bound (val) - returns an iterator pointing to the smallest value greater than $val$. If it doesn't exist, it returns the end () iterator.

Policy-Based Data Structure (PBDS)

Example of full PBDS implementation

More or less, this data structure functions the same as std::set but has additional functions, namely:

• find_by_order (k) - Returns a number in the order K if ordered in ascending.
• order_of_key (val) - Returns the number of numbers that have a value less than $val$.

The implementation of map, set, priority_queue, and PBDS uses the balanced binary search tree or heap data structure which causes accessing the elements in the STL to take logarithmic time to the number of elements $ O(lg N)$. Whereas other STLs described in this module take constant time to access their elements $O (1)$.

For more detailed information about STL, please read: cplusplus.com Especially for PBDS can be seen at: https://codeforces.com/blog/entry/11080