1 / 1

Lecture Content Overview

Part 1: C++ STL: std::set

  1. Introduction to std::set
    • Sorted, unique associative container
    • Benefits: Sorting, uniqueness, fast lookup
  2. Basic Operations
    • Declaration: #include <set>
    • Insertion: .insert()
    • Existence Check: .count(), .find()
  3. Working with Elements
    • Iteration with range-based for loop
  4. Common Functions
    • .erase(), .clear(), .empty(), .size()
  5. Alternatives
    • std::unordered_set for faster, non-sorted data

Part 2: C++ STL: Algorithms

  1. Introduction to Algorithms
    • Efficient, generic, container-agnostic functions
    • Why: Optimized, reliable, concise code
  2. Core Concepts
    • Header: #include <algorithm>
    • Operate on ranges using Iterators (.begin(), .end())
  3. Common Algorithm Examples
    • std::sort(), std::find(), std::count(), std::for_each()
  4. Modern C++: Lambdas
    • Inline, anonymous functions for concise logic
  5. Algorithm Categories
    • Non-Modifying (e.g., find)
    • Modifying (e.g., sort, remove)

Lecture Content Overview

Creating Modules (Code Organization)

  • The Problem: Why we don't use one giant file.
  • The Solution: Header (.h) vs. Source (.cpp) files.
  • Step 1: Creating a Header File with declarations & #pragma once.
  • Step 2: Creating a Source File for the implementation.
  • Step 3: Using the module in main.cpp and compiling the project.

Using Macros (The Preprocessor)

  • What are Macros? Simple text substitution via #define.
  • Defining Constants (e.g., PI, BUFFER_SIZE).
  • Function-Like Macros and the Parenthesis Pitfall.
  • Advanced Use: Conditional compilation with #ifdef for debug builds.

Bitmasking Techniques (Efficiency)

  • The Concept: Storing multiple boolean flags in a single integer.
  • The Tools: Understanding the bitwise operators (&, |, ^, ~, <<).
  • The Workflow:
    • Creating Masks using the left-shift operator (1 << n).
    • Setting and Clearing flags.
    • Checking and Toggling flags.

C++ STL: Sets

Collections of Unique Elements

What is a `std::set`?

A `std::set` is an associative container that contains a sorted set of unique objects of type Key. Sets are typically implemented as red-black trees.

Why Use `std::set`?

  • Automatically keeps elements sorted.
  • Efficiently checks for the presence of an element.
  • Stores only unique elements.

Declaring a Set

To use `std::set`, you need to include the `` header.

#include <set>
#include <string>

std::set<std::string> mySet;

Inserting Elements

You can insert elements into a set using the `insert()` member function. If an element is already in the set, the insertion is ignored.

Insertion Example

This code inserts three strings into a set.

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> names;
    names.insert("Alice");
    names.insert("Bob");
    names.insert("Alice"); // This will be ignored
    return 0;
}

Checking if an Element Exists

You can check if an element exists in a set using the `.count()` or `.find()` member functions.

`.count()` Example

This code checks if the name "Charlie" is in the set.

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> names;
    names.insert("Alice");

    if (names.count("Charlie")) {
        std::cout << "Charlie is in the set.";
    } else {
        std::cout << "Charlie is not in the set.";
    }
    return 0;
}

Iterating Through a Set

You can iterate through a set using a range-based `for` loop or iterators. The elements will be iterated in sorted order.

Range-Based `for` Loop

This is a convenient way to iterate through a set.

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> names;
    names.insert("Charlie");
    names.insert("Alice");
    names.insert("Bob");

    for (const auto& name : names) {
        std::cout << name << " ";
    }
    // Output: Alice Bob Charlie
    return 0;
}

Other Useful Member Functions

  • `erase()`: removes an element
  • `clear()`: removes all elements
  • `empty()`: returns `true` if the set is empty
  • `size()`: returns the number of elements

When to Use a Set

Use a set when you need to store a collection of unique items and you need to be able to quickly check for the existence of an item. It's also useful when you need to keep the items in sorted order.

`std::unordered_set`

If you don't need the elements to be sorted, you can use `std::unordered_set`. It is generally faster than `std::set` for insertion, deletion, and lookup.

`std::unordered_set` Example

