Hey all,
I'm implementing a hash table for a spell checker and need some assistance on vector const_iterator - at least I think that's where the problem lies. Can anyone assist in diagnosing how to fix these compiler errors?

I initially got this error, which i think will come back once I fix the is_present function:
main.cpp:101: undefined reference to `ns_1::table<word_record>::is_present(int) const'

I am now getting the below errors and can't figure out if I have a data type issue or am just defining the const_iterator incorrectly or ... Note that line 67 in the errors corresponds to line 11 of the template on the posting.

In file included from table3.h:82,
from main.cpp:10:
table3.template: In member function `bool ns_1::table<RecordType>::is_present(int) const':
table3.template:67: error: expected `;' before "it"
table3.template:69: error: `it' was not declared in this scope
table3.template: In member function `bool ns_1::table<RecordType>::is_present(int) const [with RecordType = word_record]':
main.cpp:102: instantiated from here
table3.template:67: error: dependent-name ` std::vector<RecordType,std::allocator<_CharT> >::const_iterator' is parsed as a non-type, but instantiation yields a type
table3.template:67: note: say `typename std::vector<RecordType,std::allocator<_CharT> >::const_iterator' if a type is meant
make: *** [main.o] Error 1


Note - I am already using other functions fromt the namespace ns_1 successfully.


// Header code

#include <cstdlib>      // provides size_t
#include <vector>       // provides STL vector class

namespace ns_1
{
   template <class RecordType>
   class table
   {
   public:
        // MEMBER CONSTANT
        static const std::size_t TABLE_SIZE = 1373;

        // CONSTRUCTORS (no desctructor needed, uses automatic copy constructor)
        table( );

        // MODIFICATION MEMBER FUNCTIONS
        void insert(const RecordType& entry);
        void remove(int key);

        // CONSTANT MEMBER FUNCTIONS
        void find(int key, bool& found, RecordType& result) const;
        bool is_present(int key) const;
        std::size_t size( ) const { return total_records; }

   private:
        std::vector<RecordType> data[TABLE_SIZE];  // each component of the array is a vector
        std::size_t total_records;

        // HELPER MEMBER FUNCTION
        std::size_t hash(int key) const;
   };
}

#include "table3.template"   // Include the implementation

// applicable template code

#include <cstdlib>  // Provides size_t
#include <vector>   // Provides vector class

namespace ns_1
{
    template <class RecordType>
    bool table<RecordType>::is_present(int key) const
    {
        std::size_t i = hash(key);  // If key exists, it will be somewhere in data[i]

        std::vector<RecordType>::const_iterator it;

        for (it = data[i].begin(); it != data[i].end(); ++i)
        {
           if (data[i].at(*it.key) == key)
                return true;
        }
        return false;
    }
}

// code from main.cpp
// FILE: main.cpp

#include <iostream> // provides cin, cout,...
#include <sstream>  // provides stringstream class and functionsl
#include <string>   // provides string manipulation
#include <fstream>  // provides file handling
#include <cassert>  // provides assert
#include <cstdlib>  // provides NULL constant
#include <vector>   // provides vector class
#include "table3.h" // provides hash table class

using namespace std;
using namespace ns_1;

struct word_record
{
   int key;
   string data;
};

class HFstring // Hash Function for a string
{
   public:
   unsigned int operator() (const string& item) const
   {
   unsigned int prime = 2049982463;
   int n = 0, i;

   for (i = 0; i < item.length(); ++i)
   n = n*8 + item[i];

   //cout << " N equals " << n << endl;
   return n > 0 ? (n % prime) : (-n % prime);
   }
};

ifstream& getWord(ifstream& fin, string& w)
{
  char c;

  w = ""; // clear the string of characters

  while (fin.get(c) && !isalpha(c)); // do nothing. just ignore c

  // return on end-of-file
  if (fin.eof())
    return fin;

  // record first letter of the word
  w += tolower(c);

  // collect letters and digits
  while (fin.get(c) && (isalpha(c) || isdigit(c)))
    w += tolower(c);

  return fin;
}

int main ()
{
   ifstream user_file;
   ifstream dictionary;
   table<word_record> d_table;
   bool found;
   word_record temp_record;
   word_record d_entry;
   HFstring genkey;
   string docname;
   string check_word;
   string word;
   int words_added;

   dictionary.open("dict.dat");
   assert(dictionary);


   // Create dictionary hash table for spell check
   while (dictionary) {
        while (getline(dictionary, word)) {
           // Insert data into a word_record object
           d_entry.data = word;
           d_entry.key = genkey(word);
           d_table.insert(d_entry);
           //++words_added;
           //cout << "Inserted word number : " << words_added << endl;
        }
        cout << "Hash table successfully created" << endl;
        cout << "Total Records equals" << d_table.size() << endl;
   }

   // Open user file to spell check
   cout << "Please specify the filename to spell check: ";
   cin >> docname;
   user_file.open(docname.c_str());
   assert(user_file);

   //
   while (user_file) {
        while (getWord(user_file, check_word)) {
           temp_record.data = check_word;
           temp_record.key = genkey(check_word);
           if (!(d_table.is_present(temp_record.key)))
                cout << temp_record.data << " is not spelled correctly." << endl;
        }
   }

   dictionary.close();
   user_file.close();
   return 0;
}

you have two problems with your code:

(a) missing typename on the in the template file.

std::vector<RecordType>::const_iterator it;  // THIS IS WRONG

// This is correct:
typename std::vector<RecordType>::const_iterator it;

There are many explanations around for this, it basically is because since depending on what std::vector<RecordType> is specialized as, you can't figure out what const_iterator will be. [It might resolve to a value for example].

Next you have a small issue in resolving the repeating name issue and
in precedence order:

if (data[i].at(*it.key)  == key)  // THIS IS wRONG
// This is better [precedence order correct]
if (data[i].at(it->key)  == key)

That will leave you with one function to add, and that is a bool word_record::operator==(const int&) const; since you are comparing a RecordType with an int on the line 15 of the code.
you might like to write the completely unintelligible if (data[i].at(it->key).key == key) but then I don't think that is a good idea.

Additionally , you need to provide implementations of table::table and table::insert().

Thanks StuXYZ - Appreciate the help. The table::table and table::insert functions seem to work so I did not include them here. I've updated the functions as you mentioned and experimented with accessing the table, but am running into a new error. I'm not sure that i've overloaded the operator correctly.

I changed
std::vector<RecordType> data[TABLE_SIZE];
from private to public so the word_record struct could use it, but that doesn't seem to be the right way to go about it as it still isn't able to access the vector "at" member. I also tried a static cast, but was unsuccessful.

Here is the error
main.cpp: In member function `bool word_record::operator==(const int&) const':
main.cpp:24: error: request for member `at' in `(((const std::string*)((const word_record*)this)) + 4u)->std::basic_string<_CharT, _Traits, _Alloc>::operator[] [with _CharT = char, _Traits = std::char_traits<char>, _Alloc = std::allocator<char>](((unsigned int)i))', which is of non-class type `const char'
make: *** [main.o] Error 1


