C++ Essentials for DSA

Chapter 1 · Part 1: FOUNDATIONS · Est. 31 min read

Chapter Goal: Build a rock-solid C++ foundation specifically tuned for DSA problem-solving and FAANG interviews. Every concept introduced here will be referenced repeatedly throughout this guide. Master this chapter before moving on.

1.1 Data Types, Sizes & Limits

Understanding the exact size and range of every data type is non-negotiable in interviews. Integer overflow is one of the single most common sources of wrong answers — including from experienced engineers.

Primitive Types at a Glance

Type	Size	Min Value	Max Value	Primary DSA Use Case
`bool`	1 byte	`false` (0)	`true` (1)	Flags, visited arrays
`char`	1 byte	-128	127	Characters, ASCII arithmetic
`unsigned char`	1 byte	0	255	Byte manipulation
`int`	4 bytes	-2,147,483,648	2,147,483,647 (~±2.1×10⁹)	Default choice
`unsigned int`	4 bytes	0	4,294,967,295 (~4.3×10⁹)	When no negatives
`long long`	8 bytes	-9.2×10¹⁸	9.2×10¹⁸	Large sums, products
`unsigned long long`	8 bytes	0	1.8×10¹⁹	Very large positives
`float`	4 bytes	~±3.4×10³⁸	~±3.4×10³⁸	Rarely used in DSA
`double`	8 bytes	~±1.8×10³⁰⁸	~±1.8×10³⁰⁸	Geometry, precision
`size_t`	4 or 8 bytes	0	Platform max	Container sizes

Warning: Platform Note: On most 64-bit systems (including all FAANG interview environments), int is 4 bytes and long long is 8 bytes. Always assume this.

Limit Constants

Include <climits> (C-style) or use <limits> (modern C++) to access bounds.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    // C-style macros from <climits>
    cout << INT_MAX      << "\n"; // 2147483647
    cout << INT_MIN      << "\n"; // -2147483648
    cout << LLONG_MAX    << "\n"; // 9223372036854775807
    cout << LLONG_MIN    << "\n"; // -9223372036854775808
 
    // Modern C++ from <limits>
    cout << numeric_limits<int>::max()       << "\n"; // 2147483647
    cout << numeric_limits<long long>::max() << "\n"; // 9223372036854775807
    cout << numeric_limits<double>::max()    << "\n"; // ~1.8e+308
 
    // Useful derived constants you will write constantly
    const int   INF   = INT_MAX;       // Infinity sentinel for int
    const long long LINF = LLONG_MAX;  // Infinity sentinel for long long
    const int   MOD   = 1e9 + 7;       // Standard modulus in competitive problems
    const int   MOD2  = 998244353;     // Alternative prime modulus
}

The Golden Rule: When to Use `long long`

This is one of the most common bugs in interviews. Know this cold.

Use long long whenever any intermediate value might exceed ±2.1 × 10⁹.

// --- SCENARIO 1: Large multiplication ---
int n = 100000;
 
int wrong  = n * n;                         // ❌ n*n = 10^10 > INT_MAX → Overflow
long long right = (long long)n * n;         // ✅ Cast BEFORE multiplying
 
// --- SCENARIO 2: Sum of large values ---
// n up to 10^5, each value up to 10^9 → total sum up to 10^14
int arr[5] = {1000000000, 1000000000, 1000000000, 1000000000, 1000000000};
long long sum = 0;
for (int x : arr) sum += x;    // ✅ sum accumulator is long long
 
// --- SCENARIO 3: Modular arithmetic ---
const int MOD = 1e9 + 7;
int x = 1e9, y = 1e9;
 
int bad  = (x + y) % MOD;                  // ❌ x+y overflows BEFORE % applies
long long good = ((long long)x + y) % MOD; // ✅ Use long long for intermediate
 
// --- SCENARIO 4: Combinatorics ---
// n*(n-1)/2 for n=100000 = ~5×10^9 → overflows int
int pairs_wrong = n * (n - 1) / 2;                         // ❌ Overflow
long long pairs_right = (long long)n * (n - 1) / 2;        // ✅

