Unordered Containers - Hash Tables in C++

#include <unordered_map>
#include <unordered_set>

// Hash table versions - O(1) average case lookup
std::unordered_map<std::string, int> hash_map;
std::unordered_set<std::string> hash_set;

// Tree versions - O(log n) lookup but always sorted
std::map<std::string, int> tree_map;
std::set<std::string> tree_set;

// Benchmark results I've seen in practice:
//
// Container          | Insert  | Find   | Iterate
// std::map          | O(log n)| O(log n)| O(n) sorted
// std::unordered_map| O(1)*   | O(1)*  | O(n) unordered
//
// *Average case - worst case can be O(n) with bad hash function

class UserCache {
    std::unordered_map<int, User> cache_;

public:
    std::optional<User> get_user(int user_id) {
        auto it = cache_.find(user_id);
        if (it != cache_.end()) {
            return it->second;  // Cache hit - O(1) average
        }

        // Cache miss - load from database
        if (auto user = load_user_from_db(user_id)) {
            cache_[user_id] = user.value();
            return user;
        }

        return std::nullopt;
    }

    void update_user(const User& user) {
        cache_[user.id] = user;  // O(1) average update
    }
};

std::unordered_map<std::string, int> count_words(const std::vector<std::string>& words) {
    std::unordered_map<std::string, int> counts;

    for (const auto& word : words) {
        counts[word]++;  // Increment count, creates entry if doesn't exist
    }

    return counts;
}

// Usage
std::vector<std::string> text = {"hello", "world", "hello", "cpp", "world"};
auto word_counts = count_words(text);

for (const auto& [word, count] : word_counts) {
    std::cout << word << ": " << count << std::endl;
}
// Output (order not guaranteed):
// hello: 2
// cpp: 1
// world: 2

class DuplicateDetector {
    std::unordered_set<std::string> seen_items_;

public:
    bool is_duplicate(const std::string& item) {
        auto [it, inserted] = seen_items_.insert(item);
        return !inserted;  // If insert failed, it was already there
    }

    void process_items(const std::vector<std::string>& items) {
        for (const auto& item : items) {
            if (is_duplicate(item)) {
                std::cout << "Duplicate found: " << item << std::endl;
            }
        }
    }
};

class PermissionChecker {
    std::unordered_set<std::string> allowed_actions_;

public:
    PermissionChecker(const std::vector<std::string>& permissions)
        : allowed_actions_(permissions.begin(), permissions.end()) {}

    bool can_perform(const std::string& action) const {
        return allowed_actions_.find(action) != allowed_actions_.end();
        // or: return allowed_actions_.contains(action);  // C++20
    }
};

PermissionChecker checker({"read", "write", "delete"});
if (checker.can_perform("write")) {
    // Perform write operation - O(1) check
}

struct Point {
    int x, y;

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// Custom hash function
struct PointHash {
    std::size_t operator()(const Point& p) const {
        // Simple hash combination
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    }
};

// Usage
std::unordered_set<Point, PointHash> point_set;
std::unordered_map<Point, std::string, PointHash> point_names;

point_set.insert({10, 20});
point_names[{5, 15}] = "Origin";

// Bad hash - everything maps to the same bucket
struct BadHash {
    std::size_t operator()(const std::string& s) const {
        return 42;  // Terrible! Everything collides
    }
};

// Better hash - use the standard library
struct GoodHash {
    std::size_t operator()(const std::string& s) const {
        return std::hash<std::string>{}(s);  // Let the experts handle it
    }
};

// For most cases, just let the compiler choose:
std::unordered_map<std::string, int> map;  // Uses default std::hash<std::string>

class StringInterner {
    static std::unordered_set<std::string> interned_strings_;

public:
    // Return a reference to the interned string
    static const std::string& intern(const std::string& str) {
        auto [it, inserted] = interned_strings_.insert(str);
        return *it;  // Return reference to the string in the set
    }

    // Check if a string is already interned
    static bool is_interned(const std::string& str) {
        return interned_strings_.find(str) != interned_strings_.end();
    }

    // Get statistics
    static std::pair<size_t, size_t> get_stats() {
        return {interned_strings_.size(), interned_strings_.bucket_count()};
    }
};

// Static member definition
std::unordered_set<std::string> StringInterner::interned_strings_;

// Usage - save memory by sharing identical strings
const std::string& name1 = StringInterner::intern("John");
const std::string& name2 = StringInterner::intern("John");
// name1 and name2 refer to the same string object in memory

std::unordered_map<int, std::string> map;

// Monitor load factor
std::cout << "Load factor: " << map.load_factor() << std::endl;
std::cout << "Max load factor: " << map.max_load_factor() << std::endl;
std::cout << "Bucket count: " << map.bucket_count() << std::endl;

// You can tune performance by reserving capacity
map.reserve(1000);  // Avoid rehashing for the first 1000 elements

// These are better with ordered containers:
auto range = map.lower_bound("A");  // Find all keys starting with "A"
for (const auto& [key, value] : map) {
    // Process in alphabetical order
}

// Default choice for key-value storage
std::unordered_map<UserId, UserData> users;
std::unordered_set<std::string> processed_files;

// Switch to ordered versions only when I need:
// 1. Sorted iteration
std::map<std::string, int> sorted_scores;

// 2. Range queries
std::set<int> sorted_ids;
auto range = sorted_ids.lower_bound(100);