/*
   File: vector_reallocation_demo.cpp
   Description: Demonstrates the performance impact of implicit reallocations in std::vector
                when elements are added without prior capacity reservation.
*/

#include <vector>
#include <iostream>
#include <chrono> // For high-resolution timing

// Function to demonstrate std::vector's default growth strategy and reallocations
void demonstrate_implicit_reallocations() {
    std::cout << "<p><strong>--- Demonstrating Implicit Reallocations ---</strong></p>" << std::endl;
    std::vector<int> numbers;
    const size_t num_elements = 100000;

    // Record initial capacity and track changes
    size_t current_capacity = numbers.capacity();
    size_t realloc_count = 0;

    auto start_time = std::chrono::high_resolution_clock::now();

    for (size_t i = 0; i < num_elements; ++i) {
        // Check if capacity changes before adding an element
        if (numbers.capacity() != current_capacity) {
            realloc_count++;
            current_capacity = numbers.capacity();
            // Optional: Uncomment to see each reallocation event
            // std::cout << "<p>  Reallocation detected. New capacity: " << current_capacity << "</p>" << std::endl;
        }
        numbers.push_back(i);
    }

    auto end_time = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> duration = end_time - start_time;

    std::cout << "<p>  Vector size: <strong>" << numbers.size() << "</strong>, Final capacity: <strong>" << numbers.capacity() << "</strong></p>" << std::endl;
    std::cout << "<p>  Total number of reallocations observed: <strong>" << realloc_count << "</strong></p>" << std::endl;
    std::cout << "<p>  Execution time for implicit growth: <strong>" << duration.count() << " ms</strong></p>" << std::endl;
    std::cout << "<p>  <br>Each reallocation involves: <br>" << 
                 "  <br>&bull; Allocating a new, larger block of memory.<br>" << 
                 "  <br>&bull; Copying (or moving) all existing elements from the old block to the new.<br>" << 
                 "  <br>&bull; Deallocating the old, smaller block of memory.<br>" << 
                 "  <br>This sequence, though amortized O(1) for push_back, introduces significant cumulative overhead.</p>" << std::endl;
}

// main function is intentionally omitted here to allow for sequential compilation 
// with other parts. A combined main will be provided in the final code block.

/*
   File: vector_reserve_demo.cpp
   Description: Demonstrates how using std::vector::reserve() explicitly prevents reallocations
                and significantly improves performance for known sizes.
*/

#include <vector>
#include <iostream>
#include <chrono>

// (Include demonstrate_implicit_reallocations from previous part if running this snippet standalone)

// Function to demonstrate explicit reservation using reserve()
void demonstrate_explicit_reservation() {
    std::cout << "<p><strong>--- Activating reserve() for Performance ---</strong></p>" << std::endl;
    std::vector<int> numbers;
    const size_t anticipated_size = 100000;

    // Command vector to reserve memory upfront
    // This is the CRUCIAL step: reserve enough capacity for all anticipated elements.
    numbers.reserve(anticipated_size); 

    size_t current_capacity = numbers.capacity();
    size_t realloc_count = 0;

    auto start_time = std::chrono::high_resolution_clock::now();

    for (size_t i = 0; i < anticipated_size; ++i) {
        // After reserve(), capacity should ideally not change if anticipated_size was correct.
        if (numbers.capacity() != current_capacity) {
            realloc_count++;
            current_capacity = numbers.capacity();
            // This block should ideally not be hit, or hit very few times if size estimate was slightly off.
            // std::cout << "<p>  (Unexpected) Reallocation detected. New capacity: " << current_capacity << "</p>" << std::endl;
        }
        numbers.push_back(i);
    }

    auto end_time = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> duration = end_time - start_time;

    std::cout << "<p>  Vector size: <strong>" << numbers.size() << "</strong>, Final capacity: <strong>" << numbers.capacity() << "</strong></p>" << std::endl;
    std::cout << "<p>  Total number of reallocations observed (with reserve): <strong>" << realloc_count << "</strong></p>" << std::endl;
    std::cout << "<p>  Execution time with explicit reservation: <strong>" << duration.count() << " ms</strong></p>" << std::endl;
    std::cout << "<p>  <br>Observe <strong>zero reallocations</strong> when 'reserve()' is correctly applied,
                 guaranteeing a stable memory footprint and avoiding expensive copy operations.</p>" << std::endl;
}

// main function is intentionally omitted here to allow for sequential compilation 
// with other parts. A combined main will be provided in the final code block.

/*
   File: vector_advanced_optimizations.cpp
   Description: Demonstrates combining reserve() with emplace_back for maximum efficiency
                and the judicious use of shrink_to_fit() for memory reclamation.
*/