Quick mental check: If n ≤ 10⁴, int is safe. If n ≤ 10⁵ or above, think twice before using int for products or sums.

Type Conversions & Casting

// Implicit narrowing (dangerous!)
long long ll = 10000000000LL;
int n = ll;           // ❌ Silent truncation — n gets a garbage value
 
// Explicit casting
int a = 5, b = 2;
double result = (double)a / b;      // 2.5 — cast before division
double result2 = a / b;             // 2.0 — integer division first, then convert
 
// Numeric literal suffixes
long long big  = 3000000000LL;      // Suffix LL: long long literal
float  f       = 3.14f;             // Suffix f: float literal
double d       = 3.14;              // Default floating-point literal is double
unsigned int u = 100u;              // Suffix u: unsigned

1.2 References & Pointers

References — An Alias

A reference is simply another name for an existing variable. It is bound at declaration and cannot be rebound to a different variable. Under the hood the compiler typically implements it as a pointer, but you never deal with addresses directly.

int a = 10;
int& ref = a;       // ref is an alias for a
 
ref = 20;           // Modifies a
cout << a;          // 20 ✅
 
int& bad;           // ❌ Compile error: reference MUST be initialized

Key properties of references:

Must be initialized at declaration.
Cannot be null.
Cannot be rebound after initialization.
Behave exactly like the original variable in usage.

Pointers — Storing an Address

A pointer stores the memory address of another variable. Unlike a reference, it can be null, can be reassigned, and supports arithmetic.

int a = 10;
int* ptr = &a;          // ptr holds address of a (e.g., 0x7ffd5...)
 
cout << ptr;            // Prints the address
cout << *ptr;           // Dereference: prints 10
cout << &ptr;           // Address of the pointer itself
 
*ptr = 20;              // Modifies a through the pointer
cout << a;              // 20
 
int* null_ptr = nullptr;    // Null pointer — always use nullptr, not NULL or 0

Key properties of pointers:

Can be nullptr.
Can be reassigned to point to a different variable.
Support arithmetic (ptr++ advances to next element).
Must be dereferenced (*ptr) to access the value.

Reference vs. Pointer — Comparison Table

Feature	Reference (`int& r`)	Pointer (`int* p`)
Can be null	Never	`nullptr`
Must initialize	Always	Optional (dangerous)
Rebindable	No	Yes
Arithmetic	No	Yes (`p++`)
Syntax to access	`r` directly	`*p` (dereference)
Address of variable	`&a` creates it	`&a` assigns it
DSA primary use	Function params	Linked list / tree nodes

Pointer-to-Const, Const-Pointer, and Const-Pointer-to-Const

This trips up many candidates. The rule: read from right to left.

int val = 10;
 
const int* ptr1 = &val;     // Pointer to CONST int
                            // Can change ptr1 (make it point elsewhere)
                            // Cannot change *ptr1 (the value)
*ptr1 = 20;                 // ❌ Error
ptr1 = nullptr;             // ✅ OK
 
int* const ptr2 = &val;     // CONST pointer to int
                            // Cannot change ptr2 (it's fixed to &val)
                            // Can change *ptr2 (the value)
*ptr2 = 20;                 // ✅ OK
ptr2 = nullptr;             // ❌ Error
 
const int* const ptr3 = &val; // CONST pointer to CONST int
                              // Cannot change ptr3 or *ptr3
*ptr3 = 20;                   // ❌ Error
ptr3 = nullptr;               // ❌ Error

In DSA, the most important form is const int* ptr (or const vector<int>& v) — it signals "I'm reading, not modifying."

When to Use References vs. Pointers in DSA

// ✅ REFERENCES — Function parameters you want to modify
void swap(int& a, int& b) {
    int temp = a; a = b; b = temp;
}
 
// ✅ REFERENCES — Large objects you want to read without copying
void printGraph(const vector<vector<int>>& adj) {
    for (auto& neighbors : adj) {
        for (int v : neighbors) cout << v << " ";
    }
}
 
