iterator based search algorithm help

[Clinton Portis]

I am writing a simple program.. enter first and last name and a search is performed.. and their phone number (if found) is returned.

I have used vector class iterators before a couple of times.. but devcpp does not seem to like this code.. and stops compilation somewhere inside of the algorithm find() function.

void Database::search()
{
   do{         
          iter = find(iter++, vInfo.end(), target_firstname);
         //iter = vInfo.at();
         
   }while(iter->last_name != target_lastname && iter != vInfo.end());
   
   if(iter != vInfo.end())
   
      is_found = true;
}

The function searches through a vector of "info"'s in an attempt to match the first name. If successful, the last name is checked. If the the last name does not match, the search continues.. else 'iter' will point to the vector element containing the matching first and last target name.

The entire code has been uploaded for your viewing pleasure. Any help is appreciated in advance.

[Inanna]

I'm gonna say iter isn't valid. Don't worry, I'll explain my thought process. But bear with me because it's twisted. :D You initialize iter in the Database constructor.

Database::Database()
{
   is_found = false;
   infile.clear();
   vInfo.clear();
   iter = vInfo.begin();
}

Technically you don't need to clear vInfo because it's freshly created, but that doesn't really matter. The problem is that you initialize iter to vInfo.begin() here, before inserting any data. Then you go to call load_file. Skipping the boring stuff, the problem's here.

vInfo.push_back(temp);

vInfo.push_back(temp) is like calling vInfo.insert(vInfo.end(), temp) , and if a call to insert for a sequence container reallocates memory, all iterators are invalidated. Since vInfo was both empty and freshly constructed with no resize or reserve, push_back invalidates iter. Then you try to use an invalid iterator in find.

iter = find(iter++, vInfo.end(), target_firstname);

If you move the iter = vInfo.begin() to the top of your search method, I'm guessing it'll work. Or at least crash differently. :)

[GloriousEremite]

If you're going to use std::find like that, you need to define an equality operator for your info class:

class Info
{
public:
  bool operator==(const std::string& first_name);
//...
}

However, you may want to use std::find_if instead. find_if allows you to specify an unary predicate as the matching criteria, so you could do something like (assuming my logic here is correct, since this is untested):

struct FirstNameMatch
{
FirstNameMatch(std::string name):name_(name){}
bool operator()(const Info& inf)
{
return inf.first_name==name_;
}
private:
std::string name_;
}
//...
find_if(vInfo.begin(),vInfo.end(),FirstNameMatch(target_firstname));

I believe GloriousEremite is correct.

This compiles and works but I didn't get round to overloading the ==operator as suggested by GloriousEremite.

#include <iostream>      //For DOS console operations i.e.  cin cout
#include <fstream>       //File I/O
#include <string>        //For String class objects
#include <vector>        //Efficient resizable array 
#include <algorithm>     //For find() function 
#include <cctype>        //For toupper() function

using namespace std;

class Info
{
public:
        string first_name,
          last_name,
          phone_no,
          search_first_name,
          search_last_name;
          void set(string,string,string);
          //bool operator==(Info);

};

void Info::set(string s, string t, string p)
{
     search_first_name=s;
     search_last_name=t;
     phone_no=p;
}
/*
bool Info::operator ==(Info c)
{
    
  if ((first_name==c.first_name)&&(last_name==c.last_name)) 
  {
  return true;
  }
 else
  return false;
}
*/

class Database
{
   public:
   
   Database();
   void load_file();
   void prompt();
   void search();
  
   bool again();
   
   private:
           
 
   string target_firstname,
          target_lastname;
   ifstream infile;
   vector<Info> vInfo;
   //vector<Info>::iterator iter;                          
};

int main()
{
   Database DB;
   
   DB.load_file();
   
   do{   
         DB.prompt();
         DB.search();
         
   }while(DB.again());
   
   return 0;
}


/////////////////////////////////
/////// Function Definitions ///
///////////////////////////////

Database::Database()
{
   
   infile.clear();
   vInfo.clear();
   
}

void Database::load_file()
{
   Info temp;
   
   infile.open("c:\\data.dat");
   
   if(infile.fail())
   {
      cout << "\n\n\t\aError!  File could not be opened."
           <<"\n\tProgram will now terminate."
           <<"\n\tPress [ENTER] to continue... ";
      exit(1);
   }
   
   while(!infile.eof())
   {   
      infile >> temp.first_name;
      infile >> temp.last_name;
      infile >> temp.phone_no;        
      vInfo.push_back(temp);
   }
}

void Database::prompt()
{
   cout << "\n\n\tEnter first name: ";
   cin >> target_firstname;
   cout << "\n\n\tEnter last name: ";
   cin >> target_lastname;
}

void Database::search()
{
  Info tmp;
  
  tmp.set(target_firstname,target_lastname,"000");
      
      for ( int i = 0; i <vInfo.size(); i++)
      {
          if ((vInfo[i].first_name == tmp.search_first_name)
             && (vInfo[i].last_name == tmp.search_last_name))
          {

             cout << "\n\n\tThe phone number for " << vInfo[i].first_name << " " 
           << vInfo[i].last_name << " is: "<<vInfo[i].phone_no;
             
          }
      }
}


bool Database::again()
{
   char ans;
   
   cout << "\n\n\tWould ye' like to try again?  (Y/N) ";
   cin >> ans;
   
   if(toupper(ans) == 'Y')
   
      return true;
      
   else 
   
      return false;
}

while(!infile.eof())

Is also bad!