Link to playlist : https://youtu.be/PCahjLFtlbY
Do study about the below mentioned STL data structures and inbuilt function
Some of the important STL containers are :-- Vectors :-
Vectors are sequence containers representing arrays that can change in size. Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.
vector < type > variable_name;
- Maps :-
Maps are associative containers that store elements formed by a combination of a key value and a mapped value. In a map, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key. The types of key and mapped value may differ. Map containers are generally slower than unordered_map containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.
map < type_1, typr_2 > variable_name;
- Set :-
Sets are containers that store unique elements following a specific order. In a set, the value of an element also identifies it (the value is itself the key, of type T), and each value must be unique. The value of the elements in a set cannot be modified once in the container (the elements are always const), but they can be inserted or removed from the container.
set < type > variable_name;
- 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; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept internally by the association to each element of a link to the element preceding it and a link to the element following it. They are very similar to forward_list: The main difference being that forward_list objects are single-linked lists, and thus they can only be iterated forwards, in exchange for being somewhat smaller and more efficient. The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position
list < type > variable_name;
- 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.
stack < type > variable_name;
- 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.
queue < type > variable_name;
- Deque :-
Deque (usually pronounced like "deck") is an irregular acronym of double-ended queue. Double-ended queues are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either its front or its back). They 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. But, unlike vectors, deques are not guaranteed to store all its elements in contiguous storage locations: accessing elements in a deque by offsetting a pointer to another element causes undefined behavior.
deque < type > variable_name;
- 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. This context is similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue). If you want min_priority_queue you can either use priority_queue <int, vi, greater >, or in numerical case pass the negative of all numbers as greater number negative is samller and samller's negative is greater so it will always give smaller elements first.
priority_queue < type > variable_name; //for max_heap priority_queue <type, vector < type >, greater< type > > variable_name; // for min_heap
- Bitset :-
A bitset stores bits (elements with only two possible values: 0 or 1, true or false, ...). The class emulates an array of bool elements, but optimized for space allocation: generally, each element occupies only one bit (which, on most systems, is eight times less than the smallest elemental type: char). Bitsets have the feature of being able to be constructed from and converted to both integer values and binary strings (see its constructor and members to_ulong and to_string). They can also be directly inserted and extracted from streams in binary format. The size of a bitset is fixed at compile-time.
bitset < size > variable_name;
- Pairs :-
This class couples together a pair of values, which may be of different types (T1 and T2). The individual values can be accessed through its public members first and second. Pairs are a particular case of tuple.
pair < type_1, type_2 > variable_name;
- Tuple :-
A tuple is an object capable to hold a collection of elements. Each element can be of a different type.
tuple < type_1, type2, type_3, ....., type_n > varibale_name;
-
find() :- Searches the container for an element equivalent to val and returns an iterator to it if found, otherwise it returns an iterator to container::end. O(logn) for set, map.
-
count() :- Searches the container for elements equivalent to val and returns the number of matches. O(log n) complexity in map, set.
-
erase() :- Removes from the container either a single element or a range of elements. O(1) for erase(pos), O(log n) for erase(val) and linear for range.
-
insert() :- Extends the container by inserting new elements, effectively increasing the container size by the number of elements inserted. O(log n) for set, map.
-
begin() :- Returns an iterator referring to the first element in the container. O(1).
-
end() :- Returns an iterator referring to the past-the-end element in the set container. O(1).
-
rbegin() :- Returns a reverse iterator pointing to the last element in the container (i.e., its reverse beginning). Reverse iterators iterate backwards: increasing them moves them towards the beginning of the container. O(1).
-
rend() :- Returns a reverse iterator pointing to the theoretical element right before the first element in the container (which is considered its reverse end). O(1).
-
push() :- Inserts a new element at the top of the stack,front of queue, priority_queue. The content of this new element is initialized to a copy of val. O(1).
-
push_back() :- Adds a new element at the end of the container, after its current last element. The content of val is copied (or moved) to the new element. O(1).
-
push_front():- Inserts a new element at the beginning of the deque container, right before its current first element. The content of val is copied (or moved) to the inserted element. O(1).
-
pop() :- Removes the element on top of the stack,queue, peiority_queue effectively reducing its size by one. O(1).
-
pop_back() :- Removes the last element in the deque container, effectively reducing the container size by one. O(1).
-
pop_front() :- Removes the first element in the deque container, effectively reducing its size by one. O(1).
-
top() :- Returns a reference to the top element in the stack, max element in priority_queue. O(1).
-
front() :- Returns a reference to the first element in the container. O(1).
-
back() :- Returns a reference to the last element in the container. O(1).
-
sort() :- Sorts the elements in the range [first,last) into ascending order. O(n log n).
-
reverse() :- Reverses the order of the elements in the range [first,last). O(linear).
-
stoi() :- Parses str interpreting its content as an integral number of the specified base, which is returned as an int value. O(linear).
-
to_string() :- Returns a string with the representation of val. O(linear).
-
__gcd() :- Calculate gcd of two numbers. O(log n).
-
clear() :- Removes all elements from the set container (which are destroyed), leaving the container with a size of 0. - O(n).
-
empty() :- Returns whether the container is empty (i.e. whether its size is 0). O(1).
-
equal_range() :- Returns the bounds of a range that includes all the elements in the container that are equivalent to val. O(log n) in set, map.
-
lower_bound() :- Returns an iterator pointing to the first element in the container which is not considered to go before val (i.e., either it is equivalent or goes after). O(log n)
-
upper_bound() :- Returns an iterator pointing to the first element in the container which is considered to go after val. O(log n).
-
size() :- Returns the number of elements in the set container. O(1).
-
swap() :- Swaps the two arguments. O(1) .