The C++ Standard Template Library (STL)

In this tutorial, We’ll be talking about STL, so an STL stands for standard template library.

We know that to store data in memory, we need a data structure to store data in primary memory. We need data structure for its implementation in a code. We need some easy approach, like if you are from a C language background, to implement it, we need Stack, Queue, LinkedList, or any data structure, but in C++ due to STL. It helps you to implement those data structures in your code with one line.

STL is a set of C++ template classes. It means that it can help you to create a generalized code suitable for every particular datatype.

Suppose you’re creating a stack data structure in C language. You can add only an integer data type, and for accepting floating values, you need to change the codebase. You need to replace integer with the float in every line of the code, written in C language. But due to the concept of C++, STL, what we can do. We need to write our function, having a code inside it, and we need to call it by mentioning the type of data.

So STL provides a common data structure, programming, and functions. To use these functions, one does not need to write code for a specific operation. STL is divided into three categories container, iterators, and algorithm.

What is Container

In daily life, we regularly use containers. Your cereal comes in an individual box, your book is housed inside a hardcover cover, and items can be stored in cans in your garage. Without containers, it would become difficult to work with objects. Try to imagine how difficult it would be to read a book without a binding and eat cereal without a box, and you’ll see what we mean. It would be a difficult mess. The most important function of a container is its ability to organize and store the contents it holds.

Besides, a container class holds and organizes multiple instances of another class. There are many different containers, each of which has particular uses, limitations, and strengths. Arrays are the most commonly used containers in programming, which have been discussed many times throughout this class. In addition to the array functionality of C++, programmers often use a C++ class that provides additional functionality. Unlike built-in arrays, array container classes do not perform bounds checking; they resize dynamically when the array is resized. The array property makes array classes more convenient than normal arrays while also improving their safety. Prototypes exist that have only a minimally defined set of functionality. Many well-defined containers accomplish many functions.

• Create a container
• Insert an object into the container
• Remove an object from the container
• Report the number of objects currently in the container
• Remove all objects from the container
• Provide access to the stored object (optional)

Sometimes certain container classes have less functionality than the others. For instance, array container classes tend to omit the insert and delete functions because they are slow and encourage their use as a bad practice.

Container classes come in two distinct varieties: hard and soft. Value containers hold physical analogs of things they store. (and thus are responsible for creating and destroying those copies). Items or objects stored in aggregations are references to other items or objects (and thus are not responsible for creating or destroying those objects).

Unlike in reality, which allows objects of various types to be placed into the same container, containers typically only contain a single type. When used on a data structure, an array only holds integers. Unlike some other languages, C++ does not provide separate containers for the types. If you want a container capable of holding all integers or all doubles, you will have to write two different container objects to accomplish this (or use templates, an advanced C++ feature). Containers are highly useful and can make programming easier, safer, faster, and more comfortable.

Definition: “A container is a holder with other objects stored inside it (its elements). They are implemented as class templates, and this makes the elements massively flexible.”

The container stores its elements and provides member functions that allow access to the stored elements (reference objects with similar properties to pointers).

Containers relate to popular programming concepts such as dynamic arrays, queues, stacks, heaps, linked lists, and many others (map).

Types of Container

The Standard Template Library (STL) provides several containers for storing collections of related objects. The containers are all template classes, allowing you to specify what objects are allowed in the containers. This topic provides an overview of the STL containers to decide which container is best for your needs.
Containers in STL can be divided into three categories, sequence containers, associative containers, and container adapters.

Sequence Containers

Sequences are applied to maintain the original ordering of inserted elements. The element is added in one location in the container.

Sequence containers:

• Vector (class template)
• Double ended queue (class template)
• List (class template)

A vector is a sequence container. These elements are arranged in a linear sequence.

Vector containers are implemented as dynamic arrays, which means that they are implemented as a contiguous block of memory that can be accessed using iterators and offsets.

Unlike traditional arrays, storage of the vectors is handled automatically, allowing this structure to be expanded and contracted.

Vectors are familiar with:

• Accessing elements in an array by their location index. (constant time).
• Iterating over the elements in a particular order (linear time).
• Remove and add segments to its end (constant amortized time).

Compared to arrays, they perform nearly the same in many tasks and are easily resized. They typically require more memory than arrays when their capacity is handled automatically (this is to accommodate extra storage space for future growth).

Deque (usually pronounced like “deck”) is an irregular acronym denoting a double-ended queue.
Sequence containers are a kind of queue.

By definition, elements are ordered in a linear sequence.

Despite the various ways deques may be implemented, they always allow for the individual elements to be accessed through random-access iterators, with storage handled automatically (expanding and contracting as needed).

Deque sequences have the following properties:

• The Individual elements are accessed by their position.
• Iteration occurs over various elements in any order.
• Elements can be added, removed, and manipulated from both ends (either the beginning or the end of the sequence).

List: Lists are a kind of sequential structure. In this order, the elements are arranged linearly.

List containers are implemented as doubly-linked lists; their stored elements may be stored in at least two places.
The association keeps ordering its links such that element one precedes element two, and element two follows element three.

Container Listing provides the following advantages over other list containers:

The ability to easily insert and remove elements from a container (constant time).

• The movement of elements within a container or the movement of elements between different containers (constant time).
• Make a list of the elements in a collection (linear time).

Container Adapters

These are just variations of the containers. The container adapters do not support iterator features. The STL containers are not designed to be used with iterator adapters.

Container adapters

• LIFO stack (class template)
• FIFO queue (class template)
• Priority queue (class template)

