C++ 删除数组中的重复项

Question

感谢您的帮助。

我必须调整一个函数来从数组中删除重复项。目前，我得到了我什至不理解的奇怪输出，每次我尝试清除重复项的功能时，我都没有得到预期的效果。这是代码。

主要.cpp

#include <iostream> // For cout and cin
#include <string>   // For string objects
#include "Set.h"    // For ADT Set
using namespace std;

int main()
{

  //Creating a set to hold our numbers
  Set<int> a_set;

  //Checking if a_set is empty
  cout << "This is the empty set, and IsEmpty() returns "
    << a_set.IsEmpty() << endl;

  //creating an empty array
  int Array[] = {1};

  //Checking if the set now has a single items
  cout << "This set should have a single item, and a_set.Contains "
    << a_set.Contains(Array[1]) << endl;

  //Removing the item placed in a_set.
  a_set.Remove(Array[1]);

  //Verifying that the set is empty again.
  cout << "This is the empty set, and IsEmpty() returns "
    << a_set.IsEmpty() << " The set is now empty and ready for values." << endl;    


  //Adding items in order given
  a_set.Add(Array[1]);
  a_set.Add(Array[10]);
  a_set.Add(Array[3]);
  a_set.Add(Array[10]);
  a_set.Add(Array[5]);    
  a_set.Add(Array[10]);

  //Getting current size of a_set
  int size = a_set.GetCurrentSize();
  cout << "The Array should be size=4. Size = " << size << endl;

  //Checking that the items that we placed in the set are correct
  cout << "Number 1 should be pressent in a_set. Return: " 
    << a_set.Contains(Array[1]) << endl;

  cout << "Number 3 should be pressent in a_set. Return: " 
    << a_set.Contains(Array[3]) << endl;

  cout << "Number 5 should be pressent in a_set. Return: " 
    << a_set.Contains(Array[5]) << endl;

  cout << "Number 10 should be pressent in a_set. Return: " 
    << a_set.Contains(Array[10]) << endl;

int v = 0;
do
{
    cout << Array[v] << endl;
    v++;
}while (v < 7);
   return 0;

}; // end main

现在这是我的功能。这是在我尝试删除重复项之前....

function.cpp

#include "Set.h"
#include <cstddef>

template<class ItemType>
Set<ItemType>::Set() : item_count_(0), max_items_(kDefaultSetSize_)
{
}  // end default constructor

template<class ItemType>
int Set<ItemType>::GetCurrentSize() const
{
  return item_count_;
}  // end getCurrentSize

template<class ItemType>
bool Set<ItemType>::IsEmpty() const
{
  return item_count_ == 0;
}  // end isEmpty

// Made changes to deny duplicate items in an array.
template<class ItemType>
bool Set<ItemType>::Add(const ItemType& new_entry)
{
  bool has_room_to_add = item_count_ < max_items_;
  if (has_room_to_add)
  {
    items_[item_count_] = new_entry;
    item_count_++;
  }  // end if

  return has_room_to_add;
}  // end add

template<class ItemType>
bool Set<ItemType>::Remove(const ItemType& an_entry)
{
  int located_index = GetIndexOf(an_entry);
  bool can_remove_item = !IsEmpty() && (located_index > -1);
  if (can_remove_item)
    {
      item_count_--;
      items_[located_index] = items_[item_count_];
    }  // end if
  return can_remove_item;
}  // end remove

template<class ItemType>
void Set<ItemType>::Clear()
{
  item_count_ = 0;
}  // end clear

template<class ItemType>
int Set<ItemType>::GetFrequencyOf(const ItemType& an_entry) const
{
  int frequency = 0;
  int search_index = 0;
  while (search_index < item_count_)
    {
      if (items_[search_index] == an_entry)
    {
      frequency++;
    }  // end if

      search_index++;
    }  // end while

   return frequency;
}  // end getFrequencyOf

template<class ItemType>
bool Set<ItemType>::Contains(const ItemType& an_entry) const
{
  return GetIndexOf(an_entry) > -1;
}  // end contains

template<class ItemType>
vector<ItemType> Set<ItemType>::ToVector() const
{
  vector<ItemType> bag_contents;
  for (int i = 0; i < item_count_; i++)
    bag_contents.push_back(items_[i]);
  return bag_contents;
}  // end toVector

