main.cpp

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

using namespace std;

struct Person {
    char name[64];
    int age;
};

int main()
{
    int n;
    cout << "========================================\n";
    cout << "    Data Structure Search Comparison\n";
    cout << "========================================\n\n";
    cout << "How many elements do you want to insert? ";
    cin >> n;
    cin.ignore();
    
    // Create containers
    list<Person> personList;
    map<string, int> personMap;
    unordered_map<string, int> personUnorderedMap;
    
    vector<string> insertedNames;
    
    // Dummy names
    vector<string> names = {
        "Alice", "Bob", "Charlie", "David", "Eve", "Frank",
        "Grace", "Henry", "Ivy", "Jack", "Kate", "Leo",
        "Mia", "Noah", "Olivia", "Peter", "Quinn", "Rachel",
        "Sam", "Tina", "Uma", "Victor", "Wendy", "Xavier",
        "Yara", "Zoe", "Aaron", "Brian", "Chris", "Diana"
    };
    
    // Insert data into all three containers
    cout << "\nInserting " << n << " elements...\n";
    for (int i = 0; i < n; i++) {
        Person p;
        string name = names[i % names.size()] + "_" + to_string(i);
        strcpy(p.name, name.c_str());
        p.age = 20 + (i % 60);
        
        personList.push_back(p);
        personMap[name] = p.age;
        personUnorderedMap[name] = p.age;
        insertedNames.push_back(name);
    }
    
    cout << "Insertion complete!\n";
    
    // Display 5 random names
    cout << "\n========================================\n";
    cout << "    Five Random Names Inserted\n";
    cout << "========================================\n";
    
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, insertedNames.size() - 1);
    
    for (int i = 0; i < 5; i++) {
        int randIdx = dis(gen);
        cout << (i + 1) << ". " << insertedNames[randIdx] << "\n";
    }
    
    // Ask user to search
    cout << "\n========================================\n";
    string searchName;
    cout << "Enter a name to search: ";
    getline(cin, searchName);
    cout << "========================================\n\n";
    
    // Search in List
    cout << "--- Searching in LIST (std::list) ---\n";
    auto startClockList = clock();
    auto startTimeList = chrono::high_resolution_clock::now();
    
    auto itList = find_if(personList.begin(), personList.end(),
                          [&searchName](const Person& p) {
                              return searchName == p.name;
                          });
    
    auto endTimeList = chrono::high_resolution_clock::now();
    auto endClockList = clock();
    
    double cpuTimeList = double(endClockList - startClockList) / CLOCKS_PER_SEC * 1000000;
    double wallTimeList = chrono::duration<double, micro>(endTimeList - startTimeList).count();
    
    if (itList != personList.end()) {
        cout << "Status: FOUND\n";
        cout << "Data: Name = " << itList->name << ", Age = " << itList->age << "\n";
    } else {
        cout << "Status: NOT FOUND\n";
    }
    cout << "CPU Time: " << cpuTimeList << " microseconds\n";
    cout << "Wall Clock Time: " << wallTimeList << " microseconds\n\n";
    
    // Search in Map (Red-Black Tree)
    cout << "--- Searching in MAP (std::map - Ordered) ---\n";
    auto startClockMap = clock();
    auto startTimeMap = chrono::high_resolution_clock::now();
    
    auto itMap = personMap.find(searchName);
    
    auto endTimeMap = chrono::high_resolution_clock::now();
    auto endClockMap = clock();
    
    double cpuTimeMap = double(endClockMap - startClockMap) / CLOCKS_PER_SEC * 1000000;
    double wallTimeMap = chrono::duration<double, micro>(endTimeMap - startTimeMap).count();
    
    if (itMap != personMap.end()) {
        cout << "Status: FOUND\n";
        cout << "Data: Name = " << itMap->first << ", Age = " << itMap->second << "\n";
    } else {
        cout << "Status: NOT FOUND\n";
    }
    cout << "CPU Time: " << cpuTimeMap << " microseconds\n";
    cout << "Wall Clock Time: " << wallTimeMap << " microseconds\n\n";
    
    // Search in Unordered Map (Hash Table)
    cout << "--- Searching in UNORDERED_MAP (Hash Table) ---\n";
    auto startClockUnorderedMap = clock();
    auto startTimeUnorderedMap = chrono::high_resolution_clock::now();
    
    auto itUnorderedMap = personUnorderedMap.find(searchName);
    
    auto endTimeUnorderedMap = chrono::high_resolution_clock::now();
    auto endClockUnorderedMap = clock();
    
    double cpuTimeUnorderedMap = double(endClockUnorderedMap - startClockUnorderedMap) / CLOCKS_PER_SEC * 1000000;
    double wallTimeUnorderedMap = chrono::duration<double, micro>(endTimeUnorderedMap - startTimeUnorderedMap).count();
    
    if (itUnorderedMap != personUnorderedMap.end()) {
        cout << "Status: FOUND\n";
        cout << "Data: Name = " << itUnorderedMap->first << ", Age = " << itUnorderedMap->second << "\n";
    } else {
        cout << "Status: NOT FOUND\n";
    }
    cout << "CPU Time: " << cpuTimeUnorderedMap << " microseconds\n";
    cout << "Wall Clock Time: " << wallTimeUnorderedMap << " microseconds\n\n";
    
    // Summary
    cout << "========================================\n";
    cout << "           PERFORMANCE SUMMARY\n";
    cout << "========================================\n";
    cout << "List (Linear Search)\n";
    cout << "  - CPU Time: " << cpuTimeList << " microseconds\n";
    cout << "  - Wall Time: " << wallTimeList << " microseconds\n\n";
    cout << "Map (Red-Black Tree, O(log n))\n";
    cout << "  - CPU Time: " << cpuTimeMap << " microseconds\n";
    cout << "  - Wall Time: " << wallTimeMap << " microseconds\n\n";
    cout << "Unordered Map (Hash Table, O(1) avg)\n";
    cout << "  - CPU Time: " << cpuTimeUnorderedMap << " microseconds\n";
    cout << "  - Wall Time: " << wallTimeUnorderedMap << " microseconds\n";
    cout << "========================================\n";
    
    return 0;
}