AlgoMaster Sheet -The C++ Standard Template Library (STL)

What is C++ STL?

C++ is one of the most popular high-level programming language which is used extensively for a long time by developers and has always been loved by all programmers, especially competitive programmers because of its faster execution time.

From the programmer’s point of view, the STL provides a bunch of collection classes that meet various needs, together with several algorithms that operate on them. All components of the STL are templates, so they can be used for arbitrary element types. But the STL does even more: It provides a framework for supplying other collection classes or algorithms for which existing collection classes and algorithms work. All in all, the STL gives C++ a new level of abstraction. Forget programming dynamic arrays, linked lists, binary trees, or hash tables; forget programming different search algorithms. To use the appropriate kind of collection, you simply define the appropriate container and call the corresponding member functions and algorithms to process the data.

If you dive a little deeper into STL, you will have to understand everything about templates and how they work, which is one of the most power full tools when it comes to C++ programming language.

STL has 4 components:

Algorithms

Algorithms are the methods or functions that act on containers. By using algorithms provided by STL, we can have methods to search, sort, modify, transform or initialize the contents of container class objects.

STL supports the following types of algorithms:

Algorithms provided by STL have built-in functions that can directly operate on complex data structure instead of having to write the algorithms ourselves.

Container

Containers are used to manage collections of objects of a certain kind. Every kind of container has its own advantages and disadvantages, so having different container types reflects different
requirements for collections in programs. The containers may be implemented as arrays or as linked lists, or they may have a special key for every element.

• Sequence Containers: implement data structures that can be accessed in a sequential manner.
  • vector
  • list
  • deque
  • arrays
  • Forward_list( Introduced in C++11)

• Container Adaptors: provide a different interface for sequential containers.
  • queue
  • priority_queue
  • stack

• Associative Containers: implement sorted data structures that can be quickly searched (O(log n) complexity).
  • set
  • multiset
  • map
  • multimap
• Unordered Associative Containers: implement unordered data structures that can be quickly searched.
  • unordered_set (Introduced in C++11)
  • unordered_multiset (Introduced in C++11)
  • unordered_map (Introduced in C++11)
  • unordered_multimap (Introduced in C++11)

Iterators

Iterators are used to step through the elements of collections of objects. These collections may be containers or subsets of containers. The major advantage of iterators is that they offer a small but common interface for any arbitrary container type. For example, one operation of this interface lets the iterator step to the next element in the collection. This is done independently of the internal structure of the collection. Regardless of whether the collection is an array, a tree, or a hash table, it works. This is because every container class provides its own iterator type that
simply “does the right thing” because it knows the internal structure of its container.

Iterators are the very important and distinguishing feature of STL. Iterators are the constructs that are used to traverse through the container objects. Similar to indexes that we use to step through the arrays, Iterators act on container class objects and can be used to step through the data.

Functions

The STL includes classes that overload the function call operator. Instances of such classes are called function objects or functors. Functors allow the working of the associated function to be customized with the help of parameters to be passed.

Utility Library

• Defined in header <utility>
  • pair

To master C++ Standard Template Library (STL) in the most efficient and effective way, do check out this:

Video Tutorial:

This article is contributed by : Sayan Dutta to this article on csforall.in