#include <vector>
#include <iostream>
#include <string>
#include <utility> // For std::move

// A custom class to demonstrate copy/move semantics during vector operations
class HeavyObject {
public:
    std::string data;
    static size_t copy_count; // Tracks copies
    static size_t move_count; // Tracks moves

    explicit HeavyObject(const std::string& d) : data(d) {
        // std::cout << "  HeavyObject constructed: " << data << std::endl;
    }

    // Copy constructor
    HeavyObject(const HeavyObject& other) : data(other.data) {
        copy_count++;
        // std::cout << "  HeavyObject copied: " << data << " (Copy Count: " << copy_count << ")" << std::endl;
    }

    // Move constructor
    HeavyObject(HeavyObject&& other) noexcept : data(std::move(other.data)) {
        move_count++;
        // std::cout << "  HeavyObject moved: " << data << " (Move Count: " << move_count << ")" << std::endl;
    }

    // Copy assignment operator
    HeavyObject& operator=(const HeavyObject& other) {
        if (this != &other) {
            data = other.data;
            copy_count++;
            // std::cout << "  HeavyObject assigned (copy): " << data << " (Copy Count: " << copy_count << ")" << std::endl;
        }
        return *this;
    }

    // Move assignment operator
    HeavyObject& operator=(HeavyObject&& other) noexcept {
        if (this != &other) {
            data = std::move(other.data);
            move_count++;
            // std::cout << "  HeavyObject assigned (move): " << data << " (Move Count: " << move_count << ")" << std::endl;
        }
        return *this;
    }
};

// Initialize static counters
size_t HeavyObject::copy_count = 0;
size_t HeavyObject::move_count = 0;

// Function to demonstrate optimal element insertion with reserve() and emplace_back()
void demonstrate_emplace_back_and_shrink_to_fit() {
    std::cout << "<p><strong>--- Emplace_back, Reserve, and Shrink_to_fit ---</strong></p>" << std::endl;

    // Reset counters for a clean demonstration
    HeavyObject::copy_count = 0;
    HeavyObject::move_count = 0;

    std::vector<HeavyObject> objects;
    const size_t expected_items = 5;
    const size_t initial_reserve = 10; // Intentionally over-reserving to show shrink_to_fit()

    objects.reserve(initial_reserve); // Reserve more than needed initially
    std::cout << "<p>  Initial capacity after reserve(" << initial_reserve << "): <strong>" << objects.capacity() << "</strong></p>" << std::endl;

    for (size_t i = 0; i < expected_items; ++i) {
        // Use emplace_back to construct HeavyObject in-place directly within the vector's memory.
        // This avoids temporary object creation and subsequent copy/move operations entirely.
        objects.emplace_back("Object_" + std::to_string(i));
    }

    std::cout << "<p>  Vector size after population: <strong>" << objects.size() << "</strong></p>" << std::endl;
    std::cout << "<p>  Vector capacity after population: <strong>" << objects.capacity() << "</strong></p>" << std::endl;
    std::cout << "<p>  HeavyObject copies during population: <strong>" << HeavyObject::copy_count << "</strong></p>" << std::endl;
    std::cout << "<p>  HeavyObject moves during population: <strong>" << HeavyObject::move_count << "</strong></p>" << std::endl;
    std::cout << "<p>  Observe minimal copies/moves due to reserve() preventing reallocations and emplace_back() constructing in-place.</p>" << std::endl;

    // After operations, if memory is a concern due to over-reservation or element removal,
    // we can use shrink_to_fit() to reclaim unused capacity.
    if (objects.capacity() > objects.size()) {
        std::cout << "<p>  Current capacity (" << objects.capacity() << ") is greater than size (" << objects.size() << "). Activating shrink_to_fit()...</p>" << std::endl;
        objects.shrink_to_fit(); // Request to reduce capacity to size()
        std::cout << "<p>  Capacity after shrink_to_fit(): <strong>" << objects.capacity() << "</strong></p>" << std::endl;
        std::cout << "<p>  Memory footprint optimized. Note: shrink_to_fit() is a non-binding request and may involve a reallocation.</p>" << std::endl;
    } else {
        std::cout << "<p>  No need to shrink_to_fit(); capacity is already optimal or equal to size.</p>" << std::endl;
    }
}

// main function is intentionally omitted here to allow for sequential compilation 
// with other parts. A combined main will be provided in the final code block.

/*
   File: vector_advanced_scenarios.cpp
   Description: Explores sophisticated applications of reserve() in data aggregation, 
                and emphasizes the importance of profiling for performance validation.
                Includes a combined main() function to execute all previous demonstrations.
*/

#include <vector>
#include <iostream>
#include <numeric> // For std::iota
#include <algorithm> // For std::for_each
#include <functional> // For std::ref
#include <chrono> // For timing

