我正在寻找std::set
. 我需要它来支持更多的操作std::set
:
将元素从一组移动到另一组,无需“创建新的->复制->删除旧的”。
在某个位置拆分集合以获得两个集合(可以使用 获得类似的行为
std::list splice
)设置操作(如联合),无需不必要的复制。
std::set_union
会将元素从集合 A 和 B 复制到集合 C,如果我只需要集合 C 而不再需要 A 和 B,这将是低效的。
是否有任何支持这些操作的实现,或者我需要自己编写一个?
我和你有同样的问题std::set
,C++11、C++14 似乎没有任何理智的方法。然而,在 C++17 中,添加了std::set
两个看起来很有前途的新成员。
std::set::extract
允许从集合中提取整个节点。移除的节点允许获得对基础值的非常量引用,从而有效地允许将元素移出集合。它也可以插入到另一个集合中,而无需复制或移动基础值。std::set::merge
允许合并两个集合而不复制或移动任何元素,只更新内部指针。
尝试用 a 做你建议的事情的问题std::set
是我不相信你可以把一个值移出一个。这是因为设置迭代器只返回 const 引用以阻止您更改值并破坏内部结构。你可能可以const_cast
解决这个问题,但我不推荐它。即使您采用这种方法,您仍然在树中分配了节点,并且您无法采取任何措施来避免这种开销。
如果您决定实现自己的支持移动值的集合,您应该能够获得 Boost::Intrusive 库 (http://www.boost.org/doc/libs/1_52_0/doc/html/intrusive.html ) 来完成保持一组排序值的繁重工作。您需要实现用于管理对象生命周期的代码,但这比构建 RB-tree 实现更容易。
我为将节点存储在std::list
. 这允许在地图之间移动元素,而无需复制节点结构或存储的值。如果我有时间,我会尝试整理并在此处发布。
对于第 1 点和第 3 点,您可以使用set<shared_ptr>
或其他一些智能指针,而不是直接将对象存储在set
. 在这种情况下,您应该实施
bool operator<(shared_ptr<T> const & a, shared_ptr<T> const & b)
对于第 2 点,不会有这种仅由索引确定的方法,因为set
. filter
但是,您可以在 ruby 中使用类似的东西。这里的谓词可以是函数、函数对象或闭包。
remove_copy_if(foo.begin(), foo.end(), back_inserter(bar), some_predicator);