Exploring the STL libraries in C++

Exploring the libraries in C++

The Standard Template Library is a C++ library of container classes, algorithms and iterators; it provides many of the basic algorithms and data structures of computer science. The STL is a generic library, meaning that its components are heavily parameterised: almost every component in the STL is a template.

The prospects for early widespread dissemination of STL were considerably improved with Hewlett Packard’s decision to make its implementation freely available on the Internet in August 1994. This implementation, developed by Stepanov, Lee, and Musser during the standardisation process, became the basis of many implementations offered by compiler and library vendors today.

The STL contains sequence containers and associative containers. The containers are objects that store data. The standard sequence containers include vector, deque, and list. The standard associative containers are set, multiset, map, multimap, hash_set, hash_map, hash_multiset and hash_multimap. There are also container adaptors queue, priority_queue, and stack, that are containers with specific interface, using other containers as implementation.

Lets Discuss One By One With Proper Examples:

  • PAIR
    class template

    std::pair
    template struct pair;

Pair of values

This class couples together with a pair of values, which may be of different types (T1 and T2). The individual values can be accessed through its public members first and second. Pairs are a particular case of the tuple.

Example:

include

using namespace std;
int main ()
{
pair pair1, pair3; //creats pair of integers
pair pair2; // creates pair of an integer an a string
pair1 = make_pair(1, 2); // insert 1 and 2 to the pair1
pair2 = make_pair(1, “Studytonight”) // insert 1 and “Studytonight” in pair2
pair3 = make_pair(2, 4)
cout<< pair1.first << endl; // prints 1, 1 being 1st element of pair1
cout<< pair2.second << endl; // prints Studytonight
if(pair1 == pair3)
cout<< “Pairs are equal” << endl;
else
cout<< “Pairs are not equal” << endl;
return 0;
}

* VECTOR

class template

<vector>

std::vector

template < class T, class Alloc = allocator<T> > class vector; // generic template

Vector

Vectors are sequence containers representing arrays that can change in size. Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it.

Example:

include<iostream>

include<string>

include<vector>

int main() {
// Vector with 5 integers
// Default value of integers will be 0.
std::vector < int >
vecOfInts(5);
for (int x: vecOfInts)
std::cout << x << std::endl;
}

* LISTclass template

<list>

std::list

template < class T, class Alloc = allocator<T> > class list;

List: They are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions. List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept internally by the association to each element of a link to the element preceding it and a link to the element following it.

Example:
Creating a std::list of int and pushing elements in front and back
std::list listOfNumbers;
//Inserting elements at end in list
listOfNumbers.push_back(5);
listOfNumbers.push_back(6);
//Inserting elements at front in list
listOfNumbers.push_front(2);
listOfNumbers.push_front(1);

  • DEQUEUE
    class template

    std::deque
    template < class T, class Alloc = allocator > class deque;

Double-ended queuedeque (usually pronounced like “deck”) is an irregular acronym of double-ended queue. Double-ended queues are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either it’s front or it’s back). Specific libraries may implement deques in different ways, generally as some form of a dynamic array. But in any case, they allow for the individual elements to be accessed directly through random access iterators, with storage handled automatically by expanding and contracting the container as needed.

Double ended queuedeque (usually pronounced like “deck”) is an irregular acronym of double-ended queue. Double-ended queues are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either its front or its back).

Specific libraries may implement deques in different ways, generally as some form of dynamic array. But in any case, they allow for the individual elements to be accessed directly through random access iterators, with storage handled automatically by expanding and contracting the container as needed.

Example:

include<iostream>

include<deque>

using namespace std;
void showdq(deque g)
{
deque :: iterator it;
for (it = g.begin(); it != g.end(); ++it)
cout << ‘\t’ << *it; cout << ‘\n’; } int main() { deque gquiz;
gquiz.push_back(10);
gquiz.push_front(20);
gquiz.push_back(30);
gquiz.push_front(15);
cout << “The deque gquiz is : “;
showdq(gquiz);

cout << "\ngquiz.size() : " << gquiz.size(); 
cout << "\ngquiz.max_size() : " << gquiz.max_size(); 

cout << "\ngquiz.at(2) : " << gquiz.at(2); 
cout << "\ngquiz.front() : " << gquiz.front(); 
cout << "\ngquiz.back() : " << gquiz.back(); 

cout << "\ngquiz.pop_front() : "; 
gquiz.pop_front(); 
showdq(gquiz); 

cout << "\ngquiz.pop_back() : "; 
gquiz.pop_back(); 
showdq(gquiz); 
return 0; 

}

  • QUEUE
    class template

    std::queue
    template > class queue;
    FIFO queue
    queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.

Queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed into the “back” of the specific container and popped from its “front”. The underlying container may be one of the standard container class template or some other specifically designed container class. This underlying container shall support at least the following operations:

  • empty
  • size
  • front
  • back
  • push_back
  • pop_front

Example:

include<iostream>

include<queue>