// ✅ POINTERS — Tree and linked list nodes (null is meaningful here)
struct TreeNode {
    int val;
    TreeNode* left;    // nullptr = no left child
    TreeNode* right;   // nullptr = no right child
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
// ✅ POINTERS — When you need to reassign (e.g. traversing a list)
ListNode* curr = head;
while (curr != nullptr) {
    curr = curr->next;  // Reassigning pointer
}

1.3 Pass by Value vs. Reference vs. Pointer

The choice of how you pass arguments directly affects correctness, performance, and readability. Getting this wrong is a common interview mistake.

Pass by Value — A Copy Is Made

The function receives a copy of the argument. Modifications inside the function do NOT affect the original. This is safe but expensive for large objects.

void increment(int n) {
    n++;    // Modifies only the local copy
}
 
int main() {
    int x = 5;
    increment(x);
    cout << x;    // Still 5 — original unchanged
}

Use when: The parameter is a primitive type (int, double, char, bool) and you do not need to modify the original.

Pass by Reference — Alias to the Original

The function receives a direct alias. Modifications affect the original. No copy is made — this is O(1) regardless of object size.

void increment(int& n) {
    n++;    // Modifies the original
}
 
int main() {
    int x = 5;
    increment(x);
    cout << x;    // 6 ✅
}

Const Reference — Read Without Copying (Most Common Pattern)

// ✅ Pass large objects by const reference — no copy, no modification
void processVector(const vector<int>& v) {
    for (int x : v) cout << x << " ";
    // v.push_back(99);  ← ❌ Compile error: v is const
}
 
// ✅ This applies to strings too
void printWord(const string& word) {
    cout << word;
}

Use when: You want to modify the original, or you want to read a large object without the copy overhead.

Pass by Pointer — Explicit Address

The function receives the address of the variable. Modifications through the pointer affect the original. Allows nullptr to represent "no argument."

void increment(int* ptr) {
    if (ptr != nullptr)
        (*ptr)++;
}
 
int main() {
    int x = 5;
    increment(&x);   // Explicitly pass address
    cout << x;       // 6 ✅
 
    increment(nullptr);  // Safe due to null check
}

Use when: The parameter might logically be absent (nullptr), or when working with tree/linked-list nodes that are already pointer types.

Decision Guide — Which to Use

Is the parameter a primitive (int, char, bool, double)?
  └── You need to modify the original?
        YES → Pass by reference:       void f(int& n)
        NO  → Pass by value:           void f(int n)

Is the parameter a complex type (vector, string, struct, class)?
  └── You need to modify the original?
        YES → Pass by reference:       void f(vector<int>& v)
        NO  → Pass by const reference: void f(const vector<int>& v)

Is null a meaningful state (optional param, tree/list node)?
  └── Use pointer:                     void f(TreeNode* node)

Side-by-Side Comparison

// All three do the same thing (double a value) differently:
 
void doubleVal_ByValue(int n)    { n *= 2; }          // Original unchanged!
void doubleVal_ByRef  (int& n)   { n *= 2; }          // Original changed ✅
void doubleVal_ByPtr  (int* ptr) { *ptr *= 2; }       // Original changed ✅
 
int main() {
    int a = 5, b = 5, c = 5;
    doubleVal_ByValue(a);   cout << a;  // 5  ← unchanged
    doubleVal_ByRef(b);     cout << b;  // 10 ← changed ✅
    doubleVal_ByPtr(&c);    cout << c;  // 10 ← changed ✅
}

1.4 Stack Memory vs. Heap Memory

Understanding memory layout is critical for writing correct recursive solutions and avoiding stack overflows — a very real issue in coding interviews.

The Stack

The call stack is a fixed-size, LIFO region of memory managed automatically by the CPU. Every time you call a function, a stack frame is pushed containing:

The function's local variables
Parameters
Return address

When the function returns, its frame is popped automatically.

int add(int a, int b) {
    int result = a + b;     // 'result', 'a', 'b' live on the stack
    return result;
}                           // Frame popped, memory reclaimed automatically
 
// Stack size is limited (~1–8 MB depending on OS)
// Typical max recursion depth: ~10,000–50,000 frames

Stack Overflow from Recursion:

// ❌ This will crash for large n — each call occupies a stack frame
int fib(int n) {
    return (n <= 1) ? n : fib(n-1) + fib(n-2);
}
fib(1000000);   // CRASH: Stack overflow
 
// ✅ Use memoization or iterative DP for deep recursion

Rule of thumb: If recursion depth might exceed ~10,000, convert to iterative.

The Heap

The heap is a large, dynamically managed memory region. You control allocation and deallocation with new and delete. It persists until explicitly freed or the program exits.

// Allocate on heap
int* arr = new int[1000000];    // 4 MB — fine on heap
arr[0] = 42;
delete[] arr;                   // Warning: Must free! Otherwise: memory leak
 
// Modern C++ — prefer smart pointers (auto-cleanup)
#include <memory>
auto arr = make_unique<int[]>(1000000);   // Auto-freed when out of scope
auto obj = make_shared<TreeNode>(42);    // Reference-counted

Why This Matters for DSA

// ❌ Large 2D array on stack — Stack Overflow!
void solve() {
    int dp[1001][1001];         // ~4 MB on stack → crash
}
 
// ✅ Option 1: Declare globally (goes to BSS/data segment, not stack)
int dp[1001][1001];             // Global — safe
 
// ✅ Option 2: Use vector (allocated on heap)
vector<vector<int>> dp(1001, vector<int>(1001, 0));
 
// ✅ Option 3: static local (stored in data segment)
void solve() {
    static int dp[1001][1001];  // Same as global lifetime
}

Stack vs. Heap Summary

