C ++中的稀疏数组 [英] Sparse array in C++

问题描述

我需要一个向量样的容器，整数索引，但是省略了一些索引。那么在C ++中代表稀疏数组的常见方法是什么？
我有一个直觉，std :: map主要用于这样的目的。但对于通常不添加新物品的集装箱来说，这是相当缓慢的。你可以提出什么？

I need a vector-like container, with integer indexation, but where some indices are omitted. So what is the common way to represent such sparse array in C++? I have an intuition that std::map is mostly used for such purposes. But it is rather slow for container where new items aren't usually added. What can you propose?

UPD：不是很稀疏。也许约5％。项目主要是在初始化阶段添加的（而不是很经常）。但是访问是频繁的（显然我不会启动这个话题，如果不重要）。

UPD: Not very "sparse". Maybe about 5%. Items mostly added during initialization step (and not very often after). But access is frequent (obviously I would not start this topic, if it was not crucial).

推荐答案

主要在初始化步骤中添加的项目（而不是很经常）。但是访问频繁

Items mostly added during initialization step (and not very often after). But access is frequent

在这种情况下 boost :: container :: flat_map 可以是一个很好的选择。它基本上只是一个排序的向量。优点（从网站被盗）：

In this case boost::container::flat_map can be a good option for you. It is basically just a sorted vector. Advantages (stolen from the website):

• 比标准关联容器更快的查找


• 更快的迭代比标准关联容器


• 减少小对象的内存消耗（如果使用shrink_to_fit，则为大对象）


• 提高缓存性能（数据存储在连续记忆）

• Faster lookup than standard associative containers
• Much faster iteration than standard associative containers
• Less memory consumption for small objects (and for big objects if shrink_to_fit is used)
• Improved cache performance (data is stored in contiguous memory)

潜在的缺点：

• 最坏情况线性时间插入和线性时间删除

即使最坏情况发生在插入或删除（移动元素底层向量），由于（1）缓存的良好使用，（2）底层元素的重定位可能被向量化（向量指令），仍然不是那么糟糕。您必须在应用程序中尝试使用插入/删除是一个问题，因为您的使用模式。

Even if the worst case happens during insertion or deletion (moving elements of the underlying vector), it is still not that bad thanks to (1) the good use of the cache, (2) relocation of the underlying elements may be vectorized (vector instructions). You would have to try it in your application to see if insertion / deletion is a problem, given your usage pattern.

如果 flat_map 不适合你，我会尝试 std :: unordered_map 。

If flat_map is not suitable for you, I would try std::unordered_map.

这篇关于C ++中的稀疏数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！