C++ Remove duplicated from an array

Question

Thanks for the help.

I have to adjust a function that will remove duplicates from an array. Currently, I'm getting weird output that I don't even understand and every time I attempt to cleanse the function of duplicates, i'm not getting the desired effect. Here is the code.

main.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

Now here is my function. This is prior to me even trying to remove the duplicates....

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 file

#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_

My output is:

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

I have tried to implement a while loop and a for loop in the function.cpp (as per the assignment) and haven't been able to get anything to work. Can you please point me in the right direction as I feel that I'm missing something.

Thanks.

Answer 1

After you updated to a complete listing of your code, it seems that the issue is use of values outside of the bounds of your array (the variable Array). In C++, there is no safety mechanism to prevent you from accessing uninitialized memory.

For instance, given the following snippet (adapted from your code):

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;
} 

I get this output:

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

The 'strange' values here are from uninitialized memory. Its contents are undefined. Instead, you should define an 11 element array. I say 11 elements because you access index 10 in your code, and C++ uses zero-based array indices.

If I update my snippet to this:

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;
} 

I get the following (more sane) result:

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

Take care to always initialize variables before using them in C++. Failing to do so can lead to very serious and difficult to detect bugs.

To further illustrate the difference, here's a complete example that shows statically allocating an array, then initializing it in separate steps. In the code above I use the array literal syntax to initialize it.

#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;
  }

}