	Stack	Heap
Size	~1–8 MB	Limited by RAM (GBs)
Speed	Very fast (hardware-managed)	Slower (allocator overhead)
Management	Automatic (LIFO)	Manual (`new` / `delete`)
Lifetime	Scope-bound	Manual control
Fragmentation	None	Can fragment over time
DSA use	Local vars, recursion frames	Nodes, large arrays, vectors

Heap Allocation in Tree and Graph Problems

// In practice, you almost never manually new/delete in interviews —
// LeetCode/interviewers hand you pre-built nodes.
// But you must understand this for correctness:
 
TreeNode* buildTree() {
    TreeNode* root = new TreeNode(1);       // Heap
    root->left     = new TreeNode(2);       // Heap
    root->right    = new TreeNode(3);       // Heap
    return root;
}
 
// After use:
void deleteTree(TreeNode* root) {
    if (!root) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

1.5 `const`, `constexpr` & `static`

`const` — Read-Only Variables

Once initialized, a const variable cannot be changed.

const int MAX_N = 100005;   // Cannot be changed later
MAX_N = 200000;             // ❌ Compile error
 
// Best practice: use const for any variable you don't intend to modify
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);   // ✅ Precise PI value

const in Function Signatures (Critical Pattern)

// const reference parameter: read-only, no copy — BEST practice for large objects
void process(const vector<int>& v);
 
// const method (for class methods): does not modify the object
int getSize() const { return size; }
 
// Returning const reference: caller cannot modify the returned value
const vector<int>& getData() const { return data; }

`constexpr` — Compile-Time Evaluation

constexpr tells the compiler to evaluate the expression at compile time. This makes constants zero-cost and prevents accidental misuse.

constexpr int MOD  = 1e9 + 7;      // Evaluated at compile time
constexpr int MAXN = 100005;        // Use for array sizes
constexpr int MAXV = 200005;
 
// constexpr function — computed at compile time when inputs are constant
constexpr long long power(long long base, long long exp) {
    return (exp == 0) ? 1 : base * power(base, exp - 1);
}
constexpr long long val = power(2, 10);   // Computed at compile time: 1024

const vs constexpr:

