Module 09 Tutorial

Prerequisites: Review Module 09 Concepts first.

This module focuses on practical STL applications. You’ll use different containers strategically: a map for date lookups, a stack for RPN evaluation, and two containers for sorting comparison.

Container allocation strategy:

Exercise	Container	Why
ex00	std::map	Sorted key-value pairs, efficient date lookup
ex01	std::stack	LIFO operations for RPN evaluation
ex02	std::vector + std::deque	Performance comparison for sorting

---

Exercise 00: Bitcoin Exchange

Subject Analysis

Create a program that:

• Reads a database file (CSV: date,exchange_rate)
• Reads an input file (CSV: date | value)
• For each input line, calculates value * exchange_rate
• Uses the closest earlier date if exact match not found

Key constraints:

• Date format: YYYY-MM-DD
• Input value: positive number between 0 and 1000
• Must handle invalid input gracefully
• Database file provided: data.csv

Approach Strategy

Think before coding:

1. Which container for the database?

   • std::map<std::string, float> - perfect for key-value with sorted keys
   • String dates sort correctly lexicographically (“2020-01-15” < “2020-02-01”)

2. How to find closest earlier date?

   • map::lower_bound(key) returns iterator to first element >= key
   • If no exact match, go back one position

3. What validations are needed?

   • Date format and validity (leap years!)
   • Value is positive and <= 1000
   • Line format (contains |)

Progressive Code Building

Stage 1: Class structure

BitcoinExchange.hpp

#ifndef BITCOINEXCHANGE_HPP
#define BITCOINEXCHANGE_HPP

#include <map>
#include <string>

class BitcoinExchange {
private:
    std::map<std::string, float> _database;

    bool isValidDate(const std::string& date) const;
    bool isValidValue(const std::string& value, float& result) const;
    std::string trim(const std::string& str) const;

public:
    BitcoinExchange();
    BitcoinExchange(const BitcoinExchange& other);
    BitcoinExchange& operator=(const BitcoinExchange& other);
    ~BitcoinExchange();

    void loadDatabase(const std::string& filename);
    void processInput(const std::string& filename);
};

#endif

Stage 2: Load database

BitcoinExchange.cpp - loadDatabase

#include "BitcoinExchange.hpp"
#include <fstream>
#include <sstream>
#include <iostream>

void BitcoinExchange::loadDatabase(const std::string& filename) {
    std::ifstream file(filename.c_str());
    if (!file.is_open()) {
        throw std::runtime_error("Error: could not open database file.");
    }

    std::string line;
    std::getline(file, line);  // Skip header

    while (std::getline(file, line)) {
        size_t comma = line.find(',');
        if (comma == std::string::npos) continue;

        std::string date = line.substr(0, comma);
        std::string rateStr = line.substr(comma + 1);

        float rate;
        std::istringstream iss(rateStr);
        if (iss >> rate) {
            _database[date] = rate;
        }
    }
}

Stage 3: Date validation

BitcoinExchange.cpp - validation

bool BitcoinExchange::isValidDate(const std::string& date) const {
    // Check format: YYYY-MM-DD (10 chars)
    if (date.length() != 10) return false;
    if (date[4] != '-' || date[7] != '-') return false;

    // Extract parts
    int year, month, day;
    if (sscanf(date.c_str(), "%d-%d-%d", &year, &month, &day) != 3) {
        return false;
    }

    // Validate ranges
    if (year < 1 || month < 1 || month > 12 || day < 1) return false;

    // Days per month
    int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    // Leap year check
    bool isLeap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    if (isLeap) daysInMonth[2] = 29;

    return day <= daysInMonth[month];
}

bool BitcoinExchange::isValidValue(const std::string& value, float& result) const {
    std::istringstream iss(value);
    if (!(iss >> result)) return false;
    if (result < 0) return false;
    return true;
}

Stage 4: Find closest date and process

BitcoinExchange.cpp - processing

