向量的 std::remove 和 vector::erase 的区别

std::remove :它实际上并没有从容器中删除元素,而只是将未删除的元素向前分流到已删除元素的顶部。
vector::erase :从向量中删除单个元素(位置)或一系列元素([first, last))。

std::remove 与 vector::erase

通过使用erase()std::vector 中的所有元素将被移动 1 位导致大量副本; std::remove 只是进行“逻辑”删除,并通过移动东西使向量保持不变。
如果需要从向量中删除多个元素,std::remove 会将每个未删除的元素仅复制一次到其最终位置,而 vector::erase 方法会将所有元素从该位置移动到末尾多个/次。
例如,删除以下向量中所有 < 5 的元素。

std::vector v { 1, 2, 3, 4, 5 };
// remove all elements < 5

使用擦除,如果逐个删除元素,则会删除 1,从而导致剩余元素的副本被移动 (4)。 然后,将删除 2 并将所有剩余元素移动一 (3)…按照这种模式,这是一个 O(N^2) 算法。

std::remove 的情况下,算法维护一个头部,并迭代容器。 对于前 4 个元素,头部将被移动并测试元素,但不会复制任何元素。 仅对于第五个元素,对象将从最后一个位置复制到第一个位置,并且该算法将以单个副本完成并将迭代器返回到第二个位置。 这是一个 O(N) 算法。 后面的带有范围的 std::vector::erase 将导致所有剩余元素的破坏并调整容器的大小。

因此,erase() 对容器中的元素执行的操作, remove() 是对范围执行的操作,因为它会重新排列该游侠,但不会从该范围中删除任何内容。

示例代码:

// CPP program to illustrate
// difference b/w std::remove
// and std::vector::erase algorithm
#include <bits/stdc++.h>

int main()
{
    std::vector<int> vec{ 10, 20, 30, 30, 20, 10, 10, 20 };
    std::vector<int> ve{ 10, 20, 30, 30, 20, 10, 10, 20 };

    // Print original vector
    std::cout << "Original vector :";
    for (int i = 0; i < vec.size(); i++)
        std::cout << " " << vec[i];
    std::cout << "n";

    // Iterator that store the position of last element
    std::vector<int>::iterator pend;

    // std :: remove function call
    pend = std::remove(vec.begin(), vec.end(), 20);

    // Print the vector after std :: remove
    std::cout << "Range contains:";
    for (std::vector<int>::iterator p = vec.begin(); p != pend; ++p)
        std::cout << ' ' << *p; std::cout << 'n';

            // Print original vector
            std::cout << "Original Vector :";
    for (int i = 0; i < ve.size(); i++)
        std::cout << " " << ve[i];
    std::cout << "n";

    // std :: vector :: erase function call
    // erase the first 3 elements of vector vector
    ve.erase(ve.begin(), ve.begin() + 3);

    // Print the vector
    std::cout << "Vector contains :";
    for (int i = 0; i < ve.size(); i++)
        std::cout << " " << ve[i];
    std::cout << "n";

    return 0;
}

输出结果:

Original vector : 10 20 30 30 20 10 10 20
Range contains: 10 30 30 10 10

Original Vector : 10 20 30 30 20 10 10 20
Vector contains : 30 20 10 10 20

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/276202.html

(0)
上一篇 2023年2月28日
下一篇 2023年2月28日

相关推荐

发表回复

登录后才能评论