Stack: Stacks are a type of container adapter designed to operate in a LIFO context, where elements are inserted and extracted from the end.

Stacks are implemented via containers adapters which, in turn, are implemented via encapsulated objects, which supply a specific set of member functions for accessing their elements. Elements are pushed or popped from the “back” of the container. This is known as the “top of the stack.”

The underlying container may belong to one of the standard container class templates or one specifically designed container class. The only requirement is that it support all of the following topics:

• back()
• push_back()
• pop_back()

Queues are a specialized form of containers adapters that are designed to operate in a FIFO (first-in, first-out) context, where elements are inserted into one end and extracted from the other end of the queue.
Queues are implemented as container-adapters, which use an object of a specific Container class as their underlying container, providing a specific set of member functions to access its elements. Elements are placed into the back of the particular containers, then are removed from their tops.

The container itself might be one of the standard container classes or a specially designed container class. The only requirement is that it supports the following operations:

• front()
• back()
• push_back()
• pop_front()

Priority Queue: Priority queues are a type of container adapters, specifically designed such that its first element is the greatest of the elements it contains, according to some strict weak ordering conditions.

This context is similar to a heap. Only the max heap element can be retrieved (the top in the priority queue), and elements can be inserted indefinitely.

Priority queues are implemented as container adapters, which are classes that make use of an encapsulated object of a specific container class as its underlying container, implementing member functions for accessing its elements. The Elements are popped from the back of the specific container, known as the top of the priority top.

The container may be any of the standard container class templates or a specifically designed container class. The only requirement is that it must be accessible through random access iterators, and it must support the following operations:

• front()
• push_back()
• pop_back()

Associative Containers

The defining characteristic of associative containers is that elements are placed in a pre-defined order, such as in alphabetical order.

Associative containers:

• Set (class template)
• Multiple-key set (class template)
• Map (class template)
• Multiple-key map (class template)
• Bitset (class template)

Set: Sets are a kind of associative container that can store unique elements, and the elements themselves are the keys for identifying what is stored. Associative containers are better at accessing the elements of a collection due to their design (unlike sequence containers, which are more efficient in accessing elements by their relative or absolute position).

Internally, elements in a set are always sorted from lower to higher within a structure using a unique criterion.

Sets are typically implemented as binary search trees.

Therefore, the main characteristics of the set as an associative container are:

• The elements in the set are distinct and unique from each other. Similar to a multiset, associative containers allow for the equivalent elements of multiple lists.

• The element value is the key itself. For a similar associative container where elements are accessed using a key, but the map to a value different than this key, see map.

• Elements follow a strict weak ordering at all times. Unordered associative arrays, like unordered_set, are available in implementations following TR1. This container class supports bidirectional iterators.

Multiple-key Set: Multisets are associative containers like sets except with multiple keys with equal values.

Map: Maps are kind of like associative containers that store key-value pairs together with the mapped values.

In a map, the key-value is generally used to uniquely identify the element, while the mapped value is some sort of value associated with this key. Types of key and mapped values may differ. For example, a typical example of a map is a telephone guide where the name is the key, and the telephone number is the mapped value.

Internally, the elements in the map are sorted from lower to higher key value following a specific strict weak ordering criterion set on construction.

As associative containers, they are specially designed to be efficient in accessing their elements by their key (unlike sequence containers, which are more efficient in accessing elements by their relative or absolute position).

Therefore, the main characteristics of a map as an associative container are:

• Unique key values: no two elements in the map have keys. that compare each other. For a similar associative container allowing for multiple elements with equivalent keys, see multimap.
• Each element is composed of a key and a mapped value. For a simpler associative container where the element value itself is its key, see set.
• Elements follow a strict weak ordering at all times. Unordered associative arrays, like unordered_map, are available in implementations following TRI. Maps are also unique among associative containers in that they implement the direct access operator (operator[]), which allows for direct access to the mapped value.

Bitset: A bitset is a special container class designed to store bits (elements with only two possible values: 0 or 1, true or false, …).

The class is very similar to a regular array but optimizing for space allocation. Each element occupies only one bit (eight times less than the smallest elemental type in C++: char).

Each element (each bit) can be accessed individually: for example, for a given bitset named mybitset, the expression mybitset[3] accesses its fourth bit, just like a regular array accesses its elements.

Because no such small elemental type exists in most C++ environments, the individual elements accessed as special references which mimic bool elements:

class bitset::reference {
 friend class bitset;
 reference(); // no public constructor
 public:
  ~reference();
  operator bool () canst; // convert to bool
  reference& operator= ( bool x ); // assign from boo I
  reference& operator= ( canst reference& x ); // assign from bit
  reference& flip(); // flip bit value
  bool operator~() canst; // return inverse value
}

iterator

Container means you can assume it to be a box, and inside the box, you’re going to insert an object. So an object can be an element or use a defined object and so on. It determines to traverse each element inside a container. You need an iterator. Suppose you have a box, and inside the box, you are putting 10 books. To traverse each book, you need an iterator. Assume it to be a dynamic pointer, which is traversing every object on every element present inside a container.

Algorithm

The algorithm is a technique which will help you to solve certain kind of problems. For example, if you want to sort the elements, you can directly use C++ built-in function for implementing sorting. There are more than five types of sort of labels like bubbles, heap, insertion, etc. Instead of writing the code from scratch, you can do, you can call C++ a built-in function, which is nothing but the sort function, and inside this, you can pass your container. You can call the sort function, and with a single line, you’re sorting concept will be implemented in the elements inside the container.