void BitcoinExchange::processInput(const std::string& filename) {
    std::ifstream file(filename.c_str());
    if (!file.is_open()) {
        std::cerr << "Error: could not open file." << std::endl;
        return;
    }

    std::string line;
    std::getline(file, line);  // Skip header

    while (std::getline(file, line)) {
        size_t pipe = line.find(" | ");
        if (pipe == std::string::npos) {
            std::cerr << "Error: bad input => " << line << std::endl;
            continue;
        }

        std::string date = trim(line.substr(0, pipe));
        std::string valueStr = trim(line.substr(pipe + 3));

        // Validate date
        if (!isValidDate(date)) {
            std::cerr << "Error: bad input => " << date << std::endl;
            continue;
        }

        // Validate value
        float value;
        if (!isValidValue(valueStr, value)) {
            std::cerr << "Error: bad input => " << valueStr << std::endl;
            continue;
        }
        if (value < 0) {
            std::cerr << "Error: not a positive number." << std::endl;
            continue;
        }
        if (value > 1000) {
            std::cerr << "Error: too large a number." << std::endl;
            continue;
        }

        // Find closest date
        std::map<std::string, float>::iterator it = _database.lower_bound(date);
        if (it == _database.end() || it->first != date) {
            if (it == _database.begin()) {
                std::cerr << "Error: date too early => " << date << std::endl;
                continue;
            }
            --it;  // Go to previous (closest earlier) date
        }

        float rate = it->second;
        std::cout << date << " => " << value << " = " << (value * rate) << std::endl;
    }
}

Line-by-Line Explanation

Understanding lower_bound:

Scenario	lower_bound returns
Exact match exists	Iterator to that element
No exact match	Iterator to first element > key
All elements < key	end() iterator

std::map<std::string, float> db;
db["2020-01-01"] = 100;
db["2020-02-01"] = 200;
db["2020-03-01"] = 300;

// Case 1: Exact match
db.lower_bound("2020-02-01");  // Points to 2020-02-01

// Case 2: Between two dates
db.lower_bound("2020-02-15");  // Points to 2020-03-01
// We want 2020-02-01, so --it

// Case 3: Before all dates
db.lower_bound("2019-01-01");  // Points to 2020-01-01
// No earlier date exists - error!

Leap year calculation:

bool isLeap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
// 2000: leap (divisible by 400)
// 1900: not leap (divisible by 100 but not 400)
// 2020: leap (divisible by 4, not by 100)
// 2021: not leap

Common Pitfalls

1. Not handling “earlier than database” case:

// WRONG: Assumes there's always an earlier date
std::map<std::string, float>::iterator it = _database.lower_bound(date);
--it;  // Undefined behavior if it == begin()!

// RIGHT: Check for begin()
if (it == _database.begin()) {
    std::cerr << "Error: date too early" << std::endl;
    continue;
}
--it;

2. Forgetting leap years:

// WRONG: February always 28 days
int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// RIGHT: Check leap year
if (isLeap) daysInMonth[2] = 29;

3. Wrong pipe format:

// WRONG: Subject uses " | " (with spaces)
size_t pipe = line.find("|");

// RIGHT: Look for " | "
size_t pipe = line.find(" | ");

Testing Tips

Create test input file:

input.txt

date | value
2011-01-03 | 3
2011-01-03 | 2
2011-01-03 | 1
2011-01-03 | 1.2
2011-01-09 | 1
2012-01-11 | -1
2001-42-42
2012-01-11 | 1
2012-01-11 | 2147483648

Test script:

./btc input.txt

# Expected output:
# 2011-01-03 => 3 = 0.9
# 2011-01-03 => 2 = 0.6
# 2011-01-03 => 1 = 0.3
# 2011-01-03 => 1.2 = 0.36
# 2011-01-09 => 1 = 0.32
# Error: not a positive number.
# Error: bad input => 2001-42-42
# 2012-01-11 => 1 = 7.1
# Error: too large a number.

Final Code

BitcoinExchange.hpp

#ifndef BITCOINEXCHANGE_HPP
#define BITCOINEXCHANGE_HPP

#include <map>
#include <string>

class BitcoinExchange {
private:
    std::map<std::string, float> _database;

    bool isValidDate(const std::string& date) const;
    std::string trim(const std::string& str) const;

public:
    BitcoinExchange();
    BitcoinExchange(const BitcoinExchange& other);
    BitcoinExchange& operator=(const BitcoinExchange& other);
    ~BitcoinExchange();

