Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

RegaRIP

learning STL

This topic is 5937 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Currently learning the STL in my college C++ class. Having trouble determing wether I can get from ''starting'' to ''target''...The two main problems I am having is putting all the places one word goes to into the stack (trying to push() vector[0][0] through vector[0][end]). I also get a core dump when I try setting bool vector[0] to true. any help in simple form is greatly appreciated
  
//***********************************************************************

//   Author:   Mark Bates

//   File:     map.cpp

//   Date:     9-12-02

//   Purpose:  Reads in a file supplied by the user of 5 letter words, 

//             if the words are 1 letter off the two words connect.  

//             The words are placed in a ''words'' vector and a ''graph'' 

//             is created, the index of the word is used in the graph.

//             If the words connect, the graph should contain the index

//             of the word in it''s position on the graph.  The user is

//             asked for 2 words, the program then tells if the 2nd word

//             can be reached from the first word. 

//

//***********************************************************************

 

#include <iostream.h>
#include <stdlib.h>
#include <vector>
#include <fstream.h>
#include <string>
#include <list>
#include <algorithm>
#include <stack>

//********************************************************************

//   Compare funtion to determine if words are one character off

//********************************************************************

bool comp(string a, string b)
{
    int notmatch = 0;

    for( int i = 0; i < 5; i++)
    {
        if( a[i] != b[i] )
           notmatch++;
    }

    if( notmatch > 1 )
        return false;
    else
        return true;
}    

//********************************************************************

//   Requires a file name paramter containing 5 letter words

//********************************************************************            

int main(int argc, char* argv[])
{
     if(argc != 2)
     {
          cerr << "Incorrect number of parameters passed" << endl;
          return EXIT_FAILURE;
     }

     ifstream inf( argv[1] );
     
     if( !inf )
     {
          cerr << "File " << argv[1] << " could not be opened" << endl;
          return EXIT_FAILURE;
     }

    
    
     vector<string> words;
     vector<vector<int> > graph;
     string str;
     
     int index = 0;

    while( inf >> str )
    {
          words.push_back(str);
          graph.push_back();
          
          for( int i = index -1; i >= 0; i-- )
          {
               if( comp(words[index], words[i]) )
               {
                    graph[i].push_back(index);
                    graph[index].push_back(i);
               }
          }
          index++;
    }     
    
     inf.close();
  
     ostream_iterator<string>  ot(cout, "\n" );
     copy(words.begin(), words.end(), ot);

     cout << graph[0][0] << endl; 
     cout << graph[1][0] << graph[1][1] << graph[1][2] << graph[1][3] << endl; 
     cout << graph[2][0] << graph[2][1] << graph[2][2] << endl; 
     cout << graph[3][0] << endl; 
     cout << graph[4][0] << graph[4][1] << endl; 
     cout << graph[5][0] << endl;  
    
     string from;
     string to;
     string starting;
     string target;
     
     int atposition = 0;

     cout << "From where? " << endl;
     cin >> from;
 
     cout << "To where? " << endl;
     cin >> to;

     for(int i = 0; i <= index; i++)
     {
          if(words[i] == from)
          {
               starting = from;
               target = to;
               atposition = i;
               break;
          }

          else if(words[i] == to)
          {
               starting = to;
               target = from;
               atposition = i;
               break;
          }
          
          cout << "Inside for loop" << endl;
     }

     if(starting == target)
     {
          cout << "You are already there!" << endl;
          return EXIT_FAILURE;
     }

//   My troubles start here!!!!

//   Help me!!!!



     vector<bool> visited;
     cout << "Vector visited made" << endl;

     stack<int> cango;
     cout << "stack cango made" << endl;
     
     cout << "Before while counter" << endl;

     int counter = graph[atposition].size();
     while(counter > 0)
     {
          cango.push(graph[atposition][counter]);
          counter--;
     }  
     
     cout << "After while counter" << endl;


     visited[atposition] = true;
     
     cout << "atposition made" << endl;

     while( !cango.empty() )
     {
          cout << "Inside while cango ! empty" << endl;
          atposition = cango.top();
          cango.pop();
          visited[atposition] = true;
          
          if( target == words[atposition])
          {
               cout << "You can get there" << endl;
               return EXIT_SUCCESS;
          }

          while( visited[atposition] && !cango.empty() )
          {
               atposition = cango.top();
               cango.pop();
               visited[atposition] = true;
          }    
     }          


     cout << "You can not go from " << from << " to " << to << endl;









     
      system("PAUSE");
      return 0; 
}

  
I know the code after my "need help here" comment probaly isn''t correct...but the program doesn''t make it that far where I can iron out the bugs.

Share this post


Link to post
Share on other sites
Advertisement
You appear to be a victim of the infamous "off-by-one" bug:

int counter = graph[atposition].size();
while(counter > 0)
{
cango.push(graph[atposition][counter]);
counter--;
}

The largest index you can use is actually counter-1.

But in general, you are also using the vector class wrong. In the case of visited, you try to access an element of the vector, yet the vector is empty. The only way you can access an element of a vector is if was already created via push_front or push_back, or populated by some other means.

Unlike your C arrays, vectors can grow dynamically. However, this means that nothing exists when the vector is first creatd besides the container itself - in a C array, the memory is allocated statically all at once.

To populate your visited vector so you can use it, you can use the resize function like so:

visited.resize(index, false);


However the index variable doesn't exactly indicate that it's also the size of the words vector, so if you want to use words.size() instead of index, go right ahead

quote:
I forget why exactly.

I think this might possibly be why

[edited by - Zipster on September 12, 2002 12:08:52 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Oluseyi
It is recommended not to use a vector of bools, but a std::bitset instead. I forget why exactly.


vector is a specialization that is, in fact, not an STL compatible container. It''s was a first attempt at making a bit container that compressed 8 bool''s into a byte (as opposed to one bool per byte).

Share this post


Link to post
Share on other sites
quote:
Original post by RegaRIP
I also get a core dump when I try setting bool vector[0] to true.


0.o That''s impressive - what OS are you using? (Perhaps you meant seg-fault?)

Share this post


Link to post
Share on other sites
thanks Zipster, I forgot about that...even though I had to do it earlier in the program And to think I was even checking if they were false later, when they weren''t even there yet!






WinXP...using Cygwin
yes, it was a Seg-fault(core dump)

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!