我正在为我的游戏引擎构建一个内容存储系统,我正在寻找存储数据的可能替代方案。由于这是一款游戏,性能显然很重要。特别是考虑到引擎中的各种实体将在创建时从内容管理器的数据结构中请求资源。我希望能够通过名称而不是索引号来搜索资源,因此某种字典会比较合适。
使用 std::map 和基于 std::vector 创建我自己的字典类的优缺点是什么?是否存在任何速度差异(如果有,性能会在何处受到影响?即追加与访问)以及花时间编写我自己的类是否有任何意义?
有关需要发生的事情的一些背景: 写入数据结构仅在引擎加载时发生一次。因此,在游戏过程中实际上不会发生任何书写。当引擎退出时,这些数据结构将被清理。无论何时创建实体或交换 map ,都可以随时读取它们。一次可以创建少至一个实体,也可以多至 20 个,每个实体都需要可变数量的资源。资源大小也可能因引擎启动时读取的文件大小而异,图像最小,音乐最大,具体取决于格式(.ogg 或 .midi)。
最佳答案
Map: std::map
保证了对数查找的复杂性。它通常由专家实现并且质量很高(例如异常安全)。您可以使用自定义分配器来满足自定义内存要求。
您的解决方案:它将由您编写。 vector 用于按位置随机访问的连续存储,那么您将如何实现按值查找?你能保证对数复杂度或更好吗?您有特定的内存要求吗?您确定可以正确有效地实现查找算法吗?
第三个选项:如果您的键类型是 string
(或比较昂贵的东西),也请考虑 std::unordered_map
,它具有 constant-典型情况下按值查找的时间(但不能完全保证)。
关于c++ - std::map 与自写的基于 std::vector 的字典,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6810530/