/*
 * C++ Code Example: Basic std::map Usage
 * Demonstrates insertion, ordered iteration, and lookup operations.
 */

#include <iostream>
#include <map>
#include <string>

int main() {
    // 1. Declare a std::map with string keys and int values.
    // Keys are automatically sorted in ascending order.
    std::map<std::string, int> userScores;

    // 2. Insert elements into the map.
    // Insertion complexity: O(log N) - where N is the number of elements.
    userScores["Alice"] = 150;
    userScores["Bob"] = 200;
    userScores["Charlie"] = 100;
    userScores.insert({"David", 175}); // Another way to insert

    // 3. Iterate through the map (elements are naturally sorted by key).
    // Iteration yields elements in sorted order: Alice, Bob, Charlie, David.
    std::cout << "--- Scores (Ordered by Name) ---" << std::endl;
    for (const auto& pair : userScores) {
        std::cout << "User: " << pair.first << ", Score: " << pair.second << std::endl;
    }

    // 4. Lookup a value by key.
    // Lookup complexity: O(log N).
    std::string searchName = "Bob";
    if (userScores.count(searchName)) { // check if key exists (O(log N))
        std::cout << "\nScore for " << searchName << ": " << userScores[searchName] << std::endl;
    }

    searchName = "Eve";
    auto it = userScores.find(searchName); // find() returns an iterator (O(log N))
    if (it == userScores.end()) {
        std::cout << "Score for " << searchName << " not found." << std::endl;
    } else {
        std::cout << "Score for " << searchName << ": " << it->second << std::endl;
    }
    
    // 5. Update a value
    userScores["Alice"] = 160;
    std::cout << "Alice's new score: " << userScores["Alice"] << std::endl;

    // 6. Erase an element
    userScores.erase("Charlie"); // Erase complexity: O(log N)
    std::cout << "\n--- Scores after Charlie's removal ---" << std::endl;
    for (const auto& pair : userScores) {
        std::cout << "User: " << pair.first << ", Score: " << pair.second << std::endl;
    }

    return 0;
}

/*
 * C++ Code Example: Basic std::unordered_map Usage
 * Demonstrates insertion, (unordered) iteration, lookup, and custom hash.
 */

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

// --- Example 1: Basic Usage ---
void basic_unordered_map_example() {
    std::cout << "\n--- Basic std::unordered_map Example ---" << std::endl;
    // 1. Declare a std::unordered_map.
    // No inherent order for elements.
    std::unordered_map<std::string, int> userScores;

    // 2. Insert elements.
    // Average complexity: O(1).
    // Worst-case complexity (hash collisions): O(N).
    userScores["Alice"] = 150;
    userScores["Bob"] = 200;
    userScores["Charlie"] = 100;
    userScores.insert({"David", 175});

    // 3. Iterate through the map (order is not guaranteed and can change).
    std::cout << "Scores (Unordered by Name):" << std::endl;
    for (const auto& pair : userScores) {
        std::cout << "User: " << pair.first << ", Score: " << pair.second << std::endl;
    }

    // 4. Lookup a value by key.
    // Average complexity: O(1).
    // Worst-case complexity (hash collisions): O(N).
    std::string searchName = "Bob";
    if (userScores.count(searchName)) { // O(1) average
        std::cout << "\nScore for " << searchName << ": " << userScores[searchName] << std::endl;
    }

    searchName = "Eve";
    auto it = userScores.find(searchName); // O(1) average
    if (it == userScores.end()) {
        std::cout << "Score for " << searchName << " not found." << std::endl;
    } else {
        std::cout << "Score for " << searchName << ": " << it->second << std::endl;
    }
}

// --- Example 2: Custom Hash Function for a Custom Key Type ---

// Define a custom key type for our map
struct Point {
    int x;
    int y;

