/*
    std::map employs a self-balancing binary search tree, 
    most commonly a Red-Black Tree, to maintain its ordered elements.
    This ensures logarithmic time complexity for insertions, deletions, and lookups.
    
    Red-Black Tree Properties (Simplified):
    1. Each node is either red or black.
    2. The root is black.
    3. All leaves (NIL nodes) are black.
    4. If a node is red, then both its children are black.
    5. For each node, all simple paths from the node to descendant leaves 
       contain the same number of black nodes.
    
    These properties guarantee that the longest path from the root to any leaf 
    is no more than twice the length of the shortest path, 
    thus preventing the tree from becoming skewed and ensuring O(log N) operations.
*/

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

void demonstrate_map_basics() {
    std::map<int, std::string> my_map;

    // Insertion operation: O(log N)
    my_map.insert({50, "Fifty"});
    my_map.insert({30, "Thirty"});
    my_map.insert({70, "Seventy"});
    my_map.insert({20, "Twenty"});
    my_map.insert({40, "Forty"});
    my_map.insert({60, "Sixty"});
    my_map.insert({80, "Eighty"});
    
    std::cout << "Map after insertions:\n";
    for (const auto& pair : my_map) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }

    // Lookup operation: O(log N)
    auto it = my_map.find(40);
    if (it != my_map.end()) {
        std::cout << "Found: " << it->first << ": " << it->second << "\n";
    } else {
        std::cout << "Key 40 not found.\n";
    }

    // Deletion operation: O(log N)
    my_map.erase(30);
    std::cout << "Map after deleting 30:\n";
    for (const auto& pair : my_map) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }
}

// To compile and run this example:
// g++ -std=c++17 your_file.cpp -o your_program
// ./your_program

int main() {
    demonstrate_map_basics();
    return 0;
}

/*
    Demonstrating the concept of logarithmic time complexity O(log N).
    This example conceptualizes operations rather than providing a full benchmark.
    For N elements, a search typically involves log2(N) comparisons.

    Example: N = 1,000,000
    log2(1,000,000) is approximately 19.9.
    This means roughly 20 comparisons are needed to find any element.
    
    Compare this to:
    O(1) - constant time (e.g., std::unordered_map average case, std::vector::back())
    O(N) - linear time (e.g., std::vector::find, std::list::find)
    O(N log N) - (e.g., std::sort)
*/

#include <map>
#include <chrono>
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <functional> // For std::function
#include <numeric>    // For std::iota

// Helper to measure time (conceptual)
long long measure_time_ns(std::function<void()> 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::nanoseconds>(end - start).count();
}

void analyze_logarithmic_complexity() {
    std::vector<int> data_sizes = {1000, 10000, 100000, 1000000};
    std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

    std::cout << "\nAnalyzing std::map O(log N) behavior:\n";
    for (int N : data_sizes) {
        std::map<int, int> my_map;
        std::vector<int> keys_to_insert(N);
        std::iota(keys_to_insert.begin(), keys_to_insert.end(), 0);
        std::shuffle(keys_to_insert.begin(), keys_to_insert.end(), rng);

        // Measure insertion time (total for N elements, so average is O(log N))
        long long insert_time = measure_time_ns([&]() {
            for (int i = 0; i < N; ++i) {
                my_map.insert({keys_to_insert[i], i});
            }
        });

        // Measure lookup time for N random elements (average O(log N))
        std::vector<int> keys_to_find = keys_to_insert; // Use inserted keys
        std::shuffle(keys_to_find.begin(), keys_to_find.end(), rng);
        long long lookup_time = measure_time_ns([&]() {
            for (int i = 0; i < N; ++i) {
                my_map.find(keys_to_find[i]);
            }
        });

        std::cout << "  N = " << N << ":\n";
        std::cout << "    Total insertion time: " << insert_time / 1000000.0 << " ms\n";
        std::cout << "    Total lookup time for " << N << " elements: " << lookup_time / 1000000.0 << " ms\n";
        // Note: The total time for N operations will be O(N log N).
        // The individual operation is O(log N).
        // For N elements, average insert/lookup time is (Total Time / N) -> O(log N).
    }
}

int main() {
    analyze_logarithmic_complexity();
    return 0;
}

/*
    Each node in std::map (a Red-Black Tree) incurs significant memory overhead.
    It typically stores:
    - The key itself (sizeof(Key))
    - The value itself (sizeof(Value))
    - Pointers to parent, left child, right child (3 * sizeof(Node*))
    - A color bit (bool or char, often padded to a full byte)
    - Internal allocator/overhead specific to the STL implementation.

    The exact size can vary based on compiler, architecture (32-bit vs 64-bit), 
    and the specific STL implementation. 
    Padding for alignment can also increase the effective size.
*/

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

// A conceptual representation of a std::map node to illustrate memory components.
// This is NOT the actual std::map node, which is implementation-defined.
// It serves to illustrate the components that contribute to the overhead.
struct ConceptualMapNode {
    int key;                     // Key data
    std::string value;           // Value data
    ConceptualMapNode* parent;   // Pointer to parent node
    ConceptualMapNode* left;     // Pointer to left child
    ConceptualMapNode* right;    // Pointer to right child
    bool color;                  // Color of the node (Red/Black)
    // Implicit padding may occur here for alignment purposes
};

