使用地图来检查ID是否存在

我正在执行锁定Mecahnism，为此我需要快速查找是否给定的Id已被锁定。现在我正在考虑使用地图，我想知道是否有一些更好的结构。基本上我不需要地图，因为没有完成映射。但是，如果我使用矢量，则必须进行线性搜索，这对于许多条目来说会变得很昂贵。使用地图来检查ID是否存在

现在我想知道是否有某种结构允许我进行类似的快速查找，而不需要额外的存储etra数据开销。

i.E.

std::map<IdType, bool> locked; 

// Prevent deadlock by checking if this thread already locked. Otherwise 
// it can pass through. 
if(locked.find(Id) != locked.end()) 
    lock();

正如你所看到的，我并不真的需要映射值。我知道对于std::vector，使用bool，它被压缩成比特。现在我想知道我是否浪费了大量的内存来维护这些布尔，而我甚至不需要它们。 char会更好吗？还是其他一些结构只是让我在没有额外数据的情况下进行密钥查找？

来源

2016-07-29 Devolus

如果不需要相关性，那么使用'set'怎么样？在之间，你也应该用'vector'来描述它。不要惊讶，如果你的线性搜索执行得更好，'set :: find' – Arunmu

是否应该在一些内存受限的硬件上运行？如果要在个人电脑上运行，不要打扰优化几个字节，还有一个竞争条件在您的支票 – slawekwin

@slawekwin https://www.safaribooksonline.com/library/view/c-coding-standards /0321113586/ch10.html在这里适用：写入std :: set代替std :: map更好地以零代价向程序员捕获代码的意图，而不会让未来的程序员怀疑未使用的值可能用于。 –

如果你有C++ 0x，你可以使用std::unordered_set，平均查找是O（1）。

从cppreference.com文档（重点矿山）：

...搜索，插入和删除有平均固定时间的复杂性。

在内部，元素并不按任何特定的顺序排序，而是组织成桶。一个元素放入哪个桶完全取决于其值的哈希值。这允许快速访问单个元素，因为一旦计算了散列，它就指向该元素被放入的确切桶。

如果你没有的C++ 0x，unordered_set应该在TR1：

#include <tr1/unordered_set> 
std::tr1::unordered_set<IdType> locked;

你也可以使用一个unordered_map，但我猜你的代码的读者将有一个困难时期了解映射值用于什么。

PS：而且牢记Rules Of Optimization）

来源

2016-07-29 08:10:50 sergej

如果您没有它，请改用'std :: set' - 查找是O（log n）。 –

@MartinBonner或者使用TR1中的'unordered_set'。 – sergej

您可以使用std::vector<bool>或boost::dynamic_bitset下列条件：

IdType为整型
所有ID值适合在足够短的范围内。内存使用量为(length of that range)/8，可能会比包含该范围内所有元素的std::unordered_set<int>或std::set<int>消耗的量要少几个数量级。
您不必遍历您的集合中的元素（只需插入/删除/检查存在），或者迭代不经常发生，性能侧重于插入/删除/包含测试操作。

在这种情况下，动态位集是更合适的数据结构（既速度更快，内存效率更高）。

来源

2016-07-29 10:02:53 Leon

使用地图来检查ID是否存在

回答

相关问题