c++ - 使用哈希表构建符号表

Question

我正在尝试使用哈希表构建符号表。总体思路是

int alpha;
2 int beta;
3 alpha = 0; // the alpha declared in line 1
4 beta = 0; // the beta declared in line 2
5 gamma = 0; // Error! gamma hasn't been declared.
6 {
7 int beta; // This beta shadows the one declared in line 2.
8 int gamma;
9 alpha = 0; // the alpha declared in line 1
10 beta = 0; // the beta declared in line 7
11 gamma = 0; // the gamma declared in line 8
12 }

等等。您只能使用 vector 、列表、堆栈和队列库，并尝试使其尽可能快。 我的想法是在每个范围内，我在列表中声明哈希表并将所有信息保存到该表中，每当我有新的范围时，我将新的哈希表 push_back 到列表中。 但是，当程序在很远的范围之外查找项目时，这种方法似乎非常慢，因为您必须查找每个范围才能找到该项目。

你们有什么想法可以比这更快地实现这个范围吗？它应该更快，因为我的实现比“他们提供的慢速版本”慢

非常感谢!

Answer 1

所有内容只有一个哈希表，还有一堆上下文对象。每当您看到“{”时，将一个新对象压入堆栈。当你隐藏一个变量时，记住上下文对象中的旧符号，并在哈希表中覆盖它。当您看到 '}' 并弹出上下文时，恢复您在那里记住的符号。