C++ tutorials

Vectors–>

MAP–>

  • C++ STL (Standard Template Library) is a part of the C++ Standard Library that provides a collection of template classes and functions to facilitate efficient programming. It includes containers (such as vector, list, deque, map, and set) that store and manage data, algorithms (like sort(), find(), reverse()) to perform operations on containers, and iterators for traversing through containers (e.g., begin(), end()). STL also offers function objects (e.g., greater(), less()) that can be used like functions. The use of templates makes the STL highly generic and reusable, enabling developers to work with different data types without writing custom solutions, promoting efficiency, and reducing development time.

Let’s discuss the C++ vector tutorial with examples:

Vector Definition and Declaration

This example shows how to declare and initialize a vector in various ways:

#include <iostream>
#include <vector>
using namespace std;
int main() {
    // Create an empty vector
    vector<int> v;
    // Create a vector with 5 elements, initialized to 10
    vector<int> v2(5, 10);
    // Create a vector initialized with a list of values
    vector<int> v3 = {1, 2, 3, 4, 5};
    // Output the values of v3
    cout << "Vector v3: ";
    for (int i : v3) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
Output:
Vector v3: 1 2 3 4 5
Vector Size and Capacity

This example demonstrates the difference between size() and capacity().

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    // Size of the vector
    cout << "Size: " << v.size() << endl;  // Output: 5
    // Capacity of the vector
    cout << "Capacity: " << v.capacity() << endl;  // Output may vary, likely 8 or 10
    return 0;
}

Example Output:

Size: 5
Capacity: 8

Note: The capacity may vary depending on the implementation, but typically it will be more than or equal to the size. In this case, the capacity() might return 8 because the vector can grow beyond the current number of elements.

Push Back and Pop Back

This example shows how to add and remove elements from the vector using push_back() and pop_back().

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> v;
    // Push elements to the vector
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    cout << "Vector after push_back operations: ";
    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;
    // Pop an element from the vector
    v.pop_back();
    cout << "Vector after pop_back operation: ";
    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}


Output:
Vector after push_back operations: 10 20 30 
Vector after pop_back operation: 10 20
Accessing Elements: front(), back(), and at()

This example demonstrates how to access the first, last, and specific elements using front(), back(), and at().

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 40, 50};

    // Accessing the first and last elements
    cout << "First element: " << v.front() << endl;  // Output: 10
    cout << "Last element: " << v.back() << endl;    // Output: 50

    // Accessing an element using at()
    cout << "Element at index 2: " << v.at(2) << endl;  // Output: 30

    try {
        // Trying to access an out-of-bounds element
        cout << v.at(10) << endl;  // Will throw out_of_range exception
    } catch (const out_of_range& e) {
        cout << "Exception: " << e.what() << endl;  // Output: out_of_range exception
    }
    return 0;
}
Output:
First element: 10
Last element: 50
Element at index 2: 30
Exception: out_of_range
Other Useful Functions
clear() – Removes all elements in the vector.
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    // Clear the vector
    v.clear();
    cout << "Vector size after clear: " << v.size() << endl;  // Output: 0
    return 0;
}

Output:

Vector size after clear: 0
empty() – Checks if the vector is empty.
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};

    cout << "Is vector empty? " << (v.empty() ? "Yes" : "No") << endl;  // Output: No
    v.clear();
    cout << "Is vector empty? " << (v.empty() ? "Yes" : "No") << endl;  // Output: Yes
    return 0;
}

Output:

Is vector empty? No
Is vector empty? Yes
resize() – Resizes the vector to a given number of elements.
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    // Resize the vector to hold 5 elements
    v.resize(5);
    cout << "Vector after resizing: ";
    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;  // Output: 1 2 3 0 0
    return 0;
}
Output:
Vector after resizing: 1 2 3 0 0
swap() - Swaps the contents of two vectors.
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v1 = {1, 2, 3};
    vector<int> v2 = {4, 5, 6};

    // Swap v1 and v2
    v1.swap(v2);

    cout << "Vector v1 after swap: ";
    for (int i : v1) {
        cout << i << " ";
    }
    cout << endl;  // Output: 4 5 6

    cout << "Vector v2 after swap: ";
    for (int i : v2) {
        cout << i << " ";
    }
    cout << endl;  // Output: 1 2 3

    return 0;
}

Output:

Vector v1 after swap: 4 5 6 
Vector v2 after swap: 1 2 3

Sort, reverse, begin & end 

