从std::vector中删除原始指针

Question

我有以下的模式：

1. 我有一个包含指向对象的原始指针的 std::vector（我知道原始指针很“邪恶”，但这是需要维护的遗留软件）。
2. 现在，对于向量中的每个元素，我需要进行测试，如果测试结果为正，则对指针执行某些操作，然后将其删除并从向量中移除：

伪代码：

for each pointer in vector
{
  if (SomeTest(pointer))
  {
     DoSomething(pointer)
     delete pointer
     remove pointer from vector
  }
}

我无法为此编写一些漂亮的干净代码。

这个链接提供了不同的方法，但它们看起来都更加繁琐。

我现在使用的解决方案很繁琐:

for(auto &  p : v)
{
   if (SomeTest(p))
   {
       DoSomething(p);
       delete p;
       p = nullptr;
   }
}

v.erase(std::remove(v.begin(), v.end(), nullptr), v.end());

- Jabberwocky

---

抱歉，我有点挑剔：指向其他所有者拥有的对象的裸指针相对无害。只有拥有裸指针才是有害的。 - 463035818_is_not_a_number

erase_if有什么具体问题？ - Useless

@user463035818 不用说，delete原始指针只有在拥有原始指针的邪恶情况下才有意义。问题陈述并没有明确指出指针的所有权，因此你在吹毛求疵方面是_技术上_正确的。 - Max Langhof

如果这个向量负责“删除”它们，那么我会说这个向量拥有它们。无论如何，我特别指的是“我知道原始指针是‘邪恶’的”，当某物被赋予“邪恶”的属性时，我有点挑剔，因为这很容易导致误解。 - 463035818_is_not_a_number

@Jabberwocky，这就是我的观点。你没有在“邪恶指针”部分旁边清楚地阐述，所以从技术上讲，那个人的吹毛求疵是有道理的，但我想指出的是，很明显他们的吹毛求疵在这里不适用。 - Max Langhof

Answer 1

通常的答案是：熟悉你的<algorithm>（也是对我自己的一个好提醒）;)

std::partition是你要找的东西：std::partition(begin, end, p)“移动”范围[begin, end)中不满足谓词p的元素到范围的末尾；然后你可以把它们作为一批处理。

auto const to_be_removed = std::partition(begin(v), end(v), [](auto p){ /* predicate */ });
std::for_each(to_be_removed, end(v), [](auto p) {
    /* crunch */
    delete p;
});
v.erase(to_be_removed, end(v));

完整程序

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    std::vector v = { new int{0}, new int{1}, new int{2} };

    // let's delete all even values
    auto const to_be_removed = std::partition(begin(v), end(v), [](auto p){ return *p % 2 != 0; });
    std::for_each(to_be_removed, end(v), [](auto p) {
        std::cout << "Deleting value " << *p << "...\n";
        delete p;
    });
    v.erase(to_be_removed, end(v));
}

现场演示

深入了解

该实现有两个主要缺陷：向量的顺序不稳定（1），可以将其分解为可重用函数（2）。

• （1）可以通过std::stable_partition解决。
• （2）并不难：

template<class InputIt, class UnaryPredicate, class UnaryDeleter>
InputIt delete_if(InputIt begin, InputIt end, UnaryPredicate p, UnaryDeleter d)
{
    auto const to_be_removed = std::stable_partition(begin, end, std::not_fn(p));
    std::for_each(to_be_removed, end, [d](auto p) { d(p) ; delete p; });
    return to_be_removed;
}

template<class Container, class UnaryPredicate, class UnaryDeleter>
auto delete_if(Container& c, UnaryPredicate p, UnaryDeleter d)
{
    using std::begin, std::end;
    return c.erase(delete_if(begin(c), end(c), p, d), end(c));
}

用法:

delete_if(v, SomeTest, DoSomething);

现场演示

- YSC

---

此外，delete p 应该由 UnaryDeleter 处理，否则它只能用于动态指针。 - user202729

