擦除重复元素保持秩序

Question

我想从矢量中删除重复元素，同时保持矢量的当前顺序。

下面我有一个建议的实现。首先，这样安全吗？

其次，是否有更好的方法来做到这一点，从“使用 C++ 算法而不是重新发明轮子”的角度来看，效率更高或更好。

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

int main()
{
    using namespace std;

    std::vector<int> v= {1, 7, 2, 3, 8, 4, 5, 3, 2, 3, 2, 6, 2, 3, 2, 9, 10, 1, 2, 2, 1};
    std::vector<int>::iterator finalEnd = v.end();
    for (auto vIter = v.begin(); vIter != v.end(); ++vIter) {
        for (auto nextvIter = vIter + 1; nextvIter != v.end(); ++nextProjIter) {
            if (*vIter == *nextvIter)
                finalEnd = std::remove(vIter, finalEnd, *nextvIter);
        }
    }
    v.erase(finalEnd, v.end());

    for(auto p : v)
        cout << p << "  ";

    //Should return:  1  7  2  3  8  4  5  6  9  10

    return EXIT_SUCCESS;
}

Answer 1

通过构造一个新的vector，你可以将这个vector初始化为不重复的。您可以为此使用查找功能。我建议你搜索 std :: find

std::vector<int> v= {1, 7, 2, 3, 8, 4, 5, 3, 2, 3, 2, 6, 2, 3, 2, 9, 10, 1, 2, 2, 1};
std::vector<int> nonDuplicateVect;

for (int element : v)
    if(std::find(nonDuplicateVect.begin(), nonDuplicateVect.end(), element) == nonDuplicateVect.end())
        nonDuplicateVect.push_back(element);

for (int element : nonDuplicateVect)
    std::cout << element << " ";

std::cout << "\n";

Answer 2

实现此目的的方法之一是使用 std::unordered_set to keep track of duplicates and std::stable_partition 将重复项与单独的值分开，同时保留项目的顺序：

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

int main()
{
    std::unordered_set<int> numSet;
    std::vector<int> v= {1, 7, 2, 3, 8, 4, 5, 3, 2, 3, 2, 6, 2, 3, 2, 9, 10, 1, 2, 2, 1};
    auto iter = std::stable_partition(v.begin(), v.end(), [&](int n) 
           { bool ret = !numSet.count(n); numSet.insert(n); return ret; }); // returns true if the item has not been "seen"
    v.erase(iter, v.end());           
    for(auto p : v)
        std::cout << p << "  ";
}

输出：

1  7  2  3  8  4  5  6  9  10

std::stable_partition 将 return true 如果该项目还没有看到，因此将其放在分区点的左侧。完成后，指向分区点的迭代器被 returned，我们使用此迭代器从该点到向量末尾进行一次擦除。请注意，lambda 函数会为处理的每个项目更新 unordered_set。

之所以使用std::stable_partition而不是std::remove_if是因为std::remove_if不能保证按顺序处理项目。例如，实现可以先处理该数据中的第二个 1，而不是第一个 1。所以为了保险起见stable_partition不会擦除元素，只是把元素放在正确的位置，为最后的擦除做准备。

擦除重复元素保持秩序

erase duplicate elements keeping order

c++

vector

erase