c++ - 使用 map 检查 id 是否存在

Question

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

现在我想知道是否有某种结构允许我进行类似的快速查找而无需额外的存储 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，它被压缩为位。现在我想知道我是否浪费了很多内存来维护这些 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应该在 TR1 :

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

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

---

附言:并保留 Rules Of Optimization记在心里；)