#include <iostream>
#include <vector>
#include <algorithm>  // for sort, reverse
#include <functional> // for greater
using namespace std;
int main() {
    // 1. Containers: Create a vector
    vector<int> v = {3, 1, 2, 5, 4};

    // 2. Algorithms: Sort the vector in descending order using a function object
    sort(v.begin(), v.end(), greater<int>());

    // 3. Iterators: Traverse the vector using an iterator
    cout << "Sorted vector: ";
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";  // Output: 5 4 3 2 1
    }
    cout << endl;

    // 4. Algorithms: Reverse the vector
    reverse(v.begin(), v.end());

    // 5. Iterators: Traverse again using an iterator
    cout << "Reversed vector: ";
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";  // Output: 1 2 3 4 5
    }
    cout << endl;
    return 0;
}
Summary
  • vector is a sequence container in C++ that dynamically resizes as elements are added or removed.
  • size() gives the current number of elements, while capacity() indicates how much memory has been allocated internally.
  • push_back() adds an element to the end of the vector, while pop_back() removes the last element.
  • front(), back(), and at() are used to access the first, last, and specific elements in the vector.
  • clear(), empty(), resize(), and swap() are other useful functions for manipulating the vector.

These functions form the foundation for working with vectors in C++ STL.

Vector as Stack, Queue & LinkedList using C++ STL

Here’s a short explanation with examples for using vector as a stack, queue, and linked list using C++ STL:

Vector as a Stack

A stack follows the LIFO (Last In First Out) principle. You can use push_back() to add elements and pop_back() to remove them.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> stack;

    // Push elements onto the stack
    stack.push_back(10);
    stack.push_back(20);
    stack.push_back(30);
    // Pop an element from the stack
    stack.pop_back();
    // Print the stack
    for (int i : stack) {
        cout << i << " ";  // Output: 10 20
    }
    cout << endl;
    return 0;
}
Queue Using STL (queue container)

A queue follows the FIFO (First In First Out) principle. You can use push() to add elements and pop() to remove them.

#include <iostream>
#include <queue>
using namespace std;
int main() {
    queue<int> q;
    // Enqueue elements
    q.push(10);
    q.push(20);
    q.push(30);

    // Dequeue an element
    q.pop();
    // Print the front element of the queue
    cout << "Front: " << q.front() << endl;  // Output: 20
    // Print the queue size
    cout << "Size: " << q.size() << endl;  // Output: 2
    return 0;
}
Linked List Using STL (list container)

A linked list allows efficient insertion and removal at both ends. You can use push_back(), push_front(), pop_back(), pop_front(), and insert().

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l;
    // Insert elements at the back
    l.push_back(10);
    l.push_back(20);
    // Insert element at the front
    l.push_front(5);

    // Remove element from the front
    l.pop_front();

    // Remove element from the back
    l.pop_back();

    // Print the linked list
    for (int i : l) {
        cout << i << " ";  // Output: 10
    }
    cout << endl;
    return 0;
}
Summary of Functions:
  • Stack (using vector):
    • push_back(): Add element to the stack
    • pop_back(): Remove element from the stack
  • Queue (using queue container):
    • push(): Add element to the queue
    • pop(): Remove element from the queue
    • front(): Access the front element
    • back(): Access the back element
    • size(): Get the size of the queue
  • Linked List (using list container):
    • push_back(): Add element to the end
    • push_front(): Add element to the front
    • pop_back(): Remove element from the end
    • pop_front(): Remove element from the front
    • insert(): Insert element at a specific position
