Stack Overflow

Ok I'm not getting the stack overflow problem anymore. Is there a way to change the thread title?
I am having another problem - this is very slow:

main.cpp

Code:

---

#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include "HashTable.h"

using namespace std;

bool isContained(HashTable *table, string the_string);       
bool contCapital(string the_string);       
bool goodLength(string the_string);
string format(string the_string);
bool isFormatted(string the_string);

int main(){
        list<string> filenames;
        HashTable *table = new HashTable();
        filenames.insert(filenames.end(), "american-words.10");
        filenames.insert(filenames.end(), "american-words.20");
        filenames.insert(filenames.end(), "american-words.35");
        filenames.insert(filenames.end(), "american-words.40");
        filenames.insert(filenames.end(), "american-words.50");
        filenames.insert(filenames.end(), "american-words.55");
        filenames.insert(filenames.end(), "american-words.60");
        filenames.insert(filenames.end(), "american-words.70");
        filenames.insert(filenames.end(), "american-words.80");
        filenames.insert(filenames.end(), "american-words.95");
        ifstream* inFiles = new ifstream[filenames.size()];
        int i=0;
        for(list<string>::iterator itr = filenames.begin(); itr != filenames.end(); itr++){       
                inFiles[i].open(itr->c_str());       
                i++;
        }
        string temp;
        for(int i=0;i<filenames.size();i++){
                if(inFiles[i]){
                        cout << "Working on file " << i << endl;       
                        while(inFiles[i] >> temp){
                                if(!isContained(table, format(temp))&&!contCapital(temp)&&goodLength(temp)){
                                        table->addWord(format(temp));
                                        cout << format(temp) << endl;
                                }
                        }
                }
                else cout << "Could not open file " << i << endl;       
                inFiles[i].close();
        }
        delete inFiles;       
        ofstream outFile("outFile.txt");
        for(int i=0;i<TABLESIZE;i++)
                if(!table->table[i].empty())
                        for(list<string>::iterator itr = table->table[i].begin(); itr!= table->table[i].end(); itr++)
                                outFile << *itr << endl;               
        return 0;
}

bool isContained(HashTable *table, string the_string){
        for(int i=0;i<TABLESIZE;i++)
                for(list<string>::iterator itr = table->table[i].begin(); itr != table->table[i].end(); itr++)       
                        if(itr->compare(the_string) == 0)       
                                return true;       
        return false;       
}

bool contCapital(string the_string){
        for(int i=0;i<the_string.size();i++)       
                if(the_string.at(i)>='A'&&the_string.at(i)<='Z')       
                        return true;       
        return false;       
}

bool goodLength(string the_string){
        return the_string.size()>=3&&the_string.size()<=10;
}

string format(string the_string){
        while(!isFormatted(the_string))
                for(int i=0;i<the_string.size();i++)
                        if(the_string.at(i)=='\'')
                                the_string.erase(i,1);
                        else if(the_string.at(i)=='q'&&i+1<the_string.size()&&the_string.at(i+1)=='u'){
                                the_string.erase(i,2);
                                the_string.insert(i, "1");
                        }
        return the_string;
}

bool isFormatted(string the_string){
        for(int i=0;i<the_string.size();i++)
                if(the_string.at(i)=='\'')
                        return false;
                else if(the_string.at(i)=='q')
                        if(i+1<the_string.size()&&the_string.at(i+1)=='u')
                                return false;
        return true;
}

---

HashTable.h

Code:

---

#ifndef HASHTABLE_H
#define HASHTABLE_H

#define TABLESIZE 1000000

#include <list>
#include <string>

using namespace std;

class HashTable{
private:
public:
        HashTable();
        ~HashTable();
        list<string> table[TABLESIZE];
        void addWord(string word);
        int getIndex(string word);
};

#endif

---

HashTable.cpp

Code:

---

#include "HashTable.h"
#include <string>
#include <list>
#include <cmath>

using namespace std;

HashTable::HashTable(){
}

HashTable::~HashTable(){
}

void HashTable::addWord(string word){
        int index = getIndex(word);
        table[index].insert(table[index].begin(), word);
}

int HashTable::getIndex(string word){
        //this causes negative values for some reason
        /*int sum=0;
        for(int i=0;i<(int)word.length();i++)
                sum+=(word.at(i)!='1'?(int(word.at(i)-'a')):27)*pow(27,(double)word.length()-i);
        return sum&#37;TABLESIZE;*/
        //so I replaced it with this
        return (word.at(0)*word.at(1)*word.at(2))%TABLESIZE;
}

---

I figured out that the large TABLESIZE was the problem, so I changed it to a much lower value. But I would still like to keep the load factor low to prevent collisions, so what do you suggest for a table size? I want to get as many words as possible.

No means to test it, but it is quite possible that your HashTable is trying to use too large a stack array. You may test if a smaller TABLESIZE works.

Solution: use a std::vector of std::list<std::string> instead.

It is working much better now, with TABLESIZE set to 100 or 1000. Thanks.

The error message means that somewhere (one of the places where you use the at method probably) you are accessing a container element that is beyond the container bounds. An incorrect index value.

Code:

---

  //filenames.insert(filenames.end(), "american-words.10");
  filenames.push_back("american-words.10");

---

This might be easier, but your version might work as well.

Code:

---

        //this causes negative values for some reason
        /*int sum=0;
        for(int i=0;i<(int)word.length();i++)
                sum+=(word.at(i)!='1'?(int(word.at(i)-'a')):27)*pow(27,(double)word.length()-i);
        return sum%TABLESIZE;*/

---

You get negative values because when the value becomes larger than the int type can hold, it will wrap around to negative values. You may not be able (or need) to prevent the wrap-around, but if you want to make sure no negative values emerge, you can use unsigned int (where numbers start from 0 if the wrap-around happens).

Quote:

---

Ok I'm not getting the stack overflow problem anymore. Is there a way to change the thread title?

---

You could have started a new thread. If you modify your posts, someone else reading the thread will have a hard time figuring out what people are talking about.

Quote:

---

I am having another problem - this is very slow

---

Define "very slow" :). And have you tried to find out which part of it is very slow (using profiler)?

Anyway, looking at the isContained function I see that to find a string in the table you loop through the whole table!? If you are going to do that what's the point of having a hash table in the first place?

I would expect that the getIndex method of HashTable could provide an answer to the question whether the string is contained in the table or not by returning some known value (e.g -1) if it is not found.

For this matter you should consider some data hiding (private keyword). The actual table should be only visible to the HashTable class as this is an implementation detail. Right now it looks that your HashTable class doesn't provide almost no functionality and everybody who wants to use it has to deal with the internals of the class directly.

----
And another quick optimization. If you deal with objects that are expensive to copy (like std::string), you'll pass a reference to functions. If the function shouldn't modify the argument, you'd pass it as a const reference.

In the same spirit the format function could be optimized by "returning" the result as a parameter reference.

Code:

---

void format(string& the_string);

---

No copies of the string are made and the function works on the original string that you pass into it.