C++ Cheatsheet

Photo by Sawyer Bengtson on Unsplash

std::vector

unsigned int size = v.size();

// takes in iterator
v.insert(v.begin(), value); // add to head O(n)
v.insert(v.begin()+index, value); // add to index o(n)
v.push_back(value); // add to tail o(1)

int head = v.front(); // get head o(1)
or
int head = v[0];

int val = v.at(index);
int val = v[index];

int tail = v.back();
int tail = v[v.size()-1];

// iterating
// erase takes in an iterator...coud be v.erase(it)
v.erase(v.begin()); // remove head, o(n)
v.erase(v.begin()+index); // iterator plus count o(n)
v.pop_back() // remove tail. Does not return the last element. o(1)

// clear
v.clear();


for(auto it = v.begin(); it!=v.end(); i++){
  printf("%d\n", *it);
}

for(auto &elem: v){
  elem *= 2; // modifies actual element
}

Vector is implemented by using an array that doubles in size each time the capacity is hit.

How to implement vector?

• only implement push_back() and get()

template<typename T>
class Vector{
  public:
    size_t numElements;
    size_t capacity;
    T* data;
    
    // This is a way to initialise variables before running the constructor
    Vector() : numElements(0), capacity(0), data(nullptr) {}

    // Dereferencing
    ~Vector(){
      delete[] data;
    }

    void push_back(T& element){
      if(numElements == capacity){
        // need to increase size
        capacity = capacity * 2;
        if(capacity == 0){
          capacity = 8; // default size
        }
        T* temp = new T[capacity];
        for(size_t i=0; i<numElements; i++){
          temp[i]=data[i];
        }
        delete []data;
        data = temp;
      }
      data[numElements++] = element;
    }

    T* get(int index){
      if(index>=numElements) return nullptr;
      return &data[index];
    }
}


int main() {
    Vector<int> myVector;
    myVector.push_back(2);
    myVector.push_back(3);
    myVector.push_back(4);
    myVector.push_back(5);

    myVector.print();

    int* element = myVector.get(2);
    if (element) {
        std::cout << *element << std::endl;
    }

    return 0;
}

std::deque

Similar to vector but has more efficient push_front and pop_front.

Pronounced ‘deck’, stands for double ended queue.

It is sequence container with the feature of expansion and contraction on both ends. Contiguous storage allocation may not be guaranteed.

Reference: https://thispointer.com/what-is-stddeque-and-how-deque-works-internally/

• When we insert an element in end it stores that in allocated memory block untill it gets filled and when this memory block gets filled with elements then it allocates a new memory block and links it with the end of previous memory block. Now further inserted elements in the back are stored in this new memory block.
• When we insert an element in front it allocates a new memory block and links it with the front of previous memory block. Now further inserted elements in the front are stored in this new memory block unless it gets filled.
• Consider deque as a linked list of vectors i.e. each node of this linked list is a memory block that store elements at contiguous memory location and each of the memory block node is linked with its previous and next memory block node.
• Therefore, insertion at front is fast as compared to vector because it doesn’t need the elements to shift by 1 in current memory block to make space at front. It just checks if any space is left at left of first element in current memory block, if not then allocates a new memory block.

std::deque<int> d;

//---------------------------------
// General Operations
//---------------------------------

// Insert head, index, tail
d.push_front(value);                    // head O(1)
d.insert(d.begin() + index, value);     // index O(n)
d.push_back(value);                     // tail O(1)

// Access head, index, tail, O(1)
int head = d.front();       // head 
int value = d.at(index);    // index
int tail = d.back();        // tail

// Size
unsigned int size = d.size();

// Iterate
for(std::deque<int>::iterator it = d.begin(); it != d.end(); it++) {
    std::cout << *it << std::endl;
}

// Remove head, index, tail
d.pop_front();                  // head, O(1)
d.erase(d.begin() + index);     // index, O(n)
d.pop_back();                   // tail, O(1)

// Clear
d.clear();

Chat GPT given code

#include <iostream>
#include <vector>

template <typename T>
class Deque {
private:
  std::vector<T*> blocks;  // Vector of pointers to blocks
  std::vector<size_t> block_sizes;  // Vector of block sizes
  size_t front_block;  // Index of the front block
  size_t back_block;  // Index of the back block
  size_t front_index;  // Index of the front element in the front block
  size_t back_index;  // Index of the back element in the back block

public:
  Deque() {
    front_block = back_block = front_index = back_index = 0;
    blocks.push_back(new T[1]);
    block_sizes.push_back(1);
  }

