c++ - 当 unordered_map 中不存在键时返回零

Question

我有以下容器:

std::unordered_map<uint8_t,int> um;

um假设有 0 到 255 之间的键，但不是全部。所以，在某些时候我想要求它给我例如键 13 的值。如果它在那里，我想要它的值(保证不为 0)。如果不是，我希望它返回 0。

实现它的最佳方式(性能观点)是什么？

到目前为止我尝试过的方法:使用 find 并在未找到时返回 0，如果找到则返回值。

附言改为 std::vector<int>包含 256 个项目不是一个选项。我负担不起总是存储 256 个值的空间。

---

编辑:

我的问题是直方图计算问题键(颜色 0-255)值(频繁，int 就足够了)。如果我只知道某个 key 存在与否，我不会满意。我还需要值(频繁)。

附加信息:

• 我永远不会删除任何项目。
• 我有时会添加项目(最多 256 项)，通常少于 10 项。
• 我会多次查询 key 。
• 通常查询和插入没有特定顺序。

Answer 1

您需要在内存和速度之间进行权衡。

你的 unordered_map应该具有较低的速度复杂度。

使用 std::vector<std::pair<uint8_t, int>>会更紧凑(并且对缓存更友好)。

std::pair<std::vector<uint8_t>, std::vector<int>>会更紧凑(uint8_t 和 int 之间没有填充)

您甚至可以通过分解大小/容量来做得更好，但它不再在 std:: 中.

与 vector ，然后你有另一个交易:搜索和添加 key 的复杂性:

• 未排序 vector :常量加法，线性搜索
• 排序 vector :线性加法(由于在 vector 中间插入值)，对数搜索。