Windows Datenstrukturen - C++ Beispiele

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <random>
#include <chrono>
#include <functional>
#include <string>
#include <iterator>
#include <sstream>
#include <iomanip>
#include <unordered_set>

// 1. Basic array operations with std::vector
void BasicVectorOperations() {
    std::cout << "=== Basic Vector Operations ===" << std::endl;

    // Create and initialize vector
    std::vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    std::cout << "Original vector: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Size and capacity
    std::cout << "Size: " << numbers.size() << std::endl;
    std::cout << "Capacity: " << numbers.capacity() << std::endl;
    std::cout << "Empty: " << (numbers.empty() ? "Yes" : "No") << std::endl;

    // Access elements
    std::cout << "First element (operator[]): " << numbers[0] << std::endl;
    std::cout << "First element (at()): " << numbers.at(0) << std::endl;
    std::cout << "Last element: " << numbers.back() << std::endl;
    std::cout << "Element at index 3: " << numbers[3] << std::endl;

    // Add elements
    numbers.push_back(10);
    std::cout << "After push_back(10): ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Insert element at specific position
    auto it = numbers.begin() + 3;
    numbers.insert(it, 15);
    std::cout << "After inserting 15 at position 3: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Remove elements
    numbers.pop_back();
    numbers.erase(numbers.begin() + 2);
    std::cout << "After removing back and element at position 2: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Clear all elements
    numbers.clear();
    std::cout << "After clear - Size: " << numbers.size() << std::endl;
}