	`const`	`constexpr`
When evaluated	Runtime or compile time	Always compile time
Use for	Read-only variables	True compile-time constants
Functions	N/A	Can mark functions
Prefer for	Parameters, member vars	Global limits, array sizes

// Prefer constexpr for array sizes and limits
constexpr int MAXN = 100005;
int dist[MAXN];     // ✅ Fine — MAXN is a compile-time constant

`static` — Persistent Storage

Static local variable: Initialized only once, persists for the program's lifetime.

int generateId() {
    static int id = 0;  // Initialized only the first time this function is called
    return ++id;
}
// generateId() → 1
// generateId() → 2
// generateId() → 3 ...

Static in DSA context — avoiding stack overflow for large arrays:

void solve() {
    static int dp[1001][1001] = {};  // Stored in data segment, not stack ✅
    // ... fill dp
}

Static class members — shared across all instances:

struct DSU {
    static int parent[100005];  // One array shared by all DSU instances
    static int rank_[100005];
};

1.6 Lambda Expressions & `auto`

Lambda — Anonymous Inline Functions

Lambdas are one of the most powerful modern C++ features for DSA. They let you define custom logic inline — especially for sorting, priority queues, and algorithm predicates.

Basic Syntax:

[capture list](parameters) -> return_type { body }

// Simplest lambda
auto sayHello = []() { cout << "Hello\n"; };
sayHello();   // Prints: Hello
 
// Lambda with parameters
auto add = [](int a, int b) { return a + b; };
cout << add(3, 4);   // 7
 
// Lambda with explicit return type
auto safeDivide = [](double a, double b) -> double {
    return (b != 0) ? a / b : 0.0;
};

Capture Modes — Accessing Outer Variables

int x = 10, y = 20;
 
// Capture by VALUE — lambda gets a copy of x
auto f1 = [x]() { cout << x; };    // x = 10 even if x changes later
x = 99;
f1();   // Still prints 10
 
// Capture by REFERENCE — lambda accesses the original
auto f2 = [&x]() { x++; };
f2();   // x is now 100
 
// Capture ALL local variables by value
auto f3 = [=]() { cout << x + y; };
 
// Capture ALL local variables by reference
auto f4 = [&]() { x = 0; y = 0; };
 
// Mixed capture
auto f5 = [x, &y]() { y = x * 2; };   // x by value, y by reference

Lambdas as Comparators — The #1 Interview Use Case

Sorting with a custom comparator:

vector<pair<int,int>> intervals = {{1,3}, {0,8}, {2,6}, {3,5}};
 
// Sort by start time (ascending)
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
    return a.first < b.first;
});
 
// Sort by end time (ascending) — Greedy interval problems
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
    return a.second < b.second;
});
 
// Sort by length (end - start), ascending
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
    return (a.second - a.first) < (b.second - b.first);
});

priority_queue with a custom comparator:

// Default priority_queue is a MAX-heap
priority_queue<int> maxHeap;   // Largest on top
 
// MIN-heap using greater<int>
priority_queue<int, vector<int>, greater<int>> minHeap;
 
// MIN-heap using a lambda (for complex types)
auto cmp = [](const pair<int,int>& a, const pair<int,int>& b) {
    return a.first > b.first;   // NOTE: > for min-heap (inverted from sort!)
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
 
// Example: Dijkstra's min-heap {distance, node}
pq.push({0, src});
while (!pq.empty()) {
    auto [dist, u] = pq.top(); pq.pop();
    // process...
}

Warning: Common Confusion: In sort, returning a < b gives ascending order. In priority_queue, returning a > b gives a min-heap (smallest on top). The comparator for priority_queue returns true when a should be lower priority (further from the top).

`auto` — Type Deduction

auto asks the compiler to deduce the type. It reduces boilerplate and is especially useful with complex STL types.

auto x = 42;                        // int
auto y = 3.14;                      // double
auto z = 42LL;                      // long long
 
// Replaces verbose iterator types
map<string, vector<int>> myMap;
auto it = myMap.find("key");        // vs: map<string, vector<int>>::iterator it
 
// In range-based for loops
vector<pair<int,string>> v = {{1,"a"},{2,"b"}};
for (auto& p : v) {                 // p is pair<int,string>&
    cout << p.first << " " << p.second << "\n";
}
 
// With structured bindings (C++17)
for (auto& [num, word] : v) {       // Much cleaner!
    cout << num << " " << word << "\n";
}

auto with references — don't forget the &:

vector<int> v = {1, 2, 3};
 
for (auto x : v)  x *= 2;   // ❌ x is a COPY — v unchanged
for (auto& x : v) x *= 2;   // ✅ x is a reference — v is modified

1.7 Must-Know C++11/14/17 Features

Range-Based For Loop

vector<int> v = {1, 2, 3, 4, 5};
 
for (int x : v)     cout << x << " ";  // Read-only copy
for (int& x : v)    x *= 2;            // Modifying — doubles all elements
for (auto& x : v)   cout << x << " "; // Preferred: auto deduces type
 
// Works on arrays too
int arr[] = {1, 2, 3};
for (int x : arr) cout << x << " ";
 
// On strings
string s = "hello";
for (char c : s) cout << c;

`emplace_back` vs. `push_back`

push_back constructs the object then copies/moves it into the container. emplace_back constructs directly in place — avoiding an extra step.

vector<pair<int,int>> v;
 
v.push_back({1, 2});            // Creates a pair, then moves it in
v.push_back(make_pair(1, 2));   // Same
v.emplace_back(1, 2);           // ✅ Constructs pair(1,2) directly in vector
 
// More dramatic example with a struct
struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) { cout << "Constructed!\n"; }
};
vector<Point> pts;
pts.push_back(Point(3, 4));     // "Constructed!" + move
pts.emplace_back(3, 4);         // "Constructed!" only — preferred