using namespace std;
int main()
{
queue queue1;
queue1.emplace(1);
queue1.emplace(2);
queue1.emplace(3);
if (queue1.empty())
{
cout << “The queue is empty”;
}
else
{
cout << “The queue is not empty”;
}
return 0;
}

PRIOITY QUEUE
class template

std::priority_queue
template ,
class Compare = less > class priority_queue;
Priority queue
Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion.

This context is similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue).
Operations:- empty()
• size()
• front()
• push_back()
• pop_back()

Example:

include<iostream>

include<queue>

using namespace std;
void showpq(priority_queue gq)
{
priority_queue g = gq;
while (!g.empty())
{
cout << ‘\t’ << g.top(); g.pop(); } cout << ‘\n’; } int main () { priority_queue gquiz;
gquiz.push(10);
gquiz.push(30);
gquiz.push(20);
gquiz.push(5);
gquiz.push(1);
cout << “The priority queue gquiz is : “;
showpq(gquiz);
cout << “\ngquiz.size() : ” << gquiz.size();
cout << “\ngquiz.top() : ” << gquiz.top();
cout << “\ngquiz.pop() : “;
gquiz.pop();
showpq(gquiz);
return 0;
}

  • STACK
    class template

    std::stack
    template > class stack;
    LIFO stack
    Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.

stacks are implemented as container adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed/popped from the “back” of the specific container, which is known as the top of the stack.

The underlying container may be any of the standard container class templates or some other specifically designed container class. The container shall support the following operations:
• empty
• size
• back
• push_back
• pop_back

Example:
#include<iostream>

include<stack>

using namespace std;
int main() {
stack st;
st.push(10);
st.push(20);
st.push(30);
st.push(40);

     st.pop();
st.pop();

while (!st.empty()) {
    cout << ' ' << st.top();
    st.pop();
}

}

  • SET
    class template

    Set
    Sets are containers that store unique elements following a specific order.

In a set, the value of an element also identifies it (the value is itself the key, of type T), and each value must be unique. The value of the elements in a set cannot be modified once in the container (the elements are always const), but they can be inserted or removed from the container. Internally, the elements in a set are always sorted following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).

Set containers are generally slower than unordered_set containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.
Example:
std::set
template < class T, // set::key_type/value_type class Compare = less, // set::key_compare/value_compare
class Alloc = allocator // set::allocator_type
> class set;

  • MULTI SET
    class template

    std::multiset
    Multiple-key set
    Multisets are containers that store elements following a specific order, and where multiple elements can have equivalent values.

In a multiset, the value of an element also identifies it (the value is itself the key, of type T). The value of the elements in a multiset cannot be modified once in the container (the elements are always const), but they can be inserted or removed from the container. Internally, the elements in a multiset are always sorted following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).

Example:
#include<iostream>

include<set>

include<iterator>

using namespace std;
int main()
{
// empty multiset container
multiset > gquiz1;

// insert elements in random order 
gquiz1.insert(40); 
gquiz1.insert(30); 
gquiz1.insert(60); 
gquiz1.insert(20); 
gquiz1.insert(50); 
gquiz1.insert(50); // 50 will be added again to the multiset unlike set 
gquiz1.insert(10); 

// printing multiset gquiz1 
multiset <int, greater <int> > :: iterator itr; 
cout << "\nThe multiset gquiz1 is : "; 
for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) 
{ 
    cout << '\t' << *itr; 
} 
cout << endl; 

// assigning the elements from gquiz1 to gquiz2 
multiset <int> gquiz2(gquiz1.begin(), gquiz1.end()); 

// print all elements of the multiset gquiz2 
cout << "\nThe multiset gquiz2 after assign from gquiz1 is : "; 
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) 
{ 
    cout << '\t' << *itr; 
} 
cout << endl; 

// remove all elements up to element with value 30 in gquiz2 
cout << "\ngquiz2 after removal of elements less than 30 : "; 
gquiz2.erase(gquiz2.begin(), gquiz2.find(30)); 
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) 
{ 
    cout << '\t' << *itr; 
} 

// remove all elements with value 50 in gquiz2 
int num; 
num = gquiz2.erase(50); 
cout << "\ngquiz2.erase(50) : "; 
cout << num << " removed \t" ; 
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) 
{ 
    cout << '\t' << *itr; 
} 
cout << endl; 
//lower bound and upper bound for multiset gquiz1 
cout << "gquiz1.lower_bound(40) : "
    << *gquiz1.lower_bound(40) << endl; 
cout << "gquiz1.upper_bound(40) : "
    << *gquiz1.upper_bound(40) << endl; 

//lower bound and upper bound for multiset gquiz2 
cout << "gquiz2.lower_bound(40) : "
    << *gquiz2.lower_bound(40) << endl; 
cout << "gquiz2.upper_bound(40) : "
    << *gquiz2.upper_bound(40) << endl; 
    return 0; 

  • MAP
    class template

    std::map
    Map
    Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order.

