如何从未排序的std :: vector中删除重复项，同时使用算法保持原始排序？ [英] How to remove duplicates from unsorted std::vector while keeping the original ordering using algorithms?

问题描述

我有一个整数数组，我需要从保持每个整数的第一次出现顺序的同时删除重复。我可以看到这样做，但是想象一下更好的方法更好地利用STL算法？插入不在我的控制之下，所以我无法在插入之前检查重复项。

  int unsortedRemoveDuplicates（std :: vector< int> ;& numbers）{
 std :: set< int> uniqueNumbers; 
 std :: vector< int> :: iterator allItr = numbers.begin（）; 
 std :: vector< int> :: iterator unique = allItr; 
 std :: vector< int> :: iterator endItr = numbers.end（）; （; allItr！= endItr; ++ allItr）
 
 {
 const bool isUnique = uniqueNumbers.insert（* allItr）.second; 
 
 if（isUnique）{
 * unique = * allItr; 
 ++唯一; 
} 
} 
 
 const int duplicateates = endItr  -  unique; 
 
 numbers.erase（unique，endItr）; 
返回重复; 
} 
  

如何使用STL算法完成？

解决方案

方式是使用 std :: set 告诉你。这是非常有用的，缓存的位置差（缓慢）。

智能*的方式是使用 std :: vector （请确保看到脚注底部）：

  #include< algorithm> 
 #include< vector> 
 struct target_less 
 {
 template< class It> 
 bool operator（）（It const& a，It const& b）const {return * a< * B; } 
}; 
 struct target_equal 
 {
 template< class It> 
 bool operator（）（It const& a，It const& b）const {return * a == * b; } 
}; 
 template< class It>它uniquify（它开始，它的const结尾）
 {
 std :: vector< It> v; 
 v.reserve（static_cast< size_t>（std :: distance（begin，end）））; 
 for（It i = begin; i！= end; ++ i）
 {v.push_back（i）; } 
 std :: sort（v.begin（），v.end（），target_less（））; 
 v.erase（std :: unique（v.begin（），v.end（），target_equal（）），v.end（））; 
 std :: sort（v.begin（），v.end（））; 
 size_t j = 0; 
 for（It i = begin; i！= end&& j！= v.size（）; ++ i）
 {
 if（i == v [ ）
 {
 using std :: iter_swap; iter_swap（i，begin）; 
 ++ j; 
 ++ begin; 
} 
} 
 return begin; 
} 
  

然后你可以使用它：

  int main（）
 {
 std :: vector< int> v; 
 v.push_back（6）; 
 v.push_back（5）; 
 v.push_back（5）; 
 v.push_back（8）; 
 v.push_back（5）; 
 v.push_back（8）; 
 v.erase（uniquify（v.begin（），v.end（）），v.end（））; 
} 
  

*注意：这是聪明的方式>在典型情况下，其中重复的数量不是太高。要进行更全面的性能分析，请参阅相关问题的相关答案。

I have an array of integers that I need to remove duplicates from while maintaining the order of the first occurrence of each integer. I can see doing it like this, but imagine there is a better way that makes use of STL algorithms better? The insertion is out of my control, so I cannot check for duplicates before inserting.

int unsortedRemoveDuplicates(std::vector<int> &numbers) {
    std::set<int> uniqueNumbers;
    std::vector<int>::iterator allItr = numbers.begin();
    std::vector<int>::iterator unique = allItr;
    std::vector<int>::iterator endItr = numbers.end();

    for (; allItr != endItr; ++allItr) {
        const bool isUnique = uniqueNumbers.insert(*allItr).second;

        if (isUnique) {
            *unique = *allItr;
            ++unique;
        }
    }

    const int duplicates = endItr - unique;

    numbers.erase(unique, endItr);
    return duplicates;
}

How can this be done using STL algorithms?

解决方案

The naive way is to use std::set as everyone tells you. It's overkill and has poor cache locality (slow).
The smart* way is to use std::vector appropriately (make sure to see footnote at bottom):

#include <algorithm>
#include <vector>
struct target_less
{
    template<class It>
    bool operator()(It const &a, It const &b) const { return *a < *b; }
};
struct target_equal
{
    template<class It>
    bool operator()(It const &a, It const &b) const { return *a == *b; }
};
template<class It> It uniquify(It begin, It const end)
{
    std::vector<It> v;
    v.reserve(static_cast<size_t>(std::distance(begin, end)));
    for (It i = begin; i != end; ++i)
    { v.push_back(i); }
    std::sort(v.begin(), v.end(), target_less());
    v.erase(std::unique(v.begin(), v.end(), target_equal()), v.end());
    std::sort(v.begin(), v.end());
    size_t j = 0;
    for (It i = begin; i != end && j != v.size(); ++i)
    {
        if (i == v[j])
        {
            using std::iter_swap; iter_swap(i, begin);
            ++j;
            ++begin;
        }
    }
    return begin;
}

Then you can use it like:

int main()
{
    std::vector<int> v;
    v.push_back(6);
    v.push_back(5);
    v.push_back(5);
    v.push_back(8);
    v.push_back(5);
    v.push_back(8);
    v.erase(uniquify(v.begin(), v.end()), v.end());
}

*Note: That's the smart way in typical cases, where the number of duplicates isn't too high. For a more thorough performance analysis, see this related answer to a related question.

这篇关于如何从未排序的std :: vector中删除重复项，同时使用算法保持原始排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！