Code C++

Vectors

std::vector<dataType> name({ value1, value2, value3});
std::vector<dataType> name(other_vec);
std::vector<dataType> name(size, value);

C++ Vector Functions

Basic Operations

begin(): Returns an iterator to the first element.
end(): Returns an iterator to the past-the-end element.
rbegin(): Returns a reverse iterator to the last element.
rend(): Returns a reverse iterator to the past-the-end element in reverse order.
clear(): Removes all elements from the vector.
empty(): Checks if the vector is empty.
size(): Returns the number of elements in the vector.
max_size(): Returns the maximum possible size of the vector.
capacity(): Returns the current capacity of the vector.
reserve(): Resizes the vector’s capacity.

Element Access

operator[]: Accesses an element.
at(): Accesses an element, throwing an exception if out of bounds.
front(): Returns a reference to the first element.
back(): Returns a reference to the last element.

Modifiers

push_back(): Adds an element to the end.
pop_back(): Removes the last element.
insert(): Inserts elements at a specified position.
erase(): Removes elements at a specified position or range.
swap(): Exchanges the contents of two vectors.

Iterators

iterator: A bidirectional iterator to elements in the vector.
reverse_iterator: A bidirectional iterator to elements in the vector in reverse order.

C++ Vector Iterator Functions

operator*: Dereferences the iterator to get the value.
operator->value: Dereferences the iterator to get a pointer to the value.
operator++: Increments the iterator to the next element.
operator--: Decrements the iterator to the previous element.
operator==(): Compares two iterators for equality.
operator!=(): Compares two iterators for inequality.

Example Usage:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> myVector;

    // Add elements
    myVector.push_back(10);
    myVector.push_back(20);
    myVector.insert(myVector.begin() + 1, 15);

    // Access elements
    cout << myVector[0] << endl;
    cout << myVector.at(1) << endl;

    // Iterate over elements
    for (auto it : myVector) {
        cout << it << " ";
    }
    cout << endl;

    return 0;
}

Maps

Ordered/Unordered
Ordered = map
Unordered = unordered_map

C++ Map Functions

Basic Operations

begin(): Returns an iterator to the first element.
end(): Returns an iterator to the past-the-end element.
rbegin(): Returns a reverse iterator to the last element.
rend(): Returns a reverse iterator to the past-the-end element in reverse order.
clear(): Removes all elements from the map.
empty(): Checks if the map is empty.
size(): Returns the number of elements in the map.

Element Access

operator[]: Accesses an element, inserting a new element with the default value if it doesn’t exist.
at(): Accesses an element, throwing an exception if it doesn’t exist.
count(): Returns the number of elements with the specified key.
find(): Returns an iterator to the element with the specified key, or end() if not found.
erase(): Removes an element by key or iterator.

Modifiers

insert(): Inserts a new element.
emplace(): Constructs a new element in-place.
swap(): Exchanges the contents of two maps.

Iterators

iterator: A bidirectional iterator to elements in the map.
reverse_iterator: A bidirectional iterator to elements in the map in reverse order.

C++ Map Iterator Functions

operator*: Dereferences the iterator to get the value.
operator->second: Dereferences the iterator to get a pointer to the value.
operator++: Increments the iterator to the next element.
operator--: Decrements the iterator to the previous element.
operator==(): Compares two iterators for equality.
operator!=(): Compares two iterators for inequality.

Example Usage:

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, int> myMap;

    // Insert elements
    myMap["apple"] = 10;
    myMap["banana"] = 20;
    myMap.insert({"orange", 30});

    // Access elements
    cout << myMap["apple"] << endl;
    cout << myMap.at("banana") << endl;

    // Find elements
    auto it = myMap.find("orange");
    if (it != myMap.end()) {
        cout << it->first << ": " << it->second << endl;
    }

    // Iterate over elements
    for (auto it : myMap) {
        cout << it.first << ": " << it.second << endl;
    }

    return 0;
}

Stacks

C++ Stack Functions

Basic Operations

empty(): Checks if the stack is empty.
size(): Returns the number of elements in the stack.
top(): Returns a reference to the top element (throws an exception if empty).
push(): Adds an element to the top of the stack.
pop(): Removes the top element (throws an exception if empty).

Modifiers

swap(): Exchanges the contents of two stacks.

C++ Stack Iterator Functions

Note: Stacks do not have built-in iterators. This is because stacks are designed for last-in-first-out (LIFO) access, and iterating over all elements would violate this principle.

Alternative Approach:

If you need to iterate over elements in a stack-like manner, you can use a std::vector or std::deque and implement stack operations manually:

#include <iostream>
#include <vector>

using namespace std;

class MyStack {
private:
    vector<int> data;

public:
    bool empty() const {
        return data.empty();
    }

    int size() const {
        return data.size();
    }

    int top() const {
        if (empty()) {
            throw runtime_error("Stack is empty");
        }
        return data.back();
    }

    void push(int value) {
        data.push_back(value);
    }

    void pop() {
        if (empty()) {
            throw runtime_error("Stack is empty");
        }
        data.pop_back();
    }

    // Iterator
    vector<int>::iterator begin() {
        return data.begin();
    }