// updated is_present function in .template file

template <class RecordType>
    bool table<RecordType>::is_present(int key) const
    {
        std::size_t i = hash(key);  // If key exists, it will be somewhere in data[i]
        int keycomp;

        typename std::vector<RecordType>::const_iterator it;

        for (it = data[i].begin(); it != data[i].end(); ++i)
        {
           //keycomp = data[i].at(it->key);   --- can't assign type 'word_record' to int
           //if (keycomp == key)                --- even though word_record.key is an int
           //                                    --- static cast also did not work

           if (data[i].at(it->key) == key)
                return true;
        }
        return false;
    }

// updated struct at top of main.cpp

struct word_record
{
   int key;
   string data;
   bool operator==(const int&) const
   {
        int i;
        vector<word_record>::const_iterator it;

        if (data[i].at(it->key).key == key)
           return true;
        return false;
   }

};

Edited 6 Years Ago by lasl0w: n/a

You have made the same mistake as the original [in a different place].

You bool operator does not know anything about the vector or the type, that is because it actually is the type contained in the vector:

it should be this:

bool operator==(const int& Index) const   // Get the value to be compared into index
{
  return (key==Index);
}

You have completely confused yourself by using the variable name key in just about every possible location in your code, thus it is a scope understanding master-class to figure out what is going on. Try this:

template <class RecordType>
bool table<RecordType>::is_present(int possibleTarget) const
{
  std::size_t i = hash(possibleTarget);  

  typename std::vector<RecordType>::const_iterator it;

  for (it = data[i].begin(); it != data[i].end(); ++i)
     {
       if (data[i].at(it->key) == possibleTarget)
          return true;
     }
  return false;
}

Finally, get hash() to return a reference to a data object and not an index value, you can use an empty vector for a "not found". [When you have it working!!!]

Edited 6 Years Ago by StuXYZ: n/a

It compiles now - Thanks. I need to go study more operator overloading, templates, and well, everything.

It compiles, but i get an out_of_range error when is_present attempts to iterate through the vector. I get this error even when it is accessing a vector I know is not empty. Any ideas?

BEFORE Iterator declaration
AFTER Iterator declaration
iteration through FOR loop
terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check
Aborted

template <class RecordType>
   const std::size_t table<RecordType>::TABLE_SIZE;

   template <class RecordType>
   table<RecordType>::table( )
   {
        total_records = 0;
        std::vector<RecordType> data[TABLE_SIZE];  //vectors initialized empty
        // Access using table.data[i].at(j) ?
   }

   template <class RecordType>
   void table<RecordType>::insert(const RecordType& entry)
   // Library facilities used: cassert
    {
        std::size_t index;        // data[index] is location for the new entry

        index = hash(entry.key);  // create index from key
        //std::cout << "index to place entry equals " << index << std::endl;

        data[index].push_back(entry);
        ++total_records;
    }
    template <class RecordType>
    bool table<RecordType>::is_present(int check_word_key) const
    {
        std::size_t i = hash(check_word_key);  // If key exists, it will be somewhere in data[i]

        std::cout << "BEFORE Iterator declaration" << std::endl;
        typename std::vector<RecordType>::const_iterator it;
        std::cout << "AFTER Iterator declaration" << std::endl;

        for (it = data[i].begin(); it != data[i].end(); ++i)
        {
           std::cout << "iteration through FOR loop" << std::endl;
           if (data[i].at(it->key) == check_word_key)
                return true;
        }
        return false;
    }

    template <class RecordType>
    inline std::size_t table<RecordType>::hash(int key) const
    {
        return (key % TABLE_SIZE);
    }

<Ignore > When you do data[index] if the value of index is greater than the size of vector you can get a out-of-range error. Ensure that you are inserting at valid index or resize your vector </ignore>

Sorry I did not see that you posted the output at the top and the problem was coming at some other point. But the explanation remains same , the value of 'i' is going beyond the range of vector at some point. Use vector.size() to limit value of 'i' may be.

Edited 5 Years Ago by Agni: n/a

In this particular case, it seems to be that you are getting the exception from the line if (data[i].at(it->key) == check_word_key) . That is because it->key DOES NOT correspond to the size of the vector data.

This occurs because data is not a vector of size TABLE_SIZE but is of the number inserted. E.g. you insert keys 34, 56 and 78. Now you have three vectors with one component each. THEN you access from key 34, and you do data[34].at(34). Opps error.
Since data[34] only has one component.

To see this, modify your lines:

std::cout << "iteration through FOR loop" << std::endl;
std::cout<<"Size of data["<<index<<"]=="<<data[index].size()<<std::endl;
std::cout<<"Accessing "<<it->key<<std::endl;

Edited 5 Years Ago by StuXYZ: n/a

I changed the function to cout everything to help clear it up. I also switched the method of vector access to use the size() function rather than an iterator because I don't have a good understanding of iterators yet. It works - See below. Only problem left is that i'm not matching on anything so it acts as though all words are spelled incorrectly. I think there is a difference in the way getline and getWord create a string. maybe one is null terminated and one is not - causing the key generation to differ. I would use getline in both instances, but I have to use getWord --- plus the dictionary file is single word lines and the user file is multi-word lines.

// updated is_present function