Nested STL 
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
int main() {
    // 1. Vector of Vectors: Used to represent a 2D matrix or grid.
    std::vector<std::vector<int>> matrix = { // Declaring a vector where each element is another vector.
        {1, 2, 3}, // First row of the matrix.
        {4, 5, 6}, // Second row of the matrix.
        {7, 8, 9}  // Third row of the matrix.
    };
    std::cout << "Vector of Vectors:" << std::endl;
    for (const auto& row : matrix) { // Loop through each row (a vector) in the matrix.
        for (int value : row) { // Loop through each value in the current row.
            std::cout << value << " "; // Print the value followed by a space.
        }
        std::cout << std::endl; // Print a newline after each row.
    }
    // 2. Set of Pairs: Used to store unique pairs of integers, useful for coordinate-like data.
    std::set<std::pair<int, int>> points = {{1, 2}, {3, 4}, {5, 6}}; // Declare a set of pairs and initialize it with some values.
    std::cout << "\nSet of Pairs:" << std::endl;
    for (const auto& point : points) { // Loop through each pair in the set.
        std::cout << "(" << point.first << ", " << point.second << ")" << std::endl; // Access and print the pair using `first` and `second`.
    }

    // 3. Map of Sets: Used to group unique elements (sets) under specific keys.
    std::map<std::string, std::set<int>> studentSubjects; // Declare a map where keys are strings and values are sets of integers.
    studentSubjects["Alice"] = {101, 102, 103}; // Assign a set of subject codes to "Alice".
    studentSubjects["Bob"] = {102, 104};       // Assign a set of subject codes to "Bob".
    std::cout << "\nMap of Sets:" << std::endl;
    for (const auto& pair : studentSubjects) { // Loop through each key-value pair in the map.
        std::cout << pair.first << ": "; // Print the key (student name).
        for (int subject : pair.second) { // Loop through the set of subject codes.
            std::cout << subject << " "; // Print each subject code.
        }
        std::cout << std::endl; // Print a newline after each student's subjects.
    }

    // 4. Map of Vectors: Used to store lists of values (vectors) under each key.
    std::map<std::string, std::vector<int>> studentScores; // Declare a map where keys are strings and values are vectors of integers.
    studentScores["Alice"] = {90, 85, 88}; // Assign a vector of scores to "Alice".
    studentScores["Bob"] = {78, 82};       // Assign a vector of scores to "Bob".
    std::cout << "\nMap of Vectors:" << std::endl;
    for (const auto& pair : studentScores) { // Loop through each key-value pair in the map.
        std::cout << pair.first << ": "; // Print the key (student name).
        for (int score : pair.second) { // Loop through the vector of scores.
            std::cout << score << " "; // Print each score.
        }
        std::cout << std::endl; // Print a newline after each student's scores.
    }

    // 5. Unordered Map of Unordered Sets: Used to represent fast lookups, such as a graph adjacency list.
    std::unordered_map<int, std::unordered_set<int>> graph; // Declare an unordered map where keys are integers and values are unordered sets of integers.
    graph[1] = {2, 3}; // Add edges from node 1 to nodes 2 and 3.
    graph[2] = {1, 4}; // Add edges from node 2 to nodes 1 and 4.
    std::cout << "\nUnordered Map of Unordered Sets (Graph Representation):" << std::endl;
    for (const auto& pair : graph) { // Loop through each key-value pair in the map.
        std::cout << pair.first << " -> "; // Print the key (a node in the graph).
        for (int neighbor : pair.second) { // Loop through the set of neighbors.
            std::cout << neighbor << " "; // Print each neighbor.
        }
        std::cout << std::endl; // Print a newline after each node's neighbors.
    }

    return 0; // Indicate successful execution.
}

C++ STL map Tutorial

Introduction

In C++, the Standard Template Library (STL) provides several useful container classes, and one of the most commonly used is the map. A map is an associative container that stores key-value pairs. It is similar to a dictionary or hash table in other programming languages.

Key Properties of a map:
  1. Associative: Elements in a map are stored as key-value pairs.
  2. Unique Keys: Each key in the map must be unique. If you try to insert a duplicate key, it will overwrite the existing value.
  3. Ordered: The elements in the map are always stored in a sorted order based on the key. The default sorting is in ascending order, but this can be customized.

Syntax:

#include <map>

// Declaration of a map
map<KeyType, ValueType> mapName;

Where:

  • KeyType: Type of the key (e.g., int, string).
  • ValueType: Type of the value associated with the key.
1. Basic Operations on map
1.1 Creating a map

A map can be created by specifying the key type and value type. Here’s an example:

map<int, string> studentGrades;

This creates a map where the key is of type int (e.g., student ID) and the value is of type string (e.g., grade).

1.2 Inserting Elements into a map

There are two ways to insert elements into a map:

Using operator[]:
studentGrades[101] = "A";  // Inserting key-value pair (101, "A")
studentGrades[102] = "B";  // Inserting key-value pair (102, "B")
Using insert() method:
studentGrades.insert({103, "C"});  // Inserting using a pair
studentGrades.insert(make_pair(104, "A"));
1.3 Accessing Elements

You can access values in a map by using the key:

cout << studentGrades[101] << endl;  // Output: A

Note that if the key does not exist, the operator[] will insert a default value. To check if a key exists before accessing, use find():

if (studentGrades.find(105) != studentGrades.end()) {
    cout << studentGrades[105] << endl;
} else {
    cout << "Key not found!" << endl;
}

1.4 Size of a map

The size of a map (number of elements) can be obtained using the size() method:

cout << "Size of map: " << studentGrades.size() << endl;
1.5 Erasing Elements

You can remove elements using the erase() function:

