问题标签 [intrusive-containers]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
204 浏览

c++ - 为什么 boost intrusive list 的 push_back 函数需要左值?

我正在学习侵入性列表:

我了解侵入式列表的基本思想,但我不明白为什么 push_back 需要专门的左值。从逻辑的角度来看,为什么侵入式列表无法处理 rvalue ?

左值要求是否意味着用户需要自己处理 DummyObject 的生命周期?也就是说,当 IntrusiveList pop_front 时,弹出的对象不会被破坏?

另外,我通过左值传递的事件:

二进制文件中的一个断言失败:

intrusivelist: /usr/include/boost/intrusive/detail/generic_hook.hpp:48: void boost::intrusive::detail::destructor_impl(Hook&, boost::intrusive::detail::link_dispatch<(boost::intrusive: :link_mode_type)1>) [with Hook = boost::intrusive::generic_hook<(boost::intrusive::algo_types)0, boost::intrusive::list_node_traits, boost::intrusive::dft_tag, (boost::intrusive ::link_mode_type)1, (boost::intrusive::base_hook_type)1>]: 断言 `!hook.is_linked()' 失败。

0 投票
1 回答
277 浏览

c++ - 与现代 C++ 中的非侵入式容器相比,侵入式容器是否仍然具有性能优势?

与现代 C++ 中的Boost.Intrusive非侵入式标准 ( ) 容器相比(具有移动语义等) ,容器是否仍然具有性能优势?std::emplace_back

0 投票
1 回答
52 浏览

c++ - Boost.Intrusive Containers - 不同大小的元素

在“何时使用?”一章的 Boost.Intrusive 文档中 https://www.boost.org/doc/libs/1_72_0/doc/html/intrusive/usage_when.html,据说您可以使用包含不同或未知大小的对象的侵入式容器。

我的问题是我不明白什么时候有人需要它(使用示例?)。而且我不明白给定示例中的哪个部分显示了这种行为,以及为什么你不能用标准容器做到这一点。

0 投票
1 回答
302 浏览

c++ - C++ STL - 容器实现

我目前正在学习很多关于侵入式容器的知识。所以我经常将它们与标准容器进行比较。

让我们以 std::list 为例。我读到这个容器通常实现为双向链表。但是我没有详细阅读节点是如何实现的。我假设有一个“上一个”和“下一个”指针,但是属于这样一个节点的对象呢?它是指向对象的指针,还是对象本身,是在节点分配的内存中构造的?

在 Boost.Intrusive 中指出,他们的容器具有更好的局部性(参见此处:https ://www.boost.org/doc/libs/1_72_0/doc/html/intrusive/usage_when.html ,或此处:https:// /www.boost.org/doc/libs/1_72_0/doc/html/intrusive/performance.html)。我不确定为什么会这样。当 std::list 中的节点包含一个对象并且侵入式容器在其对象中包含一个节点时,这如何导致更好的局部性?

0 投票
1 回答
231 浏览

c++ - 如何将 boost::intrusive_ptr 与 boost::intrusive::list 一起使用?

我想一次准确地分配一个对象并将其推送到几个列表中。我怎么能用 and 做到这boost::intrusive_ptr一点boost::intrusive::list?或者我应该使用另一个容器和引用计数器?

0 投票
0 回答
106 浏览

c++ - 缺少增强 AVL 树的合并和拆分?

Boost 提供了可以配置boost::container::set/map/multiset/multimap底层二叉搜索树 (BST) 的位置,并且可以选择它作为 AVL 树。

一个(也许是最关键的)原因,为什么人们更喜欢 AVL 树而不是红黑树,是复杂性的merge和操作。但是,令我惊讶的是,它似乎不提供这些操作。文档描述为复杂的元素操作(这与底层 BST 实现无关!?),文档甚至没有提到!splitO(logN)boost::containermergeO(NlogN)split

我不能说关于merge,但至于split,我可以假设缺少它可能是由恒定时间size问题所证明的,因此split复杂性O(logN)可能不知道两个结果部分的大小。但这可以通过具有侵入性容器并保持每个节点的子树节点计数来解决。

也有,但我在文档boost::intrusive::avl_set中找不到 AVLmergesplit算法。

所以问题是。

  1. 是否有一个功能齐全、现成的基于 AVL 的实现,set/map/multiset/multimap它提供mergesplit操作的复杂性为O(logN)
  2. 如果没有,我该如何构建一个使用boost::intrusive::avl_set