    // Equality operator is crucial for unordered_map
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// Define a custom hash function for the Point struct
struct PointHash {
    std::size_t operator()(const Point& p) const {
        // A simple hash combination for demonstration.
        // In production, use a more robust hash combiner (e.g., boost::hash_combine).
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

void custom_hash_example() {
    std::cout << "\n--- Custom Hash Function Example ---" << std::endl;
    // Declare an unordered_map using our custom Point key and PointHash
    std::unordered_map<Point, std::string, PointHash> pointNames;

    pointNames[{1, 2}] = "OriginPlus";
    pointNames[{5, 7}] = "RemoteLocation";
    pointNames[{1, 2}] = "UpdatedOriginPlus"; // Overwrites existing key

    std::cout << "Point (1,2) maps to: " << pointNames[{1, 2}] << std::endl;
    std::cout << "Point (5,7) maps to: " << pointNames[{5, 7}] << std::endl;

    Point searchPoint = {10, 20};
    if (pointNames.count(searchPoint)) {
        std::cout << "Point (" << searchPoint.x << "," << searchPoint.y << ") found: " << pointNames[searchPoint] << std::endl;
    } else {
        std::cout << "Point (" << searchPoint.x << "," << searchPoint.y << ") not found." << std::endl;
    }
}

int main() {
    basic_unordered_map_example();
    custom_hash_example();
    return 0;
}

/*
 * C++ Code Example (Conceptual): Illustrating Key Properties for Performance
 * This code doesn't benchmark directly, but highlights aspects impacting performance choice.
 */

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
#include <chrono>
#include <vector>

// Imagine a complex object key for our maps
struct ComplexKey {
    int id;
    std::string name;
    double value;

    // Comparison operator for std::map (required)
    bool operator<(const ComplexKey& other) const {
        if (id != other.id) return id < other.id;
        if (name != other.name) return name < other.name;
        return value < other.value;
    }

    // Equality operator for std::unordered_map (required)
    bool operator==(const ComplexKey& other) const {
        return id == other.id && name == other.name && value == other.value;
    }
};

// Hash function for std::unordered_map<ComplexKey, ...>
// This would typically be placed in the std namespace or as a functor.
struct ComplexKeyHash {
    std::size_t operator()(const ComplexKey& k) const {
        // A robust hash combine function is essential for good performance.
        // For demonstration, a simple combination is shown.
        // In real code, consider using boost::hash_combine or a similar proven method.
        std::size_t h1 = std::hash<int>()(k.id);
        std::size_t h2 = std::hash<std::string>()(k.name);
        std::size_t h3 = std::hash<double>()(k.value);
        return h1 ^ (h2 << 1) ^ (h3 << 2); // Simple XOR and shift combination
    }
};

int main() {
    std::cout << "\n--- Architecting Performance Considerations ---" << std::endl;

    // 1. Illustrating std::map with ComplexKey
    std::map<ComplexKey, std::string> orderedData;
    ComplexKey k1 = {1, "Alpha", 1.1};
    ComplexKey k2 = {2, "Beta", 2.2};
    orderedData[k1] = "Data 1";
    orderedData[k2] = "Data 2";
    std::cout << "std::map with ComplexKey: Elements are ordered by ComplexKey's operator<" << std::endl;
    // Iteration would follow the defined order

    // 2. Illustrating std::unordered_map with ComplexKey
    // Requires custom hash and equality operators.
    std::unordered_map<ComplexKey, std::string, ComplexKeyHash> unorderedData;
    unorderedData[k1] = "Data A";
    unorderedData[k2] = "Data B";
    std::cout << "std::unordered_map with ComplexKey: Order is not guaranteed, relies on custom hash." << std::endl;

    // 3. Conceptual discussion on memory footprint
    // std::map: Node-based, each node has pointers, color info, key, value.
    //   Consider: Overhead per element is higher.
    // std::unordered_map: Array of buckets, each bucket can be a list of key-value pairs.
    //   Consider: Wasted space if load factor is low; rehashes involve allocating new, larger array.
    std::cout << "\nMemory Footprint:";
    std::cout << "\n  std::map: Higher per-element overhead due to node structure (pointers, color bit)."
              << "  Better cache locality for sequential access (tree traversal)."
              << "\n  std::unordered_map: Array-based buckets, potentially less overhead per element *if* well-packed."
              << "  Can have significant unused capacity; rehashes are costly memory-wise."
              << "  Poor cache locality due to scattered memory access from hashing."
              << std::endl;

    // 4. Time Complexity Recap (Conceptual)
    // This is the core difference we're architecting around.
    std::cout << "\nTime Complexity (Average/Worst-Case for Lookup/Insertion/Deletion):"
              << "\n  std::map: O(log N) / O(log N)  (Predictable and stable)"
              << "\n  std::unordered_map: O(1) / O(N) (Fastest average, but vulnerable to bad hash/collisions)"
              << std::endl;
    
    return 0;
}

/*
 * C++ Code Example: Demonstrating a Decision Point for Container Choice
 * Focuses on a scenario where order or performance dictates the choice.
 */

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>

// Helper to measure time
template <typename Func>
long long measure_time(Func func) {
    auto start = std::chrono::high_resolution_clock::now();
    func();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}

// Simulate generating unique user IDs
std::vector<int> generate_user_ids(int count) {
    std::vector<int> ids(count);
    std::iota(ids.begin(), ids.end(), 1); // Fill with 1, 2, ..., count
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(ids.begin(), ids.end(), g);
    return ids;
}

int main() {
    std::cout << "\n--- Strategic Deployment: Optimal Container Choices ---" << std::endl;

    const int NUM_USERS = 100000; // Scale this up to see performance differences
    std::vector<int> user_ids = generate_user_ids(NUM_USERS);

    // Scenario 1: We need user data, but also often need to list users by ID in order.
    std::cout << "\nScenario: User database where ordered listing by ID is frequent." << std::endl;
    std::map<int, std::string> ordered_user_db;
    long long map_insertion_time = measure_time([&]() {
        for (int i = 0; i < NUM_USERS; ++i) {
            ordered_user_db[user_ids[i]] = "User_" + std::to_string(user_ids[i]);
        }
    });
    std::cout << "std::map insertion for " << NUM_USERS << " users took: " << map_insertion_time << " ms." << std::endl;
    
    // Demonstrate ordered access
    // We retrieve the first 5 users by ID
    std::cout << "First 5 users by ID (from std::map):\n";
    auto it = ordered_user_db.begin();
    for(int i = 0; i < 5 && it != ordered_user_db.end(); ++i, ++it) {
        std::cout << "  ID: " << it->first << ", Name: " << it->second << std::endl;
    }

    // Scenario 2: We need ultra-fast lookup of user data, order is not a concern.
    std::cout << "\nScenario: Cache for user data with maximum lookup speed." << std::endl;
    std::unordered_map<int, std::string> fast_user_cache;
    long long unordered_map_insertion_time = measure_time([&]() {
        for (int i = 0; i < NUM_USERS; ++i) {
            fast_user_cache[user_ids[i]] = "CacheUser_" + std::to_string(user_ids[i]);
        }
    });
    std::cout << "std::unordered_map insertion for " << NUM_USERS << " users took: " << unordered_map_insertion_time << " ms." << std::endl;

    // Demonstrate fast lookup
    int lookup_id = user_ids[NUM_USERS / 2]; // Pick a middle ID
    long long unordered_map_lookup_time = measure_time([&]() {
        for(int i = 0; i < 10000; ++i) { // Simulate many lookups
            volatile std::string value = fast_user_cache[lookup_id]; 
        }
    });
    std::cout << "std::unordered_map 10000 lookups for ID " << lookup_id << " took: " << unordered_map_lookup_time << " ms." << std::endl;

    int map_lookup_id = ordered_user_db.begin()->first; // Get an existing ID from map
    long long map_lookup_time = measure_time([&]() {
        for(int i = 0; i < 10000; ++i) { // Simulate many lookups
            volatile std::string value = ordered_user_db[map_lookup_id];
        }
    });
    std::cout << "std::map 10000 lookups for ID " << map_lookup_id << " took: " << map_lookup_time << " ms." << std::endl;

    std::cout << "\nConclusion: 'map' is slower for raw insertion/lookup but provides order. 'unordered_map' is faster on average." << std::endl;

    // Pitfall Example: Poor hash function for a custom struct
    // (Conceptual, as a full example would be too long for an executable snippet)
    struct BadKey {
        int x, y;
        bool operator==(const BadKey& other) const { return x == other.x && y == other.y; }
    };
    // struct BadKeyHash { std::size_t operator()(const BadKey& k) const { return k.x; } }; // Only hashes by X
    // std::unordered_map<BadKey, int, BadKeyHash> bad_map;
    std::cout << "\nCommon Pitfall: A poor hash function can cause std::unordered_map to degrade to O(N) worst-case." << std::endl;
    std::cout << "  Example: If a hash function for a Point(x,y) only considers 'x', all points with same 'x' but different 'y' will collide." << std::endl;

    return 0;
}