21xrx.com
2025-04-11 16:49:47 Friday
文章检索 我的文章 写文章
如何用 C++ 简单实现 map 数据结构
2023-07-10 21:33:35 深夜i     28     0
C++ map 数据结构 实现 简单

Map 是一种常用的数据结构，它可以将一些键值对存储在其中，使得我们可以通过键来快速访问对应的值。在 C++ 中，STL 提供了内置的 Map 类可以实现这一功能，但我们也可以手动实现一个简单的 Map 数据结构。

在实现 Map 数据结构之前，我们需要了解一些基础的概念。首先，Map 数据结构中的键是唯一的，因此我们需要用一个容器来存储这些键。在 C++ 中，可以选择使用数组或者链表等不同的数据结构来存储键值对。对于值的存储，我们可以使用数组或者链表等数据结构来存储对应的值。在此，我们选择使用链表来存储键和值的对应关系。

下面是一个简单的 Map 数据结构的实现:

c++
#include <iostream>
#include <string>
using namespace std;
struct Node {
  string key;
  int value;
  Node* next;
  Node(string key, int value) : key(key), value(value), next(nullptr) {}
  ~Node()
    delete next;
  
};
class Map {
private:
  Node* head;
public:
  Map() : head(nullptr) {}
  ~Map()
    delete head;
  
  void put(string key, int value) {
    Node* node = new Node(key, value);
    if (!head)
      head = node;
      return;
    
    Node* curr = head;
    while (curr->next) {
      if (curr->key == key)
        curr->value = value;
        delete node;
        return;
      
      curr = curr->next;
    }
    if (curr->key == key)
      curr->value = value;
      delete node;
      return;
    
    
    curr->next = node;
  }
  int get(string key) {
    Node* curr = head;
    while (curr) {
      if (curr->key == key)
        return curr->value;
      curr = curr->next;
    }
    throw "The key does not exist!";
  }
  bool contains(string key) {
    Node* curr = head;
    while (curr) {
      if (curr->key == key)
        return true;
      curr = curr->next;
    }
    return false;
  }
};
int main() {
  Map map;
  map.put("apple", 1);
  map.put("banana", 2);
  map.put("cherry", 3);
  cout << map.get("banana") << endl;
  cout << map.contains("apple") << endl;
  cout << map.contains("orange") << endl;
  return 0;
}

在以上代码中，我们首先定义了一个结构体 `Node` 用于存储键和值，并使用链表的方式将每一个 `Node` 节点连接起来。接着，我们定义了一个 `Map` 类，包含了向 Map 中添加键值对的 `put` 方法、根据键查询对应值的 `get` 方法以及判断是否包含某个键的 `contains` 方法。

在使用 Map 数据结构时，我们需要注意到其中一些细节问题。比如，如果我们向 Map 中添加一个已经存在的键，应当更新对应的值。在上述代码中，我们通过遍历链表来实现这一更新操作。同样的，如果根据一个不存在的键查询对应的值，我们需要抛出一个异常报错。在实现这些操作时，我们需要深入思考 Map 数据结构的具体实现细节。

总之，手动实现一个 Map 数据结构是一项很有趣的挑战。在具体实现时，我们可以选择不同的数据结构和算法，以实现最优的效果。我们可以通过加强对其应用场景的了解，来优化相应的实现。

  
  

评论区