template <class RecordType>
    bool table<RecordType>::is_present(int check_word_key) const
    {
        std::size_t i = hash(check_word_key);  // If key exists, it will be somewhere in data[i]

        std::cout << "BEFORE Iterator declaration" << std::endl;
        typename std::vector<RecordType>::const_iterator it;
        std::cout << "AFTER Iterator declaration" << std::endl;
        std::cout << "About to access the vector in array index: " << i << std::endl;

        std::cout << "spell check word key is: " << check_word_key << std::endl;
        for (int j=0; j<data[i].size(); ++j) {
           std::cout << "Key in vector is: " << data[i].at(j).key << std::endl;
           std::cout << "Data in vector is: " << data[i].at(j).data << std::endl;
           if (data[i].at(j).key == check_word_key)
                return true;
        }
        //for (it = data[i].begin(); it != data[i].end(); ++i)
        //{
        //   std::cout << "iteration through FOR loop" << std::endl;
        //   if (data[i].at(it->key) == check_word_key)
        //      return true;
        //}
        return false;
    }

// OUTPUT from run with a .txt file containing the words "hello" and "goodbye" on a single line.

Hash table successfully created
Total Records equals 25021
Please specify the filename to spell check: doc.txt
Got a word
temp_record key = : 485583
temp_record data = : hello
temp_record was successfully created
BEFORE Iterator declaration
AFTER Iterator declaration
About to access the vector in array index: 914
spell check word key is: 485583
Key in vector is: 460869
Data in vector is: also
Key in vector is: 235716181
Data in vector is: amatory
Key in vector is: 1877549581
Data in vector is: backlash
Key in vector is: 29524533
Data in vector is: berate
Key in vector is: 45817924
Data in vector is: chamberlain
Key in vector is: 1927757445
Data in vector is: coronado
Key in vector is: 240977517
Data in vector is: correct
Key in vector is: 1825526611
Data in vector is: deceitful
Key in vector is: 1945837109
Data in vector is: downside
Key in vector is: 1964114485
Data in vector is: filtrate
Key in vector is: 31084261
Data in vector is: fungus
Key in vector is: 32017901
Data in vector is: lariat
Key in vector is: 27488374
Data in vector is: longtime
Key in vector is: 526773
Data in vector is: pure
Key in vector is: 900465115
Data in vector is: quarterback
Key in vector is: 4272317
Data in vector is: ruben
Key in vector is: 47937836
Data in vector is: sowbelly
Key in vector is: 559725
Data in vector is: zest
hello IS NOT SPELLED CORRECTLY.

checked a word
Got a word
temp_record key = : 31151277
temp_record data = : goodbye
temp_record was successfully created
BEFORE Iterator declaration
AFTER Iterator declaration
About to access the vector in array index: 653
spell check word key is: 31151277
Key in vector is: 1911919629
Data in vector is: bowditch
Key in vector is: 1501480501
Data in vector is: disquietude
Key in vector is: 245086645
Data in vector is: epicure
Key in vector is: 3845053
Data in vector is: erwin
Key in vector is: 3845053
Data in vector is: ethan
Key in vector is: 30426333
Data in vector is: falter
Key in vector is: 1458299651
Data in vector is: fireproof
Key in vector is: 1003246261
Data in vector is: gadolinium
Key in vector is: 483949
Data in vector is: gist
Key in vector is: 483949
Data in vector is: hast
Key in vector is: 1201109291
Data in vector is: hillbilly
Key in vector is: 4009813
Data in vector is: leafy
Key in vector is: 39846486
Data in vector is: luminary
Key in vector is: 1863688885
Data in vector is: progressive
Key in vector is: 1863688885
Data in vector is: retrogressive
Key in vector is: 527885
Data in vector is: rich
Key in vector is: 4240477
Data in vector is: scrub
Key in vector is: 34018101
Data in vector is: sharpe
Key in vector is: 48729796
Data in vector is: sorption
Key in vector is: 4317365
Data in vector is: swine
Key in vector is: 1043532827
Data in vector is: thrombosis
Key in vector is: 35105517
Data in vector is: widget
goodbye IS NOT SPELLED CORRECTLY.

checked a word

Edited 5 Years Ago by lasl0w: n/a

Just fixed the final peice by replacing getline with getWord! Thanks for all the help with working through the errors!

ISSUE SOLVED.

Edited 5 Years Ago by lasl0w: n/a

This question has already been answered. Start a new discussion instead.