  ~Deque() {
    for (auto& block : blocks) {
      delete[] block;
    }
  }

  void push_front(const T& value) {
    if (front_index == 0) {
      if (front_block == 0) {
        blocks.insert(blocks.begin(), new T[1]);
        block_sizes.insert(block_sizes.begin(), 1);
        ++back_block;
      }
      else {
        --front_block;
        front_index = block_sizes[front_block] - 1;
      }
    }
    else {
      --front_index;
    }

    blocks[front_block][front_index] = value;
  }

  void pop_front() {
    if (front_index == block_sizes[front_block] - 1) {
      if (front_block == back_block) {
        front_index = back_index = 0;
      }
      else {
        delete[] blocks[front_block];
        blocks.erase(blocks.begin() + front_block);
        block_sizes.erase(block_sizes.begin() + front_block);
        ++front_block;
        front_index = 0;
      }
    }
    else {
      ++front_index;
    }
  }

  void push_back(const T& value) {
    if (back_index == block_sizes[back_block] - 1) {
      if (back_block == blocks.size() - 1) {
        blocks.push_back(new T[1]);
        block_sizes.push_back(1);
      }
      else {
        ++back_block;
        back_index = 0;
      }
    }
    else {
      ++back_index;
    }

    blocks[back_block][back_index] = value;
  }

  void pop_back() {
    if (back_index == 0) {
      if (front_block == back_block) {
        front_index = back_index = 0;
      }
      else {
        delete[] blocks[back_block];
        blocks.erase(blocks.begin() + back_block);
        block_sizes.erase(block_sizes.begin() + back_block);
        --back_block;
        back_index = block_sizes[back_block] - 1;
      }
    }
    else {
      --back_index;
    }
  }

  T& front() {
    return blocks[front_block][front_index];
  }

  T& back() {
    return blocks[back_block][back_index];
  }

  bool empty() const {
    return (front_block == back_block) && (front_index == back_index);
  }
};

std::list and std::forward_list

Use for insertion into the middle/beginning of the list

Efficient sorting (pointer swap vs copying)

Doubly-linked list…

It does not support index notation like list[idx]…need to use iterator.

std::list<int> l;

//---------------------------------
// General Operations
//---------------------------------

// Insert head, index, tail
l.push_front(value);                    // head, O(1)
l.insert(l.begin() + index, value);     // index, O(n)
l.push_back(value);                     // tail, O(1)

// Access head, index, tail
int head = l.front();                                           // head
int value = std::next(l.begin(), index);          // index
int tail = l.back();                                            // tail

// Size
unsigned int size = l.size();

// Iterate
for(std::list<int>::iterator it = l.begin(); it != l.end(); it++) {
    std::cout << *it << std::endl;
}

// Remove head, index, tail
l.pop_front();                  // head
l.erase(l.begin() + index);     // index
l.pop_back();                   // tail

// Clear
l.clear();

//---------------------------------
// Container-Specific Operations
//---------------------------------

// Splice: Transfer elements from list to list
// splice(iterator pos, list &x)
//   splice(iterator pos, list &x, iterator i)
//   splice(iterator pos, list &x, iterator first, iterator last)
l.splice(l.begin() + index, list2);

// Remove: Remove an element by value
l.remove(value);

// Unique: Remove duplicates
l.unique();

// Merge: Merge two sorted lists
l.merge(list2);

// Sort: Sort the list
l.sort();

// Reverse: Reverse the list order
l.reverse();

std::map, std::unordered_map

• Map: Ordered search tree. Similar to TreeMap -> Implemented using AVL tree.
• Unordered Map: Hash table.

std::map<std::string, std::string> m;
std::unordered_map<KEY, VALUE> m2;

//---------------------------------
// General Operations
//---------------------------------

// Insert
m.insert(std::pair<std::string, std::string>("key", "value"));
m["a"] = "b"; // O(1) for unordered map, O(logn) for map

// Access by key
std::string value = m.at("key"); // O(1) for unordered map, O(logn) for map
m["key"]; 

// Size
unsigned int size = m.size();

