如何仅使用.at()、.push_back()、.size()和/或.resize()从未排序的向量中删除数字

Question

我是C++的新手，我正在尝试编写一个void函数，该函数将删除向量中的重复项，同时保留向量的顺序。我在只使用.at((、.push_back((、.size((和.resize((从向量中删除数字时遇到了问题。我该怎么做？

这就是我目前所拥有的：

void RemoveDuplicates(std::vector<int>& vector, int vectorSize) 
{
int i;
int j;
std::vector<int> tempVec; 
for (i = 0; i < vector.size(); i++)
{
for (j = 1; j < vector.size(); j++)
{
if (vector.at(i) == vector.at(j))
{
tempVec.push_back(vector.at(i));  //Unduplicated Vector
}
}
}
}

如果我把"；1 2 3 3"；在这种情况下，它将tempVec返回为"0"；2 3 3 3 3；预期的结果只是"；1 2 3；我该如何解决这个问题，以便只使用这些向量操纵器来消除向量的重复？

Answer 1

这里有一个简单的方法，效率不高，但易于理解

void RemoveDuplicates(std::vector<int>& vector) 
{
std::vector<int> tempVec; 
for (size_t i = 0; i < vector.size(); i++)
{
// look for vector[i] in remainder of vector
bool found = false;
for (size_t j = i + 1; j < vector.size(); j++)
{
if (vector.at(i) == vector.at(j))
{
found = true;
break;
}
}
// if not found it's not a duplicate
if (!found)
tempVec.push_back(vector.at(i));
}
vector = tempVec;
}

Answer 2

基于您当前的想法，您可以将vector中的每个值与tempVec中的所有值进行比较。如果在tempVec中找不到，请添加它。

我使用基于范围的for-循环来简化循环：

#include <utility> // std::move
void RemoveDuplicates(std::vector<int>& vector) {
std::vector<int> tempVec; 

for(int in : vector) {       // `in` will be assigned one value at a time from vector
bool found = false;      // set to `true` if the `in` value has already been seen
for(int out : tempVec) { // range based for-loop again
if(in == out) {      // oups, duplicate
found = true;    // set to true to avoid storing it
break;           // and abort this inner loop
}
}
// only stored values not found:
if(not found) tempVec.push_back(in);
}
// move assign the result to `vector`:
vector = std::move(tempVec);
}

Answer 3

您不需要传递向量的大小。向量知道它的size()。您的代码实际上并没有从vector中删除任何内容。

使用可用的工具。

可以使用std::unique删除重复的相邻元素。对矢量进行排序后，将删除所有重复项：

void RemoveDuplicates(std::vector<int>& vector) 
{
std::sort(vector.begin(),vector.end());
auto it = std::unique(vector.begin(),vector.end());
vector = std::vector<int>(vector.begin(),it);
}

std::set只存储唯一元素，因此也可以使用：

void RemoveDuplicates2(std::vector<int>& vector) 
{
std::set<int> s{vector.begin(),vector.end()};
vector = std::vector<int>(s.begin(),s.end());
}

如果你想保持元素的初始顺序，你仍然可以使用std::set:

void RemoveDuplicates3(std::vector<int>& vector) 
{
std::set<int> s;
std::vector<int> result;
for (const auto& e : vector) {
if (s.insert(e).second) { // not a duplicate
result.push_back(e);
}
}
vector = result;
}

非常相似，通过搜索不在集合中而是在结果向量中的元素：

void RemoveDuplicates4(std::vector<int>& vector) 
{
std::vector<int> result;
for (const auto& e : vector) {
if (std::find(result.begin(),result.end(),e) == result.end()){
result.push_back(e);
}
}
vector = result;
}

实时演示

Answer 4

对于初学者来说，函数的第二个参数是多余的，不在函数中使用。删除它。该函数应该像一样声明

void RemoveDuplicates( std::vector<int> &vector );

此外，您忘记更改原始矢量。

看来你的意思是如果条件中的不等式

if (vector.at(i) != vector.at(j))
{
tempVec.push_back(vector.at(i));  //Unduplicated Vector
}

而不是相等的

if (vector.at(i) == vector.at(j))
{
tempVec.push_back(vector.at(i));  //Unduplicated Vector
}

尽管在任何情况下，内部for循环中的逻辑都不正确。

你的内部for循环总是从1 开始

for (j = 1; j < vector.size(); j++)

因此，对于该源向量{ 1, 2, 3, 3 }，值2将在tempVec上被推一次，并且对于值为3的每个元素，将有两个等于3的值被推送到tempVec。

使用您的方法，函数可以如下所示。

void RemoveDuplicates( std::vector<int> &vector ) 
{
std::vector<int> tempVec; 
for ( std::vector<int>::size_type i = 0; i < vector.size(); i++ )
{
std::vector<int>::size_type j = 0;
while ( j < tempVec.size() && vector.at( i ) != tempVec.at( j ) )
{
++j;
}
if ( j == tempVec.size() )
{
tempVec.push_back( vector.at( i ) );
}
}
std::swap( vector, tempVec );
}

这是一个示范节目。

#include <iostream>
#include <vector>
void RemoveDuplicates( std::vector<int> &vector ) 
{
std::vector<int> tempVec; 
for ( std::vector<int>::size_type i = 0; i < vector.size(); i++ )
{
std::vector<int>::size_type j = 0;
while ( j < tempVec.size() && vector.at( i ) != tempVec.at( j ) )
{
++j;
}
if ( j == tempVec.size() )
{
tempVec.push_back( vector.at( i ) );
}
}
std::swap( vector, tempVec );
}
int main() 
{
std::vector<int> v = { 1, 2, 3, 3 };
std::cout << v.size() << ": ";
for ( const auto &item : v )
{
std::cout << item << ' ';
}
std::cout << 'n';
RemoveDuplicates( v );
std::cout << v.size() << ": ";
for ( const auto &item : v )
{
std::cout << item << ' ';
}
std::cout << 'n';
}

程序输出为

4: 1 2 3 3 
3: 1 2 3 

Answer 5

在适当的位置调整数组(包括向量(的大小，并在每次发现重复项时将项移动1可能会很昂贵。

如果您可以使用基于哈希表的集合(即unordered_set或unordered_map(来跟踪已经看到的项目，那么您就可以使用基于O(N(的算法。

除了已经提出的std:：unqiue解决方案之外，很难击败它。std:：unique实际上是一回事。

void RemoveDuplicates(std::vector<int>& vec)
{
std::unordered_set<int> dupes;
std::vector<int> vecNew;
for (int x : vec)
{
if (dupes.insert(x).second)
{
vecNew.push_back(x);
}
}
vec = std::move(vecNew);
}