More about STL in C++ and where should we use it?

Templates is an important and most useful feature of C++, where STL(Standard Template Library) is a powerful set of C++ template classes that provide general-purpose classes and functions with templates to operate with generic types. STL is mainly composed of algorithms, containers, iterators. This library provides numerous containers and algorithms which make it easy to program in C++. Let’s find out what are algorithms, containers, iterators in STL.

Algorithms

Algorithm defines as a collection of functions specially designed to be used on ranges of elements.They act on containers and provide means by which you will perform various operations like initialization, sorting, searching, and transforming for the contents of containers.

Types of Algorithms

• Sorting Algorithms

• Search algorithms

• Non modifying algorithms

• Modifying algorithms

• Numeric algorithms

• Minimum and Maximum operations.

Containers

Containers or container classes store objects and data. Containers help us to implement and replicate simple and complex data structures very easily like arrays, lists, trees, associative arrays and many more. There are several different types of containers. These are -

Sequence based Containers - Implement data structures which can be accessed in a sequential manner.

• Vector - Vectors are same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container. Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators. In vectors, data is inserted at the end.

• List - Lists allow non-contiguous memory allocation. List has slower traversal than vector, but once a position has been found, insertion and deletion are quick.

• Deque - Deque is a shorthand for doubly ended queue. Deque allows fast insertion and deletion at both ends of the queue. They are similar to vectors, but are more efficient in case of insertion and deletion of elements at the end, and also at the beginning.

• Arrays - Arrays are collection of homogeneous objects. Array container in STL provides us the implementation of static array, though it is rarely used in competitive programming as its static in nature. Array classes know its own size. So when passing to functions, we don’t need to pass size of Array as a separate parameter.

• Forward_list - Forward list of STL implements singly linked list. Introduced from C++11, forward list are useful than other containers in insertion, removal and moving operations (like sort) and allows time constant insertion and removal of elements.

Container Adaptors - provide a different interface for sequential containers.

• Queue - The queue container is used to replicate queue in C++, insertion always takes place at the back of the queue and deletion is always performed at the front of the queue.

• Priority_queue - priority_queue is just like a normal queue except the element removed from the queue is always the greatest among all the elements in the queue, thus this container is usually used to replicate Max Heap in C++. Elements can be inserted at any order and it has O(log(n)) time complexity for insertion.

• Stack - Stacks are a type of container adaptors with LIFO(Last In First Out) type of work, where a new element is added at one end and (top) an element is removed from that end only.

Associative Containers - Implement sorted data structures that can be quickly searched (O(log n) complexity).

• Set - Sets are containers which store only unique values and permit easy lookups. The values in the sets are stored in some specific order (like ascending or descending). Elements can only be inserted or deleted, but cannot be modified. We can access and traverse set elements using iterators just like vectors.

• Multiset - same as a set, but allows duplicate elements, an exception that multiple elements can have same values.

• Map - Maps are used to replicate associative arrays. Maps contain sorted key-value pair, in which each key is unique and cannot be changed, and it can be inserted or deleted but cannot be altered. Value associated with keys can be altered. We can search, remove and insert in a map within O(n) time complexity.

• Multimap - same as a map, but allows duplicate keys. Each element is unique, the key value and mapped value pair have to be unique in this case.

Iterators

Iterators are used to step through the elements of collections of objects. These collections may be containers or subsets of containers. Iterators are used for working upon a sequence of values.

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 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.

Applications of STL

STL in Mini Max

STL in Heapsort

STL in Binary Search

STL in Merge

STL in Sort

 

Hope you like this article. Please write comments if you find anything new or you want to share more information about this topic discussed above. Thank you!