// 2. Sorting algorithms
void SortingAlgorithms() {
    std::cout << "\n=== Sorting Algorithms ===" << std::endl;

    // Create random vector for sorting demonstrations
    std::vector<int> data = {64, 34, 25, 12, 22, 11, 90, 88, 45, 50, 33};
    std::cout << "Original data: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Using std::sort
    std::vector<int> sortedData = data;
    std::sort(sortedData.begin(), sortedData.end());
    std::cout << "std::sort (ascending): ";
    for (int num : sortedData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Sort in descending order
    std::vector<int> descData = data;
    std::sort(descData.begin(), descData.end(), std::greater<int>());
    std::cout << "std::sort (descending): ";
    for (int num : descData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Sort with custom comparator (sort by last digit)
    std::vector<int> customData = data;
    std::sort(customData.begin(), customData.end(), [](int a, int b) {
        return (a % 10) < (b % 10);
    });
    std::cout << "Custom sort (by last digit): ";
    for (int num : customData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Partial sort (get top 3 elements)
    std::vector<int> partialData = data;
    std::partial_sort(partialData.begin(), partialData.begin() + 3, partialData.end());
    std::cout << "Partial sort (top 3): ";
    for (int num : partialData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Nth element (find 4th smallest)
    std::vector<int> nthData = data;
    std::nth_element(nthData.begin(), nthData.begin() + 3, nthData.end());
    std::cout << "4th smallest element: " << nthData[3] << std::endl;

    // Stable sort (preserves order of equal elements)
    std::vector<std::pair<int, std::string>> stableData = {
        {2, "Alice"}, {1, "Bob"}, {2, "Charlie"}, {1, "David"}
    };

    std::stable_sort(stableData.begin(), stableData.end(),
        [](const auto& a, const auto& b) { return a.first < b.first; });

    std::cout << "Stable sort result: ";
    for (const auto& item : stableData) {
        std::cout << "(" << item.first << "," << item.second << ") ";
    }
    std::cout << std::endl;
}

// 3. Searching operations
void SearchingOperations() {
    std::cout << "\n=== Searching Operations ===" << std::endl;

    std::vector<int> data = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21};
    std::cout << "Search data: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Linear search
    int target = 13;
    auto linearIt = std::find(data.begin(), data.end(), target);
    if (linearIt != data.end()) {
        std::cout << "Linear search: Found " << target << " at position "
                  << std::distance(data.begin(), linearIt) << std::endl;
    } else {
        std::cout << "Linear search: " << target << " not found" << std::endl;
    }

    // Binary search (requires sorted data)
    target = 15;
    bool binaryFound = std::binary_search(data.begin(), data.end(), target);
    std::cout << "Binary search: " << target << " "
              << (binaryFound ? "found" : "not found") << std::endl;

    // Find first position where condition is met
    auto conditionIt = std::find_if(data.begin(), data.end(),
        [](int value) { return value > 10; });
    if (conditionIt != data.end()) {
        std::cout << "First element > 10: " << *conditionIt
                  << " at position " << std::distance(data.begin(), conditionIt) << std::endl;
    }

    // Find all elements matching a condition
    std::vector<int> evenNumbers;
    std::copy_if(data.begin(), data.end(), std::back_inserter(evenNumbers),
        [](int value) { return value % 2 == 0; });

    std::cout << "Even numbers: ";
    for (int num : evenNumbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Adjacent find (find consecutive equal elements)
    std::vector<int> dupData = {1, 2, 3, 3, 4, 5, 5, 5, 6};
    auto adjIt = std::adjacent_find(dupData.begin(), dupData.end());
    if (adjIt != dupData.end()) {
        std::cout << "Adjacent duplicates found: " << *adjIt << " at position "
                  << std::distance(dupData.begin(), adjIt) << std::endl;
    }

    // Search for subsequence
    std::vector<int> subsequence = {7, 9, 11};
    auto subIt = std::search(data.begin(), data.end(),
                           subsequence.begin(), subsequence.end());
    if (subIt != data.end()) {
        std::cout << "Subsequence found starting at position "
                  << std::distance(data.begin(), subIt) << std::endl;
    }
}

// 4. Array transformations and operations
void ArrayTransformations() {
    std::cout << "\n=== Array Transformations ===" << std::endl;

    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::cout << "Original data: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Transform each element (square)
    std::vector<int> squared(data.size());
    std::transform(data.begin(), data.end(), squared.begin(),
                   [](int value) { return value * value; });
    std::cout << "Squared: ";
    for (int num : squared) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Filter elements
    std::vector<int> filtered;
    std::copy_if(data.begin(), data.end(), std::back_inserter(filtered),
                [](int value) { return value % 2 == 0; });
    std::cout << "Even numbers (filtered): ";
    for (int num : filtered) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Accumulate / reduce operations
    int sum = std::accumulate(data.begin(), data.end(), 0);
    std::cout << "Sum: " << sum << std::endl;

    int product = std::accumulate(data.begin(), data.end(), 1, std::multiplies<int>());
    std::cout << "Product: " << product << std::endl;

    // Calculate average
    double average = static_cast<double>(sum) / data.size();
    std::cout << "Average: " << average << std::endl;

    // Find min and max
    auto minIt = std::min_element(data.begin(), data.end());
    auto maxIt = std::max_element(data.begin(), data.end());
    std::cout << "Min: " << *minIt << ", Max: " << *maxIt << std::endl;

    // Find min and max with custom comparator
    auto minAbsIt = std::min_element(data.begin(), data.end(),
        [](int a, int b) { return std::abs(a) < std::abs(b); });
    std::cout << "Min by absolute value: " << *minAbsIt << std::endl;

    // Replace elements
    std::vector<int> replaceData = {1, 2, 3, 4, 5, 2, 3, 4};
    std::replace(replaceData.begin(), replaceData.end(), 2, 20);
    std::cout << "After replace 2 with 20: ";
    for (int num : replaceData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Replace elements matching condition
    std::replace_if(replaceData.begin(), replaceData.end(),
                   [](int value) { return value > 15; }, 99);
    std::cout << "After replace >15 with 99: ";
    for (int num : replaceData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Remove elements
    std::vector<int> removeData = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto newEnd = std::remove_if(removeData.begin(), removeData.end(),
                               [](int value) { return value % 2 == 1; });
    removeData.erase(newEnd, removeData.end());
    std::cout << "After removing odd numbers: ";
    for (int num : removeData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// 5. Set operations on arrays
void SetOperations() {
    std::cout << "\n=== Set Operations ===" << std::endl;

    std::vector<int> set1 = {1, 2, 3, 4, 5, 6, 7};
    std::vector<int> set2 = {5, 6, 7, 8, 9, 10};

    std::cout << "Set 1: ";
    for (int num : set1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::cout << "Set 2: ";
    for (int num : set2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Union
    std::vector<int> unionResult;
    std::vector<int> temp1 = set1;
    std::vector<int> temp2 = set2;

    std::sort(temp1.begin(), temp1.end());
    std::sort(temp2.begin(), temp2.end());
    std::set_union(temp1.begin(), temp1.end(),
                   temp2.begin(), temp2.end(),
                   std::back_inserter(unionResult));

    std::cout << "Union: ";
    for (int num : unionResult) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Intersection
    std::vector<int> intersectionResult;
    std::set_intersection(temp1.begin(), temp1.end(),
                         temp2.begin(), temp2.end(),
                         std::back_inserter(intersectionResult));

    std::cout << "Intersection: ";
    for (int num : intersectionResult) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Difference (elements in set1 but not in set2)
    std::vector<int> differenceResult;
    std::set_difference(temp1.begin(), temp1.end(),
                       temp2.begin(), temp2.end(),
                       std::back_inserter(differenceResult));

    std::cout << "Difference (Set1 - Set2): ";
    for (int num : differenceResult) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Symmetric difference (elements in either set but not both)
    std::vector<int> symmetricDifferenceResult;
    std::set_symmetric_difference(temp1.begin(), temp1.end(),
                                 temp2.begin(), temp2.end(),
                                 std::back_inserter(symmetricDifferenceResult));

    std::cout << "Symmetric difference: ";
    for (int num : symmetricDifferenceResult) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Check if one set is a subset of another
    bool isSubset = std::includes(temp1.begin(), temp1.end(),
                                  intersectionResult.begin(), intersectionResult.end());
    std::cout << "Intersection is subset of Set1: " << (isSubset ? "Yes" : "No") << std::endl;
}

// 6. Custom array implementation
class DynamicArray {
private:
    int* data;
    int size;
    int capacity;
    float growthFactor;

    void resize(int newCapacity) {
        int* newData = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
        std::cout << "Resized array to capacity " << newCapacity << std::endl;
    }

public:
    DynamicArray(int initialCapacity = 4) : size(0), capacity(initialCapacity), growthFactor(1.5f) {
        data = new int[capacity];
        std::cout << "Created dynamic array with capacity " << capacity << std::endl;
    }

    ~DynamicArray() {
        delete[] data;
        std::cout << "Destroyed dynamic array" << std::endl;
    }

    void push_back(int value) {
        if (size >= capacity) {
            int newCapacity = static_cast<int>(capacity * growthFactor);
            resize(newCapacity);
        }
        data[size++] = value;
        std::cout << "Added " << value << " (size: " << size << ", capacity: " << capacity << ")" << std::endl;
    }

    int pop_back() {
        if (size > 0) {
            int value = data[--size];
            std::cout << "Removed " << value << " (size: " << size << ")" << std::endl;
            return value;
        }
        throw std::out_of_range("Array is empty");
    }

    int& operator[](int index) {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index out of range");
        }
        return data[index];
    }

    const int& operator[](int index) const {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index out of range");
        }
        return data[index];
    }

    int getSize() const { return size; }
    int getCapacity() const { return capacity; }
    bool isEmpty() const { return size == 0; }

    void clear() {
        size = 0;
        std::cout << "Cleared array (size: " << size << ")" << std::endl;
    }

    void print() const {
        std::cout << "Array [";
        for (int i = 0; i < size; i++) {
            std::cout << data[i];
            if (i < size - 1) std::cout << ", ";
        }
        std::cout << "] (size: " << size << ", capacity: " << capacity << ")" << std::endl;
    }

    // Iterator support for STL algorithms
    int* begin() { return data; }
    int* end() { return data + size; }
    const int* begin() const { return data; }
    const int* end() const { return data + size; }
};

void CustomArrayOperations() {
    std::cout << "\n=== Custom Dynamic Array ===" << std::endl;

    DynamicArray arr(3);
    arr.push_back(10);
    arr.push_back(20);
    arr.push_back(30);
    arr.push_back(40); // This should trigger a resize
    arr.push_back(50);

    arr.print();

    std::cout << "Access element at index 2: " << arr[2] << std::endl;

    arr[1] = 25;
    std::cout << "After setting arr[1] = 25:" << std::endl;
    arr.print();

    int removed = arr.pop_back();
    std::cout << "Removed value: " << removed << std::endl;
    arr.print();

    // Use with STL algorithms
    int sum = std::accumulate(arr.begin(), arr.end(), 0);
    std::cout << "Sum of elements: " << sum << std::endl;

    std::sort(arr.begin(), arr.end());
    std::cout << "After sorting: ";
    arr.print();

    arr.clear();
    std::cout << "Final state: size=" << arr.getSize() << ", capacity=" << arr.getCapacity() << std::endl;
}

// 7. Performance comparison
void PerformanceComparison() {
    std::cout << "\n=== Performance Comparison ===" << std::endl;

    const int SIZE = 1000000;
    const int ITERATIONS = 100;

    // Generate random data
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 1000000);

    std::cout << "Generating " << SIZE << " random numbers..." << std::endl;

    std::vector<int> data(SIZE);
    for (int i = 0; i < SIZE; i++) {
        data[i] = dis(gen);
    }

    // Test sorting performance
    auto start = std::chrono::high_resolution_clock::now();

    std::vector<int> sortData = data;
    for (int i = 0; i < ITERATIONS; i++) {
        sortData = data; // Reset
        std::sort(sortData.begin(), sortData.end());
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto sortDuration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    std::cout << "std::sort " << ITERATIONS << " iterations: "
              << sortDuration.count() << " ms" << std::endl;

    // Test search performance
    start = std::chrono::high_resolution_clock::now();

    int searchTarget = 500000;
    for (int i = 0; i < ITERATIONS; i++) {
        auto it = std::binary_search(sortData.begin(), sortData.end(), searchTarget);
        (void)it; // Suppress unused variable warning
    }

    end = std::chrono::high_resolution_clock::now();
    auto searchDuration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "std::binary_search " << ITERATIONS << " iterations: "
              << searchDuration.count() << " μs" << std::endl;

    // Test memory usage
    size_t vectorSize = data.size() * sizeof(int);
    size_t vectorCapacity = data.capacity() * sizeof(int);

    std::cout << "Vector memory usage:" << std::endl;
    std::cout << "  Elements: " << data.size() << " x " << sizeof(int) << " bytes = "
              << vectorSize << " bytes" << std::endl;
    std::cout << "  Capacity: " << data.capacity() << " x " << sizeof(int) << " bytes = "
              << vectorCapacity << " bytes" << std::endl;
    std::cout << "  Overhead: " << (vectorCapacity - vectorSize) << " bytes" << std::endl;
}

// 8. Advanced array operations
void AdvancedArrayOperations() {
    std::cout << "\n=== Advanced Array Operations ===" << std::endl;

    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::cout << "Original data: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Rotate elements
    std::rotate(data.begin(), data.begin() + 3, data.end());
    std::cout << "After rotating left by 3: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Shuffle elements
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(data.begin(), data.end(), g);
    std::cout << "After shuffle: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Partition elements
    std::vector<int> partitionData = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto pivot = std::stable_partition(partitionData.begin(), partitionData.end(),
                                    [](int value) { return value <= 5; });
    std::cout << "After partition (<=5): ";
    for (int num : partitionData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Remove consecutive duplicates
    std::vector<int> dupData = {1, 2, 2, 3, 3, 3, 4, 5, 5};
    auto newEnd = std::unique(dupData.begin(), dupData.end());
    dupData.erase(newEnd, dupData.end());
    std::cout << "After removing consecutive duplicates: ";
    for (int num : dupData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Reverse elements
    std::vector<int> revData = {1, 2, 3, 4, 5};
    std::reverse(revData.begin(), revData.end());
    std::cout << "After reverse: ";
    for (int num : revData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Generate sequence
    std::vector<int> sequence(10);
    std::iota(sequence.begin(), sequence.end(), 1);
    std::cout << "Generated sequence: ";
    for (int num : sequence) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Apply operation in-place
    std::vector<int> transformData = {1, 2, 3, 4, 5};
    std::transform(transformData.begin(), transformData.end(), transformData.begin(),
                   [](int value) { return value * value; });
    std::cout << "After in-place square: ";
    for (int num : transformData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::cout << "=== C++ Windows Data Structures - Array Operations ===" << std::endl;
    std::cout << "Demonstrating comprehensive array manipulation techniques\n" << std::endl;

    try {
        // Run all array operation examples
        BasicVectorOperations();
        SortingAlgorithms();
        SearchingOperations();
        ArrayTransformations();
        SetOperations();
        CustomArrayOperations();
        AdvancedArrayOperations();
        PerformanceComparison();

        std::cout << "\nAll array operation examples completed successfully!" << std::endl;

    } catch (const std::exception& e) {
        std::cerr << "Unexpected error: " << e.what() << std::endl;
        return 1;
    }

    return 0;
}

#include <iostream>
#include <unordered_map>
#include <map>
#include <string>
#include <vector>
#include <functional>
#include <chrono>
#include <random>
#include <sstream>
#include <iomanip>
#include <memory>

// Custom hash function for strings
struct StringHash {
    std::size_t operator()(const std::string& key) const {
        std::size_t hash = 5381;
        for (char c : key) {
            hash = ((hash << 5) + hash) + c; // hash * 33 + c
        }
        return hash;
    }
};

// 1. Basic unordered_map operations
void BasicUnorderedMapOperations() {
    std::cout << "=== Basic Unordered Map Operations ===" << std::endl;

    // Create and initialize unordered_map
    std::unordered_map<std::string, int> scores = {
        {"Alice", 95},
        {"Bob", 87},
        {"Charlie", 92},
        {"Diana", 78}
    };

    std::cout << "Initial scores:" << std::endl;
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << std::endl;
    }

    // Check size and capacity
    std::cout << "\nSize: " << scores.size() << std::endl;
    std::cout << "Bucket count: " << scores.bucket_count() << std::endl;
    std::cout << "Load factor: " << scores.load_factor() << std::endl;
    std::cout << "Max load factor: " << scores.max_load_factor() << std::endl;

    // Access and modify elements
    std::cout << "\nAlice's score: " << scores["Alice"] << std::endl;
    scores["Alice"] = 98; // Modify existing
    std::cout << "Alice's updated score: " << scores["Alice"] << std::endl;

    // Add new element
    scores["Eve"] = 85;
    std::cout << "Added Eve with score: " << scores["Eve"] << std::endl;

    // Check if key exists
    std::string name = "Frank";
    if (scores.find(name) != scores.end()) {
        std::cout << name << "'s score: " << scores[name] << std::endl;
    } else {
        std::cout << name << " not found in scores" << std::endl;
    }

    // Use at() for safe access (throws if key not found)
    try {
        std::cout << "Bob's score (using at): " << scores.at("Bob") << std::endl;
        std::cout << "Frank's score (using at): " << scores.at("Frank") << std::endl;
    } catch (const std::out_of_range& e) {
        std::cout << "Error: " << e.what() << std::endl;
    }

    // Insert elements
    auto result = scores.insert({"Frank", 88});
    if (result.second) {
        std::cout << "Successfully inserted Frank" << std::endl;
    } else {
        std::cout << "Frank already exists" << std::endl;
    }

    // Insert or update
    scores["Frank"] = 90; // Updates if exists, inserts if doesn't
    std::cout << "Frank's score after insert/update: " << scores["Frank"] << std::endl;

    // Remove elements
    int removed = scores.erase("Diana");
    std::cout << "Removed " << removed << " elements" << std::endl;

    // Clear all elements
    // scores.clear();
    // std::cout << "Size after clear: " << scores.size() << std::endl;

    std::cout << "\nFinal scores:" << std::endl;
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << std::endl;
    }
}

// 2. Custom hash function
void CustomHashFunction() {
    std::cout << "\n=== Custom Hash Function ===" << std::endl;

    // Use custom hash function
    std::unordered_map<std::string, int, StringHash> customMap;

    // Add some elements
    std::vector<std::string> names = {"Alice", "Bob", "Charlie", "Diana", "Eve"};
    for (const auto& name : names) {
        customMap[name] = name.length() * 10; // Score based on name length
    }

    std::cout << "Custom hash map results:" << std::endl;
    for (const auto& [name, score] : customMap) {
        std::cout << name << " (hash: " << StringHash{}(name) << "): " << score << std::endl;
    }

    // Demonstrate hash distribution
    std::cout << "\nHash distribution analysis:" << std::endl;
    std::vector<std::pair<std::size_t, std::string>> hashValues;
    for (const auto& name : names) {
        std::size_t hashValue = StringHash{}(name);
        hashValues.emplace_back(hashValue, name);
    }

    std::sort(hashValues.begin(), hashValues.end());
    for (const auto& [hash, name] : hashValues) {
        std::cout << name << ": " << hash << std::endl;
    }
}

// 3. Custom hash table implementation
template<typename K, typename V>
class CustomHashTable {
private:
    struct Entry {
        K key;
        V value;
        std::shared_ptr<Entry> next; // For collision resolution via chaining

        Entry(const K& k, const V& v) : key(k), value(v), next(nullptr) {}
    };

    std::vector<std::shared_ptr<Entry>> buckets;
    std::size_t size;
    std::size_t capacity;
    float maxLoadFactor;
    std::hash<K> hashFunction;

    std::size_t getBucketIndex(const K& key) const {
        return hashFunction(key) % capacity;
    }

    void rehash(std::size_t newCapacity) {
        std::cout << "Rehashing from " << capacity << " to " << newCapacity << " buckets" << std::endl;

        std::vector<std::shared_ptr<Entry>> newBuckets(newCapacity);
        std::size_t oldCapacity = capacity;
        capacity = newCapacity;

        // Move all entries to new buckets
        for (std::size_t i = 0; i < oldCapacity; i++) {
            std::shared_ptr<Entry> current = buckets[i];
            while (current != nullptr) {
                std::shared_ptr<Entry> next = current->next;
                std::size_t newIndex = getBucketIndex(current->key);

                // Insert at beginning of new bucket
                current->next = newBuckets[newIndex];
                newBuckets[newIndex] = current;

                current = next;
            }
        }

        buckets = std::move(newBuckets);
    }

    void checkLoadFactor() {
        if (static_cast<float>(size) / capacity > maxLoadFactor) {
            std::size_t newCapacity = capacity * 2;
            rehash(newCapacity);
        }
    }

public:
    CustomHashTable(std::size_t initialCapacity = 16, float maxLoadFactor = 0.75f)
        : size(0), capacity(initialCapacity), maxLoadFactor(maxLoadFactor) {
        buckets.resize(capacity);
        std::cout << "Created custom hash table with " << capacity << " buckets" << std::endl;
    }

    ~CustomHashTable() {
        std::cout << "Destroyed custom hash table" << std::endl;
    }

    bool insert(const K& key, const V& value) {
        std::size_t index = getBucketIndex(key);
        std::shared_ptr<Entry> current = buckets[index];

        // Check if key already exists
        while (current != nullptr) {
            if (current->key == key) {
                current->value = value; // Update existing
                std::cout << "Updated existing entry for key: " << key << std::endl;
                return false;
            }
            current = current->next;
        }

        // Insert new entry at beginning of bucket
        auto newEntry = std::make_shared<Entry>(key, value);
        newEntry->next = buckets[index];
        buckets[index] = newEntry;

        size++;
        checkLoadFactor();

        std::cout << "Inserted entry - key: " << key << ", bucket: " << index
                  << " (size: " << size << ", capacity: " << capacity << ")" << std::endl;
        return true;
    }

    bool find(const K& key, V& value) const {
        std::size_t index = getBucketIndex(key);
        std::shared_ptr<Entry> current = buckets[index];

        while (current != nullptr) {
            if (current->key == key) {
                value = current->value;
                return true;
            }
            current = current->next;
        }

        return false;
    }

    bool erase(const K& key) {
        std::size_t index = getBucketIndex(key);
        std::shared_ptr<Entry> current = buckets[index];
        std::shared_ptr<Entry> previous = nullptr;

        while (current != nullptr) {
            if (current->key == key) {
                if (previous == nullptr) {
                    buckets[index] = current->next;
                } else {
                    previous->next = current->next;
                }

                size--;
                std::cout << "Erased entry - key: " << key << " (size: " << size << ")" << std::endl;
                return true;
            }

            previous = current;
            current = current->next;
        }

        return false;
    }

    std::size_t getSize() const { return size; }
    std::size_t getCapacity() const { return capacity; }
    float getLoadFactor() const { return static_cast<float>(size) / capacity; }
    bool isEmpty() const { return size == 0; }

    void printStatistics() const {
        std::cout << "Hash Table Statistics:" << std::endl;
        std::cout << "  Size: " << size << std::endl;
        std::cout << "  Capacity: " << capacity << std::endl;
        std::cout << "  Load factor: " << getLoadFactor() << std::endl;
        std::cout << "  Max load factor: " << maxLoadFactor << std::endl;

        // Bucket distribution
        std::vector<std::size_t> bucketSizes(capacity, 0);
        for (std::size_t i = 0; i < capacity; i++) {
            std::shared_ptr<Entry> current = buckets[i];
            std::size_t count = 0;
            while (current != nullptr) {
                count++;
                current = current->next;
            }
            bucketSizes[i] = count;
        }

        std::size_t maxBucketSize = *std::max_element(bucketSizes.begin(), bucketSizes.end());
        std::size_t emptyBuckets = std::count(bucketSizes.begin(), bucketSizes.end(), 0);

        std::cout << "  Max bucket size: " << maxBucketSize << std::endl;
        std::cout << "  Empty buckets: " << emptyBuckets << "/" << capacity << std::endl;

        // Print first few bucket contents
        std::cout << "  Sample bucket contents:" << std::endl;
        std::size_t samples = std::min(std::size_t(5), capacity);
        for (std::size_t i = 0; i < samples; i++) {
            std::cout << "    Bucket " << i << ": ";
            std::shared_ptr<Entry> current = buckets[i];
            if (current == nullptr) {
                std::cout << "empty";
            } else {
                while (current != nullptr) {
                    std::cout << "(" << current->key << ":" << current->value << ")";
                    if (current->next != nullptr) {
                        std::cout << " -> ";
                    }
                    current = current->next;
                }
            }
            std::cout << std::endl;
        }
    }

    void printAll() const {
        std::cout << "All entries:" << std::endl;
        for (std::size_t i = 0; i < capacity; i++) {
            std::shared_ptr<Entry> current = buckets[i];
            while (current != nullptr) {
                std::cout << "  " << current->key << ": " << current->value << std::endl;
                current = current->next;
            }
        }
    }
};

void CustomHashTableOperations() {
    std::cout << "\n=== Custom Hash Table Operations ===" << std::endl;

    CustomHashTable<std::string, int> table(4, 0.75f); // Small initial capacity to trigger rehashing

    // Insert elements
    std::vector<std::pair<std::string, int>> entries = {
        {"apple", 10},
        {"banana", 20},
        {"cherry", 30},
        {"date", 40},
        {"elderberry", 50},
        {"fig", 60},
        {"grape", 70}
    };

    for (const auto& [key, value] : entries) {
        table.insert(key, value);
    }

    table.printStatistics();

    // Test find operation
    std::cout << "\nTesting find operations:" << std::endl;
    std::string searchKey = "cherry";
    int value;
    if (table.find(searchKey, value)) {
        std::cout << "Found " << searchKey << ": " << value << std::endl;
    } else {
        std::cout << "Not found: " << searchKey << std::endl;
    }

    // Test erase operation
    std::cout << "\nTesting erase operations:" << std::endl;
    table.erase("banana");
    table.erase("nonexistent"); // Should return false

    table.printStatistics();
    table.printAll();
}

// 4. Hash table performance comparison
void PerformanceComparison() {
    std::cout << "\n=== Performance Comparison ===" << std::endl;

    const int NUM_ELEMENTS = 100000;
    const int NUM_LOOKUPS = 50000;

    // Generate random keys and values
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> keyDist(1, NUM_ELEMENTS * 10);
    std::uniform_int_distribution<> valueDist(1, 1000);

    std::vector<std::pair<int, int>> testData;
    testData.reserve(NUM_ELEMENTS);

    for (int i = 0; i < NUM_ELEMENTS; i++) {
        int key = keyDist(gen);
        int value = valueDist(gen);
        testData.emplace_back(key, value);
    }

    // Test std::unordered_map
    std::cout << "Testing std::unordered_map..." << std::endl;
    auto start = std::chrono::high_resolution_clock::now();

    std::unordered_map<int, int> unorderedMap;
    for (const auto& [key, value] : testData) {
        unorderedMap[key] = value;
    }

    auto insertEnd = std::chrono::high_resolution_clock::now();
    auto insertDuration = std::chrono::duration_cast<std::chrono::milliseconds>(insertEnd - start);

    // Random lookups
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_LOOKUPS; i++) {
        int key = keyDist(gen);
        auto it = unorderedMap.find(key);
        (void)it; // Suppress unused warning
    }

    auto lookupEnd = std::chrono::high_resolution_clock::now();
    auto lookupDuration = std::chrono::duration_cast<std::chrono::microseconds>(lookupEnd - start);

    std::cout << "std::unordered_map:" << std::endl;
    std::cout << "  Insert " << NUM_ELEMENTS << " elements: " << insertDuration.count() << " ms" << std::endl;
    std::cout << "  Lookup " << NUM_LOOKUPS << " elements: " << lookupDuration.count() << " μs" << std::endl;
    std::cout << "  Bucket count: " << unorderedMap.bucket_count() << std::endl;
    std::cout << "  Load factor: " << unorderedMap.load_factor() << std::endl;

    // Test std::map (ordered map)
    std::cout << "\nTesting std::map..." << std::endl;
    start = std::chrono::high_resolution_clock::now();

    std::map<int, int> orderedMap;
    for (const auto& [key, value] : testData) {
        orderedMap[key] = value;
    }

    insertEnd = std::chrono::high_resolution_clock::now();
    insertDuration = std::chrono::duration_cast<std::chrono::milliseconds>(insertEnd - start);

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_LOOKUPS; i++) {
        int key = keyDist(gen);
        auto it = orderedMap.find(key);
        (void)it;
    }

    lookupEnd = std::chrono::high_resolution_clock::now();
    lookupDuration = std::chrono::duration_cast<std::chrono::microseconds>(lookupEnd - start);

    std::cout << "std::map:" << std::endl;
    std::cout << "  Insert " << NUM_ELEMENTS << " elements: " << insertDuration.count() << " ms" << std::endl;
    std::cout << "  Lookup " << NUM_LOOKUPS << " elements: " << lookupDuration.count() << " μs" << std::endl;

    // Memory usage comparison
    size_t unorderedSize = unorderedMap.size() * (sizeof(int) + sizeof(int)) +
                          unorderedMap.bucket_count() * sizeof(void*);
    size_t orderedSize = orderedMap.size() * (sizeof(int) + sizeof(int) + 3 * sizeof(void*));

    std::cout << "\nMemory usage (estimated):" << std::endl;
    std::cout << "  std::unordered_map: ~" << unorderedSize << " bytes" << std::endl;
    std::cout << "  std::map: ~" << orderedSize << " bytes" << std::endl;
}

// 5. Advanced hash table techniques
void AdvancedHashTableTechniques() {
    std::cout << "\n=== Advanced Hash Table Techniques ===" << std::endl;

    // Using unordered_map with custom objects
    struct Person {
        std::string name;
        int age;
        std::string city;

        Person(const std::string& n, int a, const std::string& c)
            : name(n), age(a), city(c) {}

        bool operator==(const Person& other) const {
            return name == other.name && age == other.age;
        }
    };

    // Custom hash function for Person
    struct PersonHash {
        std::size_t operator()(const Person& p) const {
            return std::hash<std::string>{}(p.name) ^
                   (std::hash<int>{}(p.age) << 1) ^
                   (std::hash<std::string>{}(p.city) << 1);
        }
    };

    std::unordered_map<Person, std::string, PersonHash> people;
    people[Person("Alice", 30, "New York")] = "Software Engineer";
    people[Person("Bob", 25, "San Francisco")] = "Data Scientist";
    people[Person("Charlie", 35, "Chicago")] = "Product Manager";

    std::cout << "People directory:" << std::endl;
    for (const auto& [person, profession] : people) {
        std::cout << person.name << " (" << person.age << ", " << person.city
                  << "): " << profession << std::endl;
    }

    // Using unordered_set
    std::cout << "\nUsing unordered_set:" << std::endl;
    std::unordered_set<std::string> uniqueWords;
    std::string text = "the quick brown fox jumps over the lazy dog the fox is quick";
    std::istringstream iss(text);
    std::string word;

    while (iss >> word) {
        uniqueWords.insert(word);
    }

    std::cout << "Unique words in text: " << uniqueWords.size() << std::endl;
    for (const auto& w : uniqueWords) {
        std::cout << "  " << w << std::endl;
    }

    // Multi-value hash map
    std::cout << "\nMulti-value hash map simulation:" << std::endl;
    std::unordered_map<std::string, std::vector<int>> multiMap;

    multiMap["even"] = {2, 4, 6, 8, 10};
    multiMap["odd"] = {1, 3, 5, 7, 9};
    multiMap["primes"] = {2, 3, 5, 7, 11, 13};

    for (const auto& [category, numbers] : multiMap) {
        std::cout << category << ": ";
        for (int num : numbers) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }

    // Hash table with bucket iteration
    std::cout << "\nBucket iteration example:" << std::endl;
    std::unordered_map<std::string, int> exampleMap = {
        {"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}, {"e", 5}
    };

    for (std::size_t i = 0; i < exampleMap.bucket_count(); i++) {
        std::cout << "Bucket " << i << ": ";
        for (auto it = exampleMap.begin(i); it != exampleMap.end(i); ++it) {
            std::cout << "(" << it->first << ":" << it->second << ") ";
        }
        std::cout << std::endl;
    }
}

int main() {
    std::cout << "=== C++ Windows Data Structures - Hash Table ===" << std::endl;
    std::cout << "Demonstrating comprehensive hash table implementations\n" << std::endl;

    try {
        // Run all hash table examples
        BasicUnorderedMapOperations();
        CustomHashFunction();
        CustomHashTableOperations();
        PerformanceComparison();
        AdvancedHashTableTechniques();

        std::cout << "\nAll hash table examples completed successfully!" << std::endl;

    } catch (const std::exception& e) {
        std::cerr << "Unexpected error: " << e.what() << std::endl;
        return 1;
    }

    return 0;
}

#include <iostream>
#include <list>
#include <forward_list>
#include <memory>
#include <algorithm>
#include <vector>
#include <string>

// 1. Basic std::list operations
void BasicListOperations() {
    std::cout << "=== Basic std::list Operations ===" << std::endl;

    // Create and initialize list
    std::list<int> numbers = {1, 2, 3, 4, 5};
    std::cout << "Initial list: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Size operations
    std::cout << "Size: " << numbers.size() << std::endl;
    std::cout << "Empty: " << (numbers.empty() ? "Yes" : "No") << std::endl;

    // Access elements
    std::cout << "First element: " << numbers.front() << std::endl;
    std::cout << "Last element: " << numbers.back() << std::endl;

    // Add elements
    numbers.push_front(0);
    numbers.push_back(6);
    std::cout << "After push_front(0) and push_back(6): ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Insert at specific position
    auto it = numbers.begin();
    std::advance(it, 3); // Move to 4th position
    numbers.insert(it, 99);
    std::cout << "After inserting 99 at position 3: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Remove elements
    numbers.pop_front();
    numbers.pop_back();
    std::cout << "After pop_front() and pop_back(): ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Remove by value
    numbers.remove(99);
    std::cout << "After removing 99: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Remove by condition
    numbers.remove_if([](int value) { return value % 2 == 0; });
    std::cout << "After removing even numbers: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Clear list
    numbers.clear();
    std::cout << "Size after clear: " << numbers.size() << std::endl;
}

// 2. Advanced list operations
void AdvancedListOperations() {
    std::cout << "\n=== Advanced List Operations ===" << std::endl;

    std::list<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::cout << "Original data: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Splice operation - move elements from one list to another
    std::list<int> source = {100, 200, 300};
    std::cout << "\nSource list for splice: ";
    for (int num : source) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    auto it = data.begin();
    std::advance(it, 5);
    data.splice(it, source); // Move all elements from source to data

    std::cout << "After splice at position 5: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::cout << "Source list after splice: ";
    for (int num : source) {
        std::cout << num << " ";
    }
    std::cout << "(should be empty)" << std::endl;

    // Merge two sorted lists
    std::list<int> list1 = {1, 3, 5, 7, 9};
    std::list<int> list2 = {2, 4, 6, 8, 10};

    std::cout << "\nBefore merge:" << std::endl;
    std::cout << "List1: ";
    for (int num : list1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    std::cout << "List2: ";
    for (int num : list2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    list1.merge(list2);

    std::cout << "After merge:" << std::endl;
    std::cout << "List1: ";
    for (int num : list1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    std::cout << "List2: ";
    for (int num : list2) {
        std::cout << num << " ";
    }
    std::cout << "(should be empty)" << std::endl;

    // Sort and unique operations
    std::list<int> unsorted = {5, 2, 8, 1, 5, 3, 9, 2, 5, 7};
    std::cout << "\nUnsorted list: ";
    for (int num : unsorted) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    unsorted.sort();
    std::cout << "After sort: ";
    for (int num : unsorted) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    unsorted.unique();
    std::cout << "After unique: ";
    for (int num : unsorted) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Reverse list
    unsorted.reverse();
    std::cout << "After reverse: ";
    for (int num : unsorted) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Custom sort with comparator
    unsorted.sort(std::greater<int>());
    std::cout << "After custom sort (descending): ";
    for (int num : unsorted) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// 3. Custom singly linked list implementation
template<typename T>
class SinglyLinkedList {
private:
    struct Node {
        T data;
        std::unique_ptr<Node> next;

        Node(const T& value) : data(value), next(nullptr) {}
        Node(T&& value) : data(std::move(value)), next(nullptr) {}
    };

    std::unique_ptr<Node> head;
    size_t size_;

public:
    SinglyLinkedList() : head(nullptr), size_(0) {}

    ~SinglyLinkedList() {
        clear();
    }

    // Copy constructor
    SinglyLinkedList(const SinglyLinkedList& other) : size_(0) {
        for (const auto& value : other) {
            push_back(value);
        }
    }

    // Move constructor
    SinglyLinkedList(SinglyLinkedList&& other) noexcept
        : head(std::move(other.head)), size_(other.size_) {
        other.size_ = 0;
    }

    // Assignment operator
    SinglyLinkedList& operator=(const SinglyLinkedList& other) {
        if (this != &other) {
            clear();
            for (const auto& value : other) {
                push_back(value);
            }
        }
        return *this;
    }

    // Move assignment
    SinglyLinkedList& operator=(SinglyLinkedList&& other) noexcept {
        if (this != &other) {
            clear();
            head = std::move(other.head);
            size_ = other.size_;
            other.size_ = 0;
        }
        return *this;
    }

    void push_front(const T& value) {
        auto newNode = std::make_unique<Node>(value);
        newNode->next = std::move(head);
        head = std::move(newNode);
        size_++;
    }

    void push_front(T&& value) {
        auto newNode = std::make_unique<Node>(std::move(value));
        newNode->next = std::move(head);
        head = std::move(newNode);
        size_++;
    }

    void push_back(const T& value) {
        auto newNode = std::make_unique<Node>(value);

        if (!head) {
            head = std::move(newNode);
        } else {
            Node* current = head.get();
            while (current->next) {
                current = current->next.get();
            }
            current->next = std::move(newNode);
        }
        size_++;
    }

    void pop_front() {
        if (head) {
            head = std::move(head->next);
            size_--;
        }
    }

    T& front() {
        if (!head) {
            throw std::out_of_range("List is empty");
        }
        return head->data;
    }

    const T& front() const {
        if (!head) {
            throw std::out_of_range("List is empty");
        }
        return head->data;
    }

    bool empty() const {
        return head == nullptr;
    }

    size_t size() const {
        return size_;
    }

    void clear() {
        while (head) {
            head = std::move(head->next);
        }
        size_ = 0;
    }

    // Iterator support
    class Iterator {
    private:
        Node* current;

    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = T*;
        using reference = T&;

        Iterator(Node* node) : current(node) {}

        reference operator*() const { return current->data; }
        pointer operator->() const { return &current->data; }

        Iterator& operator++() {
            if (current) {
                current = current->next.get();
            }
            return *this;
        }

        Iterator operator++(int) {
            Iterator temp = *this;
            ++(*this);
            return temp;
        }

        bool operator==(const Iterator& other) const {
            return current == other.current;
        }

        bool operator!=(const Iterator& other) const {
            return current != other.current;
        }
    };

    Iterator begin() { return Iterator(head.get()); }
    Iterator end() { return Iterator(nullptr); }

    const Iterator begin() const { return Iterator(head.get()); }
    const Iterator end() const { return Iterator(nullptr); }

    // Find operation
    Iterator find(const T& value) {
        Node* current = head.get();
        while (current) {
            if (current->data == value) {
                return Iterator(current);
            }
            current = current->next.get();
        }
        return Iterator(nullptr);
    }

    // Insert after iterator
    Iterator insert_after(Iterator pos, const T& value) {
        if (pos == end()) {
            push_back(value);
            return Iterator(head.get());
        }

        Node* current = pos.current;
        auto newNode = std::make_unique<Node>(value);
        newNode->next = std::move(current->next);
        current->next = std::move(newNode);
        size_++;

        return Iterator(current->next.get());
    }

    // Erase after iterator
    Iterator erase_after(Iterator pos) {
        if (pos == end() || !pos.current->next) {
            return end();
        }

        Node* current = pos.current;
        current->next = std::move(current->next->next);
        size_--;

        return Iterator(current->next.get());
    }

    // Remove first occurrence
    bool remove(const T& value) {
        if (!head) {
            return false;
        }

        if (head->data == value) {
            pop_front();
            return true;
        }

        Node* current = head.get();
        while (current->next) {
            if (current->next->data == value) {
                current->next = std::move(current->next->next);
                size_--;
                return true;
            }
            current = current->next.get();
        }

        return false;
    }

    void print() const {
        std::cout << "List: [";
        bool first = true;
        for (const auto& value : *this) {
            if (!first) {
                std::cout << ", ";
            }
            std::cout << value;
            first = false;
        }
        std::cout << "] (size: " << size_ << ")" << std::endl;
    }
};

void CustomSinglyLinkedListOperations() {
    std::cout << "\n=== Custom Singly Linked List ===" << std::endl;

    SinglyLinkedList<int> list;
    std::cout << "Created empty list" << std::endl;

    // Add elements
    std::cout << "\nAdding elements..." << std::endl;
    list.push_back(10);
    list.push_back(20);
    list.push_back(30);
    list.push_front(5);
    list.push_front(1);
    list.print();

    // Access elements
    std::cout << "Front element: " << list.front() << std::endl;
    std::cout << "Size: " << list.size() << std::endl;
    std::cout << "Empty: " << (list.empty() ? "Yes" : "No") << std::endl;

    // Iterator operations
    std::cout << "\nIterator operations:" << std::endl;
    std::cout << "Elements using iterator: ";
    for (auto it = list.begin(); it != list.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // Find operation
    auto foundIt = list.find(20);
    if (foundIt != list.end()) {
        std::cout << "Found 20 in list" << std::endl;
        std::cout << "Next element: " << *(++foundIt) << std::endl;
    }

    // Insert after iterator
    auto insertIt = list.find(10);
    if (insertIt != list.end()) {
        list.insert_after(insertIt, 15);
        std::cout << "After inserting 15 after 10: ";
        list.print();
    }

    // Remove operation
    bool removed = list.remove(15);
    std::cout << "Removed 15: " << (removed ? "Yes" : "No") << std::endl;
    list.print();

    // Pop front
    list.pop_front();
    std::cout << "After pop_front: ";
    list.print();

    // Test range-based for loop
    std::cout << "Elements using range-based for loop: ";
    for (const auto& value : list) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    // Copy constructor test
    SinglyLinkedList<int> copy = list;
    std::cout << "Copy of list: ";
    copy.print();

    // Clear list
    list.clear();
    std::cout << "After clear - Size: " << list.size() << ", Empty: " << (list.empty() ? "Yes" : "No") << std::endl;
}

// 4. Custom doubly linked list implementation
template<typename T>
class DoublyLinkedList {
private:
    struct Node {
        T data;
        std::unique_ptr<Node> next;
        Node* prev;

        Node(const T& value) : data(value), next(nullptr), prev(nullptr) {}
        Node(T&& value) : data(std::move(value)), next(nullptr), prev(nullptr) {}
    };

    std::unique_ptr<Node> head;
    Node* tail;
    size_t size_;

    void push_back_node(std::unique_ptr<Node> node) {
        if (!head) {
            head = std::move(node);
            tail = head.get();
        } else {
            tail->next = std::move(node);
            tail->next->prev = tail;
            tail = tail->next.get();
        }
        size_++;
    }

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), size_(0) {}

    ~DoublyLinkedList() {
        clear();
    }

    void push_back(const T& value) {
        push_back_node(std::make_unique<Node>(value));
    }

    void push_back(T&& value) {
        push_back_node(std::make_unique<Node>(std::move(value)));
    }

    void push_front(const T& value) {
        auto newNode = std::make_unique<Node>(value);
        if (!head) {
            head = std::move(newNode);
            tail = head.get();
        } else {
            newNode->next = std::move(head);
            head->prev = newNode.get();
            head = std::move(newNode);
        }
        size_++;
    }

    void pop_front() {
        if (head) {
            head = std::move(head->next);
            if (head) {
                head->prev = nullptr;
            } else {
                tail = nullptr;
            }
            size_--;
        }
    }

    void pop_back() {
        if (tail) {
            if (tail->prev) {
                tail = tail->prev;
                delete tail->next.release();
                tail->next = nullptr;
            } else {
                head.reset();
                tail = nullptr;
            }
            size_--;
        }
    }

    T& front() {
        if (!head) {
            throw std::out_of_range("List is empty");
        }
        return head->data;
    }

    T& back() {
        if (!tail) {
            throw std::out_of_range("List is empty");
        }
        return tail->data;
    }

    const T& front() const {
        if (!head) {
            throw std::out_of_range("List is empty");
        }
        return head->data;
    }

    const T& back() const {
        if (!tail) {
            throw std::out_of_range("List is empty");
        }
        return tail->data;
    }

    bool empty() const {
        return head == nullptr;
    }

    size_t size() const {
        return size_;
    }

    void clear() {
        while (head) {
            head = std::move(head->next);
        }
        tail = nullptr;
        size_ = 0;
    }

    // Reverse iterator support
    class ReverseIterator {
    private:
        Node* current;

    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = T*;
        using reference = T&;

        ReverseIterator(Node* node) : current(node) {}

        reference operator*() const { return current->data; }
        pointer operator->() const { return &current->data; }

        ReverseIterator& operator++() {
            if (current) {
                current = current->prev;
            }
            return *this;
        }

        ReverseIterator operator++(int) {
            ReverseIterator temp = *this;
            ++(*this);
            return temp;
        }

        ReverseIterator& operator--() {
            if (current) {
                current = current->next.get();
            }
            return *this;
        }

        ReverseIterator operator--(int) {
            ReverseIterator temp = *this;
            --(*this);
            return temp;
        }

        bool operator==(const ReverseIterator& other) const {
            return current == other.current;
        }

        bool operator!=(const ReverseIterator& other) const {
            return current != other.current;
        }
    };

    // Forward iterator
    class Iterator {
    private:
        Node* current;

    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = T*;
        using reference = T&;

        Iterator(Node* node) : current(node) {}

        reference operator*() const { return current->data; }
        pointer operator->() const { return &current->data; }

        Iterator& operator++() {
            if (current) {
                current = current->next.get();
            }
            return *this;
        }

        Iterator operator++(int) {
            Iterator temp = *this;
            ++(*this);
            return temp;
        }

        Iterator& operator--() {
            if (current) {
                current = current->prev;
            } else {
                // If current is null, we're at end(), so move to tail
                current = tail;
            }
            return *this;
        }

        Iterator operator--(int) {
            Iterator temp = *this;
            --(*this);
            return temp;
        }

        bool operator==(const Iterator& other) const {
            return current == other.current;
        }

        bool operator!=(const Iterator& other) const {
            return current != other.current;
        }
    };

    Iterator begin() { return Iterator(head.get()); }
    Iterator end() { return Iterator(nullptr); }
    ReverseIterator rbegin() { return ReverseIterator(tail); }
    ReverseIterator rend() { return ReverseIterator(nullptr); }

    void print() const {
        std::cout << "List: [";
        bool first = true;
        for (const auto& value : *this) {
            if (!first) {
                std::cout << ", ";
            }
            std::cout << value;
            first = false;
        }
        std::cout << "] (size: " << size_ << ")" << std::endl;
    }

    void print_reverse() const {
        std::cout << "Reverse: [";
        bool first = true;
        for (auto it = rbegin(); it != rend(); ++it) {
            if (!first) {
                std::cout << ", ";
            }
            std::cout << *it;
            first = false;
        }
        std::cout << "]" << std::endl;
    }
};

void CustomDoublyLinkedListOperations() {
    std::cout << "\n=== Custom Doubly Linked List ===" << std::endl;

    DoublyLinkedList<std::string> list;
    std::cout << "Created empty string list" << std::endl;

    // Add elements
    std::cout << "\nAdding elements..." << std::endl;
    list.push_back("World");
    list.push_front("Hello");
    list.push_back("!");
    list.push_back("C++");
    list.push_front("Start:");

    list.print();
    list.print_reverse();

    // Access elements
    std::cout << "Front element: " << list.front() << std::endl;
    std::cout << "Back element: " << list.back() << std::endl;

    // Remove elements
    std::cout << "\nRemoving elements..." << std::endl;
    list.pop_front();
    std::cout << "After pop_front: ";
    list.print();

    list.pop_back();
    std::cout << "After pop_back: ";
    list.print();

    // Bidirectional iteration
    std::cout << "\nForward iteration: ";
    for (auto it = list.begin(); it != list.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    std::cout << "Reverse iteration: ";
    for (auto it = list.rbegin(); it != list.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

// 5. List algorithms and operations
void ListAlgorithms() {
    std::cout << "\n=== List Algorithms and Operations ===" << std::endl;

    std::list<int> data = {64, 34, 25, 12, 22, 11, 90, 88, 45, 50};
    std::cout << "Original data: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Sort the list
    data.sort();
    std::cout << "After sort: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Find elements
    auto it = std::find(data.begin(), data.end(), 45);
    if (it != data.end()) {
        std::cout << "Found 45 in the list" << std::endl;
        std::cout << "Distance from begin: " << std::distance(data.begin(), it) << std::endl;
    }

    // Find if any element satisfies condition
    auto evenIt = std::find_if(data.begin(), data.end(), [](int value) {
        return value % 2 == 0;
    });
    if (evenIt != data.end()) {
        std::cout << "First even number: " << *evenIt << std::endl;
    }

    // Count elements
    int evenCount = std::count_if(data.begin(), data.end(), [](int value) {
        return value % 2 == 0;
    });
    std::cout << "Number of even elements: " << evenCount << std::endl;

    // Transform elements
    std::transform(data.begin(), data.end(), data.begin(), [](int value) {
        return value * 2;
    });
    std::cout << "After doubling all elements: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Accumulate values
    int sum = std::accumulate(data.begin(), data.end(), 0);
    std::cout << "Sum of all elements: " << sum << std::endl;

    // Partition list
    std::list<int> partitionData = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto partitionPoint = std::stable_partition(partitionData.begin(), partitionData.end(),
                                            [](int value) { return value <= 5; });

    std::cout << "\nAfter stable partition (<=5): ";
    for (int num : partitionData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Generate sequence into list
    std::list<int> sequence(10);
    std::iota(sequence.begin(), sequence.end(), 1);
    std::cout << "Generated sequence: ";
    for (int num : sequence) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::cout << "=== C++ Windows Data Structures - Linked List ===" << std::endl;
    std::cout << "Demonstrating comprehensive linked list implementations\n" << std::endl;

    try {
        // Run all linked list examples
        BasicListOperations();
        AdvancedListOperations();
        CustomSinglyLinkedListOperations();
        CustomDoublyLinkedListOperations();
        ListAlgorithms();

        std::cout << "\nAll linked list examples completed successfully!" << std::endl;

    } catch (const std::exception& e) {
        std::cerr << "Unexpected error: " << e.what() << std::endl;
        return 1;
    }

    return 0;
}