时间戳

首页 > 解决方案 > 无法使用列表列表找出重载的构造函数

c++ - 无法使用列表列表找出重载的构造函数

问题描述

我被指派制作一个程序，hashtable通过获取ifstream英语词典、莎士比亚的所有作品和地形图的数据文件来分析 a 的性能。我几乎完成了，但我被卡住了。

下面是我的代码。我在使用文件中的"first"和"last"迭代器的重载构造函数时遇到问题.h。我对它应该是什么样子的猜测被注释掉了，但是在我们本章学到的所有内容中，我不知道该怎么做。我的老师根本没有教我们这个。

这是我的 .h 文件：

#ifndef HASHTABLE_H_INCLUDED
#define HASHTABLE_H_INCLUDED

#include <iostream>
#include <list>
#include <fstream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdlib>

using namespace std;
using std::chrono::system_clock;

const size_t HASHTABLE_SIZE = 1048576;

template<typename T>
class HashTable
{
public:

    HashTable() :hashTable(new list<T>(HASHTABLE_SIZE)){}   ///allocates hashTable to 1048576
    ~HashTable() {delete[] hashTable;}
    template<typename InputIterator> HashTable(InputIterator first, InputIterator last);
    ///{
        ///first = hashTable?
        ///last = hashTable + HASHTABLE_SIZE?
    ///}     
    using iterator = list<T>*;
    iterator begin()    ///points to beginning of array
    {
        iterator it;
        it = hashTable;
        return it;
    }
    iterator end()  ///points to one element past the last valid element
    {
        iterator it;
        it = hashTable + HASHTABLE_SIZE;
        return it;
    }
    void insert(const T& key); ///hash input key, use that to index into hash table, then push
                             ///back the element into the list at that index
    iterator find(const T& key)   ///hash input key, use that to index into has table, then
                                ///see if the key exists in the list at that index
    {
        size_t locate = hash_it(key);
        list<T>& lst = hashTable[locate];
        iterator it;
        it = std::find(begin(),end(),lst);
        if(it != hashTable + HASHTABLE_SIZE)
        {
            return it;
        }
        return end();
    }

private:

    list<T>* hashTable; ///This is a pointer to an allocated array of lists
    size_t hash_it(const string& key)
    {
        size_t hash = 0;
        for(size_t i = 0, n = key.size();i < n; i++)
            hash = (hash << 2) ^ key[i];
        return hash % HASHTABLE_SIZE;
    }
    size_t hash_it(const int& key) {return key * (key + 3) % HASHTABLE_SIZE;}
};

#endif // HASHTABLE_H_INCLUDED

这是我们正在使用的主要内容：

#include "HashTable.h"

int main()
{
    istream_iterator<string> eos1;

    cout << "Loading the complete works of Shakespeare into a vector..." << endl;
    ifstream f("shakespeare.txt");
    if(!f)
        cout << "Failed loading shakespeare.txt" << endl;
    istream_iterator<string> iit(f);
    vector<string> vShake(iit, eos1);

    cout << "Loading English dictionary into hash table as C++ strings..." << endl;
    ifstream f2("words_alpha.txt");
    if(!f2)
        cout << "Failed loading words_alpha.txt" << endl;
    istream_iterator<string> iit2(f2);
    HashTable<string> ht1(iit2, eos1);
    //ht1.loadTable(f2);

    int foundCount = 0;
    auto t1 = system_clock::now();
    for(const string& str : vShake)
    {
        auto it = ht1.find(str);
        if(it != ht1.end())
            foundCount++;
    }
    auto t2 = system_clock::now();
    cout << foundCount << " out of " << vShake.size() << " total words matched.\n";
    cout << "Time to search HashTable: "
         << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count()
         << "ms" << endl;

    cout << "Loading up a vector with 500000 randoms [0:30000]" << endl;
    vector<int> vElev;
    for(size_t i = 0; i < 500000; i++)
        vElev.push_back(rand() % 30001);

    cout << "Loading elevations file into hash table as ints..." << endl;
    ifstream f3("map-input-844-480.dat");
    if(!f3)
        cout << "Failed loading map-input-844-480.dat" << endl;
    istream_iterator<int> iit3(f3);
    istream_iterator<int> eos2;
    HashTable<int> ht2(iit3, eos2);
    //ht2.loadTable(f3);

    foundCount = 0;
    t1 = system_clock::now();
    for(const int& x : vElev)
    {
        auto it = ht2.find(x);
        if(it != ht2.end())
            foundCount++;
    }
    t2 = system_clock::now();
    cout << foundCount << " out of " << vElev.size() << " total elevations matched.\n";
    cout << "Time to search HashTable: "
         << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count()
         << "ms" << endl;

    return 0;
}

标签： c++listconstructoriteratorconstructor-overloading

解决方案

  1. You do not need the pointer list<T>* hashTable. Use list<T> hashTable and forget about destructor (by the way delete [] there is an error, it must be used after new Type[]), leave it default.
  2. List is not a proper container for hash table. It does not have access by index for constant time. std::vector<T> is appropriate.
  3. template<typename InputIterator> HashTable(InputIterator first, InputIterator last) -- it should insert elements from first till last into the hash table. Like this below:
HashTable(InputIterator first, InputIterator last)` 
{
    for (; first != last; ++first)
        insert(*first);
}

Other problems: you declared hashTables as list of T, and then it used as vector of list of T.

推荐阅读