    void loadDatabase(const std::string& filename);
    void processInput(const std::string& filename);
};

#endif

---

Exercise 01: RPN (Reverse Polish Notation)

Subject Analysis

Create a program that:

• Takes an RPN expression as argument
• Evaluates it and prints the result
• Numbers are always single digits (< 10)
• Operators: +, -, *, /

RPN explained:

• Normal: (3 + 4) * 2
• RPN: 3 4 + 2 *
• Read left to right, no parentheses needed

Approach Strategy

Think before coding:

1. Why use a stack?

   • RPN naturally uses LIFO order
   • Push numbers, pop for operations, push result

2. Algorithm:

   For each token:
     If number: push to stack
     If operator: pop two, calculate, push result
   Final answer: only item on stack

3. Order matters for subtraction/division:

   • 5 3 - means 5 - 3 = 2, not 3 - 5
   • Pop b first, then a: result = a OP b

Progressive Code Building

Stage 1: Class structure

RPN.hpp

#ifndef RPN_HPP
#define RPN_HPP

#include <stack>
#include <string>

class RPN {
private:
    std::stack<int> _stack;

    bool isOperator(char c) const;

public:
    RPN();
    RPN(const RPN& other);
    RPN& operator=(const RPN& other);
    ~RPN();

    int evaluate(const std::string& expression);
};

#endif

Stage 2: Core evaluation

RPN.cpp

#include "RPN.hpp"
#include <cctype>
#include <stdexcept>

bool RPN::isOperator(char c) const {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int RPN::evaluate(const std::string& expression) {
    // Clear stack from any previous run
    while (!_stack.empty()) {
        _stack.pop();
    }

    for (size_t i = 0; i < expression.length(); i++) {
        char c = expression[i];

        // Skip spaces
        if (c == ' ') {
            continue;
        }

        // Number: push to stack
        if (std::isdigit(c)) {
            _stack.push(c - '0');
        }
        // Operator: pop two, calculate, push result
        else if (isOperator(c)) {
            if (_stack.size() < 2) {
                throw std::runtime_error("Error");
            }

            int b = _stack.top(); _stack.pop();
            int a = _stack.top(); _stack.pop();

            int result;
            switch (c) {
                case '+': result = a + b; break;
                case '-': result = a - b; break;
                case '*': result = a * b; break;
                case '/':
                    if (b == 0) {
                        throw std::runtime_error("Error");
                    }
                    result = a / b;
                    break;
                default:
                    throw std::runtime_error("Error");
            }
            _stack.push(result);
        }
        // Invalid character
        else {
            throw std::runtime_error("Error");
        }
    }

    // Must have exactly one result
    if (_stack.size() != 1) {
        throw std::runtime_error("Error");
    }

    return _stack.top();
}

Line-by-Line Explanation

RPN evaluation trace:

Expression: "8 9 * 9 - 9 - 9 - 4 - 1 +"

Step | Token | Stack (bottom->top) | Action
-----|-------|---------------------|--------
1    | 8     | [8]                 | Push 8
2    | 9     | [8, 9]              | Push 9
3    | *     | [72]                | Pop 9,8; push 8*9=72
4    | 9     | [72, 9]             | Push 9
5    | -     | [63]                | Pop 9,72; push 72-9=63
6    | 9     | [63, 9]             | Push 9
7    | -     | [54]                | Pop 9,63; push 63-9=54
8    | 9     | [54, 9]             | Push 9
9    | -     | [45]                | Pop 9,54; push 54-9=45
10   | 4     | [45, 4]             | Push 4
11   | -     | [41]                | Pop 4,45; push 45-4=41
12   | 1     | [41, 1]             | Push 1
13   | +     | [42]                | Pop 1,41; push 41+1=42

Result: 42

Why pop b before a?

// For "5 3 -":
// Stack after pushes: [5, 3]  (3 on top)
int b = _stack.top(); _stack.pop();  // b = 3
int a = _stack.top(); _stack.pop();  // a = 5
result = a - b;  // 5 - 3 = 2 (correct!)

// If we did a - b wrong:
// result = b - a;  // 3 - 5 = -2 (wrong!)

Common Pitfalls

1. Wrong operand order:

// WRONG: Reversed operands
int a = _stack.top(); _stack.pop();
int b = _stack.top(); _stack.pop();
result = a - b;  // Wrong order!

// RIGHT: b is popped first (was on top)
int b = _stack.top(); _stack.pop();
int a = _stack.top(); _stack.pop();
result = a - b;  // Correct!

2. Not handling division by zero:

// WRONG: Crash on divide by zero
case '/': result = a / b; break;

// RIGHT: Check first
case '/':
    if (b == 0) throw std::runtime_error("Error");
    result = a / b;
    break;

3. Accepting multi-digit numbers:

// WRONG: Subject says single digits only
if (std::isdigit(c)) {
    // Parse full number...
}

// RIGHT: Single digit only
if (std::isdigit(c)) {
    _stack.push(c - '0');  // Only 0-9
}

4. Not validating final stack:

// WRONG: Accept any stack state
return _stack.top();

// RIGHT: Must have exactly one result
if (_stack.size() != 1) {
    throw std::runtime_error("Error");
}
return _stack.top();

Testing Tips

main.cpp

#include <iostream>
#include "RPN.hpp"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " <expression>" << std::endl;
        return 1;
    }

    RPN calculator;
    try {
        int result = calculator.evaluate(argv[1]);
        std::cout << result << std::endl;
    } catch (std::exception& e) {
        std::cerr << e.what() << std::endl;
        return 1;
    }

    return 0;
}

