使用erase-remove范例将元素从一个向量移动到另一个向量

Question

使用erase-remove范例将元素从一个向量移动到另一个向量

4

这个问题清楚地阐述了如何将内容从一个std::vector移动到另一个std::vector。简而言之，需要进行std::move调用以物理移动内存，同时还需要进行std::erase调用来调整原始向量的大小以适应已删除的元素。

使用擦除-删除范式是否存在问题，就像在迭代向量时删除向量一样（例如这里）？

例如，类似于这样的操作：

// 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]

当我运行这段代码时，它在我的测试器中可以工作。但是，当处理对象而不是int时，我担心我实际上并没有“移动”任何东西，而只是引用；例如，使用std::vector<MyObj>（使用适当的lambda测试）时是否也是如此。

这是否真正执行了移动操作，或者我担心我只是共享一个引用？

- marcman

1

你实际上在这里创建了副本，对于 int 来说这是可以的。但如果你想更通用和高效地处理对象，你应该使用 push_back(std::move(x))。 - Kurt Stutsman

1

const TYPE x也需要更加明亮。否则你只是移动了一个const副本，TYPE & x可以解决这个问题。 - user4581301

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nir Friedman · Accepted Answer

我认为这些算法的总体目的是通过应用函数来实现你想要达到的目标。一旦函数产生了副作用，似乎最终结果可能会误导，可能最好使用for循环。

话虽如此，要记住C++不是Java。一个vector<Foo>必须存储Foo，它不能仅仅存储引用。然而，你整个想法仍然存在问题。

myNewVec.push_back(x);

这行代码会将x的副本推入新向量中。因为是副本，所以不必担心共享引用的问题。对于整数来说，复制和移动是相同的。但对于复杂对象（比如向量），移动比复制快得多。而且唯一的向量总是要摆脱x，所以我们肯定想要移动。因此，理想情况下，我们应该将那行代码改成：

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

然而，将对象移动会明显改变其状态，需要取消const限定。然而，remove_if的要求是传递一个谓词函数对象。这又意味着：

谓词函数对象pred不能通过解引用迭代器应用任何非常量函数。

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);
}

这样做至少不会复制任何元素。它基本上将要保留和离开的元素分开，并高效地移出离开的元素，然后简单地调整数组大小。正如评论中指出的那样，与最优解相比，这可能涉及到额外的操作，但是我的感觉是最优版本不容易编写，并且可能涉及到权衡（例如更多状态），因此可能并非完全胜利。

请注意，我的算法专门接受向量而不是迭代器，因为对于其他容器（如链表），这种实现方式相当远离最优。