studentGrades.erase(101);  // Removes the element with key 101

You can also remove elements using iterators:

auto it = studentGrades.find(102);
if (it != studentGrades.end()) {
    studentGrades.erase(it);
}
2. Iterating Over a map
2.1 Using Iterator

To iterate over a map, you can use an iterator:

for (auto it = studentGrades.begin(); it != studentGrades.end(); ++it) {
    cout << "ID: " << it->first << ", Grade: " << it->second << endl;
}
2.2 Using Range-based For Loop

Since C++11, you can also use a range-based for loop for simpler iteration:

for (const auto& entry : studentGrades) {
    cout << "ID: " << entry.first << ", Grade: " << entry.second << endl;
}
2.3 Reverse Iteration

To iterate in reverse order, you can use rbegin() and rend():

for (auto it = studentGrades.rbegin(); it != studentGrades.rend(); ++it) {
    cout << "ID: " << it->first << ", Grade: " << it->second << endl;
}

3. Advanced map Topics

3.1 Custom Sorting (Comparators)

By default, map sorts its keys in ascending order. However, you can provide a custom comparator to change the sorting order.

Example: Sorting in descending order
map<int, string, greater<int>> reverseStudentGrades;
reverseStudentGrades[101] = "A";
reverseStudentGrades[102] = "B";
reverseStudentGrades[103] = "A";

for (const auto& entry : reverseStudentGrades) {
    cout << "ID: " << entry.first << ", Grade: " << entry.second << endl;
}
3.2 multimap

A multimap allows multiple elements with the same key, unlike map where each key is unique. This is useful when you need to store multiple values under the same key.

Example:
multimap<int, string> studentSubjects;
studentSubjects.insert({101, "Math"});
studentSubjects.insert({101, "Physics"});
studentSubjects.insert({102, "Chemistry"});

for (const auto& entry : studentSubjects) {
    cout << "ID: " << entry.first << ", Subject: " << entry.second << endl;
}
3.3 map with Complex Types (Custom Classes)

You can use custom types (classes or structs) as keys in a map. To do so, you need to define how the keys should be compared (usually by overloading the < operator).

Example with a custom comparator:
struct Student {
    int id;
    string name;
    
    // Overload the < operator for comparison
    bool operator<(const Student& other) const {
        return id < other.id;
    }
};

map<Student, string> studentInfo;
studentInfo[Student{101, "John"}] = "A";
studentInfo[Student{102, "Jane"}] = "B";

for (const auto& entry : studentInfo) {
    cout << "ID: " << entry.first.id << ", Name: " << entry.first.name << ", Grade: " << entry.second << endl;
}
3.4 Performance Considerations
  • Time Complexity:
    • Insertion, deletion, and lookup operations all take O(log n) time because map is implemented as a balanced binary search tree (typically Red-Black Tree).
  • Space Complexity:
    • The space complexity of a map is O(n), where n is the number of elements stored in the map.
4. Example: Complete Code of Using map
#include <iostream>
#include <map>
using namespace std;

int main() {
    // 1. Creating a map
    map<int, string> studentGrades;

    // 2. Inserting elements
    studentGrades[101] = "A";
    studentGrades[102] = "B";
    studentGrades.insert({103, "C"});

    // 3. Accessing elements
    cout << "Grade of student with ID 101: " << studentGrades[101] << endl;

    // 4. Iterating over the map
    cout << "All student grades:\n";
    for (const auto& entry : studentGrades) {
        cout << "ID: " << entry.first << ", Grade: " << entry.second << endl;
    }

    // 5. Using custom comparator for reverse sorting
    map<int, string, greater<int>> reverseMap;
    reverseMap[101] = "A";
    reverseMap[102] = "B";
    reverseMap[103] = "C";

    cout << "Reverse sorted map:\n";
    for (const auto& entry : reverseMap) {
        cout << "ID: " << entry.first << ", Grade: " << entry.second << endl;
    }

    return 0;
}
Output:
Grade of student with ID 101: A
All student grades:
ID: 101, Grade: A
ID: 102, Grade: B
ID: 103, Grade: C
Reverse sorted map:
ID: 103, Grade: C
ID: 102, Grade: B
ID: 101, Grade: A
Conclusion
  • map is a powerful associative container in C++ STL that stores key-value pairs.
  • It automatically sorts the keys in ascending order by default, but you can customize the sorting using comparators.
  • Basic operations include insertion, access, deletion, and iteration.
  • Advanced topics include custom comparators, multi-maps, and using complex types as keys.

.

.

Scroll to Top