擦除/移除std::vector元素

由于std::vector能自动增长,并且使用方式简单,很受C++开发新手的喜爱。可以通过查阅手册,来了解这个容器该如何使用,比如删除元素。这样使用STL容器,只是了解容器的皮毛,容器应该帮助我们写出更简洁、维护性好和更快的代码。

本节的全部内容都是在一个vector实例中删除元素。当vector中部的一个元素消失了,那么位于消失元素右边的所有元素都要往左移(这种操作的时间复杂度为O(n)。新手们会用循环来做这件事,因为循环的确好用。不过,循环会降低代码的优化空间。最后,比起STL的方法,循环是既不快,也不美,

How to do it...

首先,我们使用整数来填充一个std::vector实例,之后剔除一些特定元素。我们演示的从vector实例中删除元素正确的方法。

  1. 包含文件是首要任务。

    #include <iostream>
    #include <vector>
    #include <algorithm>
  2. 声明我们所要使用的命名空间。

    using namespace std;
  3. 现在我们来创建一个vector实例,并用整数填满它。

    int main(){
        vector<int> v{1, 2, 3, 2, 5, 2, 6, 2, 4, 8};
  4. 然后移除一些元素。需要我们移除哪些呢?2出现的太多次了,就选择2吧。让我们移除它们吧。

        const auto new_end(remove(begin(v), end(v), 2));
  5. 已经完成了两步中的一步。vector在删除这些元素之后,长度并没有发生变化。那么下一步就让这个vector变得短一些。

        v.erase(new_end, end(v));
  6. 我们在这里暂停一下,输出一下当前vector实例中所包含的元素。

        for(auto i : v){
            cout << i << ", "; 
        }
        cout << '\n';
  7. 现在,让我们来移除一组指定的数据。为了完成这项工作,我们先定义了一个谓词函数,其可接受一个数作为参数,当这个数是奇数时,返回true。

        const auto odd([](int i){return i % 2 != 0;});
  8. 这里我们使用remove_if函数,使用上面定义的谓词函数,来删除特定的元素。这里我们将上面删除元素的步骤合二为一。

        v.erase(remove_if(begin(v), end(v), odd), end(v));
  9. 所有的奇数都被删除,不过vector实例的容量依旧是10。最后一步中,我们将其容量修改为正确的大小。需要注意的是,这个操作会让vector重新分配一段内存,以匹配相应元素长度,vector中已存的元素会移动到新的内存块中。

        v.shrink_to_fit();
  10. 打印一下现在vector实例中的元素。

        for (auto i : v) {
            cout << i << ", ";
        }
        cout << '\n';
    }
  11. 编译完成后,运行程序,就可以了看到两次删除元素后vector实例中所存在的元素。

    $ ./main
    1, 3, 5, 6, 4, 8,
    6, 4, 8,

How it works...

我们可以清楚的看到,要从一个vector实例中移除一个元素,首先要进行删除,然后进行擦除,这样才算真正的移除。这会让人感到困惑,那就让我们近距离观察一下这些步骤是如何工作的。

vector中移除2的代码如下所示:

const auto new_end (remove(begin(v), end(v), 2));
v.erase(new_end, end(v));

std::beginstd::end函数都以一个vector实例作为参数,并且返回其迭代器,迭代器分别指向第一个元素和最后一个元素,就如下图所示。

std::remove在删除2的时候,会先将非2元素进行移动,然后修改end迭代器的指向。该算法将严格保留所有非2个值的顺序。

在2步中,2的值仍然存在,并且vector应该变短。并且4和8在现有的vector中重复了。这是怎么回事?

让我们再来看一下所有的元素,目前vector的范围并不是原来那样了,其是从begin迭代器,到new_end迭代器。new_end之后的值其实就不属于vector实例了。我们会注意到,在这个范围内的数值,就是我们想要的正确结果,也就是所有的2都被移除了。

最后,也就是为什么要调用erase函数:我们需要告诉vector实例,new_endend之间的元素我们不需要了。我们仅需要保留beginnew_end间的元素就好了。erase函数会将end指向new_end。这里需要注意的是std::remove会直接返回new_end迭代器,所以我们可以直接使用它。

Note:

vector在这里不仅仅移动了内部指针。如果vector中元素比较复杂,那么在移除的时候,会使用其析构函数来销毁相应的对象。

最后,这个向量就如步骤3所示:的确变短了。那些旧的元素已经不在vector的访问范围内了,不过其仍存储在内存中。

为了不让vector浪费太多的内存,我们在最后调用了shrink_to_fit。该函数会为元素分配足够的空间,将剩余的元素移到该空间内,并且删除之前那个比较大的内存空间。

在上面的第8步中,我们定义了一个谓词函数,并在std::remove_if中使用了它。因为不论删除函数返回怎么样的迭代器,在对vector实例使用擦除函数都是安全的。如果vector中全是偶数,那么std::remove_if不会做任何事情,并且返回end迭代器。之后的调用就为v.erase(end, end);,同样没有做任何事情。

There's more...

std::remove函数对其他容器同样有效。当使用std::array时,其不支持erase操作,因为其内存空间固定,无法进行自动化处理。因为std::remove只是将要删除的元素移动到容器末尾,而不是将其真正删除,所以这个函数也可以用于不支持空间大小变化的数据类型。当然也有其他类似的方法,例如字符串中,可以用哨兵值\0来覆盖原始的end迭代所指向的值。

Last updated