C++ Удалить дубликаты из массива

Question

Спасибо за помощь.

Мне нужно настроить функцию, которая удалит дубликаты из массива. В настоящее время я получаю странный вывод, который я даже не понимаю, и каждый раз, когда я пытаюсь очистить функцию дубликатов, я не получаю желаемого эффекта. Вот код.

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 

Теперь вот моя функция. Это до меня даже пытается удалить дубликаты ....

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 

Я попытался реализовать в то время как цикл и цикл for в функции.cpp (в соответствии с назначением) и не могут заставить что-то работать. Не могли бы вы указать мне в правильном направлении, поскольку я чувствую, что что-то упускаю.

Спасибо.

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

}