c++ - 堆内存损坏 C++ 模板化类

Question

我只是一个谦虚的学生，希望进一步了解我的 C++ 语言知识。我的教授没有帮助!我认为标题和代码中的注释清楚地解释了我的问题。

#ifndef H_Htable
#define H_Htable

//****************************************************************
// Author: D.S. Malik
//
// This class specifies the members to implement a hash table as 
// an ADT. It uses quadratic probing to resolve collisions.
//****************************************************************

#include <iostream>
#include <cassert>

using namespace std;

template <class elemType>
class hashT
{
public:
  void insert(int hashIndex, const elemType& rec);
  //Function to insert an item in the hash table. The first
  //parameter specifies the initial hash index of the item to 
  //be inserted. The item to be inserted is specified by the 
  //parameter rec.
  //Postcondition: If an empty position is found in the hash
  //   table, rec is inserted and the length is incremented by
  //   one; otherwise, an appropriate error message is
  //   displayed.

  //sequential search
  bool search(int& hashIndex, const elemType& rec, bool found = false) const;
  //Function to determine whether the item specified by the
  //parameter rec is in the hash table. The parameter hashIndex
  //specifies the initial hash index of rec.
  //Postcondition: If rec is found, found is set to true and
  //   hashIndex specifies the position where rec is found;
  //   otherwise, found is set to false.

  bool isItemAtEqual(int hashIndex, const elemType& rec) const;
  //Function to determine whether the item specified by the
  //parameter rec is the same as the item in the hash table 
  //at position hashIndex.
  //Postcondition: Returns true if HTable[hashIndex] == rec;
  //   otherwise, returns false.

  void retrieve(int hashIndex, elemType& rec) const;
  //Function to retrieve the item at position hashIndex.
  //Postcondition: If the table has an item at position
  //   hashIndex, it is copied into rec.

  void remove(int hashIndex, const elemType& rec);
  //Function to remove an item from the hash table.
  //Postcondition: Given the initial hashIndex, if rec is found
  //   in the table it is removed; otherwise, an appropriate
  //   error message is displayed.

  void print() const;
  //Function to output the data.

  //provide for both int and string data types in the hash table
  hashT(int size = 101, bool isIntTable = true);
  //constructor
  //Postcondition: Create the arrays HTTable and indexStatusList;
  //   initialize the array indexStatusList to 0; length = 0;
  //   HTSize = size; and the default array size is 101.

  ~hashT();
  //destructor
  //Postcondition: Array HTable and indexStatusList are deleted.

private:
  elemType *HTable;   //pointer to the hash table
  int *indexStatusList;  //pointer to the array indicating the
  //status of a position in the hash table
  int length;    //number of items in the hash table
  int HTSize;    //maximum size of the hash table
};

template <class elemType>
void hashT<elemType>::insert(int hashIndex, const elemType& rec)
{
  int pCount;
  int inc;

  pCount = 0;
  inc = 1;

  while (indexStatusList[hashIndex] == 1
    && HTable[hashIndex] != rec
    && pCount < HTSize / 2)
  {
    pCount++;
    hashIndex = (hashIndex + inc) % HTSize;
    inc = inc + 2;
  }


  if (indexStatusList[hashIndex] != 1)
  {
    HTable[hashIndex] = rec;
    indexStatusList[hashIndex] = 1;
    length++;
  }
  else
  if (HTable[hashIndex] == rec)
    cerr << "Error: No duplicates are allowed." << endl;
  else
    cerr << "Error: The table is full. "
    << "Unable to resolve the collision." << endl;
}

//sequential search
template <class elemType>
bool hashT<elemType>::search(int& hashIndex, const elemType& rec, bool found) const
{
  for (int i = 0; i < HTSize; i++) {
    if (HTable[i] == rec) { //assuming no repeat data
      found = true;
      hashIndex = i;
      break;
    }
  }
  return found;
}

template <class elemType>
bool hashT<elemType>::isItemAtEqual(int hashIndex, const elemType& rec) const
{
  //first make sure the item has not been removed
  if (indexStatusList[hashIndex] != -1) {
    //make equality comparison
    if (HTable[hashIndex] == rec)
      return true;
    else
      return false; //comparison fails
  }
  else
  {
    std::cerr << "isItemEqual():  Item has been removed" << endl;
    return false;
  }
}

template <class elemType>
void hashT<elemType>::retrieve(int hashIndex, elemType& rec) const
{
  if (indexStatusList[hashIndex] != -1)
    rec = HTable[hashIndex];
  else
    std::cerr << "retrieve(): item has been removed" << endl;
}

template <class elemType>
void hashT<elemType>::remove(int hashIndex, const elemType& rec)
{
  //make sure the item hasn't already been removed
  if (indexStatusList[hashIndex] != -1) {
    bool isInList = hashT<elemType>::search(hashIndex, rec);
    //update the status
    if (isInList)
    {
      indexStatusList[hashIndex] = -1;
      length--; //decrement length
    }
    else
      std::cerr << "hasT::remove() could not remove the specified item" << endl;
  }
  else
  {
    std::cerr << "remove():  Item has already been removed from the table" << endl;
  }
}

