C++-----------映射

探索 C++ 中的映射与查找表
在 C++ 编程中，映射（Map）和查找表（Lookup Table）是非常重要的数据结构，它们能够高效地存储和检索数据，帮助我们解决各种实际问题。今天，我们就来深入探讨一下如何在 C++ 中实现这些数据结构，包括使用矢量（Vector）实现映射以及使用哈希（Hash）实现 hashMap 类。

一、使用矢量实现映射 矢量（std::vector）是 C++ 标准库中的一个强大的容器，我们可以借助它来实现简单的映射功能。

#include <iostream>
#include <vector>
#include <utility>
#include <stdexcept>

template <typename Key, typename Value>
class VectorMap {
private:
    std::vector<std::pair<Key, Value>> data;

    // 查找键的位置
    int find(const Key& key) const {
        for (size_t i = 0; i < data.size(); ++i) {
            if (data[i].first == key) {
                return i;
            }
        }
        return -1;
    }

public:
    VectorMap() {}

    // 插入键值对
    void insert(const Key& key, const Value& value) {
        int index = find(key);
        if (index == -1) {
            data.push_back(std::make_pair(key, value));
        } else {
            data[index].second = value;
        }
    }

    // 获取值
    Value& operator[](const Key& key) {
        int index = find(key);
        if (index == -1) {
            data.push_back(std::make_pair(key, Value()));
            return data.back().second;
        }
        return data[index].second;
    }

    // 删除键值对
    void erase(const Key& key) {
        int index = find(key);
        if (index!= -1) {
            data.erase(data.begin() + index);
        }
    }

    // 判断键是否存在
    bool contains(const Key& key) const {
        return find(key)!= -1;
    }

    // 获取映射大小
    size_t size() const {
        return data.size();
    }

    // 清空映射
    void clear() {
        data.clear();
    }

    // 检查映射是否为空
    bool empty() const {
        return data.empty();
    }

 - [ ] List item

};

在这个 VectorMap 类中，我们使用一个 std::vector 来存储键值对（std::pair）。find
函数用于查找给定键在向量中的位置，如果未找到则返回 -1。insert
函数根据键是否已存在来决定是插入新的键值对还是更新已有键的值。operator[] 函数提供了方便的访问方式，类似于 std::map
的操作，如果键不存在则会插入一个默认值并返回其引用。erase 函数用于删除指定键的键值对，contains
函数用于判断键是否存在于映射中，其他函数则用于获取映射的大小、清空映射以及检查映射是否为空。

二、查找表 查找表是一种用于快速查找数据的数据结构，我们可以使用 std::vector 来简单实现一个查找表。

#include <iostream>
#include <vector>

template <typename T>
class LookupTable {
private:
    std::vector<T> data;

public:
    LookupTable() {}

    // 插入元素
    void insert(const T& value) {
        data.push_back(value);
    }

    // 查找元素
    bool contains(const T& value) const {
        for (const T& element : data) {
            if (element == value) {
                return true;
            }
        }
        return false;
    }

    // 获取查找表大小
    size_t size() const {
        return data.size();
    }

    // 清空查找表
    void clear() {
        data.clear();
    }

    // 检查查找表是否为空
    bool empty() const {
        return data.empty();
    }
};

这个 LookupTable
类非常简单，它提供了插入元素、查找元素以及获取查找表大小、清空查找表和检查查找表是否为空的功能。插入元素就是将元素添加到
std::vector 中，查找元素则是遍历向量来判断是否存在给定元素。

三、哈希实现 hashMap 类
哈希表是一种高效的查找数据结构，通过哈希函数将键映射到桶（Bucket）中，每个桶可以存储多个键值对。下面是使用哈希实现 hashMap
类的代码：

#include <iostream>
#include <vector>
#include <list>
#include <utility>
#include <functional>

template <typename Key, typename Value>
class HashMap {
private:
    std::vector<std::list<std::pair<Key, Value>>> buckets;
    size_t size_;

    // 哈希函数
    size_t hash(const Key& key) const {
        std::hash<Key> hasher;
        return hasher(key) % buckets.size();
    }

public:
    HashMap(size_t bucket_count = 10) : size_(0) {
        buckets.resize(bucket_count);
    }

    // 插入键值对
    void insert(const Key& key, const Value& value) {
        size_t index = hash(key);
        for (auto& pair : buckets[index]) {
            if (pair.first == key) {
                pair.second = value;
                return;
            }
        }
        buckets[index].push_back(std::make_pair(key, value));
        size_++;
    }

    // 获取值
    Value& operator[](const Key& key) {
        size_t index = hash(key);
        for (auto& pair : buckets[index]) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        buckets[index].push_back(std::make_pair(key, Value()));
        size_++;
        return buckets[index].back().second;
    }

    // 删除键值对
    void erase(const Key& key) {
        size_t index = hash(key);
        auto& bucket = buckets[index];
        for (auto it = bucket.begin(); it!= bucket.end(); ++it) {
            if (it->first == key) {
                bucket.erase(it);
                size_--;
                return;
            }
        }
    }

    // 判断键是否存在
    bool contains(const Key& key) const {
        size_t index = hash(key);
        for (const auto& pair : buckets[index]) {
            if (pair.first == key) {
                return true;
            }
        }
        return false;
    }

    // 获取映射大小
    size_t size() const {
        return size_;
    }

    // 清空映射
    void clear() {
        buckets.clear();
        size_ = 0;
    }

    // 检查映射是否为空
    bool empty() const {
        return size_ == 0;
    }
};

***在 HashMap 类中，我们使用一个 std::vector 来存储桶，每个桶是一个 std::list，用于解决哈希冲突。hash 函数使用 std::hash 函数将键映射到桶的索引。insert 函数首先根据哈希值找到对应的桶，然后查找键是否已存在，

如果存在则更新值，否则将新的键值对插入到桶中。operator[] 函数类似地先查找键，如果不存在则插入默认值并返回其引用。erase 函数用于删除指定键的键值对，contains 函数用于判断键是否存在于哈希表中，其他函数用于获取哈希表的大小、清空哈希表以及检查哈希表是否为空。*

*通过以上三种实现方式，我们可以根据不同的场景选择合适的数据结构来满足需求。矢量实现的映射简单直观，适用于数据量较小且对性能要求不高的情况；查找表则侧重于快速判断元素是否存在；

而哈希实现的 hashMap 类在处理大量数据时具有较高的查找效率，但需要注意哈希冲突的处理和哈希函数的选择。在实际编程中，我们可以根据数据的特点和操作的频繁程度来灵活运用这些数据结构，以提升程序的性能和效率。***

希望这篇文章能够帮助大家更好地理解 C++ 中的映射和查找表的实现方式，如果你有任何问题或建议，欢迎在评论区留言。