Emi*_*ier 6 c++ optimization gcc dictionary c++11
对于内存使用比速度更重要的嵌入式系统应用程序，最好使用什么地图容器？std::map, std::unordered_map? 这适用于N小于例如一百的情况。
如果实现很重要，那么我关心的是 libstdc++ 实现（GCC）。
虽然我知道不可能在内存使用方面击败简单的数组，但我想避免使用具有 O(N) 性能的数据结构。因此，虽然我想减少内存占用，但我也希望查找速度合理（优于 O(N)）。我不关心其他操作（插入、删除），因为它们很少发生。
如果我想进行自己的内存使用测量，我将如何在 Linux 平台上执行此操作？
将提振:: flat_map适合作为具有占地面积小和查找时间比O（n）的关联容器？
对于小 N，排序向量通常是最快的容器，并且具有最小的内存占用。boost::flat_map 是一个实现，其他人称之为 AssociativeVector。您可以使用std::lower_bound它轻松实现它。由于数据必须排序，插入和删除操作是 O(n)，因为数据必须在向量中移动。
使用排序向量，您可以进行 O(log N) 的二分搜索以进行检索。的复杂度std::lower_bound为：
执行的比较次数是 first 和 last 之间距离的对数（最多 log2(last - first) + O(1) 比较）
| 归档时间： |
|
| 查看次数： |
5117 次 |
| 最近记录： |