    vector<int>::iterator end() {
        return data.end();
    }
};

int main() {
    MyStack myStack;

    myStack.push(10);
    myStack.push(20);

    // Iterate over elements (using a vector iterator)
    for (auto it = myStack.begin(); it != myStack.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

Deque

C++ Deque Functions

Basic Operations

begin(): Returns an iterator to the first element.
end(): Returns an iterator to the past-the-end element.
rbegin(): Returns a reverse iterator to the last element.
rend(): Returns a reverse iterator to the past-the-end element in reverse order.
empty(): Checks if the deque is empty.
size(): Returns the number of elements in the deque.
max_size(): Returns the maximum possible size of the deque.
front(): Returns a reference to the first element.
back(): Returns a reference to the last element.

Modifiers

push_front(): Adds an element to the front.
push_back(): Adds an element to the back.
pop_front(): Removes the first element.
pop_back(): Removes the last element.
insert(): Inserts elements at a specified position.
erase(): Removes elements at a specified position or range.
swap(): Exchanges the contents of two deques.

Iterators

iterator: A bidirectional iterator to elements in the deque.
reverse_iterator: A bidirectional iterator to elements in the deque in reverse order.

Example Usage:

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> myDeque;

    // Add elements
    myDeque.push_front(10);
    myDeque.push_back(20);
    myDeque.insert(myDeque.begin() + 1, 15);

    // Access elements
    cout << myDeque.front() << endl;
    cout << myDeque.back() << endl;

    // Iterate over elements
    for (auto it : myDeque) {
        cout << it << " ";
    }
    cout << endl;

    return 0;
}

Sets

C++ Set Functions

Basic Operations

begin(): Returns an iterator to the first element.
end(): Returns an iterator to the past-the-end element.
rbegin(): Returns a reverse iterator to the last element.
rend(): Returns a reverse iterator to the past-the-end element in reverse order.
empty(): Checks if the set is empty.
size(): Returns the number of elements in the set.
max_size(): Returns the maximum possible size of the set.
clear(): Removes all elements from the set.

Element Access

count(): Checks if an element exists.
find(): Returns an iterator to the element if found, otherwise end().
equal_range(): Returns a pair of iterators defining the range of elements equal to a given value.

Modifiers

insert(): Inserts an element.
erase(): Removes an element or a range of elements.
swap(): Exchanges the contents of two sets.

C++ Set Iterator Functions

iterator: A bidirectional iterator to elements in the set.
reverse_iterator: A bidirectional iterator to elements in the set in reverse order.

Example Usage:

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> mySet = {10, 20, 30};

    // Insert an element
    mySet.insert(40);

    // Find an element
    auto it = mySet.find(20);
    if (it != mySet.end()) {
        cout << "Found: " << *it << endl;
    }

    // Iterate over elements
    for (auto it : mySet) {
        cout << it << " ";
    }
    cout << endl;

    return 0;
}

Queue

C++ Queue Functions

Basic Operations

empty(): Checks if the queue is empty.
size(): Returns the number of elements in the queue.
front(): Returns a reference to the front element (throws an exception if empty).
back(): Returns a reference to the back element (throws an exception if empty).
push(element): Adds an element to the back of the queue.
pop(): Removes the front element from the queue (throws an exception if empty).

Other Operations

swap(other_queue): Exchanges the contents of two queues.

Example Usage:

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> myQueue;

    // Add elements to the queue
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);

    // Access elements
    cout << "Front element: " << myQueue.front() << endl;
    cout << "Back element: " << myQueue.back() << endl;

    // Remove elements
    myQueue.pop();
    myQueue.pop();

    // Check if empty
    if (myQueue.empty()) {
        cout << "Queue is empty" << endl;
    } else {
        cout << "Queue is not empty" << endl;
    }

    return 0;
}

Deque

C++ Deque Functions

Basic Operations

begin(): Returns an iterator to the first element.
end(): Returns an iterator to the past-the-end element.
rbegin(): Returns a reverse iterator to the last element.
rend(): Returns a reverse iterator to the past-the-end element in reverse order.
clear(): Removes all elements from the deque.
empty(): Checks if the deque is empty.
size(): Returns the number of elements in the deque.
max_size(): Returns the maximum possible size of the deque.

Element Access

front(): Returns a reference to the first element.
back(): Returns a reference to the last element.

Modifiers

push_front(value): Inserts an element at the beginning.
push_back(value): Inserts an element at the end.
pop_front(): Removes the first element.
pop_back(): Removes the last element.
insert(position, value): Inserts an element at a specified position.
erase(position): Removes an element at a specified position.
erase(first, last): Removes a range of elements.

Iterators

iterator: A bidirectional iterator to elements in the deque.
reverse_iterator: A bidirectional iterator to elements in the deque in reverse order.

Example Usage:

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> myDeque;

    // Insert elements
    myDeque.push_back(10);
    myDeque.push_front(20);
    myDeque.insert(myDeque.begin() + 1, 15);

    // Access elements
    cout << myDeque.front() << endl;
    cout << myDeque.back() << endl;

    // Iterate over elements
    for (auto it : myDeque) {
        cout << it << " ";
    }
    cout << endl;

    return 0;
}