Test cases:

./RPN "8 9 * 9 - 9 - 9 - 4 - 1 +"  # 42
./RPN "7 7 * 7 -"                   # 42
./RPN "1 2 * 2 / 2 * 2 4 - +"      # 0
./RPN "(1 + 1)"                     # Error (parentheses not allowed)
./RPN "1 2 + +"                     # Error (not enough operands)
./RPN "1 2"                         # Error (no operator)
./RPN "5 0 /"                       # Error (division by zero)

Final Code

RPN.hpp

#ifndef RPN_HPP
#define RPN_HPP

#include <stack>
#include <string>

class RPN {
private:
    std::stack<int> _stack;
    bool isOperator(char c) const;

public:
    RPN();
    RPN(const RPN& other);
    RPN& operator=(const RPN& other);
    ~RPN();

    int evaluate(const std::string& expression);
};

#endif

RPN.cpp

#include "RPN.hpp"
#include <cctype>
#include <stdexcept>

RPN::RPN() {}
RPN::RPN(const RPN& other) : _stack(other._stack) {}
RPN& RPN::operator=(const RPN& other) {
    if (this != &other) _stack = other._stack;
    return *this;
}
RPN::~RPN() {}

bool RPN::isOperator(char c) const {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int RPN::evaluate(const std::string& expression) {
    while (!_stack.empty()) _stack.pop();

    for (size_t i = 0; i < expression.length(); i++) {
        char c = expression[i];

        if (c == ' ') continue;

        if (std::isdigit(c)) {
            _stack.push(c - '0');
        }
        else if (isOperator(c)) {
            if (_stack.size() < 2)
                throw std::runtime_error("Error");

            int b = _stack.top(); _stack.pop();
            int a = _stack.top(); _stack.pop();

            switch (c) {
                case '+': _stack.push(a + b); break;
                case '-': _stack.push(a - b); break;
                case '*': _stack.push(a * b); break;
                case '/':
                    if (b == 0) throw std::runtime_error("Error");
                    _stack.push(a / b);
                    break;
            }
        }
        else {
            throw std::runtime_error("Error");
        }
    }

    if (_stack.size() != 1)
        throw std::runtime_error("Error");

    return _stack.top();
}

---

Exercise 02: PmergeMe

Subject Analysis

Implement the Ford-Johnson merge-insertion sort algorithm:

• Take positive integers as arguments
• Sort using two different containers
• Display: before, after, time for each container
• Handle at least 3000 numbers

Output format:

Before: 3 5 9 7 4
After:  3 4 5 7 9
Time to process a range of 5 elements with std::vector : 0.00031 us
Time to process a range of 5 elements with std::deque  : 0.00014 us

Approach Strategy

Think before coding:

1. What is Ford-Johnson?

   • Also called “merge-insertion sort”
   • Minimizes comparisons through clever pairing
   • Uses binary insertion with Jacobsthal sequence

2. Simplified algorithm:

   1. Pair adjacent elements
   2. Put larger in "main chain", smaller in "pend"
   3. Recursively sort main chain
   4. Insert pend elements using binary search

3. Why two containers?

   • Subject requires performance comparison
   • vector: contiguous memory, cache-friendly
   • deque: fast insertion at both ends

Progressive Code Building

Stage 1: Class structure

PmergeMe.hpp

#ifndef PMERGEME_HPP
#define PMERGEME_HPP

#include <vector>
#include <deque>
#include <string>

class PmergeMe {
private:
    std::vector<int> _vec;
    std::deque<int>  _deq;

    void sortVector();
    void sortDeque();

public:
    PmergeMe();
    PmergeMe(const PmergeMe& other);
    PmergeMe& operator=(const PmergeMe& other);
    ~PmergeMe();

    void parseInput(int argc, char** argv);
    void sort();
    void displayBefore() const;
    void displayAfter() const;
};

#endif

Stage 2: Parse and validate input

PmergeMe.cpp - parsing

#include "PmergeMe.hpp"
#include <cstdlib>
#include <stdexcept>
#include <iostream>

void PmergeMe::parseInput(int argc, char** argv) {
    for (int i = 1; i < argc; i++) {
        char* endptr;
        long num = std::strtol(argv[i], &endptr, 10);

        if (*endptr != '\0') {
            throw std::runtime_error("Error: invalid input.");
        }
        if (num <= 0) {
            throw std::runtime_error("Error: only positive integers.");
        }
        if (num > 2147483647) {
            throw std::runtime_error("Error: integer overflow.");
        }

        _vec.push_back(static_cast<int>(num));
        _deq.push_back(static_cast<int>(num));
    }
}

Stage 3: Ford-Johnson for vector

PmergeMe.cpp - sortVector

void PmergeMe::sortVector() {
    if (_vec.size() <= 1) return;

    std::vector<int> larger, smaller;
    bool hasOdd = (_vec.size() % 2 != 0);
    int oddElement = hasOdd ? _vec.back() : 0;

    // Step 1: Pair elements
    size_t limit = hasOdd ? _vec.size() - 1 : _vec.size();
    for (size_t i = 0; i < limit; i += 2) {
        if (_vec[i] > _vec[i + 1]) {
            larger.push_back(_vec[i]);
            smaller.push_back(_vec[i + 1]);
        } else {
            larger.push_back(_vec[i + 1]);
            smaller.push_back(_vec[i]);
        }
    }

    // Step 2: Recursively sort larger elements
    _vec = larger;
    sortVector();
    larger = _vec;

    // Step 3: Insert smaller elements using binary search
    for (size_t i = 0; i < smaller.size(); i++) {
        std::vector<int>::iterator pos =
            std::lower_bound(larger.begin(), larger.end(), smaller[i]);
        larger.insert(pos, smaller[i]);
    }

    // Step 4: Insert odd element if exists
    if (hasOdd) {
        std::vector<int>::iterator pos =
            std::lower_bound(larger.begin(), larger.end(), oddElement);
        larger.insert(pos, oddElement);
    }

    _vec = larger;
}

Stage 4: Timing

PmergeMe.cpp - sort with timing

#include <ctime>

void PmergeMe::sort() {
    // Time vector sort
    clock_t startVec = clock();
    sortVector();
    clock_t endVec = clock();
    double timeVec = (double)(endVec - startVec) / CLOCKS_PER_SEC * 1000000;

    // Time deque sort
    clock_t startDeq = clock();
    sortDeque();
    clock_t endDeq = clock();
    double timeDeq = (double)(endDeq - startDeq) / CLOCKS_PER_SEC * 1000000;

    std::cout << "Time to process a range of " << _vec.size()
              << " elements with std::vector : " << timeVec << " us" << std::endl;
    std::cout << "Time to process a range of " << _deq.size()
              << " elements with std::deque  : " << timeDeq << " us" << std::endl;
}

Line-by-Line Explanation

Ford-Johnson algorithm trace:

Input: [3, 5, 9, 7, 4, 1]

Step 1: Pair and separate
Pairs: (3,5) (9,7) (4,1)
Larger:  [5, 9, 4]
Smaller: [3, 7, 1]

Step 2: Recursively sort larger
[5, 9, 4] -> [4, 5, 9]  (after recursion)

Step 3: Insert smaller using binary search
Insert 3: [3, 4, 5, 9]
Insert 7: [3, 4, 5, 7, 9]
Insert 1: [1, 3, 4, 5, 7, 9]

Result: [1, 3, 4, 5, 7, 9]

Why lower_bound for insertion?

// lower_bound returns iterator to first element >= value
std::vector<int> v = {1, 3, 5, 7};

// Insert 4:
std::vector<int>::iterator pos = std::lower_bound(v.begin(), v.end(), 4);
// pos points to 5 (first element >= 4)
v.insert(pos, 4);
// v = {1, 3, 4, 5, 7}

Common Pitfalls

1. Not implementing actual Ford-Johnson:

// WRONG: Just using std::sort
void sortVector() {
    std::sort(_vec.begin(), _vec.end());
}

// RIGHT: Implement the pairing and recursive merge-insertion

2. Forgetting odd element:

// WRONG: Ignores odd element
for (size_t i = 0; i < _vec.size(); i += 2) {
    // Pairs only
}

// RIGHT: Handle odd element separately
bool hasOdd = (_vec.size() % 2 != 0);
int oddElement = hasOdd ? _vec.back() : 0;
size_t limit = hasOdd ? _vec.size() - 1 : _vec.size();

3. Timing the wrong thing:

// WRONG: Include parsing in timing
clock_t start = clock();
parseInput(argc, argv);  // Wrong!
sortVector();
clock_t end = clock();

// RIGHT: Only time the sort
parseInput(argc, argv);
clock_t start = clock();
sortVector();
clock_t end = clock();

4. Using same container:

// WRONG: Subject requires TWO different containers
std::vector<int> _data1;
std::vector<int> _data2;  // Both vectors!

// RIGHT: Different container types
std::vector<int> _vec;
std::deque<int>  _deq;

Testing Tips

# Generate test numbers
./PmergeMe 3 5 9 7 4

# Test with random numbers
./PmergeMe `shuf -i 1-100000 -n 3000 | tr "\n" " "`

# Verify sorting
./PmergeMe 5 4 3 2 1
# Should show: Before: 5 4 3 2 1
#              After:  1 2 3 4 5

Verification script:

#!/bin/bash
# Generate random numbers, sort, and verify
NUMS=$(shuf -i 1-10000 -n 100 | tr "\n" " ")
./PmergeMe $NUMS 2>&1 | head -2

# Compare with sort command
echo "Expected: $(echo $NUMS | tr " " "\n" | sort -n | tr "\n" " ")"

Final Code

PmergeMe.hpp

#ifndef PMERGEME_HPP
#define PMERGEME_HPP

#include <vector>
#include <deque>

class PmergeMe {
private:
    std::vector<int> _vec;
    std::deque<int>  _deq;

    void sortVector();
    void sortDeque();

public:
    PmergeMe();
    PmergeMe(const PmergeMe& other);
    PmergeMe& operator=(const PmergeMe& other);
    ~PmergeMe();

    void parseInput(int argc, char** argv);
    void sort();
    void displayBefore() const;
    void displayAfter() const;
};

#endif

main.cpp

#include <iostream>
#include "PmergeMe.hpp"

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "Usage: " << argv[0] << " <numbers...>" << std::endl;
        return 1;
    }

    try {
        PmergeMe sorter;
        sorter.parseInput(argc, argv);
        sorter.displayBefore();
        sorter.sort();
        sorter.displayAfter();
    } catch (std::exception& e) {
        std::cerr << e.what() << std::endl;
        return 1;
    }

    return 0;
}

---

Module 09 Summary

Exercise	Container	Algorithm
ex00	std::map	lower_bound for date lookup
ex01	std::stack	RPN evaluation (LIFO)
ex02	vector + deque	Ford-Johnson merge-insertion

Key takeaways:

1. Choose containers wisely - each has strengths
2. STL algorithms - lower_bound, sort, find save time
3. Performance matters - measure with clock()
4. Validate input - robust error handling is essential