Не могу понять перегруженный конструктор, используя список списков - PullRequest
Новая
       40

Не могу понять перегруженный конструктор, используя список списков

0 голосов
/ 12 мая 2018

Мне поручили создать программу, которая анализирует производительность hashtable, взяв ifstream словаря английского языка, все произведения Шекспира и файл данных для топографической карты. Я почти закончил, но застрял.

Ниже мой код. У меня проблемы с перегруженным конструктором, использующим итераторы "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;
}

1 Ответ

0 голосов
/ 12 мая 2018
  1. Вам не нужен указатель list<T>* hashTable. Используйте list<T> hashTable и забудьте о деструкторе (кстати, delete [] есть ошибка, ее нужно использовать после new Type[]), оставьте ее по умолчанию.
  2. Список не является подходящим контейнером для хэш-таблицы. Он не имеет доступа по индексу в течение постоянного времени. std::vector<T> подходит.
  3. template<typename InputIterator> HashTable(InputIterator first, InputIterator last) - он должен вставлять элементы от first до last в хеш-таблицу. Как это показано ниже: 
HashTable(InputIterator first, InputIterator last)` 
{
    for (; first != last; ++first)
        insert(*first);
}

Другие проблемы: вы объявили hashTables как список T, а затем он использовал как вектор списка T.

...