Rule: Always prefer emplace_back over push_back for non-trivial types. For primitives and pairs in practice, the difference is negligible, but it is good habit.

Structured Bindings (C++17) — Unpacking Pairs and Tuples

// Unpack a pair
pair<int, string> p = {42, "hello"};
auto [num, str] = p;
cout << num << " " << str;   // 42 hello
 
// Unpack in range-for (extremely common with maps)
unordered_map<string, int> freq = {{"apple", 3}, {"banana", 1}};
for (auto& [fruit, count] : freq) {
    cout << fruit << ": " << count << "\n";
}
 
// Unpack a tuple
tuple<int, double, string> t = {1, 2.5, "hi"};
auto [a, b, c] = t;
 
// In algorithm results
auto [minIt, maxIt] = minmax_element(v.begin(), v.end());
cout << *minIt << " " << *maxIt;

`nullptr` — Always Use This, Not `NULL`

NULL is simply the integer 0, which can cause function overload ambiguity. nullptr has its own type (std::nullptr_t) and always resolves correctly.

void process(int n) { cout << "int version\n"; }
void process(int* p) { cout << "pointer version\n"; }
 
process(NULL);      // ❌ Ambiguous — may call int version!
process(nullptr);   // ✅ Always calls pointer version
 
// In DSA, always initialize pointers to nullptr
TreeNode* root = nullptr;
ListNode* head = nullptr;
 
// Always check before dereferencing
if (root != nullptr) {
    cout << root->val;
}
// Shorthand (nullptr evaluates to false)
if (root) cout << root->val;

String Conversions — Essential for Every Interview

// int / long long → string
string s1 = to_string(42);       // "42"
string s2 = to_string(3.14);     // "3.140000"
 
// string → numeric
int    n  = stoi("42");          // 42
long   l  = stol("42");          // 42
long long ll = stoll("123456789012345"); // large number
double d  = stod("3.14");        // 3.14
float  f  = stof("3.14");        // 3.14f
 
// char ↔ int
char c = 'A';
int ascii = (int)c;              // 65
char back = (char)65;            // 'A'
 
// Digit char → integer value
char digit = '7';
int val = digit - '0';           // 7  (works for '0' through '9')
 
// Lowercase letter → 0-based index
char letter = 'c';
int idx = letter - 'a';         // 2  (works for 'a' through 'z')
 
// Character classification (<cctype>)
isdigit('5');    // true
isalpha('a');    // true
isalnum('3');    // true (alpha or digit)
isupper('A');    // true
islower('a');    // true
isspace(' ');    // true
tolower('A');    // 'a'
toupper('a');    // 'A'

`std::tie` — Lexicographic Multi-Field Comparison

// Compare structs by multiple fields cleanly
struct Person {
    string name;
    int age;
    double score;
 
