Module 09: STL Practical Applications

Download Official Subject PDF

Key Concepts:

• Choosing the right container
• File parsing
• Algorithm implementation
• Performance considerations

---

1. Module Rules

Container Restrictions

• Must use at least one container per exercise
• Exercise 02 requires TWO different containers
• Once a container is used, it’s forbidden for remaining exercises

Suggested Container Allocation

Exercise	Suggested Container(s)	Why
ex00	map	Key-value pairs (date -> price)
ex01	stack	RPN naturally uses stack
ex02	vector + deque (or list)	Sorting comparison

---

2. Exercise 00: Bitcoin Exchange

Problem

Read a database of Bitcoin prices and calculate values for given amounts on specific dates.

Input Format

// Database (CSV): date,exchange_rate
2009-01-02,0
2011-01-03,0.3
2011-01-09,0.32

// Input file: date | value
date | value
2011-01-03 | 3
2011-01-03 | 2

Solution Approach

class BitcoinExchange {
private:
    std::map<std::string, float> _database;  // date -> price

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

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

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

### File I/O with ifstream
```cpp
#include <fstream>
#include <string>

void BitcoinExchange::loadDatabase(const std::string& filename) {
    // Open file (.c_str() needed for C++98 compatibility)
    std::ifstream file(filename.c_str());

    // Check if file opened successfully
    if (!file.is_open())
        throw std::runtime_error("Cannot open database file");

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

    // Read line by line
    while (std::getline(file, line)) {
        size_t pos = line.find(',');
        if (pos != std::string::npos) {
            std::string date = line.substr(0, pos);
            float price = std::atof(line.substr(pos + 1).c_str());
            _database[date] = price;
        }
    }

    file.close();  // Optional - closes automatically on destruction
}

std::getline for Line-by-Line Reading

std::ifstream file("input.txt");
std::string line;

// Read until EOF
while (std::getline(file, line)) {
    // Process line
    std::cout << line << std::endl;
}

// Check why loop ended
if (file.eof()) {
    // Normal end of file
}
else if (file.fail()) {
    // Read error occurred
}

map::lower_bound for Efficient Lookup

std::string BitcoinExchange::findClosestDate(const std::string& date) {
    // lower_bound returns iterator to first element >= date
    std::map<std::string, float>::iterator it = _database.lower_bound(date);

    // Case 1: Exact match found
    if (it != _database.end() && it->first == date) {
        return it->first;
    }

    // Case 2: date is smaller than all keys
    if (it == _database.begin()) {
        return "";  // No earlier date exists
    }

    // Case 3: Go to previous (earlier) date
    --it;
    return it->first;
}

Date Validation with Leap Year Logic

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

    // Check that year, month, day are digits
    for (int i = 0; i < 10; i++) {
        if (i == 4 || i == 7) continue;  // Skip dashes
        if (!std::isdigit(date[i]))
            return false;
    }

    int year = std::atoi(date.substr(0, 4).c_str());
    int month = std::atoi(date.substr(5, 2).c_str());
    int day = std::atoi(date.substr(8, 2).c_str());

    // Basic range checks
    if (year < 1)
        return false;
    if (month < 1 || month > 12)
        return false;
    if (day < 1 || day > 31)
        return false;

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

    // Leap year calculation
    // A year is a leap year if:
    // - Divisible by 4 AND not divisible by 100
    // - OR divisible by 400
    bool isLeapYear = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    if (isLeapYear && month == 2)
        daysInMonth[2] = 29;

    return day <= daysInMonth[month];
}

Leap Year Examples

// 2000: divisible by 400 -> LEAP YEAR
// 1900: divisible by 100 but not 400 -> NOT leap year
// 2024: divisible by 4, not by 100 -> LEAP YEAR
// 2023: not divisible by 4 -> NOT leap year

bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

---

3. Exercise 01: Reverse Polish Notation (RPN)

Problem

Evaluate mathematical expressions in postfix notation.

How RPN Works

Infix:   (3 + 4) * 2
Postfix: 3 4 + 2 *

Evaluation:
- Read 3, push: [3]
- Read 4, push: [3, 4]
- Read +, pop 4,3, push 7: [7]
- Read 2, push: [7, 2]
- Read *, pop 2,7, push 14: [14]
- Result: 14

Solution

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

    bool isOperator(char c);
    int applyOperator(int a, int b, char op);

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

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

int RPN::evaluate(const std::string& expression) {
    for (size_t i = 0; i < expression.length(); i++) {
        char c = expression[i];

        if (c == ' ')
            continue;

        if (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();

            _stack.push(applyOperator(a, b, c));
        }
        else {
            throw std::runtime_error("Error");
        }
    }

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

    return _stack.top();
}

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

int RPN::applyOperator(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/':
            if (b == 0)
                throw std::runtime_error("Error");
            return a / b;
    }
    throw std::runtime_error("Error");
}

---

4. vector::insert Operation

Insert at Position

std::vector<int> v;
v.push_back(10);
v.push_back(30);
v.push_back(40);
// v = {10, 30, 40}

// Insert 20 at position 1 (before 30)
std::vector<int>::iterator it = v.begin() + 1;
v.insert(it, 20);
// v = {10, 20, 30, 40}

Insert with lower_bound (Sorted Insert)

std::vector<int> sorted = {10, 20, 40, 50};

// Insert 30 in sorted position
std::vector<int>::iterator pos = std::lower_bound(sorted.begin(), sorted.end(), 30);
sorted.insert(pos, 30);
// sorted = {10, 20, 30, 40, 50}

Insert Performance

Container	Insert at front	Insert at back	Insert in middle
vector	O(n)	O(1) amortized	O(n)
deque	O(1)	O(1)	O(n)
list	O(1)	O(1)	O(1)*

*After finding position

---

5. deque Operations

deque - Double-Ended Queue

#include <deque>

std::deque<int> dq;

// Add elements (efficient at BOTH ends)
dq.push_back(30);   // {30}
dq.push_front(10);  // {10, 30}
dq.push_back(40);   // {10, 30, 40}
dq.push_front(5);   // {5, 10, 30, 40}

// Random access (like vector)
dq[0];              // 5
dq.at(1);           // 10

// Remove from both ends
dq.pop_front();     // {10, 30, 40}
dq.pop_back();      // {10, 30}

// Insert in middle
std::deque<int>::iterator it = dq.begin() + 1;
dq.insert(it, 20);  // {10, 20, 30}

deque vs vector

Feature	vector	deque
push_front	O(n) slow	O(1) fast
push_back	O(1)	O(1)
Random access	O(1)	O(1)
Memory	Contiguous	Chunked
Cache locality	Better	Worse

---

6. Exercise 02: PmergeMe (Ford-Johnson Algorithm)

Problem

Implement merge-insert sort using two different containers and compare performance.

Ford-Johnson Algorithm Overview

1. Pair elements: Group input into pairs
2. Sort each pair: Within each pair, identify larger and smaller element
3. Recursively sort: Sort the sequence of larger elements
4. Binary insert: Insert smaller elements using binary search (lower_bound)

Why Ford-Johnson?

• Minimizes the number of comparisons
• Uses Jacobsthal sequence for optimal insertion order
• Theoretical improvement over simple merge sort in comparison count

Jacobsthal Sequence (Optional Optimization)

The Jacobsthal sequence determines optimal insertion order: 1, 3, 5, 11, 21, 43, …

// J(n) = J(n-1) + 2*J(n-2), J(0)=0, J(1)=1
int jacobsthal(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return jacobsthal(n - 1) + 2 * jacobsthal(n - 2);
}

Simplified Implementation

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 display() const;
};

// Ford-Johnson for vector
void PmergeMe::sortVector() {
    if (_vec.size() <= 1)
        return;

    std::vector<int> larger, smaller;

    // Step 1: Create pairs
    for (size_t i = 0; i + 1 < _vec.size(); 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]);
        }
    }

    // Handle odd element
    bool hasOdd = (_vec.size() % 2 != 0);
    int oddElement = hasOdd ? _vec.back() : 0;

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

    // Step 3: Insert smaller elements
    // First element of smaller goes first (paired with first of larger)
    if (!smaller.empty()) {
        std::vector<int>::iterator pos = std::lower_bound(
            larger.begin(), larger.end(), smaller[0]);
        larger.insert(pos, smaller[0]);
    }

    // Insert remaining using Jacobsthal sequence for optimal insertions
    for (size_t i = 1; i < smaller.size(); i++) {
        std::vector<int>::iterator pos = std::lower_bound(
            larger.begin(), larger.end(), smaller[i]);
        larger.insert(pos, smaller[i]);
    }

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

    _vec = larger;
}

Step-by-Step Example

Input: [3, 1, 4, 1, 5, 9, 2, 6]

1. PAIR AND SORT PAIRS:
   (3,1) -> larger=3, smaller=1
   (4,1) -> larger=4, smaller=1
   (5,9) -> larger=9, smaller=5
   (2,6) -> larger=6, smaller=2

   Larger:  [3, 4, 9, 6]
   Smaller: [1, 1, 5, 2]

2. RECURSIVELY SORT LARGER:
   [3, 4, 9, 6] -> [3, 4, 6, 9]

3. BINARY INSERT SMALLER:
   Start: [3, 4, 6, 9]
   Insert 1 (paired with 3): lower_bound finds 3, insert before -> [1, 3, 4, 6, 9]
   Insert 1 (paired with 4): lower_bound finds 3, insert before -> [1, 1, 3, 4, 6, 9]
   Insert 5 (paired with 9): lower_bound finds 6, insert before -> [1, 1, 3, 4, 5, 6, 9]
   Insert 2 (paired with 6): lower_bound finds 3, insert before -> [1, 1, 2, 3, 4, 5, 6, 9]

Result: [1, 1, 2, 3, 4, 5, 6, 9]

Using Two Different Containers

class PmergeMe {
private:
    std::vector<int> _vec;  // First container
    std::deque<int> _deq;   // Second container (must be different!)

    void sortVector();
    void sortDeque();       // Same algorithm, different container
};

// Parse input into both containers
void PmergeMe::parseInput(int argc, char** argv) {
    for (int i = 1; i < argc; i++) {
        int num = std::atoi(argv[i]);
        if (num < 0)
            throw std::runtime_error("Error: negative number");
        _vec.push_back(num);
        _deq.push_back(num);  // Same data in both
    }
}

Timing

#include <ctime>

void PmergeMe::sort() {
    // Vector
    clock_t start = clock();
    sortVector();
    clock_t end = clock();
    double vecTime = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000000;

    // Deque
    start = clock();
    sortDeque();
    end = clock();
    double deqTime = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000000;

    std::cout << "Time to process " << _vec.size()
              << " elements with std::vector: " << vecTime << " us" << std::endl;
    std::cout << "Time to process " << _deq.size()
              << " elements with std::deque: " << deqTime << " us" << std::endl;
}

---

5. Common Pitfalls

Exercise 00

• Not handling missing dates (use closest earlier date)
• Not validating date format
• Value must be positive and <= 1000

Exercise 01

• Forgetting division by zero check
• Numbers must be < 10 (single digit in input)
• Result can be any size

Exercise 02

• Using same container for both implementations
• Not measuring time correctly
• Not implementing actual Ford-Johnson (simplified sorts may not pass)

---

6. Container Properties Summary

Container	Random Access	Insert Front	Insert Back	Insert Middle	Sorted
vector	O(1)	O(n)	O(1)*	O(n)	No
deque	O(1)	O(1)	O(1)	O(n)	No
list	O(n)	O(1)	O(1)	O(1)	No
map	O(log n)	-	-	O(log n)	Yes
set	O(log n)	-	-	O(log n)	Yes
stack	-	-	O(1)	-	No

*amortized

---

Quick Reference

Parsing Tips

// String to int
int n = std::atoi(str.c_str());

// String to float
float f = std::atof(str.c_str());

// Split string
size_t pos = str.find(delimiter);
std::string first = str.substr(0, pos);
std::string second = str.substr(pos + 1);

Timing

clock_t start = clock();
// ... code ...
clock_t end = clock();
double microseconds = (double)(end - start) / CLOCKS_PER_SEC * 1000000;

Binary Search (for insertion)

std::vector<int>::iterator pos = std::lower_bound(v.begin(), v.end(), value);
v.insert(pos, value);