The usage is very similar to `std::set`.

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> names;
    names.insert("Alice");
    names.insert("Bob");
    return 0;
}

C++ STL: Algorithms

Working with Your Data

What are STL Algorithms?

The C++ STL provides a rich collection of algorithms that operate on ranges of elements. These algorithms are designed to be efficient and generic.

Why Use STL Algorithms?

  • They are highly optimized.
  • They are well-tested and reliable.
  • They make your code more concise and readable.
  • They work with a variety of container types.

Using Algorithms

To use the STL algorithms, you need to include the `` header.

#include <algorithm>
#include <vector>

Iterators

Algorithms operate on ranges of elements using iterators. An iterator is an object that points to an element in a container. Common iterators are `begin()` (points to the first element) and `end()` (points to the position after the last element).

`sort()`

The `sort()` algorithm sorts the elements in a range.

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

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9};
    std::sort(v.begin(), v.end());
    // v is now {1, 1, 3, 4, 5, 9}
    return 0;
}

`find()`

The `find()` algorithm searches for a value in a range.

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

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9};
    auto it = std::find(v.begin(), v.end(), 5);
    if (it != v.end()) {
        std::cout << "Found 5!";
    }
    return 0;
}

`count()`

The `count()` algorithm counts the number of occurrences of a value in a range.

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

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9};
    int n = std::count(v.begin(), v.end(), 1);
    // n is 2
    return 0;
}

`for_each()`

The `for_each()` algorithm applies a function to each element in a range.

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

void print(int n) {
    std::cout << n << " ";
}

int main() {
    std::vector<int> v = {3, 1, 4};
    std::for_each(v.begin(), v.end(), print);
    return 0;
}

Lambda Expressions

Lambda expressions allow you to write anonymous functions inline. They are often used with STL algorithms.

Lambda with `for_each()`

This code uses a lambda expression to print the elements of a vector.

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

int main() {
    std::vector<int> v = {3, 1, 4};
    std::for_each(v.begin(), v.end(), [](int n) {
        std::cout << n << " ";
    });
    return 0;
}

Non-Modifying Algorithms

These algorithms do not change the elements in the container. Examples include `find()`, `count()`, `equal()`, `search()`.

Modifying Algorithms

These algorithms can change the elements in the container. Examples include `sort()`, `copy()`, `remove()`, `reverse()`, `transform()`.

Explore the Possibilities

There are many more algorithms in the STL. Exploring them will make you a more effective C++ programmer.

Modules

Why Split Code into Multiple Files?

Imagine building a large application (like a game or a text editor) in a single main.cpp file.

  • It would become thousands of lines long and very difficult to read.
  • Finding specific functions would be a nightmare.
  • Working in a team would be almost impossible, as everyone would need to edit the same file.
  • Reusing code (like a special math function) in another project would mean copy-pasting.

The solution is to organize our code into logical modules.

// one_big_file.cpp (Don't do this!)

#include <iostream>
#include <string>
#include <vector>

// --- A bunch of math functions ---
int add(int a, int b) { return a + b; }
int subtract(int a, int b) { return a - b; }
// ... many more ...

// --- A bunch of string functions ---
void print_greeting(std::string name) {
    std::cout << "Hello, " << name << std::endl;
}
// ... many more ...

int main() {
    int sum = add(5, 3);
    print_greeting("World");
    // ... main logic gets lost in the clutter ...
    return 0;
}

Header (.h) vs. Source (.cpp)

We split our modules into two types of files:

Header Files (.h or .hpp)

This is the "declaration" or "interface" file. It tells other parts of the program what functions and classes exist, but not how they work.

  • Contains function prototypes (declarations).
  • Contains class definitions.
  • Contains constants and type definitions.
  • Acts like a menu for your module.

Source Files (.cpp)

This is the "definition" or "implementation" file. It contains the actual code that makes the functions work.

  • Contains the full function bodies.
  • This is where the logic lives.
// Analogy: A Restaurant

// The Menu is like a Header file (.h)
// It tells you WHAT you can order.
// - Burger
// - Fries
// - Soda

// The Kitchen is like a Source file (.cpp)
// It contains the implementation of HOW
// to make each item.
// - Burger: Grill patty, toast bun...
// - Fries: Cut potatoes, fry in oil...
// - Soda: Get cup, add ice, fill...

