tr1::散列为提升::线：id?

StackOverflow https://stackoverflow.com/questions/772192

题

我开始使用 unordered_set 类的 tr1 名字空间，加速访问对纯(树)STL map.然而，我想储存的参考线ID在提高(boost::thread::id)，并意识到的这些识别符如此不透明，无法清楚地获得的散列。

令人惊讶的是，提高实现了部分 tr1 (包括 hash 和 unordered_set)，但它没有界定一个哈类能够哈希thread ID.

看看文件 boost::thread::id 我发现thread Id可以输出到流，所以我的解决方案这样做的散列物种：

struct boost_thread_id_hash
{
    size_t operator()(boost::thread::id const& id) const
    {
        std::stringstream ostr;
        ostr << id;
        std::tr1::hash<std::string> h;
        return h(ostr.str());
    }
};

就是说，化，适用的散列的所得串。然而，这似乎是效率低于实际使用的STL map<boost::thread::id>.

因此，我的问题：你找到一个更好的方式这样做？它是一个明显的不一致性在这两种提高和tr1不力的存在 hash<boost::thread::id> 课吗？

谢谢。

有帮助吗？

解决方案

字符串化thread::id（只计算该字符串的散列后）的开销，因为你几乎自己说的，天文数字相比，任何性能上的优势tr1::unordered_map可能赋予面对面的人std::map。所以，简单的答案是：坚持使用的std ::地图<线程ID :: ...>

如果您的绝对的必须使用无序的容器，尝试usenative_handle_type 而不是thread::id如果可能的话，也就是喜欢tr1::unordered_map< thread::native_handle_type, ... >，thread::native_handle()ing和thread::get_id()ing时调用insert代替find的。

<强>不要试图像什么以下：

struct boost_thread_id_hash {
   // one and only member of boost::thread::id is boost::thread::id::thread_data
   //   of type boost::detail::thread_data_ptr;
   // boost::thread::id::operator==(const id&) compares boost::thread::id::thread_data's
   size_t operator()(boost::thread::id const& id) const {
      const boost::detail::thread_data_ptr* pptdp = \
        reinterpret_cast< boost::detail::thread_data_ptr* >(&id);
      return h(pptdp->get());
   }
};

它可以工作，但是极脆和几乎保证定时炸弹。它假定thread::id实施的内部运作成竹在胸。这将让你在诅咒其他开发人员。不要做，如果可维护性任何关注！即使修补boost/thread/detail/thread.hpp添加size_t hash_value(const id& tid)作为thread::id的朋友是“更好”。 ：）

其他提示

显而易见的问题是你为什么想实际使用一个哈?

我了解的问题 map / set 对业绩的关键码，事实上这些容器不是非常缓友好，因为该项目可能分配非常不同的存储位置。

作为KeithB建议(我不会评论在使用的二进制代表因为没有什么保障，2id具有相同的二进制代表后所有的...)，使用排序 vector 可以加速代码的情况下，有非常少数的项目。

排矢量/双端队列是更高速缓存友好的，但是他们会遭受 O(N) 复杂性插入/清除因复制的参与。一旦你到达几百线(从没见过许多的方式)，它可能受到伤害。

但是，数据结构，试图将益处从地图和排矢量：的 B+树.

你可以把它看作一个地图对其中每个节点将包含多个元素(按顺序)。只叶节点使用。

得到一些更多的表现你可以：

  • 链接叶线性:即根缓存的指针的第一个和最后一个叶片和叶子是相互连接的本身，所以，线性行完全绕过内部节点。
  • 高速缓存的最后一次访问中的树叶根本的，毕竟这是可能的，也将是下一个访问。

渐近性能相同于对地图的，因为它是实现为一个平衡的二进制树，但是，因为价值包装团体，你们的代码可以成为更快的一个恒定不变。

真正的困难是要调整大小的每一个"桶"，你会需要一些分析，所以它将会是更好，如果你执行允许一些定制的没有(作为它将取决于建筑上的代码是执行)。

你为什么要这些存储在一组。除非你做一些与众不同的，会有线程的数量很少。维护一套的开销可能比只是把它们放在一个矢量和做线性搜索更高。

如果搜索会比添加和删除更频繁地发生，你可以只使用一个排序的载体。有升压::螺纹:: ID定义<操作符，所以你可以排序的载体（或插入到正确的位置），每次添加或删除之后，并使用lower_bound()做一个二进制搜索。这是相同的复杂性，寻找一组，并且应该有少量数据的低开销。

如果你仍然需要做到这一点，如何只把它当作一个的sizeof（升压::线程：ID）。字节，操作上那些

这个例子假设升压::螺纹:: ID的大小是一个int的大小的倍数，并且，没有包装，并没有虚函数。如果不为真，则必须修改，否则不会在所有工作。

编辑：我把一看boost::thread::id类，且其具有作为boost::shared_pointer<>成员，所以下面的代码是可怕的破碎。我认为唯一的解决办法是让boost::thread的作者补充的哈希函数。我要走的例子，以防万一其有用在一些其它上下文。

boost::thread::id id;
unsigned* data;
// The next line doesn't do anything useful in this case.
data = reinterpret_cast<unsigned *>(&id);
unsigned hash = 0;

for (unsigned int i = 0; i < sizeof(boost::thread::id)/4; i++)
  hash ^= data[i];

几年下旬来回答这个问题，但这种试图把一个boost ::螺纹:: ID在一个std :: unordered_map关键的时候出现了作为最相关的一个。获取本机句柄是一个很好的建议，在接受了答复，除了它不适用于this_thread。

相反提振了一段有螺纹:: ID的哈希值，所以这个工作对我罚款：

namespace boost {
  extern std::size_t hash_value(const thread::id &v);
}

namespace std {
  template<>
  struct hash<boost::thread::id> {
    std::size_t operator()(const boost::thread::id& v) const {
      return boost::hash_value(v);
    }
  };
}

当然，需要针对libboost_thread库链接。

您可以创建的类，它的线程:: ID和东西（例如：整数）之间的映射，可以作为哈希使用。唯一的缺点是，必须确保有映射对象的只有一个实例在系统中。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top