    bool operator<(const Person& o) const {
        // Sort by name first, then age, then score
        return tie(name, age, score) < tie(o.name, o.age, o.score);
    }
};
 
// Also useful for swap of multiple variables
int a = 1, b = 2, c = 3;
tie(a, b, c) = make_tuple(c, a, b);   // a=3, b=1, c=2

Initializer Lists — Clean Container Construction

vector<int>              v  = {1, 2, 3, 4, 5};
set<int>                 s  = {3, 1, 4, 1, 5};    // {1, 3, 4, 5} (sorted, unique)
unordered_map<string,int> m = {{"a",1},{"b",2},{"c",3}};
pair<int,int>             p = {10, 20};
tuple<int,int,int>        t = {1, 2, 3};

Move Semantics — A Brief, Practical View

You don't need to master move semantics for interviews, but knowing when it kicks in avoids unnecessary copy overhead.

vector<int> a = {1, 2, 3, 4, 5};
 
// std::move transfers ownership — O(1), no element copy
vector<int> b = move(a);
// a is now in a valid but unspecified (usually empty) state
// b has {1,2,3,4,5}
 
// Use when returning large containers from functions
vector<int> buildResult() {
    vector<int> res;
    for (int i = 0; i < 1000000; i++) res.push_back(i);
    return res;    // Modern compilers apply RVO/NRVO — no copy at all
}

1.8 Common Pitfalls & Undefined Behavior

These are the bugs that cause wrong answers in interviews and contests — often silently. Know them cold.

Pitfall 1: Integer Overflow

// ❌ Multiplying two large ints
int a = 100000, b = 100000;
int result = a * b;                    // Overflow: 10^10 > 2.1×10^9
 
// ✅ Cast one operand to long long before multiplying
long long result = (long long)a * b;   // Correct
 
// ❌ Overflow in sum with modular arithmetic
int x = 1000000000, y = 1000000000;
int bad = (x + y) % (int)(1e9 + 7);   // x+y overflows before %
 
// ✅ Intermediate in long long
long long good = ((long long)x + y) % (int)(1e9 + 7);
 
// ❌ For loop accumulator
int sum = 0;
for (int i = 0; i < n; i++) sum += arr[i];  // arr[i] can be up to 10^9
 
// ✅
long long sum = 0;
for (int i = 0; i < n; i++) sum += arr[i];

Pitfall 2: Signed/Unsigned Comparison

vector::size() and string::length() return size_t which is unsigned. Comparing a signed int with an unsigned value causes subtle bugs.

vector<int> v = {1, 2, 3};
 
// ❌ Classic off-by-one bug when v is empty
for (int i = 0; i <= v.size() - 1; i++) { ... }
// If v is empty: v.size() = 0 (unsigned), 0-1 wraps to ~4×10^9 → infinite loop!
 
// ✅ Cast size() to int
for (int i = 0; i < (int)v.size(); i++) { ... }
 
// ✅ Or use the right type
for (size_t i = 0; i < v.size(); i++) { ... }
 
// ✅ Or use range-based for (best)
for (auto& x : v) { ... }

Pitfall 3: Out-of-Bounds Array Access

int arr[5] = {1, 2, 3, 4, 5};   // Valid indices: 0 to 4
 
arr[5]  = 10;    // ❌ UB: index 5 is out of bounds
arr[-1] = 10;    // ❌ UB: negative index
 
// Always validate bounds
if (i >= 0 && i < n) process(arr[i]);
 
// In 2D grids (very common in BFS/DFS)
int rows = 4, cols = 4;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
 
for (int d = 0; d < 4; d++) {
    int nx = x + dx[d], ny = y + dy[d];
    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
        // ✅ Safe to access grid[nx][ny]
    }
}

Pitfall 4: Uninitialized Variables

Local variables in C++ are NOT zero-initialized by default. They contain whatever garbage was in that memory location.

int x;               // ❌ Garbage value — may be 0, may be anything
bool found;          // ❌ Garbage — may be true or false
 
int arr[100];        // ❌ All elements have garbage values
cout << arr[0];      // Could print anything
 
