C++ Standard Template Library (STL) – Introduction

In this tutorial you will learn about what is STL in C++, what it provides and overview of all STL items.

STL means Standard Template Library. STL is the most crafted libraries among all other libraries in C++. It is heart of C++. It includes containers, algorithms and iterators.

C++ Standard Template Library (STL)

What STL Provides?

Standard Template Library provides Algorithms and Containers. Containers contain data and algorithms operate on the data which is in containers.

The aim of object oriented language is combining algorithm and data into a class which is called object. STL goes opposite way of OOP language. It separates algorithms and data structures. Purpose of that is code reuse. We want one algorithm apply on different containers. And we want one container to use different algorithms. Containers have different interfaces from each other. So if we want to apply one algorithm on different containers, we need to provide different implementations for that. So if we have N algorithms and M containers we need to provide N*M implementations. This is quite lot work and not scalable also.

To solve this problem STL library provides another group of modules called Iterators. Each container required to provide a common interface defined by iterators. Iterator can iterate each item inside a container. So the algorithm instead of working on containers directly it only works on the iterators. So the algorithm doesn’t know about on which container it is working. It only knows about the iterator. This will very useful to reuse the code instead of writing N*M implementations (above mentioned example). Now we only need to provide N+M implementations. There are so many uses by this. If we define a new algorithm that operates on iterator then all the existing containers can use that algorithm. Similarly if we define a new container that provides appropriate iterate interface then all the existing algorithms can be applied on that new container. So this ST Library is very much useful.

Image Source

Containers

Sequence Containers

These implemented with arrays and linked lists.

• Vector: Vector is a dynamic array that grows in one direction; it is at end of vector.
• Deque: Deque is similar to vector. But deque can grow both beginning and at ending in both directions
• List: It is same as double linked list. Each item in list points to both previous and next item of that item.
• Forward list: Forward list only contain forward pointer. So it can traverse beginning to the end but not from end to the beginning.
• Array: There are limitations to container array. That is size can’t be changed.

Associative Containers

These are typically implemented by Binary Trees. The key attribute of associative containers is all the elements are always sorted.

• Set: Set has no duplicate items. When we insert elements into set all elements automatically sorted. It takes O(log( n)) time.
• Multiset: It is same as set. But only difference is it allows duplicates also.
• Map: Sometimes we don’t want to sort items by values. We are interested to sort them by key value. Map and Multimap contain key value pair structure. Map doesn’t allow duplicate keys.
• Multimap: It is just like a map. But only difference is it allows duplicate keys. Important note is that, keys can’t be modified in map and multimap.

The word associative means, associating key with value. We can say that, set and multiset are special kind or map or multimap where the key of element is the same. This is the reason they called associative.

Unordered Containers

Unordered containers internally implemented with hash table. Each item calculated by hash function, to map to hash table. The main advantage is if we have effective hash function we can find elements in O (1) time.

This is fastest among all containers.

In Unordered containers the order is not defined. And they may change over the time.

• Unordered Set: Unordered set that doesn’t allow duplicates.
• Unordered Multiset: Unordered set that allows duplicate elements.
• Unordered Map: It is unordered set of paris.
• Unordered Multimap: Unordered map that allow duplicate keys.

Container Adaptors

Along with containers, container adaptors also provided by the ST library.

Container adaptors are not full container classes, but classes that provide a specific interface relying on an object of one of the container classes (such as deque or list) to handle the elements. The underlying container is encapsulated in such a way that its elements are accessed by the members of the container adaptor independently of the underlying container class used.

• Stack: Stack provides push, pop, top operations to work on it
• Queue: Push, pop, front, back allowed operations on this.
• Priority Queue: It is keys of items of different priority. First item always have the highest priority. 

Iterators

There are five categories of iterators based on types of operations performed on them.

1. Random Access Iterator

In random access iterator we can access elements in a container randomly. Here we can increment, decrement, add, subtract and also can compare. We can perform all these operations.

Ex: Vector, deque, Array provides random access iterator.

2. Bidirectional Iterator

With bidirectional iterator we can increment and decrement but we can’t add or subtract or compare.

Ex: list , set/multiset, map/multimap provide bidirectional iterators.