template<class ItemType>
int Set<ItemType>::GetIndexOf(const ItemType& target) const
{
  bool found = false;
  int result = -1;
  int search_index = 0;
  // if the bag is empty, item_count is zero, so loop is skipped
  while (!found && (search_index < item_count_))
    {
      if (items_[search_index] == target)
    {
      found = true;
      result = search_index;
    } 
      else
    {
      search_index++;
    }  // end if
    }  // end while
  return result;
}  // end getIndexOf

*.h文件

#ifndef TEACH_CSCI235_BAGADT_BAG_H_
#define TEACH_CSCI235_BAGADT_BAG_H_

#include "SetInterface.h"

template<class ItemType>
class Set : public SetInterface<ItemType>
{
 public:
  Set();
  int GetCurrentSize() const;
  bool IsEmpty() const;
  bool Add(const ItemType& new_entry);
  bool Remove(const ItemType& an_entry);
  void Clear();
  bool Contains(const ItemType& an_ntry) const;
  int GetFrequencyOf(const ItemType& an_entry) const;
  vector<ItemType> ToVector() const; 

 private:
  static const int kDefaultSetSize_ = 6;  
  ItemType items_[kDefaultSetSize_]; // array of bag items
  int item_count_;                    // current count of bag items 
  int max_items_;                 // max capacity of the bag

  // Returns either the index of the element in the array items that
  // contains the given target or -1, if the array does not contain 
  // the target.
  int GetIndexOf(const ItemType& target) const;   
};  // end Set

#include "Set.cpp"

#endif  // TEACH_CSCI235_BAGADT_BAG_H_

我的输出是:

This is the empty set, and IsEmpty() returns 1
This set should have a single item, and a_set.Contains 1
This is the empty set, and IsEmpty() returns 1 The set is now empty and ready for values.
The Array should be size=4. Size = 6
Number 1 should be pressent in a_set. Return: 1
Number 3 should be pressent in a_set. Return: 1
Number 5 should be pressent in a_set. Return: 1
Number 10 should be pressent in a_set. Return: 1
1
0
42563728
1
2056807160
32767
42563728

我已经尝试在 function.cpp 中实现一个 while 循环和一个 for 循环(根据分配)，但没有任何效果。你能给我指出正确的方向吗，因为我觉得我错过了什么。

谢谢。

Answer 1

在更新为完整的代码列表后，问题似乎出在数组边界之外的值的使用(变量 Array)。在 C++ 中，没有安全机制可以防止您访问未初始化的内存。

例如，给定以下片段(改编自您的代码):

int main(int, char**) {
  /* Notice I only specify one element */
  int array[] = { 1 };

  int v = 0;
  do {
      std::cout << array[v] << std::endl;
      v++;
  } while (v < 7);

  return 0;
} 

我得到这个输出:

rdahlgren@athas:~/work/cpp $ g++ main.cpp 
rdahlgren@athas:~/work/cpp $ ./a.out
1
32767
0
3
4196544
0
372508672

此处的“奇怪”值来自未初始化的内存。它的内容是未定义的。相反，您应该定义一个包含 11 个元素的数组。我说 11 个元素是因为您在代码中访问索引 10，而 C++ 使用从零开始的数组索引。

如果我将代码片段更新为:

int main(int, char**) {
  /* Now I specify 11 elements */
  int array[] = { 
    0, 1, 2, 3, 4, 5, 
    6, 7, 8, 9, 10
  };

  int v = 0;
  do {
      std::cout << array[v] << std::endl;
      v++;
  } while (v < 7);

  return 0;
} 

我得到以下(更理智的)结果:

rdahlgren@athas:~/work/cpp $ g++ main.cpp 
rdahlgren@athas:~/work/cpp $ ./a.out
0
1
2
3
4
5
6

在 C++ 中使用变量之前，请注意始终对其进行初始化。如果不这样做，可能会导致非常严重且难以检测的错误。

为了进一步说明差异，这里有一个完整的示例，展示了静态分配一个数组，然后在单独的步骤中对其进行初始化。在上面的代码中，我使用数组字面量语法对其进行初始化。

#include <iostream>

int main(int, char**) {
  const unsigned int arrayLength = 5;
  int array[arrayLength]; // <-- allocated, but uninitialized

  std::cout << "Uninitialized values:\n";
  for (int i = 0; i < arrayLength; ++i) {
    std::cout << "Array index " << i << " is " << array[i] << std::endl;
  }

  // Now we can initialize it / insert values / whatever
  for (int i = 0; i < arrayLength; ++i) {
    array[i] = i * 10; // Times ten just for fun
  }

  for (int i = 0; i < arrayLength; ++i) {
    std::cout << "Array index " << i << " is " << array[i] << std::endl;
  }

}