template <class elemType>
void hashT<elemType>::print() const
{
  std::cout << "Hash Table Data:  " << endl;
  for (int i = 0; i < (length - 5); i++) {
    elemType item = HTable[i];
    //std::cout << item << " ";
  }
}

template <class elemType>
hashT<elemType>::hashT(int size, bool isIntTable)
{
  HTable = new elemType[]; //is this right? HTable is an array just like indexStatusList
  HTSize = size;
  length = 0;
  indexStatusList = new int[0]; //I think this one works?
}

template <class elemType>
hashT<elemType>::~hashT()  //deleting always causes heap errors!!!
//says writing to unallocated memory -- debugging shows otherwise
{
  //delete[] HTable;
  //delete[] indexStatusList; //still causing errors -- error now not associated with any particular line (of my code)
}



#endif

在 main 中实例化 hashT 时，我一直在提高边界检查的安全性。我确信这是因为我的数据成员初始化不正确。这是我在尝试一些操作后收到的一条错误消息:“exercise7Chap9.exe 中 0x773F627C (ntdll.dll) 处未处理的异常:0xC0000374:堆已损坏(参数:0x77426480)。”

最后，为了以防万一，这是主要的:

#include <iostream>
#include "hashT.h"

int main() {
  //add one item and test for equality
  //hashT<int> ht = hashT<int>(20);
  //ht.insert(0, 1);
  //bool itemInsertSuccess = ht.isItemAtEqual(0, 1);
  //if (itemInsertSuccess)
  //  std::cout << "first test has succeeded" << endl;
  //else
  //  std::cout << "first test has failed" << endl;
  ////remove item and make sure isItemEqual returns false
  //ht.remove(0, 1);
  //bool itemRemoved = ht.isItemAtEqual(0, 1);
  //if (!itemRemoved)
  //  std::cout << "second test passed" << endl;
  //else
  //  std::cout << "second test failed" << endl;

  //add many items then make sure search() works
  hashT<int> ht1 = hashT<int>(51);
  for (int i = 0; i < 10; i++)
    ht1.insert(i, i);
  int indx = -1;
  ht1.search(indx, 0);
  if (indx == 25)
    std::cout << "Test 3 has passed" << endl;
  else
    std::cout << "Test 3 has failed" << endl;

  //print data then test retrieve() and print a single item
  /*ht1.print();
  int item = -1;
  ht1.retrieve(10, item);
  if (item != -1) {
    std::cout << item << endl;
    std::cout << "test 4 has passed" << endl;
  }
  else
    std::cout << "test 4 has failed" << endl;

  hashT<int> HtRetrieve = hashT<int>(10);
  HtRetrieve.insert(0, 0);
  int it = -1;
  HtRetrieve.retrieve(0, it);
  std::cout << it << endl;*/

  char stop;
  std::cin >> stop;
  //return 0;
}

Answer 1

在您的例子中，废弃变量 isIntTable .模板是一种编译时构造，运行时值不会以任何方式影响模板编译成类的方式。

然后，在您的构造函数中，只需使用模板类型作为您要分配的类型即可。

template <class elemType>
hashT<elemType>::hashT(int size)
{
    HTable = new elemType[size];
    length = 0;
    indexStatusList = new int[0];
}

但是，这可能会好得多。考虑使用初始化而不是赋值:

hashT<elemType>::hashT(int size) :
    HTable{new elemType[size]},
    length{size},
    indexStatusList{int[size]} { /* empty constructor */ }

而且还可以做得更好。考虑使用智能指针而不是原始拥有指针和 vector 而不是动态分配的数组:

template<typename T>
struct hashT {
    // using the right type for size
    hashT(std::size_t size) : pointerToOneT{std::make_unique<T>()}, HTable(size) {}
    // make_unique is the `new` for unique pointers

    // no need for destructors, the vector and unique_ptr are freeing themselves

private:
    std::unique_ptr<T> pointerToOneT;
    std::vector<T> HTable;
    std::vector<int> indexStatusList;
};

如果你不想使用std::vector , 你总是可以使用 std::unique_ptr<T[]> ，这是一个动态分配的数组，可以释放自身。

template<typename T>
struct hashT {
    // using the right type for size
    hashT(std::size_t size) : 
        HTable{std::make_unique<T[]>(size)},
        indexStatusList(std::make_unique<int[]>(size)) {}

private:
    std::unique_ptr<T[]> HTable;
    std::unique_ptr<int[]> indexStatusList;
};

编辑

在您实际的析构函数中，问题是您初始化了 int*与 new[]但你正在使用 delete .要删除数组，必须使用 delete[]

template <class elemType>
hashT<elemType>::~hashT()
{
  delete HTable;
  delete[] indexStatusList;
}