我不同意这一点；我的理由是我们正在解决 OP 的具体问题：“对于向量中的每个元素，我需要进行测试，如果测试结果为正，则对 [原始] 指针执行某些操作，然后将其删除并从向量中移除”。他们没有理由不在 delete_if 函数上放置 delete 语句。 - YSC

Answer 2

您可以使用std::remove_if。我不确定为什么您链接的文章在删除指针之前使用std::remove_if，因为那样是行不通的。您必须先删除指针，然后再进行去除操作：

std::vector<int*> v;

v.erase(std::remove_if(std::begin(v), std::end(v), [](int* p){

    // do your test and do not remove on failure
    if(!SomeTest(p))
        return false; // keep this one

    DoSomething(p);

    // Now we remove but be sure to delete here, before the
    // element is moved (and therefore invalidated)

    delete p;

    return true; // signal for removal

}), std::end(v));

注意: 这个做法为什么是安全的。

删除指针并不会修改指针本身，而是被指向的对象。这意味着使用此方法不会修改任何元素。

C++17 28.6.8 5 标准保证谓词对每个元素只调用一次。

- Galik

---

回应你的评论，是的：针对这个具体情况，这是一个好主意。(+1) - YSC

Answer 3

最简单的解决方案 - 从链接的文章开始 - 是使用erase_if函数。

template <typename Container, typename Pred>
void erase_if(Container &c, Pred p)
{
    c.erase(std::remove_if(std::begin(c), std::end(c), p), std::end(c));
}

只需使用以下命令调用：

erase_if(v, [](T *pointer)
         {
           if (SomeTest(pointer))
           {
              DoSomething(pointer);
              delete pointer;
              return true; //remove pointer from vector
           }
           return false;
         });

如果您想将SomeTest/DoSomething部分与delete部分分开，可以明显地将谓词分为两个部分：

template <typename Container, typename Pred>
void delete_if(Container &c, Pred p)
{
    auto e = std::remove_if(std::begin(c), std::end(c),
        [&p](Container::value_type *pointer)
        {
          if (p(pointer)) {
            delete pointer;
            return true;
          }
          return false;
        });
    c.erase(e, std::end(c));
}

由于您没有说明为什么不喜欢您自己提供的erase_if，我无法猜测是否存在相同的问题。

- Useless

---

这种方法存在问题：std::erase_if(...) 等同于 v.erase(std::remove_if(...))，而 明确指定 谓词 不能修改元素。 - You

@你 从技术上讲，它并没有修改元素，但我想精神上的意义是p应该是幂等的（可多次调用而不会有害），在这种情况下肯定不是这样的，因为对已删除指针的下一次调用可能会有未定义行为。 - Arne Vogel

说得好。 （我相信确切的措辞是“[谓词]不得通过取消引用的迭代器应用任何非常量函数。”，因为删除技术上不会这样做，因为可以安全地删除一个const指针。） - You

@ArneVogel 标准保证谓词只会对每个元素调用一次。 - Galik

我猜你是从(alg.remove/5)推断出来的 - 在我看来这仍然有点技术性。如果我在进行代码审查，我会建议切换到partition/stable_partition或编写一个有意义的注释来说明它为什么是正确的。 - Arne Vogel

Answer 4

使用以下方法，首先将要删除的元素拆分，然后进行删除，最后调整向量。最初的回答。

auto badIt = std::stable_partition(std::beging(v), std::end(v), SomeTestInverse);
std::for_each(badIt, std::end(v), [](auto e){ DoSomething(e); delete e;});
v.erase(badIt,std::end(v));

为了让操作生效，提供的谓词必须对元素返回 true，因为未通过谓词的元素位于最后一个范围内。

需要翻译的内容：

The predicate provided must be true for element to keep in order to work, as elements failing the predicate are in the last range.

- UmNyobe

Answer 5

假设您有一个整数指针向量。这是我的解决方案：

vector<int*> vpi;

