Standard Template library Tutorial for competitive programming part 1.

In this two part tutorial for standard template library I am going to tell you about C++ Standard Template Library.

C++ is the most preferred programming language for competitive programming.C++ is extremely fast and user friendly as compared to its Parent C.

To help the programmer in competions C++ has Standard Template Library(STL).STL has three components viz.Algorithms,containers and iterators.We will discuss them One by one.

1. Algorithms : - They are the step by step guide to solve certain problem.They Design the solution in way so that Programmers can impelements them with programming languages.Algortihms are first thought in Natural languages.Then Pseudocode and flow chart for the same is drawn.Pseudocode bridges the gap between programming language and natural language.Natural language is the most basic way of writing an algorithm.

Examples of algorithms:-Sorting algorithms like insertion sort, merge sort,etc.Searching algorihtms like Binary Search,linear search,etc.Shortest path finding algorithms like Djikstra,krustkat,Bellman ford,etc.

2. Iterators:- Iterators are used to point at the memory addresses of STL containers. They are primarily used in sequence of numbers, characters etc. They reduce the complexity and execution time of program.

Operations of iterators :-

1. begin() :- This function is used to return the beginning position of the container.

2. end() :- This function is used to return the after end position of the container.

3. advance() :- This function is used to increment the iterator position till the specified number mentioned in its arguments.

4. next() :- This function returns the new iterator that the iterator would point after advancing the positions mentioned in its arguments.

5. prev() :- This function returns the new iterator that the iterator would point after decrementing the positions mentioned in its arguments.

6. inserter() :- This function is used to insert the elements at any position in the container. It accepts 2 arguments, the container and iterator to position where the elements have to be inserted.

For Code visit: https://ide.codingblocks.com/s/191592

3. Container: there are four Different types of containers.They are as follows.

STL Containers

A) Sequence containers

B) Associative containers

C) Unordered associative containers

D) Container adaptors

A) Sequence Containers: Sequence containers implement data structures which can be accessed sequentially.Examples of Sequential containers are

• Vector: Dynamic contiguous array
• Deque: Double-ended queue
• Forward List : Singly-linked list
• List : Doubly-linked list

B) Associative Containers:Associative containers implement sorted data structures that can be quickly searched (O(log n) complexity).Examples of associative contaners are

• Set : Collection of unique keys, sorted by keys.
• Map : Collection of key-value pairs, sorted by keys, keys are unique.
• Multiset : Collection of keys, sorted by keys .
• Multimap : Collection of key-value pairs, sorted by key.

C) Unordered Associative Containers : Unordered associative containers implement unsorted (hashed) data structures that can be quickly searched (O(1) amortized, O(n) worst-case complexity).Examples of unordered associative contaners are

• unordered Set : Collection of unique keys, hashed by keys.
• Unordered Map:Collection of key-value pairs, hashed by keys, keys are unique.
• Unordered_Multiset : Collection of keys, hashed by keys.
• Unordered Multimap : Collection of key-value pairs, hashed by keys.

D) Container Adaptor or Derived Contaner: Container adaptors provide a different interface for sequential containers.

• Stack : Adapts a container to provide stack (LIFO data structure).
• queue : Adapts a container to provide queue (FIFO data structure).
• priority_queue : Adapts a container to provide priority queue.

Lets discuss Sequential Containers

1. Vectors : They are dynamic or resizable array.Vectors double themselves once the size is complete.

Functions in vectors:

1. begin() — Returns an iterator pointing to the first element in the vector
2. end() — Returns an iterator pointing to the theoretical element that follows the last element in the vector
3. rbegin() — Returns a reverse iterator pointing to the last element in the vector (reverse beginning). It moves from last to first element
4. rend() — Returns a reverse iterator pointing to the theoretical element preceding the first element in the vector (considered as reverse end)
5. size() — Returns the number of elements in the vector.
6. max_size() — Returns the maximum number of elements that the vector can hold.
7. capacity() — Returns the size of the storage space currently allocated to the vector expressed as number of elements.
8. resize() — Resizes the container so that it contains ’n’ elements.
9. empty() — Returns whether the container is empty.
10. reserve() — Requests that the vector capacity be at least enough to contain n elements.

For Code snippet visit : https://ide.codingblocks.com/s/191602

2. Deque : Double ended queues are sequence containers with the feature of expansion and contraction on both the ends.
They are similar to vectors, but are more efficient in case of insertion and deletion of elements.
Double Ended Queues are basically an implementation of the data structure double ended queue. A queue data structure allows insertion only at the end and deletion from the front. This is like a queue in real life, wherein people are removed from the front and added at the back. Double ended queues are a special case of queues where insertion and deletion operations are possible at both the ends.

The functions for deque are same as vector with an addition of push and pop operations for both front and back.

1. push_back() : appends an elements at the back.
2. push_front() : add an elements in the front.
3. size(): returns the current size of a deque.
4. max_size() : returns the maximum size of a deque.
5. pop_front() : Remove element from the front.
6. pop_back() : Remove element from the back.

for Code visit : https://ide.codingblocks.com/s/191611

3. list : list is another sequential container which is similar to vector.Insertion and deletion takes o(N) time in vectors but in list we can do insertion and deletion in o(1) time.list is nothing but a doubly linked list.operations in list are

1. push_back() : append elements in the back.
2. push_front() : add element in the front.
3. sort(): sort the list in lexicographical order.
4. reverse(): returns reversed list as output.
5. pop_back(): deletes elements from back.
6. pop_front(): deletes elements from front.
7. empty(): checks whether list is empty or not.
8. clear() : erase all the elements from the list

for code visit: https://ide.codingblocks.com/s/191618

That’s it For now.Remaining containers will be discussed in next part.

ps:Source C++ primer plus,Geeks for Geeks,Topcoder tutorials.

Thank You!

Dungeon_Master🙏