• ### Popular Now

• 13
• 18
• 19
• 27
• 9

#### Archived

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

# learning STL

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

## 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 on other sites
It is recommended not to use a vector of bools, but a std::bitset instead. I forget why exactly.

##### Share on other sites
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 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 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 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)