Chapter 2.4: Structs & Classes

📝 Prerequisites: Chapters 2.1–2.3 (variables, control flow, functions, arrays)

In competitive programming, you often need to group related data together — for example, a point has an x and y, an edge has two endpoints and a weight, a student has a name and a score. C++ provides struct and class to bundle data (and behavior) into a single type. This chapter covers both, with a strong focus on what matters most in competitive programming.

2.4.1 Why Group Data Together?

🎒 The Backpack Analogy

Imagine you're going on a trip. You could carry each item separately:
  - left hand: passport
  - right hand: phone
  - pocket: wallet
  - teeth: ticket 😬

Or you could put everything in a BACKPACK:
  - backpack.passport ✅
  - backpack.phone ✅
  - backpack.wallet ✅
  - backpack.ticket ✅

A struct/class is that backpack — it groups related items under one name.

Without structs, if you want to store 1000 students' names and scores, you'd need two separate arrays:

string names[1000];
int scores[1000];
// You have to manually keep indices in sync — error-prone!

With a struct, it's clean and safe:

struct Student {
    string name;
    int score;
};
Student students[1000];  // Each student carries its own name and score

2.4.2 Struct Basics

Defining a Struct

#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x;
    int y;
};  // <-- Don't forget the semicolon!

int main() {
    Point p;       // Declare a Point variable
    p.x = 3;       // Access members with the dot (.) operator
    p.y = 7;
    cout << "(" << p.x << ", " << p.y << ")" << endl;  // (3, 7)
    return 0;
}

Initialization Methods

// Method 1: Aggregate initialization (C++11, most common in CP)
Point p1 = {3, 7};

// Method 2: Designated initializers (C++20)
Point p2 = {.x = 3, .y = 7};

// Method 3: Assign fields one by one
Point p3;
p3.x = 3;
p3.y = 7;

💡 CP Tip: In competitive programming, aggregate initialization {val1, val2, ...} is the most commonly used style — fast to type, easy to read.

Struct with a Constructor

You can define a constructor so that creating an instance is even cleaner:

struct Point {
    int x, y;

    // Constructor
    Point(int _x, int _y) : x(_x), y(_y) {}
};

int main() {
    Point p(3, 7);  // Calls the constructor
    cout << p.x << " " << p.y << endl;  // 3 7
}

⚠️ Warning: Once you define a custom constructor, you can no longer use Point p; (no arguments) unless you also provide a default constructor or add default parameter values.

struct Point {
    int x, y;

    Point() : x(0), y(0) {}            // Default constructor
    Point(int _x, int _y) : x(_x), y(_y) {}  // Parameterized constructor
};

Point p1;       // OK — uses default constructor, x=0, y=0
Point p2(3, 7); // OK — uses parameterized constructor

2.4.3 Structs in Competitive Programming

Storing Edges in Graph Problems

struct Edge {
    int from, to, weight;
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].from >> edges[i].to >> edges[i].weight;
    }
}

Sorting Structs with Custom Comparison

This is extremely common in USACO problems. You often need to sort objects by a specific field.

Method 1: Overload operator< inside the struct

struct Event {
    int start, end;

    // Sort by end time (greedy scheduling)
    bool operator<(const Event& other) const {
        return end < other.end;
    }
};

int main() {
    vector<Event> events = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}};
    sort(events.begin(), events.end());  // Uses operator< automatically

    for (auto& e : events) {
        cout << "[" << e.start << ", " << e.end << "] ";
    }
    // Output: [1, 4] [3, 5] [0, 6] [5, 7] [3, 8] [5, 9]
}

Method 2: Lambda comparator (more flexible)

struct Event {
    int start, end;
};

int main() {
    vector<Event> events = {{1, 4}, {3, 5}, {0, 6}, {5, 7}};

    // Sort by start time
    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
        return a.start < b.start;
    });
}

Method 3: Write a comparison function

bool compareByEnd(const Event& a, const Event& b) {
    return a.end < b.end;
}

sort(events.begin(), events.end(), compareByEnd);

💡 CP Tip: For most USACO problems, Method 1 (operator overloading) is the cleanest when you have one natural sort order. Use Method 2 (lambda) when you need multiple different sort orders in the same program.

Multi-Key Sorting

Sometimes you need to sort by one field first, then break ties with another:

struct Student {
    string name;
    int score;

    bool operator<(const Student& other) const {
        if (score != other.score) return score > other.score;  // Higher score first
        return name < other.name;  // Alphabetical for ties
    }
};

Or use tie() for a cleaner approach:

struct Student {
    string name;
    int score;

    bool operator<(const Student& other) const {
        // Sort by score descending, then name ascending
        return tie(other.score, name) < tie(score, other.name);
    }
};

💡 tie() Trick: tie() creates a tuple for lexicographic comparison. Swapping the order of elements reverses the sort direction for that field. This is a very common competitive programming technique.

