c++ - 如何在遍历的同时添加要设置的元素？

Question

我们有一组 S {1,10,100,1000,10000}。现在我们输入一个整数 x(比如说 x = 4)。

现在我们必须将带有 x 的集合乘积的每个元素添加到集合本身。所以最后

S={1,10,100,1000,10000,4,40,400,4000,40000}

[S最初不限于只有5个条目]

我们只需访问集合中的初始元素。 我尝试了一种方法:

for(auto i=s.begin();i!=s.end();i++)
{
    s.insert((*i)*x);
}

这并没有给出预期的结果，因为集合的大小不断增加。

我尝试的另一种方法是将所有倍数 (*i​​)*x 存储在另一个临时集合/vector 中，稍后将其与 s 合并。 但是由于原始数据集很大，这加剧了时间复杂度。 有什么优化吗？

Answer 1

由于 std::set 是有序的，并且迭代器不会因插入而失效，您可以在迭代时简单地插入，只要您不插入到仍未插入的范围即可迭代。

如果我们可以假设所有数字都是正数，那么我们可以反向迭代，因为乘法的结果总是大于输入:

for (auto it = S.rbegin(); it != S.rend(); ++it)
    S.insert(*it*x);

如果 x 为负数且集合仅包含正数，则迭代顺序无关紧要。如果该集合可能包含负数，这将变得更具挑战性。

---

But since the original dataset is huge, it worsens the time complexity.

将 N 个元素插入 std::set 是 O(N log N)。合并 std::set 是 O(N log N)。合并方法不会恶化渐近时间复杂度。

不过，如果您要使用 std::unordered_set，合并方法在平均情况下为 O(N)。然而，在最坏的情况下它仍然是 O(N log N)。我建议对无序集使用合并方法。