// ✅ Always initialize
int x = 0;
bool found = false;
int arr[100] = {};              // Zero-initializes the entire array
vector<int> v(100, 0);         // All zeros
 
// ✅ Global and static variables ARE zero-initialized
int global_arr[100];            // All zeros — safe
static int static_arr[100];    // All zeros — safe

Pitfall 5: Floating Point Comparison

Due to binary representation, floating-point arithmetic is rarely exact.

double a = 0.1 + 0.2;
 
if (a == 0.3)          { cout << "Equal\n"; }    // ❌ May NOT print!
if (a == 0.30000000004){ cout << "Equal\n"; }    // More like this internally
 
// ✅ Use epsilon (tolerance) comparison
const double EPS = 1e-9;
if (abs(a - 0.3) < EPS) { cout << "Equal\n"; }   // ✅ Reliable
 
// ✅ For geometry problems, define EPS at the top
#define EPS 1e-9
bool equal(double a, double b) { return fabs(a - b) < EPS; }
bool lessThan(double a, double b) { return a < b - EPS; }

Pitfall 6: Dangling References and Iterator Invalidation

// ❌ Modifying a vector invalidates all iterators and references
vector<int> v = {1, 2, 3, 4, 5};
int& ref = v[0];                // Reference to v[0]
v.push_back(6);                 // May reallocate — ref is now dangling!
cout << ref;                    // ❌ UB: memory was moved
 
// ❌ Erasing while iterating
for (auto it = v.begin(); it != v.end(); it++) {
    if (*it == 3) v.erase(it);  // ❌ UB: it is now invalid
}
 
// ✅ Erase-remove idiom
v.erase(remove(v.begin(), v.end(), 3), v.end());
 
// ✅ Or collect and erase by index (safe)
vector<int> toRemove;
for (int i = 0; i < (int)v.size(); i++) {
    if (v[i] == 3) toRemove.push_back(i);
}
// Erase from back to front
for (int i = (int)toRemove.size() - 1; i >= 0; i--) {
    v.erase(v.begin() + toRemove[i]);
}

Pitfall 7: Using `endl` in Tight Loops (Performance)

// ❌ endl flushes the output buffer every time — extremely slow
for (int i = 0; i < 1000000; i++) {
    cout << i << endl;    // 10-100x slower than necessary
}
 
// ✅ Use "\n" — no flush
for (int i = 0; i < 1000000; i++) {
    cout << i << "\n";
}

Pitfall 8: Division with Negative Numbers

// In C++, integer division truncates toward zero (not floor)
cout << 7 / 2;     // 3   (truncates, same as floor for positives)
cout << -7 / 2;    // -3  (truncates toward 0, NOT -4!)
cout << 7 % 2;     // 1
cout << -7 % 2;    // -1  (sign follows dividend in C++)
 
// If you need floor division (Python behavior):
int floorDiv(int a, int b) {
    return a / b - (a % b != 0 && (a ^ b) < 0);
}
 
// Modular arithmetic with negative numbers
int mod = 1e9 + 7;
int x = -5;
int result = ((x % mod) + mod) % mod;  // ✅ Always non-negative result

The Essential Boilerplate

Every competitive programming / interview solution should start with this:

#include <bits/stdc++.h>      // Includes everything: vector, map, algorithm, etc.
using namespace std;
 
// Common constants
const int    MOD  = 1e9 + 7;
const int    INF  = INT_MAX / 2;   // /2 to avoid overflow when added to something
const long long LINF = LLONG_MAX / 2;
const double EPS  = 1e-9;
 
int main() {
    ios_base::sync_with_stdio(false);   // Faster I/O (unties C/C++ streams)
    cin.tie(NULL);                       // Unties cin from cout
 
    // Your solution here
 
    return 0;
}

What ios_base::sync_with_stdio(false) and cin.tie(NULL) do:

By default, C++ syncs its I/O with C's stdio, adding overhead. Disabling this synchronization makes cin/cout 5–10× faster. cin.tie(NULL) prevents cout from flushing before every cin read. Use these in every solution that reads significant input.

Warning: Note: After using ios_base::sync_with_stdio(false), do NOT mix printf/scanf with cout/cin in the same program.