Logicmojo - Updated Sept 18, 2021
Introduction
The Standard Template Library (STL's) are a collection of C++ template classes To provide popular programming data structures and methods like doubly linked lists (list), paired arrays (map), expandable arrays (vector), huge string storage and manipulation (rope), etc.,
The STL offers a mechanism to create generic, reusable code that can be used with many data types, which is one of its main advantages. This implies that you don't need to create unique pieces of code for each type of data you want to use an algorithm with.
The STL offers a mechanism to create effective code as well. Several algorithms and data structures in the STL use optimised algorithms to implement them, which can lead to quicker execution speeds than custom code.
STL is primarily made up of
1) Algorithms
2) Containers
3) Iterators
4) Functions
For example, you can very easily define a linked list in a single sentence by using the list container of the container library in STL, which will save you time and effort. STL also provides a wide variety of containers and algorithms that are particularly helpful in concurrent programming.
1.Algorithms
A group of functions that are specifically created to be used on a variety of items are defined by the header algorithm. They influence containers and give the contents of the containers the means for a variety of functions.
Types of Algorithms in STL Library:
• Searching Algorithms
• Sorting Algorithms
• Numeric Algorithms
• Modifying Algorithms
• Non Modifying Algorithms
i. Searching and Sorting Algorithms
A binary search is a common search method in STL. The binary search algorithm uses a sorted array and divides the array in half to look for an entry. This is accomplished by first comparing the element to be searched with the middle element of the array, then depending on whether it is less than or greater than the middle element, restricting the search to the first half or second half of the array. The most popular search algorithms are those that use binary search.
ii. Numeric Algorithms
The STL contains a number of functions that work with numeric values under the numeric header. These operations include finding lcds and gcds as well as computing the total of the items included in an array, a vector, etc., across a certain range, etc.
iii. Modifying Algorithms
When executed, modifying algorithms change or affect the contents of the containers. The most well-known and frequently applied modifying algorithms are "swap" and "reverse," which swap two values and, correspondingly, reverse the items in the container.
iv. Non Modifying Algorithms
Algorithms that do not transform or modify the contents of the container they are operating in are known as non-modifying algorithms. Several non-modifying algorithms are supported by STL.
2. Containers
A container is an item that serves as a holder for a group of other things (its elements). They are implemented as class templates, allowing for a wide range of supported element kinds. The container controls how its elements are stored and gives its members member functions to access them directly or through iterators (reference objects with similar properties to pointers).
There are generally 3 kinds of STL containers in c++:
• Sequential Containers
• Associative Containers
• Unordered Associative Containers
• Container Adapters in c++
i. Sequential Containers
We can store elements that can be accessed in consecutive order using sequential containers in C++. Internally, linked lists or arrays are used to implement sequential containers.
Sequential Container Types: Vector,Array,Deque, List, Forward List
Vector:A dynamic array or an array with certain extra properties are both definitions of vectors.
vector<int>v;
Array:A sequential homogenous container with a constant size is an array. The components are kept in close proximity to one another in memory.
array<object_type, size> array_name;
Deque: A double-ended queue that allows insertion and deletion from both ends is referred to as a deque and is more effective for insertion and deletion than vectors.
deque<int>d;
List: List, which supports non-contiguous allocation, is also a sequential container. Anything in the sequence can be used for insertion and deletion.
list<int>l;
Forward List:Starting with C++ 11, forward lists are added. In STL in C++, they are implemented as singly linked lists. Compared to lists, it consumes less memory and only supports one-way iteration.
forward_list<object_type> forward_list_name;
ii. Associative Containers
The ability to store elements in sorted order in C++ is provided via associative containers. The element's insertion time has no bearing on the order. They are implemented internally as binary tree data structures.
Associative Container Types: Set ,Map, Multiset,Multimap
Set: A set is an associative container used to store singular components.
set<int>s;
Multiset:The only distinction between this container and the set container is the storage of non-unique members.
multiset<int>m;
Map:Sets of key-value pairs with a single value for each key are contained in a map's container.
map<int,int>mm;
Multimap: Key-value pairs are also stored in multimaps, but unlike maps, multimaps allow for duplicate items.
map<int,int>mm1;
iii. Unordered Associative Containers
The unordered associative containers in C++ are provided by STL Unordered Associative Containers. Unordered associative containers are internal data structures known as hash tables.
Unordered Associative Containers Types:
Orderless Set
Orderless Map
Unordered Multimap
Unordered Multiset
Unordered Set:It is used to keep special components.
unordered_set<object_type> unordered_set_name;
Unordered Map:It is employed to keep separate key-value pairs.
unordered_map<key_object_type, value_object_type> unordered_map_name;
Unordered Multiset:Since the elements do not need to be unique, it is similar to an unordered set.
unordered_multiset<object_type> unordered_multiset_name;
Unordered Multimap:It is also similar to unordered map but the duplicate key-value pairs can be inserted here.
unordered_map<key_object_type, value_object_type> unordered_map_name;
iv. Container Adapters in c++
In C++, STL also consists of a unique class of containers that modify existing containers to provide an entirely new interface with constrained functionality. Hence, Container Adapters was born. The members of the container adaptor can access the elements of the underlying container regardless of the underlying container class being used because the underlying container is encapsulated. Values are initialised using other supported methods rather than directly, as is the case with other containers.
Stack:
A container that offers Last-In First-Out (LIFO) access is called a stack. The top of the stack is the same location where all operations take place. By default, it is implemented on top of a deque.
stack<data_type> stack_name;
Queue:
A container called a queue offers First-In, First-Out access. The front is where deletion occurs, while the back is where insertion takes place. By default, it is implemented on top of a deque.
queue<data_type> queue_name;
Priority Queue:
Similar to a queue, a priority queue also has a priority value assigned to each piece. In the case of STL in C++, this value determines which element is present at the top, which is by default the greatest element. The max heap data structure and this are comparable. By default, it is implemented on top of the vector.
priority_queue<object_type> priority_queue_name;
3. Iterators
The STL container's memory addresses are pointed to using iterators. In sequences of numbers, letters, etc., it is primarily utilised. The iterator operations begin(), end(), advance(), next(), and prev are the most used ones ().
Types of Iterators:
• Input Iterators
• Output Iterators
• Random-Access Iterators
• Forward Iterator
• Bidirectional Iterators
Common syntax for declaration of an iterator:
container_name<object_type>::iterator iterator_name;
The following member functions of a container return the two most popular iterators:
begin() — Returns an iterator to a container's initial element.
end() — Returns an iterator past a container's final element.
i. Input Iterators
Input iterators are said to be the most basic and weakest of all the iterators,Based on their capabilities and the results they can produce.These are the iterators that can be applied to sequential input processes, where each value the iterator points to is read-only once before the iterator is incremented.
ii. Output Iterators
Since output iterators serve the opposite purpose from input iterators, they are thought of as being the exact opposite of input iterators. In contrast to input iterators, which perform the opposite of accessing values and cannot be given values, they can be given values in a sequence but cannot be used to access values. Thus, input and output iterators are complementary to one another, according to this definition.
iii. Random Access Iterators
The same capability as pointers is provided by random-access iterators, which provide access to elements at any place relative to the element they point to. The most functionally complete iterators are random-access iterators. Any type of pointer is also a legitimate random-access iterator. It should be noted that random-access iterators are supported by containers like vector and deque. This means that if we declare regular iterators for them, they will be random-access iterators, just like list, map, multimap, set, and multiset are bidirectional iterators in the case of these objects.
iv. Forward Iterators
It is generally accepted that forward iterators combine input and output iterators. The functionality of both of them is supported by it. It allows values to be accessed as well as updated. The fact that random-access and bidirectional iterators are likewise acceptable forward iterators should not be overlooked.
v. Bidirectional Iterators
Iterators that allow access to the sequence of elements in a range in both directions are known as bidirectional iterators (towards the end and towards the beginning). They resemble forward iterators, except they can also go in the opposite direction, whereas forward iterators can only move in one direction. It should be noted that bidirectional iterators are supported by containers like list, map, multimap, set, and multiset. As a result, if normal iterators are declared for them, they will be bidirectional iterators, just like they are for vectors and deque, which both have random-access iterators.
4. Functions
Classes that overload the function call operator are included in the STL (). Functors or function objects are the names given to these classes' instances. Several C++ applications on the standard template library, sequence containers, container adaptors, associative containers, and unordered associative containers are included in the next section. A programme description, C++ code, and programme output are all included in each sample programme. Each example has been built and put through testing on Linux and Windows platforms.
// A C++ program uses transform() in STL to add // 1 to all elements of arr[] #include <bits/stdc++.h> using namespace std; int increment(int x) { return (x+1); } int main() { int arr[] = {1, 2, 3, 4, 5}; int n = sizeof(arr)/sizeof(arr[0]); // Apply increment to all elements of // arr[] and store the modified elements // back in arr[] transform(arr, arr+n, arr, increment); for (int i=0; i<n; i++) cout << arr[i] <<" "; return 0; }
Advantages Of Function Objects over Regular Function:
1.Both member functions and member attributes are possible for function objects.
2.Before being used, function objects can be initialised.
3.Only when the signature is different from a regular function can it have a different type. Even if a function object's signature is the same, it can yet have a distinct type.
4.The speed of function objects exceeds that of conventional functions.
Advantages of C++ Standard Template Library (STL)
1. Reusability: The STL offers a mechanism to create generic, reusable code that can be used with many data types, which is one of its main benefits. This may result in more effective and dependable coding.
2.Effective Algorithms:A lot of the STL's algorithms and data structures are implemented using efficient methods, which might lead to quicker execution rates than custom code.
3. Enhances Code Readability:A more consistent and well-documented method of interacting with data is provided by the STL, which can make your code simpler to comprehend and maintain.
4.Wide user base: Since the STL is extensively used, there is a sizable developer community that can offer assistance and resources, such as forums and tutorials.
Disadvantages of the C++ Standard Template Library (STL)
1.Learning curve: The STL's complex syntax and use of sophisticated features like iterators and function objects make it challenging to master, especially for novices.
2.Lack of control: Using the STL forces you to rely on the library's implementation, which can reduce your ability to influence some areas of your code.
3.Performance: When working with little amounts of data, employing the STL occasionally leads to longer execution speeds than writing custom code.
Applications and usage of STL
Because STL is a generic library, it offers containers and algorithms that may be used to store and handle a variety of data types, saving us the time and effort of having to create these data structures and algorithms from scratch. Thanks to STL, we can now use the generic container and algorithms in STL rather than having to declare our sort function each time we create a new application or twice for the various data types.
Because to the significant time, code, and effort savings, STL is widely employed in competitive programming. It is also dependable and quick.
Conclusion
You would have a thorough understanding of the Standard Template Library, generic programming, and all the STL in C++ components, such as containers, iterators, and algorithms, after reading this STL in C++ course. Together with certain examples, function objects were also covered.