使用地图检查 id 是否存在

Question

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

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

即

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 会更好还是其他一些结构可以在没有额外数据的情况下为我提供密钥查找？

Answer 1

如果你有 C++0x，你可以使用 std::unordered_set，平均查找是 O(1).

来自 cppreference.com 文档（强调我的）：

... Search, insertion, and removal have average constant-time complexity.

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value. This allows fast access to individual elements, since once a hash is computed, it refers to the exact bucket the element is placed into.

如果你没有 C++0x，unordered_set should be in TR1:

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

您也可以使用 unordered_map，但我想您代码的读者很难理解映射值的用途。

P.S.: 记住 Rules Of Optimization ;)

Answer 2

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

IdType是整型
所有 id 值都在足够短的范围内。内存使用量将为 (length of that range)/8，这可能比包含该范围内所有元素的 std::unordered_set<int> 或 std::set<int> 消耗的内存少几个数量级。
您不必迭代集合中的元素（只需 insert/remove/check 存在），或者迭代很少发生并且性能重点放在 insertion/removal/containment-testing 操作上。

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

使用地图检查 id 是否存在

Using a map to check if an id exists

c++

dictionary

lookup-tables