sub*_*sub 19 c++ stl vector map
在我的实验性编程语言的解释器中,我有一个符号表.每个符号由一个名称和一个值组成(值可以是:例如:string,int,function等类型).
首先,我用一个向量表示该表,并通过符号迭代检查给定的符号名称是否合适.
然后,我使用地图,在我的情况下map<string,symbol>,总是比迭代迭代矢量更好,但是:
解释这部分有点难,但我会试试.
如果在我的语言的程序中第一次检索变量,当然必须找到它在符号表中的位置(现在使用向量).如果我每次执行该行时都会迭代向量(想想一个循环),那么它将非常慢(因为它目前是,几乎和microsoft的批处理一样慢).
所以我可以使用地图来检索变量: SymbolTable[ myVar.Name ]
但想想以下内容:如果第一次找到仍使用向量的变量,我可以将它的精确整数位置存储在向量中.这意味着:下次需要它时,我的解释器知道它已被"缓存"并且不会在符号表中搜索它,而是执行类似的操作SymbolTable.at( myVar.CachedPosition ).
现在我的(相当难的？)问题:
我应该使用向量作为符号表,同时缓存向量中变量的位置吗？
我应该使用地图吗？为什么？[]运算符的速度有多快？
我应该使用完全不同的东西吗？
小智 17
地图是用于符号表的好东西.但operator[]对于地图不是.一般来说,除非你正在编写一些简单的代码,否则你应该使用map的成员函数insert()而find()不是operator[].语义operator[]有点复杂,如果你要查找的符号不在地图中,几乎肯定不会做你想要的.
至于在map和之间的选择unordered_map,在实现简单的解释性语言时,性能差异极不可能显着.如果使用map,则可以保证所有当前的标准C++实现都支持它.
Mat*_* M. 13
你实际上有很多选择.
图书馆存在:
vector由于缓存局部性而在一对上实现的地图的接口,比小型或冻结集的地图更快.批评者
O(log N),但项目可能分散在整个内存中,因此无法很好地使用缓存策略.O(N)性能find,是否可以接受？unordered_map？它们提供O(1)查找和检索(虽然常量可能很高),当然适合这项任务.如果您查看维基百科关于哈希表的文章,您会发现有许多可用的策略,您当然可以选择一个适合您特定使用模式的策略.| 归档时间： |
|
| 查看次数： |
36349 次 |
| 最近记录： |