如何在std::set中使用std::back_inserter？

Question

我猜这是一个简单的问题。我需要做类似于这样的事情：

std::set<int> s1, s2;
s1 = getAnExcitingSet();
std::transform(s1.begin(), s1.end(), std::back_inserter(s2), ExcitingUnaryFunctor());

当然，std::back_inserter 不起作用，因为没有 push_back 函数。 std::inserter 是否也需要一个迭代器？我没有使用过 std::inserter，所以不确定该怎么做。

有人有想法吗？

---

当然，我的另一个选择是对 s2 使用 vector，稍后再进行排序。也许这更好？

- rlbond

Answer 1

set没有push_back是因为元素在set中的位置由比较器决定。可以使用std::inserter并将.begin()传递给它：

std::set<int> s1, s2;
s1 = getAnExcitingSet();
transform(s1.begin(), s1.end(), 
          std::inserter(s2, s2.begin()), ExcitingUnaryFunctor());

插入迭代器然后将调用s2.insert(s2.begin(), x)，其中x是写入迭代器时传递的值。集合使用迭代器作为提示来插入。您也可以使用s2.end()。

- Johannes Schaub - litb

---

既然inserter(vec, vec.end())也适用于向量，那么为什么有人会首选使用back_inserter呢？ - NHDaly

因为使用back_inserter更快。 - marton78

@marton78 但是如果有的话，调用insert而不是push_back应该只会快一点点，对吧？当没有元素需要移动时，在向量上调用insert和push_back应该大致相同（O（1））。 - Felix Dombek

@FelixDombek 你说得对，它不会慢很多。v.insert(x, v.end()) 在开头将有一个额外的分支（因为它移动了n个元素，但这里n是零）。然而，使用inserter 1)传达了不同的意图，而不是使用push_back 2)不寻常并使读者停下来思考 3)是一种过早的悲观化。 - marton78

@marton78 为什么没有 std::back_inserter<std::set> 的专门化，可以调用 std::inserter(set, set.end())？这将允许更通用的代码。 - Sergey Kolesnik

Answer 2

在2016年，有一个提案提出了“单参数插入迭代器”的想法。具体信息可以参考链接：https://isocpp.org/files/papers/p0471r0.html。我没有找到它是否得到了进一步的推进，但我认为这个想法很有意义。

目前，您可以通过定义maker函数来实现这种行为:

template<class Container>
auto sinserter(Container& c){
    using std::end;
    return std::inserter(c, end(c));
}

用途：

std::transform(begin(my_vec), end(my_vec), sinserter(my_set), [](auto& e){return e.member;});

- alfC

---

这个程序是否旨在适用于所有标准容器？它不能在std::forward_list上工作（编译器错误为“forward_list没有名为'insert'的成员”，在insert_iterator::operator =的实例化内）。 它应该工作吗？ - Don Hatch

@DonHatch，任何具有“insert”（和“end”）的内容。似乎forward_list一开始就没有insert操作，只有insert_after。即使更改了这个问题，它也不能在结尾后插入，我想。你不能使用std::list吗？ - alfC

当然，我个人没有使用std::forward_list的需求。但是我对于一个通用的“如何将一个容器复制到另一个容器？”感兴趣，适用于所有有意义的容器对。我目前的兴趣在于练习通用容器分配器，例如@HowardHinnant的short_alloc。 - Don Hatch

@DonHatch，不一定，set 不保留顺序 (std::set<T> new_set(c.begin(), c.end())，这是可以接受的。此外，创建一个“新”容器并将其移动到现有容器中是现在非常明智的做法。existing_list = std::list(c.begin(), c.end())。值语义很棒。干杯！ - alfC

是的，std::set不是一个SequentialContainer，这很好 :-) existing_list = std::list(c.begin(), c.end(), existing_list.get_allocator()) 很好，我想这就是我的答案。干杯！ - Don Hatch