如何在 C++ 中创建递归嵌套哈希映射？

Question

def recursiveDict():
   return collections.defaultdict(recursiveDict)

# I can create a dictionary like the following
dic = recursiveDict()
dic['a'] = 1
dic['a']['a'] = 1
dic['a']['a']['a'] = 1
dic['a']['a']['a']['a'] = 1
and so on....

在使用 Python 和其他动态语言工作了 4 年后，我重新开始使用 C++。我希望能够使用 unordered_map 或映射 class.

创建一个递归嵌套列表（如上面 Python 代码中所示的列表）

我找不到办法做到这一点。

我要实现的是key是char/string类型，插入的值是int类型

请告诉我如何做到这一点。

我最接近的是这个

struct CharMap {
    std::unordered_map<char,CharMap> map;
} root_map;

and use it like

root_map.map['a'].map['b'];

但是我应该重载什么才能获得上面的确切语法？

提前致谢。

Answer 1

既然您明确表示您熟悉运算符重载的基本概念，我将勾勒出一个基本蓝图，您可以按照该蓝图来实现此语法。

您的容器将实施 operator[] 重载，return 是一个辅助对象。假设您的容器名为 CharMap，总而言之，您的容器存储 ints.

class CharMap {

    struct key {

        key operator[](const std::string &);

        operator int();

        key &operator=(int n);
    };

public:

    key operator[](const std::string &);

};

这将允许，例如：

CharMap container;

container["A"]["B"]["C"]=5;

int n=container["D"]["E"]["F"};

CharMap::operator[] return 是一个 key 辅助对象。该对象还实现了自己的 operator[] 重载，return 是另一个 key。最后，key 对象实现了一个 operator= 重载，因此您可以将其赋值，或者 operator int() 重载到 return 容器中的值。

很明显，key 会在内部存储指向它来自的 CharMap 容器的指针，以便它可以更新或 return 适当的来自容器的价值。 key 还在内部以零碎的方式跟踪所有用于创建它的键。 CharMap::key 在内部记录第一个字符串。然后，它的 key::operator[] return 是另一个 key，在内部记录原始字符串和另一个字符串。

一旦 operator[] 或 operator int() 被调用，它们将使用所有累积的字符串来完成它们的工作，以您需要弄清楚的某种形式或方式。

还有一些效率问题可能会或可能不会被解决。这种方法实现了你想要的语法，但根据你的情况，它可能需要一些微调来优化底层实现，以消除一堆内部复制和改组。

此外，还需要做一些额外的工作来实现正确的 const-正确性。但所有这些都只是实现细节，这就是您如何实现这种语法来访问由多个字符串索引的容器。

Answer 2

I wanted to be able to create a recursive nested list(like the one shown in the Python code above)

我怀疑你是否真的想这样做。当然，我们不知道您尝试使用它的详细信息，但是：

如果您希望您的关联结构由短字符串键入，请考虑使用 std::string 键，例如std::unoredered_map<std::string, int>.
如果您希望您的关联结构仅由 K 个字符序列作为键 - 使用类似 struct key { char[K] data; } 的东西作为您的键（并可能为该键添加相关方法/转换运算符 class ), 或者 std::array<char, K>.
等等

我怀疑的是，您真的需要能够说“我正在部分应用密钥”，而且不能将一般哈希和部分密钥（例如字符串前缀）视为您的“子哈希映射” ".

PS - 如果性能是一个问题，请记住。 std::string 作为键也会减慢你的速度，因为它们通常将字符串数据存储在堆上，这意味着一堆 de/allocation 工作并访问堆上可能任意的位置。

如何在 C++ 中创建递归嵌套哈希映射？

How to create a recursive nested hashmap in C++?

c++

recursion

stl

hashmap

data-structures