Structs in Sets and Maps

If you want to use a struct as a key in set or map, you must define operator<:

struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        return tie(x, y) < tie(other.x, other.y);
    }
};

set<Point> visited;
visited.insert({1, 2});
visited.insert({3, 4});

if (visited.count({1, 2})) {
    cout << "Already visited!" << endl;
}

Structs in Priority Queues

struct State {
    int dist, node;

    // For min-heap: we want the SMALLEST dist on top
    // priority_queue is a MAX-heap by default, so we reverse the comparison
    bool operator>(const State& other) const {
        return dist > other.dist;
    }
};

// Min-heap using operator>
priority_queue<State, vector<State>, greater<State>> pq;
pq.push({0, 1});   // distance 0, node 1
pq.push({5, 2});   // distance 5, node 2

auto top = pq.top();  // {0, 1} — smallest distance

2.4.4 Struct vs. Class — What's the Difference?

Here's the truth: struct and class are almost identical in C++. The only difference is the default access level:

// These two are functionally identical:

struct PointS {
    int x, y;  // public by default
};

class PointC {
public:          // Must explicitly say "public"
    int x, y;
};

When to Use Which?

💡 CP Convention: In competitive programming, always use struct. It's simpler, shorter, and you almost never need private members. You'll see struct in virtually every competitive programmer's code.

2.4.5 Classes — The Full Picture

While struct is sufficient for competitive programming, understanding class is valuable for broader C++ knowledge.

Access Modifiers

class BankAccount {
private:    // Only accessible inside the class
    double balance;

public:     // Accessible from anywhere
    BankAccount(double initial) : balance(initial) {}

    void deposit(double amount) {
        if (amount > 0) {
            balance += amount;
        }
    }

    void withdraw(double amount) {
        if (amount > 0 && amount <= balance) {
            balance -= amount;
        }
    }

    double getBalance() const {
        return balance;
    }
};

int main() {
    BankAccount acc(100.0);
    acc.deposit(50.0);
    acc.withdraw(30.0);
    cout << acc.getBalance() << endl;  // 120.0

    // acc.balance = 999999;  // ERROR! balance is private
}

Why Encapsulation?

Think of a vending machine:

- PUBLIC interface:  insert coin, press button, take drink
- PRIVATE internals: coin counter, inventory, temperature control

You interact with the machine through its public buttons.
You can't directly reach in and grab a drink.

Encapsulation protects data from being misused.

In competitive programming, this level of protection is unnecessary — speed of writing code matters more. But in software engineering, it prevents bugs in large codebases.

Member Functions (Methods)

Both struct and class can have member functions:

struct Rect {
    int width, height;

    int area() const {
        return width * height;
    }

    int perimeter() const {
        return 2 * (width + height);
    }

    bool contains(int x, int y) const {
        return x >= 0 && x < width && y >= 0 && y < height;
    }
};

int main() {
    Rect r = {10, 5};
    cout << "Area: " << r.area() << endl;        // 50
    cout << "Perimeter: " << r.perimeter() << endl;  // 30
    cout << r.contains(3, 4) << endl;              // 1 (true)
}

💡 const After Method Name: The const keyword after a method name means "this method does not modify the object." Always mark methods as const if they only read data — this is good practice and required when working with const references.

2.4.6 Advanced Struct Patterns for CP

Pair — The Built-in "Two-Field Struct"

C++ provides pair as a lightweight alternative when you only need two fields:

#include <bits/stdc++.h>
using namespace std;

int main() {
    pair<int, int> p = {3, 7};
    cout << p.first << " " << p.second << endl;  // 3 7

    // Pairs have built-in comparison (lexicographic)
    vector<pair<int, int>> v = {{3, 1}, {1, 5}, {3, 0}, {1, 2}};
    sort(v.begin(), v.end());
    // Result: {1, 2}, {1, 5}, {3, 0}, {3, 1}

    // You can use make_pair or just braces
    auto q = make_pair(10, 20);
}

When to use pair vs struct:

Tuple — The Built-in "N-Field Struct"

tuple<int, string, double> t = {42, "Alice", 3.14};
cout << get<0>(t) << endl;  // 42
cout << get<1>(t) << endl;  // Alice

// Structured bindings (C++17) — much cleaner
auto [id, name, gpa] = t;
cout << name << " has GPA " << gpa << endl;

💡 CP Tip: For anything more than 2 fields, a named struct is almost always more readable than tuple. Use pair freely, but avoid tuple when you can use a struct instead.

Struct with array or vector Members

struct Graph {
    int n;
    vector<vector<int>> adj;

    Graph(int _n) : n(_n), adj(_n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(1, 2);

    for (int v : g.adj[1]) {
        cout << v << " ";  // 0 2
    }
}

2.4.7 Common Mistakes

❌ Mistake 1: Forgetting the Semicolon After }

