C++ Standard Template Library (STL)

It is a part of the ANSI/ISO C++ standard, so it is part of the C++ standard.

• It mostly focused on providing containers and supporting data types like vectors, lists, queues, and iterators.
• it is a library that is divided into mainly three parts:
  • Containers
    • Sequence
      • Array
      • Vector
      • List
      • Forward List
    • Simple
      • Pair
    • Associative
      • Set
        • MultiSet
        • unordered_set
        • unordered_multiset
      • Map
        • MultiMap
        • unordered_map
        • unordered_multimap
    • Adapter
      • Stack
      • Queue
      • Deque
      • Priority Queue
  • Iterators
  • Algorithms: for performing operations on the containers

Containers:

They are the holder object that stores a collection of other objects (elements).

Sequence

Array

Arrays are used to store multiple values of similar data types in a single variable in contiguous memory allocation.

#include < array >
//std::array< data_type, no_of_elements> nameOfArray;
std::array< int, 3> a = {1,2,3};

Array has a fixed size, and it can not be changed, and the initial value for it is a garbage value, so it is a good practice to assign value to it at initialisation.

Vector

Vectors are used to store multiple values of similar data types in contiguous memory allocation, and size does not need to be known in advance, and easy access to a specific item or all of them.

#include < vector>

//std::vector< data_type> nameOfVector;
std::vector< int> v = {1,2,3};
std::vector< int> iv(3, 100); // {100, 100, 100}

std::cout << v.size(); // 3
v.capacity(); // size of vector + the extra size that can be added.
std::cout << v.front(); // 1
std::cout << v.back(); // 3

// range-base iterator (C++11)
for (int& vec: v) {
    cout << vec << " ";
}

// insert in the middle of vector
v.insert(v.begin() + 1, 5); // 1,5,2,3
v.push_back(4); // 1,5,2,3,4
v.insert(v.end(), 5); // 1,5,2,3,4,5
v.emplace(v.end(), 6); // 1,5,2,3,4,5,6
v.emplace_back(7); // 1,5,2,3,4,5,6,7

// To initialized from c-array
const static int size = 10;
int ia[size] = { 1, 2, 3, ,4, 5, 6, 7, 8, 9, 10};
vector iv2(ia, ia+size);

// To initialized from argc/argv list
 // argv : argument value. argc : argument count.
vector args(argv, argv_argc);

• When you need fast random access to elements.
• When you primarily add or remove elements at the end of the collection.
• When the number of elements does not change frequently.

Unlike arrays, the size of a vector can grow dynamically, but if the capacity is exceeded, the vector reallocates its storage to a large contiguous block.
Which copying all elements to the new block and it is time and memory expensive.

Properties:

Add or delete from back = O(1)
Add or delete from middle or front = O(n) (because of the shift needed)
Access [], or at() = o(1)
find = O(Log(n)) ( and it needs to be ordered)

List

List is a double linked list (Each element in the list contains a pointer to next and previous node), which allow efficient insertion and deletions from anywhere in the list, including both the front, and back.

#include < list>

std::list< int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3); // {1, 2, 3}
l.push_front(4); // {4, 1, 2, 3}

// Insert in middle
std::list< int>::iterator it = l.begin();
std::advance(it, 2);
l.insert(it, 5); // {4, 1, 5, 2, 3}

// You can not use [] or at() to access list element
for (const auto& elem : l)  { 
    std::cout << elem << " "; 
}

Simple

Pair

Is a type of container that receive two elements

#include < utility>
pairp = make_pair("Amr", 20);
pairp2 = {"Tarek", 10};
pairp3{"Hassan", 1};

// For accessing
cout<< p.first() << ":"<< p.second() << endl;

Associative

Set

Set is a immutable, sorted, and unique data type

#include < set>
std::set< int>s;
s.insert(4); // insert at the end
s.emplace(5); insert but faster

std::sets{12,3,4,5,6,23,121}; // sort descending

MultiSet

Multiset is the same of set but it can hold duplicated value (use it when you just want the sorting).

#include < multiset>

std::multiset< int> ms;
ms.emplace(1);
ms.count(1); // check how many 1 in the set.

Map

Map is the array of pair data type plus it has a unique and sorted keys but not values.
it has a fast insertion, search o(log n), removal o(1)

#include < map>
std::map< int, string>m
m.emplace(key, value)

Adapter

Queue

is a FIFO (first in, first out), where elements are added to the back and removed from the front

#include < queue>
std::queue< int> q;
q.push(1); // will push to front (FI)
q.push(2);
q.push(3);  // {3,2,1}

q.pop() // remove the front element (1) (FO)
q.back(); // 3
q.front(); // 1

Deque

Double ended queue, allows insertion and deletion at both ends.

#include < deque>
std::deque< int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_front(3); {3, 1, 2}

dq.pop_front(); // Remove the front element (3) 
dq.pop_back(); // Remove the back element (2)

• When you need efficient insertion and deletion at both ends of the collection.
• When you do not need strict contiguous memory layout.
• When the number of elements changes frequently at both ends.

Queue and Deque are not contiguous they are saving the data in memory chunks, so it can grow and shrink more efficiently than vector

Properties:

Add or delete from back or front = O(1)
Add or delete from middle = O(n) (because of the shift needed)
Access [], or at() = o(1)
find = O(n) (slow search)

Iterators:

They are an objects like a pointer that points to an element inside a container

#include < iterator>
using namespace std;
// container_type< type>::iterator iterator_name;
vector< int>::iterator it;
vector< int> v = {1,2,3,4};

it = v.begin();

while(it != v.end()){
    cout << *it << endl;
    it ++;
}

Use iterator to deal with container rather than pointers because it is safer and it will prevent the known behaviour in case of the container is empty.

Algorithms:

They are algorithms that already build to be used directly, rather than re-build them from scratch.

#include < algorithm>
std::vector< string> words;
// sort asending
std::sort(words.begin(), words.end());
// sort descending
std::sort(words.rbegin(), words.rend());
// reverse the container
std::reverse(words.begin(), words.end());
// it will count how many "Amr" string in the vector or any collection
int threes = count(begin(words), end(words), "Amr");

Templates

maybe you have noticed the <> in vectors, these are the template type operator, so the vector class is using template to handle different types of data types, so do the algorithm functions sort and count.
And actually, the template approach is using the operator overloading to work, you already use it to add two strings with the + sign, which is operator overloading for the plus sign to handle the different data types.