2

我正在寻找std::set. 我需要它来支持更多的操作std::set：

  1. 将元素从一组移动到另一组，无需“创建新的->复制->删除旧的”。

  2. 在某个位置拆分集合以获得两个集合（可以使用 获得类似的行为std::list splice）

  3. 设置操作（如联合），无需不必要的复制。std::set_union会将元素从集合 A 和 B 复制到集合 C，如果我只需要集合 C 而不再需要 A 和 B，这将是低效的。

是否有任何支持这些操作的实现，或者我需要自己编写一个？

4

3 回答 3

5

我和你有同样的问题std::set，C++11、C++14 似乎没有任何理智的方法。然而，在 C++17 中，添加了std::set两个看起来很有前途的新成员。 std::set::extract允许从集合中提取整个节点。移除的节点允许获得对基础值的非常量引用，从而有效地允许将元素移出集合。它也可以插入到另一个集合中，而无需复制或移动基础值。std::set::merge允许合并两个集合而不复制或移动任何元素，只更新内部指针。

于 2017-11-07T08:10:36.833 回答
2

尝试用 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. 这允许在地图之间移动元素，而无需复制节点结构或存储的值。如果我有时间，我会尝试整理并在此处发布。

于 2012-12-14T11:17:37.450 回答
2

对于第 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);
于 2012-12-14T10:00:40.720 回答