// Iterate
for(std::map<std::string, std::string>::iterator it = m.begin(); it != m.end(); it++) {
    std::cout << (*it).first << " " << (*it).second << std::endl;
}

// Remove by key
m.erase("key"); // O(1) for unordered map, O(logn) for map

// Clear
m.clear();

//---------------------------------
// Container-Specific Operations
//---------------------------------

// Find if an element exists by key
bool exists = (m.find("key") != m.end());

// Count the number of elements with a certain key
unsigned int count = m.count("key");


// Defining order
std::map<MyClass, int, [](const MyClass& a, const MyClass& b) {
        return a.id < b.id;
}> myMap;

std::set

They are implemented like std::map and std::unordered_map, but since they don’t store values, their iterator types point to T objects rather than pairs and they do not support map[key] bracket notation.

std::set<int> s;

//---------------------------------
// General Operations
//---------------------------------

// Insert
s.insert(20);

// Size
unsigned int size = s.size();

// Iterate
for(std::set<int>::iterator it = s.begin(); it != s.end(); it++) {
    std::cout << *it << std::endl;
}

// Remove
s.erase(20);

// Clear
s.clear();

//---------------------------------
// Container-Specific Operations
//---------------------------------

// Find if an element exists
bool exists = (s.find(20) != s.end());

// Count the number of elements with a certain value
unsigned int count = s.count(20);

std::stack

std::stack<int> s;

//---------------------------------
// Container-Specific Operations
//---------------------------------

// Push O(1)
s.push(20);

// Size
unsigned int size = s.size();

// Pop O(1)
s.pop();

// Top O(1)
int top = s.top();

std::queue

• Often implemented as std::queue

#include <queue>

std::queue<int> q;

//---------------------------------
// General Operations
//---------------------------------

// Insert
q.push(value);

// Access head, tail
int head = q.front();       // head
int tail = q.back();        // tail

// Size
unsigned int size = q.size();

// Remove
q.pop();

std::priority_queue

#include <queue>

std::priority_queue<int> p;

//---------------------------------
// General Operations
//---------------------------------

// Insert
p.push(value);

// Access
int top = p.top();  // 'Top' element

// Size
unsigned int size = p.size();

// Remove
p.pop();


// compare//the following 2 ways works
std::priority_queue<MyStruct, std::vector<MyStruct>, decltype([](const MyStruct& a, const MyStruct& b) {
    return a.value - b.value;
})> pq([](const MyStruct& a, const MyStruct& b) {
    return a.value - b.value;
});


auto compare = [](const MyStruct& a, const MyStruct& b) {
    return a.value - b.value;
};
std::priority_queue<MyStruct, std::vector<MyStruct>, decltype(compare)> pq(compare);

decltype is a C++ keyword that allows you to deduce the type of an expression at compile-time. It is often used to declare variables or specify types based on the result of an expression.

The syntax of decltype is decltype(expression), where expression is the expression for which you want to determine the type. The result of decltype(expression) is the type of the expression.

// example of usage

int x = 5;
decltype(x) y = 10;  // y is of type int, deduced from the expression x

Malloc or New

Generally it is recommended to use new and delete. New not only allocates memory but also calls the constructor to initialise the object and destructor to clean up the object before freeing the memory.

Good for Object oriented programming.

Only if you are using legacy code or using C libraries, you can use malloc and free.

Apart from these 2 methods, we can also use smart pointers. Smart pointers take care of automatic deallocation and we don’t need to explicitly call delete[].

• std::unique_ptr
• std::shared_ptr (If multiple pointers need to share ownership of the dynamically allocated array).

#include <iostream>
#include <memory> // Include the <memory> header for smart pointers

int main() {
    int size;
    std::cout << "Enter the size of the array: ";
    std::cin >> size;

    // Use std::unique_ptr to dynamically allocate memory for the array
    std::unique_ptr<int[]> arr = std::make_unique<int[]>(size);

    // Populate the array with values
    for (int i = 0; i < size; ++i) {
        arr[i] = i * 10;
    }

    // Print the array
    for (int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    // No explicit deallocation needed. Memory is automatically released.

    return 0;
}

More on shared ptr

• Shared ownership is typically needed in scenarios where multiple entities or components need to access and use a dynamically allocated resource, such as an object or an array, and they need to share the responsibility of managing its lifetime. Eg, database connection, shared data strcuture, caching..

Other resources:

C++ Programming Language

End :)