使用擦除-删除范例将元素从一个向量移动到另一个向量

Question

This question 清楚地阐明了如何将内容从一个 std::vector 移动到另一个。简而言之，物理移动内存需要一个 std::move 调用，同时还需要一个 std::erase 调用来调整原始向量的大小以考虑删除的元素。

使用 erase-remove paradigm as one uses to delete from a vector while iterating over it (like here) 这样做有问题吗？

例如，像这样：

// Vector with values [0, 1, ..., 19]
std::vector<int> myOldVec;
for (int i = 0; i < 20; i++) { myOldVec.push_back(i); }

// New vector to move into
std::vector<int> myNewVec;

// Move from myOldVec to myNewVec if value is less than 5
myOldVec.erase(
    std::remove_if(
        myOldVec.begin(),
        myOldVec.end(),
        [&](const int x)
        {
            if (x < 5)
            {
                myNewVec.push_back(x);
                return true;
            }
            return false;
        }
    ),
    myOldVec.end()
);

预期的输出将是

myOldVec --> [5, 6, ..., 19]
myNewVec --> [0, 1, 2, 3, 4]

当我运行这段代码在我的测试仪中工作时。但是，当处理对象而不是 ints 时，我担心我实际上并没有移动任何东西，而只是引用；例如，当使用 std::vector<MyObj> 执行上述操作时（使用适当的 lambda 测试）。

这真的是在表演动作，还是我担心我只是分享一个参考？

Answer 1

我认为通常这些算法的要点是，您正在通过应用函数来实现您想要实现的目标。一旦函数有副作用，看起来最终结果可能会产生误导，做一个 for 循环可能会更好。

也就是说，请记住 C++ 不是 Java。 vector<Foo> 必须存储 Foo 的，它不能存储引用。不过，你的整个思路还是有问题。

myNewVec.push_back(x);

代码中的这一行会将 x 的 copy 推送到新向量中。因为它是副本，所以您不必担心共享引用。现在，对于整数，复制和移动是相同的。但是对于复杂的对象（比如矢量），移动可能比复制快得多。无论如何，唯一的向量就是摆脱 x，所以我们肯定要移动。所以理想情况下，我们将该行更改为：

myNewVec.push_back(std::move(x));

但是，从一个对象移动显然会使它发生变异，并且要求它不是常量。然而，remove_if 的要求要求传递的函数对象是谓词。这反过来意味着：

The function object pred shall not apply any non-constant function through the dereferenced iterator.

http://en.cppreference.com/w/cpp/concept/Predicate

换句话说，您的函数必须接受取消引用迭代器的结果，但不应该改变它。因为它不应该改变它，所以您永远不能从原始对象移动，而必须复制它。因此，我认为对于非平凡类型，这个想法没有任何一致、有效的实现。

这是一个合理的实现：

template <class T, class F>
void transfer_if_not(std::vector<T>& old, std::vector<T>& new, F pred)
{
    auto part = std::partition(old.begin(), old.end(), pred);
    std::move(part, old.end(), std::back_inserter(new));
    old.erase(part);
}

这至少不应该复制任何元素。它基本上会分离出原始向量中要保留和保留的元素。然后有效地搬走那些离开的人。然后简单地调整数组的大小。正如评论中指出的那样，与最佳版本相比，这可能涉及额外的操作，但我的感觉是最佳版本的代码编写起来并不简单，并且可能涉及权衡（如更多状态），因此它可能不是纯粹的胜利.

请注意，我的算法专门接受向量而不是迭代器，因为对于其他容器（比如链表），此实现远非最佳。

使用擦除-删除范例将元素从一个向量移动到另一个向量

Moving elements from one vector to another using erase-remove paradigm

c++

move

vector

c++11