for (vector<int*>::iterator it = vpi.begin(); it != vpi.end(); )
{
    if (SomeTest(*it))
    {
        DoSomething(*it)
        int* old = *it;
        it = vpi.erase(it);
        delete old;
    } else
    {
       it++;
    }
}

- Loc Tran

---

我不确定，但据我理解问题，这是OP想要避免编写的代码。 - 463035818_is_not_a_number

‰∏∫‰ªÄ‰πà˶ʼnΩøÁî®old? DoSomething(*it);delete *it;it = vpi.erase(it);ËøôÊƵ‰ª£Á†ÅÂè؉ª•ÂÆûÁé∞Âêåʆ∑ÁöÑÂäüËÉΩ„ÄÇ - NathanOliver

如果您删除*it，原始指针会丢失或未定义。更好的方法是我们应该保存旧指针。 - Loc Tran

这个解决方案的时间复杂度为O(N^2)（考虑在中间删除元素时需要移动的元素）。使用std::partition，然后再使用单个erase。 - rustyx

考虑一个有1000个元素的向量，其中需要删除前100个元素。剩下的一个元素需要在向量内移动多少次（大约95000次）。 - rustyx

Answer 6

我会使用一些方法：

for (auto i = vector.begin(); i != vector.end(); ++i) {
  if (SomeTest(*i)) {
    DoSomething(*i);
    delete *i;
    *i = nullptr;
  }
}
vector.erase(std::remove(vector.begin(), vector.end(), nullptr), vector.end());

- 273K

---

这差不多就是我现在正在做的事情。 - Jabberwocky

@UmNyobe 使用nullptr作为魔术值有什么问题吗？ - Galik

@Galik，也许向量中包含了 nullptr，也许 SomeTest 函数对于一个 nullptr 返回 false。 - 463035818_is_not_a_number

Answer 7

保持简单。YAGNI。没有理由去解决一个更通用和复杂版本的问题，只是为了万一你需要它（提示：你不会需要），或者寻找晦涩的STL方法（除非你希望这样做）。

size_t target = 0;
for (size_t idx = 0; idx < v.size(); idx++) {
    if (should_delete(v[idx]))
        delete v[idx];
    else
        v[target++] = v[idx];
}
v.resize(target);

- jick

---

<algorithm> 不是一堆“晦涩的 STL 方法”。学习它们，使用它们。它们可以产生易于阅读、易于维护、易于优化的代码。 - YSC

当然，“易”是因人而异的，但我见过太多使用多层模板继承编写的代码，如果程序员抵制将所有东西泛化到最大程度，这些代码本可以用简单的for循环或switch语句来实现。如果有人发现使用带有lambda表达式的std::for_each比使用for更容易，那么这只是他们的个人喜好：但我怀疑它是否会更快。 - jick

当然，“易”是因人而异的。如果在C++社区中存在一个习语，那么除了该习语之外的任何东西都不容易阅读，并且会增加代码库中每行代码的wtf值。关于优化，没有测试就无法得出结论，但通常符合惯用法和依赖标准库的代码更容易被编译器理解并以更好的方式进行优化。 - YSC

“易用性”并不是观察者的主观感受？我很高兴你同意for循环在客观上更优秀！开个玩笑，自从C++被称为“带类的C”以来，for循环就一直是它的惯用语法，而且与C风格字符串不同，它不会消失。Stroustrup本人在他的《C++程序设计语言》（第二版）中警告过“试图将C++写成$(其他语言)”：我不确定他后来是否改变了立场，但C++并不完全是一种函数式语言，试图将其写成这样很容易陷入过于复杂的混乱之中。 - jick

将单个 for 循环更改为 for_each 可能没有什么危害，但是仅因为它是新的就声称后者是客观上更优越的是愚蠢的。C++ 拥有大量特性，这些特性会让你感受到“仅因为你可以在这里使用它并不意味着这是一个好主意”的警示。 - jick

“for_each” 经常是一个不好的替代品，用它来代替一个好的老式“for”循环，我完全同意。但我所说的是其他103个算法。 - YSC