Heap

C++ Heap Functions

Basic Operations

make_heap(begin, end): Creates a max heap from a range of elements.
push_heap(begin, end): Pushes an element onto the heap.
pop_heap(begin, end): Removes the root element from the heap.
sort_heap(begin, end): Sorts a heap into ascending order.

Other Operations

is_heap(begin, end): Checks if a range of elements is a heap.
is_heap_until(begin, end): Checks if a range of elements is a heap, returning an iterator to the first element that violates the heap property.
nth_element(begin, nth, end): Rearranges the elements in a range such that the nth element is in its sorted position.

Example Usage:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> data = {5, 2, 8, 1, 9, 3};

    // Create a max heap
    make_heap(data.begin(), data.end());

    // Push an element onto the heap
    data.push_back(7);
    push_heap(data.begin(), data.end());

    // Pop the root element
    pop_heap(data.begin(), data.end());
    data.pop_back();

    // Sort the heap
    sort_heap(data.begin(), data.end());

    // Print the sorted data
    for (int num : data) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Making Heap from scratch using Vectors

A heap is a special kind of binary tree where every node is greater than or equal to (in a max heap) or less than or equal to (in a min heap) its children. This property is called the heap property. Heaps are often used to implement priority queues.

Types of Heaps

Max Heap: Every node is greater than or equal to its children.
Min Heap: Every node is less than or equal to its children.

Operations on Heaps

Insertion: Adds a new element to the heap while maintaining the heap property.
Deletion: Removes the root element (maximum or minimum) from the heap and restores the heap property.
Heapify: Converts a binary tree into a heap.
Build Heap: Constructs a heap from an array of elements.

Implementation Using Vectors

#include <vector>

template <typename T>
class Heap {
public:
    explicit Heap(const std::vector<T>& elements) : data(elements) {
        buildHeap();
    }

    void push(const T& element) {
        data.push_back(element);
        siftUp(data.size() - 1);
    }

    T pop() {
        if (data.empty()) {
            throw std::out_of_range("Heap is empty");
        }
        std::swap(data[0], data.back());
        data.pop_back();
        siftDown(0);
        return data[0];
    }

    T top() const {
        if (data.empty()) {
            throw std::out_of_range("Heap is empty");
        }
        return data[0];
    }

    bool empty() const {
        return data.empty();
    }

private:
    std::vector<T> data;

    void siftUp(int index) {
        while (index > 0 && data[index] > data[(index - 1) / 2]) {
            std::swap(data[index], data[(index - 1) / 2]);
            index = (index - 1) / 2;
        }
    }

    void siftDown(int index) {
        int largest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < data.size() && data[leftChild] > data[largest]) {
            largest = leftChild;
        }

        if (rightChild < data.size() && data[rightChild] > data[largest]) {
            largest = rightChild;
        }

        if (largest != index) {
            std::swap(data[index], data[largest]);
            siftDown(largest);
        }
    }

    void buildHeap() {
        for (int i = data.size() / 2 - 1; i >= 0; --i) {
            siftDown(i);
        }
    }
};

Priority Queue

C++ Priority Queue Functions

Basic Operations

empty(): Checks if the priority queue is empty.
size(): Returns the number of elements in the priority queue.
top(): Returns a reference to the top element (highest priority).
push(value): Inserts an element into the priority queue.
pop(): Removes the top element from the priority queue.

Custom Comparator

priority_queue<T, container, Compare>: Creates a priority queue using a custom comparator.

Example Usage:

#include <iostream>
#include <queue>

using namespace std;

struct Compare {
    bool operator()(int a, int b) {
        return a > b; // Create a min heap
    }
};

int main() {
    // Create a max heap using the default comparator
    priority_queue<int> maxHeap;

    // Create a min heap using a custom comparator
    priority_queue<int, vector<int>, Compare> minHeap;

    // Add elements to the heaps
    maxHeap.push(5);
    maxHeap.push(2);
    maxHeap.push(8);

    minHeap.push(5);
    minHeap.push(2);
    minHeap.push(8);

    // Access and remove elements
    cout << "Max Heap: ";
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    cout << endl;

    cout << "Min Heap: ";
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;

    return 0;
}

With Pairs:

#include <iostream>
#include <queue>
using namespace std;
 
// Function to print the data of
// the priority queue ordered by first
void showpq(priority_queue<pair<int,int> , vector<pair<int,int>>, greater<pair<int,int>> > g)
{
    // Loop to print the elements
    // until the priority queue
    // is not empty
    while (!g.empty()) {
        cout << g.top().first
             << " " << g.top().second
             << endl;
        g.pop();
    }
    cout << endl;
}
 
// Driver Code
int main()
{
  // Min heap
    priority_queue<pair<int,int> , vector<pair<int,int>>, greater<pair<int,int>> > p1;
 
    // Insertion of elements
    p1.push(make_pair(4, 5));
    p1.push(make_pair(5, 4));
    p1.push(make_pair(1, 6));
    p1.push(make_pair(7, 3));
    p1.push(make_pair(9, 4));
    showpq(p1);
    return 0;
}