// Include function definitions from previous parts for a single compilation unit
// It's assumed these functions are defined in the same or linked translation units.
// For a truly self-contained snippet, one would copy their definitions here.

// --- Re-declaring for compilation if functions are in separate files --- 
// If compiling as one file, these declarations are not strictly needed if definitions are above.
void demonstrate_implicit_reallocations();
void demonstrate_explicit_reservation();
void demonstrate_emplace_back_and_shrink_to_fit();

// Dummy processing function to simulate computation on vector elements
void process_data(int& val) {
    val *= 2; // Simulate some computation, e.g., in a data processing pipeline
}

// Function to simulate data aggregation from multiple sources with pre-calculated total size
std::vector<int> aggregate_data(const std::vector<std::vector<int>>& sources) {
    size_t total_elements = 0;
    // First pass: calculate the exact total number of elements
    for (const auto& source_vec : sources) {
        total_elements += source_vec.size();
    }

    std::vector<int> combined_data;
    // Second pass: reserve capacity based on the known total BEFORE adding elements
    combined_data.reserve(total_elements); 

    // Third pass: efficiently insert all elements
    for (const auto& source_vec : sources) {
        // Using insert for ranges is also efficient, especially after reserve()
        combined_data.insert(combined_data.end(), source_vec.begin(), source_vec.end());
    }
    return combined_data;
}

// Function to explore advanced scenarios where reserve() plays a critical role
void explore_advanced_scenarios() {
    std::cout << "<p><strong>--- Exploring Advanced Scenarios with reserve() ---</strong></p>" << std::endl;

    // Scenario 1: Efficient Data Aggregation from multiple sources
    std::cout << "<p>  Scenario 1: Data Aggregation with Pre-calculation</p>" << std::endl;
    std::vector<std::vector<int>> data_sources;
    data_sources.push_back({1, 2, 3});
    data_sources.push_back({4, 5, 6, 7});
    data_sources.push_back({8, 9});

    auto start_agg = std::chrono::high_resolution_clock::now();
    std::vector<int> aggregated = aggregate_data(data_sources);
    auto end_agg = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> agg_duration = end_agg - start_agg;

    std::cout << "<p>  Aggregated vector size: <strong>" << aggregated.size() << "</strong>, Capacity: <strong>" << aggregated.capacity() << "</strong></p>" << std::endl;
    std::cout << "<p>  Resulting data: ";
    for (int x : aggregated) {
        std::cout << x << " ";
    }
    std::cout << "</p>" << std::endl;
    std::cout << "<p>  Execution time for aggregation: <strong>" << agg_duration.count() << " ms</strong></p>" << std::endl;
    std::cout << "<p>  Observe near-perfect capacity match due to pre-calculation and reserve(), minimizing reallocations during inserts.</p>" << std::endl;

    // Scenario 2: Processing elements in-place with a known large dataset
    std::cout << "<p>  Scenario 2: Processing a Large Pre-sized Dataset</p>" << std::endl;
    const size_t large_dataset_size = 5000000; // 5 million elements
    std::vector<int> large_dataset(large_dataset_size); // Vector is constructed with size and capacity = large_dataset_size
    std::iota(large_dataset.begin(), large_dataset.end(), 0); // Fill with 0, 1, ..., N-1

    std::cout << "<p>  Processing pre-sized vector (size: <strong>" << large_dataset.size() << "</strong>, capacity: <strong>" << large_dataset.capacity() << "</strong>)</p>" << std::endl;
    auto start_process = std::chrono::high_resolution_clock::now();
    // Use std::for_each to apply processing, ensuring no reallocations occur here
    std::for_each(large_dataset.begin(), large_dataset.end(), process_data);
    auto end_process = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> process_duration = end_process - start_process;

    std::cout << "<p>  Time to process <strong>" << large_dataset_size << "</strong> elements: <strong>" << process_duration.count() << " ms</strong></p>" << std::endl;
    std::cout << "<p>  First few elements after processing: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << large_dataset[i] << " ";
    }
    std::cout << "...<br>" << std::endl;
    std::cout << "<p>  For such large datasets, the initial allocation efficiency provided by reserve() (or constructor with size) is paramount for stable performance.</p>" << std::endl;
}

// Consolidated main function to run all demonstrations
int main() {
    std::cout << "<p>--- Starting C++ std::vector Performance Demos ---</p>" << std::endl;
    demonstrate_implicit_reallocations();
    demonstrate_explicit_reservation();
    demonstrate_emplace_back_and_shrink_to_fit();
    explore_advanced_scenarios();
    std::cout << "<p>--- All Demos Concluded ---</p>" << std::endl;
    return 0;
}