Thread: Stack Overflow

  1. #1
    cout << "Bye World!";
    Join Date
    Jun 2006
    Posts
    40

    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.
    Last edited by ldb88; 07-24-2007 at 04:16 AM.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    cout << "Bye World!";
    Join Date
    Jun 2006
    Posts
    40
    It is working much better now, with TABLESIZE set to 100 or 1000. Thanks.
    Last edited by ldb88; 07-24-2007 at 04:20 AM.

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.

    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.
    Last edited by anon; 07-24-2007 at 09:14 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack overflow errors in 3 areas
    By ulillillia in forum C Programming
    Replies: 13
    Last Post: 04-29-2007, 03:20 PM
  2. stack and pointer problem
    By ramaadhitia in forum C Programming
    Replies: 2
    Last Post: 09-11-2006, 11:41 PM
  3. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 10:12 PM
  4. error trying to compile stack program
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2003, 06:27 PM
  5. Stack Program Here
    By Troll_King in forum C Programming
    Replies: 7
    Last Post: 10-15-2001, 05:36 PM