// The customer (main.cpp) only needs to
// see the menu to place an order.

Step 1: Create the Header File

Let's create a module for our math functions. We'll call it math_utils.h.

The most important part is the include guard.

#pragma once is a modern, simple way to do this. It tells the compiler to only include this file one time, even if multiple other files try to include it. This prevents redefinition errors.

Inside, we declare our functions without their bodies (note the semicolons).

// File: math_utils.h

#pragma once // Important! Prevents multiple inclusions.

// This is a "function prototype" or "declaration".
// It tells the compiler a function named 'add' exists
// that takes two integers and returns an integer.
int add(int a, int b);

// Another function prototype.
int subtract(int a, int b);

Step 2: Create the Source File

Now we create math_utils.cpp to implement the functions we declared in the header.

First, we must #include the corresponding header file ("math_utils.h"). This connects the implementation to its declaration.

Notice we use quotes " " for our own local files, and angle brackets < > for system libraries like iostream.

// File: math_utils.cpp

#include "math_utils.h" // Link to the header file

// Here is the "definition" or "implementation"
// of the 'add' function. This is the actual code.
int add(int a, int b) {
    return a + b;
}

// And the implementation for 'subtract'.
int subtract(int a, int b) {
    return a - b;
}

Step 3: Use it in main.cpp

In our main file, we just need to #include "math_utils.h". We don't need to see the .cpp file's implementation details.

The compiler will know about the add and subtract functions because their declarations are in the header.

Compiling

When you compile, you must tell the compiler about all the source files involved.

g++ main.cpp math_utils.cpp -o my_program
// File: main.cpp

#include <iostream>
#include "math_utils.h" // Include our custom module

int main() {
    int x = 10;
    int y = 4;

    int sum = add(x, y);
    int difference = subtract(x, y);

    std::cout << "Sum: " << sum << std::endl;
    std::cout << "Difference: " << difference << std::endl;

    return 0;
}

// --- Expected Output ---
// Sum: 14
// Difference: 6

Practice: Create a String Utility Module