void analyze_memory_overhead() {
    std::cout << "\nAnalyzing Memory Overhead:\n";

    std::cout << "  Size of int (key): " << sizeof(int) << " bytes\n";
    std::cout << "  Size of std::string (value, small string optimized): " << sizeof(std::string) << " bytes (on stack)\n";
    std::cout << "  Size of pointer (e.g., Node*): " << sizeof(void*) << " bytes\n";
    std::cout << "  Size of bool (color): " << sizeof(bool) << " bytes\n";

    // Approximate conceptual node size:
    // sizeof(Key) + sizeof(Value) + 3*sizeof(pointer) + sizeof(bool) + padding
    // This is a lower bound, actual size can be higher due to allocator overhead 
    // and compiler-specific padding/alignment. For std::string, its actual memory
    // usage depends on the string's length (Small String Optimization).
    size_t conceptual_node_size = sizeof(int) + sizeof(std::string) + 3 * sizeof(void*) + sizeof(bool);
    std::cout << "  Approximate conceptual node size (sum of components, without actual node allocations/padding): " << conceptual_node_size << " bytes\n";

    // It's challenging to directly query std::map's internal node size.
    // However, on a 64-bit system, for std::map<int, int>:
    // 4 (key) + 4 (value) + 3*8 (pointers) + 1 (color) = 33 bytes raw data.
    // With padding for alignment (e.g., to 8-byte boundaries) and allocator overhead, 
    // an actual node often consumes 40-48 bytes or more.
    std::cout << "\n  std::map, unlike std::vector, allocates each node individually.";
    std::cout << "  This can lead to significant memory fragmentation and reduced cache locality.\n";
}

int main() {
    analyze_memory_overhead();
    return 0;
}

/*
    Optimizing std::map usage or choosing alternatives requires understanding
    its strengths and weaknesses.

    When std::map shines:
    - Ordered iteration over keys.
    - Stable iterators (insertions/deletions don't invalidate others).
    - Guaranteed O(log N) worst-case performance.
    
    When to consider alternatives:
    - If order is not required and average O(1) performance is critical: std::unordered_map
    - If N is small, and memory locality is critical: std::vector + std::sort + std::binary_search
    - If order is required and insertions/deletions are rare, but cache locality is vital: boost::flat_map
*/

#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <chrono>
#include <utility> // For std::make_pair

void demonstrate_optimization_and_alternatives() {
    std::cout << "\nDemonstrating Optimization and Alternatives:\n";

    // Using std::map with std::emplace for efficient insertion (avoids temporary object creation)
    std::map<int, std::string> map_emplace;
    auto start_emplace = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 10000; ++i) {
        map_emplace.emplace(i, "Value_" + std::to_string(i));
    }
    auto end_emplace = std::chrono::high_resolution_clock::now();
    std::cout << "  std::map::emplace for 10000 elements: " 
              << std::chrono::duration_cast<std::chrono::microseconds>(end_emplace - start_emplace).count() 
              << " us\n";

    // Contrast with std::insert (can be less efficient if constructing temporary pair)
    // Note: With C++11 initializer list, {key, value} implicitly creates a std::pair.
    // For simple types, the difference might be negligible, but for complex types, emplace is better.
    std::map<int, std::string> map_insert;
    auto start_insert = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 10000; ++i) {
        map_insert.insert({i, "Value_" + std::to_string(i)}); 
    }
    auto end_insert = std::chrono::high_resolution_clock::now();
    std::cout << "  std::map::insert for 10000 elements: " 
              << std::chrono::duration_cast<std::chrono::microseconds>(end_insert - start_insert).count() 
              << " us (potentially slower with complex values due to temporary pair)\n";

    // Alternative: std::unordered_map for speed when order is not critical
    std::unordered_map<int, std::string> unordered_map_example;
    auto start_unord = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 10000; ++i) {
        unordered_map_example.insert({i, "Value_" + std::to_string(i)}); 
    }
    auto end_unord = std::chrono::high_resolution_clock::now();
    std::cout << "  std::unordered_map::insert for 10000 elements: " 
              << std::chrono::duration_cast<std::chrono::microseconds>(end_unord - start_unord).count() 
              << " us (often faster total insertion due to O(1) average)\n";

    // Alternative: Sorted std::vector for small N or infrequent changes, good cache locality
    std::vector<std::pair<int, std::string>> vec_example;
    for (int i = 0; i < 100; ++i) { // Smaller N for vector demonstration to keep insertions fast
        vec_example.push_back({i, "Value_" + std::to_string(i)}); 
    }
    std::sort(vec_example.begin(), vec_example.end());

    auto start_vec_search = std::chrono::high_resolution_clock::now();
    // std::lower_bound requires a comparable value, not necessarily a full pair.
    // We create a temporary pair with a dummy second element if only key is needed for comparison.
    auto it_vec = std::lower_bound(vec_example.begin(), vec_example.end(), std::make_pair(50, std::string()));
    if (it_vec != vec_example.end() && it_vec->first == 50) {
        std::cout << "  Found key 50 in sorted std::vector.\n";
    } else {
        std::cout << "  Key 50 not found in sorted std::vector.\n";
    }
    auto end_vec_search = std::chrono::high_resolution_clock::now();
    std::cout << "  std::vector + lower_bound lookup for 100 elements: " 
              << std::chrono::duration_cast<std::chrono::microseconds>(end_vec_search - start_vec_search).count() 
              << " us (excellent cache locality)\n";

    std::cout << "\n  Choose the right container based on requirements: ordered access, lookup speed, memory profile.\n";
}

int main() {
    demonstrate_optimization_and_alternatives();
    return 0;
}