3. Forward Iterator

Forward iterator can only be incremented can’t be decremented.

Ex: forword_list

Remaining “Un ordered containers” they provide at least “forward iterators”. And also chance to growth “bidirectional iterators”. It depends on implementation of the STL.

4. Input Iterator

Input iterator used to read and process values while iterating forward. We can read only but not write.

5. Output Iterator

Used to output values.  We can write but not read. Both input iterator and output iterator can only move forward. They can’t move backward.

Iterator Adaptor (Predefined Iterator)

This is a special, more powerful iterator.

• Insert iterator
• Stream iterator
• Reverse iterator
• Move iterator

Algorithms

Algorithms are mostly loops. Algorithms always process ranges in a half-open way. That means it will include the first item but not include the last item.

Non-modifying Algorithms

• Count: Count function counts number of items in some data range.
• Min and max: Max elements returns first maximum number, min returns minimum number.
• Linear Search: When data is not sorted, this search for an element and returns first match.
• Binary Search: When data is sorted, this search for an element and returns first match
• Comparing ranges: Used to compare between two vector/list….etc
• Check attributes: There are different check attributes in this like is sorted, any of/none of satisfied given condition… etc… We learn all of these clearly in further modules.

Modifying Algorithms (Value Changing Algorithms)

• Copy: Copies everything from one container to other.
• Move: It moves items to one place to other.
• Transform: It transforms the data with certain operation. And then save the results at different place.
• Swap: Swap the data between two places. It is also called two way copying.
• Fill: Fill is used to fill the data with certain values.
• Replace: Replace the existing value in container with another value.
• Remove: Remove can remove any element based on condition.

Order Changing Algorithms

They changes the order of the elements in container, but not necessarily the elements themselves.

• Reverse: Reverse the entire data.
• Rotate: Rotates the data from vector begin to vector end.
• Permute: Next permutation results lexicographically next greater permutation. Prev permutation results lexicographically next small permutation.
• Shuffle: Rearrange the elements randomly. Swap each element with a randomly selected element.

Sorting Algorithms

Sorting algorithms are widely used algorithms in programming.

Sorting algorithms requires random access iterators. So that option limits our options to containers vector, deque, container array, native array. List and un-ordered containers cannot be sorted. And associative container doesn’t need sort anyway.

Sort() function directly sort by default. Some other cases also in this. We learn those in further tutorials.

Partial sort: Sometimes we doesn’t need all elements need to be sorted. In that case we use this partial sort like top 5 elements or least 10 elements like this.

Heap Algorithms

Heap has two properties: First element is always larger and add/remove takes O(log(n)) time.

Heap algorithms often used to implement priority queue. These are four important heap algorithms.

• Make_heap: Creates new heap on given container.
• Pop_heap: It removes largest element from heap, for that it does two things, swaps the first and last items of the heap and then heapify to satisfy heap conditions.
• Push_heap: Add new element into heap.
• Sort_heap: It does heap sorting on given heap.

Sorted Data Algorithms

 These are the algorithms that require data being pre-sorted.

• Binary search: It checks for data in a data range. It returns a Boolean as a result.
• Merge: Merge operation does two ranges of sorted data into one range of big sorted data.
• Set operations: Set Union, Set intersection, Set difference, Symmetric difference all these are set operations.

Numeric Algorithms

Numeric algorithms defined in the header of numeric not in the header of algorithm.

• Accumulate: It accumulates the data, in given range, on given operation.
• Inner product: To calculate the inner product of two ranges of data.
• Partial sum: Partial sum calculates partial sum of given range of data and stores in other location.
• Adjacent difference: It calculates the difference between adjacent items and stores in other location.

Reasons to Use C++ Standard Template Library (STL)

• Code reuse. Instead of implementing lot of code we just reuse it.
• Efficiency (fast and use less resources). This is the reason that modern C++ compiler are usually tuned to optimize for C++ Standard Library.
• Accurate, less buggy.
• Terse, readable code; reduced control flow.
• Standardization, guaranteed availability.
• A role model of writing library.
• Good knowledge of data structures and algorithms.

Comment below if you have queries or found any information incorrect in above tutorial for Standard Template Library in C++.