Your turn! Apply what you've learned to create a new module for string manipulation.

  1. Create string_utils.h
    • Add an include guard (#pragma once).
    • #include <string> since you'll be using the std::string type.
    • Declare the following two functions:
      std::string create_greeting(std::string name);
      std::string to_uppercase(std::string text);
  2. Create string_utils.cpp
    • #include "string_utils.h"
    • Implement the two functions. (Hint: For to_uppercase, you can loop through the characters and use the toupper() function, which requires #include <cctype>).
  3. Compile and Run

    Use the main.cpp on the right and compile all source files:

    g++ main.cpp string_utils.cpp -o my_app
// File: main.cpp (Use this to test)

#include <iostream>
#include <string>
#include "string_utils.h" // Your new header!

int main() {
    std::string user_name = "Alice";
    
    std::string greeting = create_greeting(user_name);
    std::cout << greeting << std::endl;

    std::string loud_greeting = to_uppercase(greeting);
    std::cout << loud_greeting << std::endl;

    return 0;
}

// --- Expected Output ---
// Hello, Alice!
// HELLO, ALICE!

Macros

Instructions for the Preprocessor

A macro is a rule that tells the C++ preprocessor to perform text substitution before the actual compilation begins.

It's like a simple "find and replace" feature.

We define macros using the #define directive.

Constant Macros

The simplest use is to define a constant. By convention, macro names are in ALL_CAPS to distinguish them from regular variables.

The preprocessor will replace every instance of PI with 3.14159 in your code.

#include <iostream>

// Define a macro named PI
#define PI 3.14159

// Define another for a buffer size
#define BUFFER_SIZE 1024

int main() {
    double radius = 5.0;
    // The line below becomes:
    // double area = 3.14159 * radius * radius;
    double area = PI * radius * radius;

    std::cout << "Area: " << area << std::endl;

    int my_buffer[BUFFER_SIZE];
    std::cout << "Buffer can hold " 
              << BUFFER_SIZE << " integers." 
              << std::endl;

    return 0;
}

Function-Like Macros

Macros can also take arguments, making them look like functions.

However, they are very different! They are still just text substitution and have no concept of types.

A Major Pitfall

Always wrap macro arguments and the entire macro body in parentheses ( ) to avoid unexpected order-of-operations errors.

Look at the example. BAD_SQUARE(2+3) becomes 2+3*2+3 which is 2+6+3 = 11. Not what we wanted!

GOOD_SQUARE(2+3) becomes ((2+3)*(2+3)) which is 5*5 = 25. Correct!

#include <iostream>

// DANGEROUS: No parentheses
#define BAD_SQUARE(x) x * x

// GOOD PRACTICE: Parentheses everywhere!
#define GOOD_SQUARE(x) ((x) * (x))

int main() {
    int a = 5;
    std::cout << "Good square of 5: " 
              << GOOD_SQUARE(a) << std::endl;

    // See what happens with an expression
    std::cout << "Bad square of 2+3: " 
              << BAD_SQUARE(2+3) << std::endl;
    // Expands to: 2 + 3 * 2 + 3 = 11 (Wrong!)

    std::cout << "Good square of 2+3: "
              << GOOD_SQUARE(2+3) << std::endl;
    // Expands to: ((2+3) * (2+3)) = 25 (Correct!)

    return 0;
}

Conditional Compilation

A powerful use of macros is to include or exclude blocks of code from compilation based on whether a macro is defined.

This is extremely useful for things like:

  • Writing code that works on different operating systems (Windows, Linux, etc.).
  • Including extra "debug" code that you don't want in the final release version of your program.

The main directives are: #ifdef (if defined), #ifndef (if not defined), #else, and #endif.

// To run this code, compile with:
// g++ -DDEBUG main.cpp -o debug_program
// Then run without the flag:
// g++ main.cpp -o release_program

#include <iostream>

// You can define a macro in the code...
// #define DEBUG

// Or with a compiler flag like -DDEBUG

int main() {
    std::cout << "Program starting..." << std::endl;

#ifdef DEBUG
    // This block of code is ONLY compiled
    // if the DEBUG macro is defined.
    std::cout << "DEBUG mode is ON." << std::endl;
    int x = 42;
    std::cout << "Debug variable x = " << x << std::endl;
#endif

    std::cout << "Processing data..." << std::endl;
    
    std::cout << "Program finished." << std::endl;
    return 0;
}

Bitmasking

Using Bits as Flags

Imagine you have a set of 8 on/off options for a character in a game:

  • IsVisible, IsInvincible, IsFlying, IsPoisoned...

You could use 8 separate boolean variables, but this can be inefficient.

Bitmasking lets us store all 8 flags in a single byte (like an unsigned char). Each bit in the byte represents one flag.

00101001

This is highly memory-efficient and can be very fast, as the CPU is designed to work with bits.

// Storing options the "normal" way
struct PlayerOptions {
    bool is_visible;
    bool is_invincible;
    bool is_flying;
    bool is_poisoned;
    bool has_shield;
    bool is_on_fire;
    bool can_swim;
    bool has_key;
};
// This uses at least 8 bytes of memory!


// Storing options with bitmasking
// This uses only 1 byte (char) or 4 bytes (int).
unsigned char player_flags = 0; 
// All flags are initially off (00000000)

The Bitwise Operators

To manipulate individual bits, we use bitwise operators.

  • & (AND): Result bit is 1 only if both input bits are 1.
  • | (OR): Result bit is 1 if either input bit is 1.
  • ^ (XOR): Result bit is 1 if input bits are different.
  • ~ (NOT): Flips all the bits (0s become 1s, 1s become 0s).
  • << (Left Shift): Shifts bits to the left, filling with zeros. 1 << 2 means "shift the number 1 left by 2 places".
  • >> (Right Shift): Shifts bits to the right.
/*
  Let a = 5  (0101 in binary)
  Let b = 3  (0011 in binary)
*/

// a & b (AND)
//   0101
// & 0011
// ------
//   0001  (Result is 1)

// a | b (OR)
//   0101
// | 0011
// ------
//   0111  (Result is 7)

// 1 << n (Left Shift) is key for creating masks!
// 1 << 0  is 1 (0001)
// 1 << 1  is 2 (0010)
// 1 << 2  is 4 (0100)
// 1 << 3  is 8 (1000)

Creating the Masks

First, we define our flags. We assign each flag to a specific bit position using the left shift << operator on the number 1.

This creates a series of integer "masks" where only one bit is turned on (a power of 2).

Using const or enum is a good way to define these so they have meaningful names and cannot be changed by accident.

Now, instead of remembering "bit 3 is the flying flag", we can just use the name FLAG_FLYING.

#include <iostream>
#include <bitset> // For printing binary

// Define masks for our player options
const int FLAG_VISIBLE    = 1 << 0; // 00000001 (1)
const int FLAG_INVINCIBLE = 1 << 1; // 00000010 (2)
const int FLAG_FLYING     = 1 << 2; // 00000100 (4)
const int FLAG_POISONED   = 1 << 3; // 00001000 (8)

int main() {
    std::cout << "FLAG_VISIBLE:    " 
              << std::bitset<8>(FLAG_VISIBLE) << std::endl;
              
    std::cout << "FLAG_INVINCIBLE: " 
              << std::bitset<8>(FLAG_INVINCIBLE) << std::endl;
              
    std::cout << "FLAG_FLYING:     " 
              << std::bitset<8>(FLAG_FLYING) << std::endl;
              
    std::cout << "FLAG_POISONED:   " 
              << std::bitset<8>(FLAG_POISONED) << std::endl;
    return 0;
}

Manipulating Flags

We can now combine our masks and operators to change the flags.

Setting a Bit (Turning a flag ON)

Use the bitwise OR | operator. This adds the flag without affecting other flags.

flags |= MASK;

Clearing a Bit (Turning a flag OFF)

Use the bitwise AND & with a negated mask ~. The ~MASK creates a number with all bits ON *except* for the one we want to turn off.

flags &= ~MASK;

// (Continuing from previous slide's constants)
const int FLAG_VISIBLE    = 1 << 0; // 1
const int FLAG_INVINCIBLE = 1 << 1; // 2
const int FLAG_FLYING     = 1 << 2; // 4

int player_flags = 0; // 00000000

// --- SET a flag ON ---
// Make the player visible
player_flags |= FLAG_VISIBLE; // 00000000 | 00000001 = 00000001

// Also make the player fly
player_flags |= FLAG_FLYING; // 00000001 | 00000100 = 00000101

// --- CLEAR a flag OFF ---
// The player is no longer flying
// ~FLAG_FLYING is 11111011
//   00000101 (player_flags)
// & 11111011 (~FLAG_FLYING)
// ----------
//   00000001 
player_flags &= ~FLAG_FLYING;

Checking and Toggling Flags

Checking a Bit (Is a flag ON?)

Use the bitwise AND & operator. If the result is non-zero, the flag is on.

if (flags & MASK) { ... }

This works because if the specific bit is ON in both numbers, the result will have that bit ON, making it greater than zero.

Toggling a Bit (Flipping a flag)

Use the bitwise XOR ^ operator. If the flag was OFF, it turns ON. If it was ON, it turns OFF.

flags ^= MASK;

// (Continuing from previous slide's constants)
const int FLAG_VISIBLE    = 1 << 0; // 1
const int FLAG_INVINCIBLE = 1 << 1; // 2

// Start with player being visible
int player_flags = FLAG_VISIBLE; // 00000001

// --- CHECK a flag ---
if (player_flags & FLAG_VISIBLE) {
    // This will run
    // (00000001 & 00000001) is 1 (non-zero)
}
if (player_flags & FLAG_INVINCIBLE) {
    // This will NOT run
    // (00000001 & 00000010) is 0
}

// --- TOGGLE a flag ---
// Toggle invincibility on
player_flags ^= FLAG_INVINCIBLE; // 00000001 ^ 00000010 = 00000011

// Toggle invincibility off again
player_flags ^= FLAG_INVINCIBLE; // 00000011 ^ 00000010 = 00000001

Summary

What We Learned Today

Modules (Multiple Files):

  • Use .h files for declarations (the "what") and .cpp files for definitions (the "how").
  • Use #pragma once to prevent header file errors.
  • Compile all .cpp files together.

Macros:

  • #define is a preprocessor text-replacement tool.
  • Always wrap function-like macro arguments in parentheses!
  • Use #ifdef and #ifndef for conditional compilation (e.g., debug code).

Bitmasking:

  • An efficient way to store multiple boolean flags in a single integer.
  • Use bitwise operators (|, &, ^, ~, <<) to manipulate flags.