struct Point {
    int x, y;
}   // ← Missing semicolon!

int main() { ... }
// Compiler gives a confusing error pointing at main()

Fix: Always put ; after the closing brace of a struct/class definition.

❌ Mistake 2: Forgetting const in Operator Overloads

struct Point {
    int x, y;
    // WRONG — missing const
    bool operator<(const Point& other) {  // ← won't work in some STL containers
        return tie(x, y) < tie(other.x, other.y);
    }
};

Fix: Always mark comparison operators as const:

bool operator<(const Point& other) const {  // ✅
    return tie(x, y) < tie(other.x, other.y);
}

❌ Mistake 3: Using Uninitialized Struct Members

struct State {
    int dist, node;
};

State s;
cout << s.dist;  // Undefined behavior! Could be any value

Fix: Always initialize, or provide default values:

struct State {
    int dist = 0;
    int node = 0;
};

❌ Mistake 4: Confusing operator< Direction for Priority Queues

struct State {
    int dist;
    // For min-heap, you might think:
    bool operator<(const State& other) const {
        return dist < other.dist;  // This gives MAX-heap! (opposite of what you want)
    }
};

Fix: For min-heap with priority_queue, either reverse the comparison or use greater<>:

// Option A: Reverse operator<
bool operator<(const State& other) const {
    return dist > other.dist;  // Larger dist has LOWER priority → min-heap
}
priority_queue<State> pq;

// Option B: Define operator> and use greater<>
bool operator>(const State& other) const {
    return dist > other.dist;
}
priority_queue<State, vector<State>, greater<State>> pq;

2.4.8 Practice Problems

🟢 Problem 1: Student Ranking

Read n students (name and score), sort them by score descending, and print the ranking.

Input:
3
Alice 85
Bob 92
Charlie 85

Output:
1. Bob 92
2. Alice 85
3. Charlie 85

#include <bits/stdc++.h>
using namespace std;

struct Student {
    string name;
    int score;

    bool operator<(const Student& other) const {
        if (score != other.score) return score > other.score;
        return name < other.name;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Student> students(n);
    for (int i = 0; i < n; i++) {
        cin >> students[i].name >> students[i].score;
    }
    sort(students.begin(), students.end());
    for (int i = 0; i < n; i++) {
        cout << i + 1 << ". " << students[i].name << " " << students[i].score << "\n";
    }
}

🟢 Problem 2: Closest Pair of Points (1D)

Given n points on a number line, find the pair with the smallest distance between them.

Input:
5
7 1 4 9 2

Output:
1
(between points 1 and 2)

#include <bits/stdc++.h>
using namespace std;

struct PointVal {
    int val, originalIndex;

    bool operator<(const PointVal& other) const {
        return val < other.val;
    }
};

int main() {
    int n;
    cin >> n;
    vector<PointVal> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].val;
        points[i].originalIndex = i;
    }
    sort(points.begin(), points.end());

    int minDist = INT_MAX;
    int bestI = 0, bestJ = 1;
    for (int i = 0; i + 1 < n; i++) {
        int d = points[i + 1].val - points[i].val;
        if (d < minDist) {
            minDist = d;
            bestI = i;
            bestJ = i + 1;
        }
    }
    cout << minDist << "\n";
    cout << "(between points " << points[bestI].val << " and " << points[bestJ].val << ")\n";
}

🟡 Problem 3: Interval Scheduling (Greedy)

Given n intervals [start, end], find the maximum number of non-overlapping intervals.

Input:
6
1 4
3 5
0 6
5 7
3 8
5 9

Output:
3
(select [1,4], [5,7], [5,9] — wait, [5,7] and [5,9] overlap!)
Correct: select [1,4], [5,7] → 2 non-overlapping, or [1,4], [5,7] → Actually:
3

#include <bits/stdc++.h>
using namespace std;

struct Interval {
    int start, end;

    bool operator<(const Interval& other) const {
        return end < other.end;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Interval> intervals(n);
    for (int i = 0; i < n; i++) {
        cin >> intervals[i].start >> intervals[i].end;
    }
    sort(intervals.begin(), intervals.end());

    int count = 0, lastEnd = -1;
    for (auto& it : intervals) {
        if (it.start >= lastEnd) {
            count++;
            lastEnd = it.end;
        }
    }
    cout << count << "\n";
}

📋 Chapter Summary

🎯 Key CP Takeaways

1. Always use struct in competitive programming — simpler and shorter
2. Master operator< overloading — you'll use it in nearly every USACO problem
3. Use tie() for multi-key sorts — clean and bug-free
4. Remember const on comparison operators — required for STL compatibility
5. Initialize your members — avoid undefined behavior
6. pair for 2 fields, custom struct for 3+ — good rule of thumb