std::map 与自写的 std::vector 基于字典
我正在为我的游戏引擎构建一个内容存储系统，并且正在寻找存储数据的可能替代方案。既然这是一款游戏，那么性能显然很重要。特别是考虑到引擎中的各种实体在创建时将向内容管理器的数据结构请求资源。我希望能够通过名称而不是索引号来搜索资源，因此某种字典是合适的。
使用 std::map 和基于 std::vector 创建我自己的字典类有哪些优点和缺点？是否存在任何速度差异（如果是这样，性能会在哪里受到影响？即附加与访问）以及花时间编写我自己的类有什么意义吗？
有关需要发生的事情的一些背景： 对数据结构的写入仅在引擎加载时发生一次。因此，在游戏过程中实际上并没有发生任何写入。当引擎退出时，这些数据结构都要被清理掉。无论何时创建实体或交换地图，都可以随时读取它们。一次创建的实体可以少至一个，也可以多至 20 个，每个实体需要不同数量的资源。资源大小也会根据引擎启动时读入的文件大小而变化，图像最小，音乐最大，具体取决于格式（.ogg 或 .midi）。
I'm building a content storage system for my game engine and I'm looking at possible alternatives for storing the data. Since this is a game, it's obvious that performance is important. Especially considering various entities in the engine will be requesting resources from the data structures of the content manager upon their creation. I'd like to be able to search resources by a name instead of an index number, so a dictionary of some sort would be appropriate.
What are the pros and cons to using an std::map and to creating my own dictionary class based on std::vector? Are there any speed differences (if so, where will performance take a hit? I.e. appending vs. accessing) and is there any point in taking the time to writing my own class?
For some background on what needs to happen:
Writing to the data structures occurs only at one time, when the engine loads. So no writing actually occurs during gameplay. When the engine exits, these data structures are to be cleaned up. Reading from them can occur at any time, whenever an entity is created or a map is swapped. There can be as little as one entity being created at a time, or as many as 20, each needing a variable number of resources. Resource size can also vary depending on the size of the file being read in at the start of the engine, images being the smallest and music being the largest depending on the format (.ogg or .midi).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Map：
std::map保证了对数查找复杂性。它通常由专家实施并且具有高质量（例如异常安全性）。您可以使用自定义分配器来满足自定义内存需求。您的解决方案：它将由您编写。向量用于连续存储并按位置随机访问，那么如何实现按值查找呢？你能保证对数复杂度或更好吗？您有特定的内存要求吗？您确定可以正确有效地实现查找算法吗？
第三个选项：如果您的键类型是
string（或者比较成本较高的类型），请同时考虑std::unordered_map，它具有常量 - 在典型情况下按值进行时间查找（但不能完全保证）。Map:
std::maphas guaranteed logarithmic lookup complexity. It's usually implemented by experts and will be of high quality (e.g. exception safety). You can use custom allocators for custom memory requirements.Your solution: It'll be written by you. A vector is for contiguous storage with random access by position, so how will you implement lookup by value? Can you do it with guaranteed logarithmic complexity or better? Do you have specific memory requirements? Are you sure you can implement a the lookup algorithm correctly and efficiently?
3rd option: If you key type is
string(or something that's expensive to compare), do also considerstd::unordered_map, which has constant-time lookup by value in typical situations (but not quite guaranteed).如果您想要
std::map的速度保证以及std::vector的低内存使用量，您可以将数据放入std::向量，std::sort它，然后使用std::lower_bound查找元素。If you want the speed guarantee of
std::mapas well as the low memory usage ofstd::vectoryou could put your data in astd::vector,std::sortit and then usestd::lower_boundto find the elements.无论如何，std::map 的编写都考虑到了性能，虽然它确实有一些开销，因为它们试图推广到所有情况，但无论如何它最终可能会比您自己的实现更有效。它使用红黑二叉树，使其所有操作都具有 O[log n] 效率（除了出于明显原因的复制和迭代之外）。
您将多久读/写一次地图，以及每个元素将在其中多长时间？此外，您还必须考虑需要多久调整一次大小等。这些问题中的每一个对于为您的实现选择正确的数据结构都至关重要。
总的来说，其中一个 std 函数可能就是您想要的，除非您需要的功能不在其中一个函数中，或者您有一个可以提高其时间复杂度的想法。
编辑：根据您的更新，我同意 Kerrek SB 的观点，如果您使用 C++0x，那么
std::unordered_map将是一个很好的数据结构在这种情况下使用。但是，请记住，如果哈希值冲突（std::map不会发生这种情况），您的性能可能会降级为线性时间复杂度，因为它将把两对存储在同一个存储桶中。虽然这种情况很少见，但其概率明显随着元素数量的增加而增加。因此，如果您正在编写大型游戏，std::unordered_map的优化程度可能会低于std::map。只是一个考虑。 :)std::mapis written with performance in mind anyway, whilst it does have some overhead as they have attempted to generalize to all circumstances, it will probably end up more efficient than your own implementation anyway. It uses a red-black binary tree, giving all of it's operations O[log n] efficiency (aside from copying and iterating for obvious reasons).How often will you be reading/writing to the map, and how long will each element be in it? Also, you have to consider how often will you need to resize etc. Each of these questions is crucial to choosing the correct data structure for your implementation.
Overall, one of the std functions will probably be what you want, unless you need functionality which is not in a single one of them, or if you have an idea which could improve on their time complexities.
EDIT: Based on your update, I would agree with Kerrek SB that if you're using C++0x, then
std::unordered_mapwould be a good data structure to use in this case. However, bear in mind that your performance can degrade to linear time complexity if you have conflicting hashes (this cannot happen withstd::map), as it will store the two pair's in the same bucket. Whilst this is rare, the probability of it obviously increases with the number of elements. So if you're writing a huge game, it's possible thatstd::unordered_mapcould become less optimal thanstd::map. Just a consideration. :)