In a map, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated with this key. The types of key and mapped value may differ and are grouped together in member type value_type, which is a pair type combining both:

 typedef pair<const Key, T> value_type;

The mapped values in a map can be accessed directly by their corresponding key using the bracket operator ((operator[]).

Maps are typically implemented as binary search trees.
Example:
#include<iostream>

include<map>

using namespace std;
int main ()
{
map m{ {1,2} , {2,3} , {3,4} };
/* creates a map m with keys 1,2,3 and
their corresponding values 2,3,4 / map map1; / creates a map with keys of type character and
values of type integer */

map1["abc"]=100;    // inserts key = "abc" with value = 100
map1["b"]=200;      // inserts key = "b" with value = 200
map1["c"]=300;      // inserts key = "c" with value = 300
map1["def"]=400;    // inserts key = "def" with value = 400

map<char,int> map2 (map1.begin(), map1.end());
/* creates a map map2 which have entries copied 
    from map1.begin() to map1.end() */ 

map<char,int> map3 (m);
/* creates map map3 which is a copy of map m */

}

hash_set
hash_multiset
hash-map
hash_multimap
similar to a set, multiset, map, or multimap, respectively, but implemented using a hash_table; keys are not ordered, but a hash function must exist for the key type. These types were left out of the C++ standard; similar containers were standardized in C++, but with different names (unordered_set and unordered_map).

*  BITSET

class template

<bitset>

std::bitset

template <size_t N> class bitset;

Bitset A bitset stores bits (elements with only two possible values: 0 or 1, true or false, …).The class emulates an array of bool elements, but optimised for space allocation: generally, each element occupies only one bit (which, on most systems, is eight times less than the smallest elemental type: char).

Each bit position can be accessed individually: for example, for a given bitset named foo, the expression foo[3] accesses its fourth bit, just like a regular array accesses its elements. But because no elemental type is a single bit in most C++ environments, the individual elements are accessed as special references type (see bitset:: reference).

Example:

include<bits/stdc++.h>

using namespace std;
int main()
{
bitset<4> bset1(9); // bset1 contains 1001
bitset<4> bset2(3); // bset2 contains 0011

// comparison operator 
cout << (bset1 == bset2) << endl; // false 0 
cout << (bset1 != bset2) << endl; // true  1 

// bitwise operation and assignment 
cout << (bset1 ^= bset2) << endl; // 1010 
cout << (bset1 &= bset2) << endl; // 0010 
cout << (bset1 |= bset2) << endl; // 0011 

// left and right shifting 
cout << (bset1 <<= 2) << endl; // 1100 
cout << (bset1 >>= 1) << endl; // 0110 

// not operator 
cout << (~bset2) << endl; // 1100 

// bitwise operator 
cout << (bset1 & bset2) << endl; // 0010 
cout << (bset1 | bset2) << endl; // 0111 
cout << (bset1 ^ bset2) << endl; // 0101 

}

  • SORT
    function template

    std::sort
    default (1)
    Sort elements in range
    Sorts the elements in the range [first,last) into ascending order.

The elements are compared using the operator< for the first version, and comp for the second.
Example:

include<iostream>

include<algorithm>

using namespace std;
void show(int a[])
{
for(int i = 0; i < 10; ++i)
cout << a[i] << ” “;
}
int main()
{
int a[10]= {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
cout << “\n The array before sorting is : “;
show(a);
sort(a, a+10);
cout << “\n\n The array after sorting is : “;
show(a);
return 0;
}

  • ValARRAY
    class template

    std::valarray
    template class valarray;
    Valarray class
    A valarray object is designed to hold an array of values, and easily perform mathematical operations on them. It also allows special mechanisms to refer to subsets of elements in the arrays (see its operator[] overload).

Most mathematical operations can be applied directly to valarray objects, including arithmetical and comparison operators, affecting all its elements.

The valarray specification allows for libraries to implement it with several efficiency optimisations, such as parallelisation of certain operations, memory recycling or support for copy-on-reference / copy-on-write optimisations. Implementations may even replace valarray as the return type for standard functions described below, provided they behave as, and can be converted to, valarray objects.

Example:
// C++ code to demonstrate the working of
// apply() and sum()

include<iostream>

include<valarray> // for valarray functions

using namespace std;
int main()
{
// Initializing valarray
valarray varr = { 10, 2, 20, 1, 30 };

// Declaring new valarray 
valarray<int> varr1 ; 
// Using apply() to increment all elements by 5 
varr1 = varr.apply([](int x){return x=x+5;}); 

// Displaying new elements value 
cout << "The new valarray with manipulated values is : "; 
for (int &x: varr1) cout << x << " "; 
cout << endl; 
// Displaying sum of both old and new valarray 
cout << "The sum of old valarray is : "; 
cout << varr.sum() << endl; 
cout << "The sum of new valarray is : "; 
cout << varr1.sum() << endl; 
return 0; 

}

If you want to read more, read here.

By Akhil Sharma

Exit mobile version