Thread: How do you search a list container....

  1. #1
    Registered User
    Join Date
    Jun 2005
    Posts
    131

    How do you search a list container....

    I have a program that is a crude CD database. It first asks the user to enter a CD name in which it stores into a list, then at the users on accord they can enter an artist name into another list that is a list of the CD name. So its a list of a list. I think I have it working correct but I am always open for opinions on improvment. Anyways what I am working on at the moment is giving the user the option to search out a CD from the list and display back that CD name and artist. Hear is what I have so far..

    This is in a Class called Controller
    Code:
    //Adds Artist Name
    void Controller::AddArtBandName() { 
    	string artName; 
    
    		cout << endl << "Enter the bands name: " << flush; 
    		cin >> artName; 
    	
    		myArtist.push_back( (artName));	
    		
    		cout << "\tAdded : " << artName << endl << endl ;	
    } 
    
    //Displays Artist List 
    void Controller::DisplayArtistList(){
    		cout << endl << "List of Artist: " << endl;
    
    	list<Artist>::iterator iter;
    
    		for(iter = myArtist.begin(); iter != myArtist.end(); iter++)
    		{
    		cout << (*iter).getArtBandName()<<endl;
    		(*iter).DisplayCdList();
    		}
    }
    void Controller::FindCd(){
    	string search;
    
    		cout <<" Enter name of CD you want to find " << endl;
    		cout <<"             WARNING               " << endl;
    		cout <<"   THIS SEARCH IS CASE SENSITIVE   " << endl;
    		cin >> search;
    
    }
    this is in a class called Artist
    Code:
    //Adds Cd Name
    void Artist::AddCdName(){
    	string cdName; 
    
    		cout << "Enter Cd's Name:" << flush; 
    		cin >> cdName; 
    
    		myCdInfo.push_back(CdInfo(cdName));	
    
    		cout << "\tAdded : " << cdName << endl << endl;		
    	OptionArtistInfo();
    }
    
    //Display Cd List
    void Artist::DisplayCdList(){
    		cout << endl << "Cd List:" << endl;
      
    	list<CdInfo>::iterator iter;
    
    		for(iter = myCdInfo.begin(); iter != myCdInfo.end(); iter++)
    			
    			cout << (*iter).getCdName() << endl;		
    }
    
    void Artist::OptionArtistInfo(){
    	 int input;
    
    			cout << "Would you like to add Artist info for the cd : " << endl; 
    			cout << "\tType 1 for yes or 2 for no : " << flush;
    			cin >> input;
    		
    			switch (input)
    			{
    			case 1:
    					cout << endl << "Enter the bands name: " << flush; 
    					cin >> artName; 
    				break;
    			case 2:
    				cout << "Returning to main menu" << endl;
    				break;
    			default:
    				cout << input << " : Is not a valid command" << endl;
    				cout << " 1 and 2 are valid commands " << endl;
    			}
    }
    The FindCd function in the Controller class is were I am trying to search through the Cd list and find a Cd based on the users input. For now I just want it to display back that Cd and the Artist Name associated with it. To be honest I have no clue how to go about this. I am guessing a for if loop of some sorts. Can anyone help put me on the correct path.....

    Thanks

    Chad
    Last edited by chadsxe; 07-14-2005 at 10:35 AM. Reason: Updated code.....

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    The way you have it set up you won't get a very efficient search because it appears that you don't have access to CD information from the Controller except through the artists. That is ok for small amounts of input, though.

    To search in your current setup you should add a function called FindCd in the artist class that takes a CD name as a string and returns true if it finds the Cd for that artist. This would be an easy function to implement - just a for loop like in DisplayCdList() and a comparison of each Cd name with the passed in string. Then add a loop in the Controller::FindCd function that loops through Artist instances in the list just like you do in DisplayArtistList(). For each artist call the new Artist::FindCd function and pass the string that the user input. If the Artist FindCd function returns true, then you've found the Cd.

    BTW, AddArtBandName and AddCdName both have two memory leaks. There is no reason for you to be using new to allocate memory. Just create an object on the stack and a copy will be placed on to the list:
    Code:
    cin >> cdName;
    myCdInfo.push_back(CdInfo(cdName));

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    131
    I went ahead and updated the code with the suggested fix for the memory leak. For my own know how, what is a memory leak?

    As far as your suggestion that my search won't be very efficent let me see if I understand you. Are you saying that I should attempt to move my DisplayCdList function from the Artist class to the Controller class. Why does it make a diffrence in the efficency of my search.

    Another thing that I am trying to figure. When I run the program and enter two diffrent CD names with there own indvidual artist and then display the list back I get this

    List of Artist:
    FirstArt

    Cd List:
    FirstCD
    SecondArt

    Cd List:
    SecondCd

    The more I add to the list the more it dispalys back weird. Any suggestion as to why?

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    When you allocate memory with new, you get dynamic memory that you must clean up later with a call to delete. C++ has no garbage collection, it allows you to control dynamic memory cleanup on your own. If you don't call delete to free the memory, then the memory is still allocated for your program but never used again. If you keep doing this, your program will keep requesting more and more memory and hog system resources. It is often better to just use stack based memory that is automatically cleaned up, which is what my suggested code does.

    For the efficiency part, it is more of an overall design decision. Searching by going through the list linearly is not very efficient. It is usually better to keep a sorted list, or use a map of some sort. I might have a map of Artists in the Controller and a map of CdNames to the Artist that contains them. This way, to look up a Cd, you just check the CdName map (much more efficient on larger data sets, although other options are even better). That will give you the Artist as well. To look up the Artist, you would use the Artist name map.

    Making this change would be a big deal, and there are a lot of other considerations beyond those that I've mentioned. For example, you would have to start using pointers with the setup I just mentioned to avoid having multiple separate copies of an Artist in your data, and that would mean dynamic memory using new and delete, which would make things harder. Your current setup is fine for small amounts of data.

    As for your output, it is doing exactly what the code says it should do. Step through your output code and write down on paper how it will show up. You'll find that it looks just as you typed it here. Hopefully that will show you where to put more newlines in the output.

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    131
    Quote Originally Posted by Daved
    or use a map of some sort. I might have a map of Artists in the Controller and a map of CdNames to the Artist that contains them. This way, to look up a Cd, you just check the CdName map (much more efficient on larger data sets, although other options are even better). That will give you the Artist as well. To look up the Artist, you would use the Artist name map.
    Can you further you explanation of map. If I am understanding this correctly you would esentially have two copys of your list. The first copy would be the list itself but the second would be the "map" (Which is what?). If this was the case woulden't you be waisting memory due to the list being twice as big, or is this were the pointers would come into play.

    Also the way I had it before (new), would it still be considered a memory leak if I did use some type of memory cleanup.

    I am more into figuring out how to do things the corret way, not the easy.

    Thanks

    Chad

  6. #6
    Registered User
    Join Date
    Jun 2005
    Posts
    131
    I am trying to figure out the for loop.....

    This is what I have
    Code:
    void Artist::FindCd()
    {
    	string search;
    
    	cin >> search;
    
    	list<CdInfo>::iterator iter ;
    
    		for(iter = myCdInfo.begin(); iter != search; iter++)
    				
    }
    This is what I am getting

    error C2679: binary '!=' : no operator found which takes a right-hand operand of type 'std::string' (or there is no acceptable conversion)

    I am also trying to figure out how I would display this information back. How would I display both the CD and Artist that the user is looking for from this one function?

    I will keep working on it in the mean time

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    If you use new, you have to remember the pointer location of the allocated memory so you can delete it later. In your original code (which you have edited so I might not remember exactly), when you call push_back you dereference the pointer returned from new. This means that a copy of the object is placed into the container, and the pointer location returned by new is never saved. Because of that, you would never be able to clean up that memory.

    To use new, you would want to have the list hold pointers instead of objects (e.g. list<CdInfo*>). Then to clean up when you are done, you would go through the list and delete the pointers.

    As for the map, map and set (and multimap and multiset) are standard containers like list and vector. A set just holds items, but it keeps them sorted so you can find them more quickly. A map is like a set, except it holds a key and a value. The key is sorted and the value is paired with the key. So for example, you could have a map with Artist name as a string key and the pointer to the Artist object as the value. Then looking up the artist by name is faster because the names are sorted already.

    You are correct that this does duplicate some data, but you would be using pointers anyway, which are small enough that it is often worth the extra memory for the increased speed, especially if you will be holding thousands of CDs and artists or you want to program as if you might be.

    So read up on maps and try a few test programs to get used to them. There are even better ways to implement this stuff, IMO, than what I'm suggesting, but each new idea is more and more advanced, and probably too advanced to just jump right into. That doesn't mean the easier way is less correct, it just means that it is more appropriate for your current knowledge.

    If you really want to know how I would implement this off the top of my head, I'd probably hold boost::shared_ptr's of Artists and CDs in an unordered_set in the Controller using the names as keys to the sorting criterion. Then each Artist would have a list or set of shared_ptr's to it's CDs, and each CD would have a shared_ptr back to its Artist. I am not necessarily an advanced programmer either so I'm sure others could do better. If I were you I wouldn't worry about it though, just do what you can with the tools you know and pick up a few things along the way.


    As for the for loop, the loop itself should look exactly like DisplayCdList() because in both cases you are looping through all the Cds. The inside of the for loop should be different. You should probably just have a simple if statement that returns true if the strings are equal (you want your function to return success or failure).

    I would make the Artist's FindCd function take a string as an argument, because you will be calling it from the Controller's FindCd function and you don't want it to ask the user for the Cd name each time. Inside the Controller's FindCd function is where you should output the Artist's name if it returned true and the cd name entered by the user.
    Last edited by Daved; 07-14-2005 at 12:58 PM.

  8. #8
    Registered User
    Join Date
    Jun 2005
    Posts
    131
    Quote Originally Posted by Daved

    As for your output, it is doing exactly what the code says it should do. Step through your output code and write down on paper how it will show up. You'll find that it looks just as you typed it here. Hopefully that will show you where to put more newlines in the output.
    You know as as sad as it is, I spent a good part of last night trying to follow my code but I still am failing to see why it is ouputting the way it is. It makes sense for the first CD and Artist I enter but after that I am lost. Why I am getting

    List of Artist:
    FirstArt

    Cd List:
    FirstCD
    SecondArt

    Cd List:
    SecondCd


    By the way, thank you so much for taking time to help me figure some of this stuff out. I can only hope it all becomes easier with time. Like I said I have only been doing this for about 6 months and am 90% self taught.

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    In pseudo code, your output looks like this (remember that endl inserts a new line):

    DisplayArtistList():
    - newline, "List of Artist: ", newline
    - for each artist:
    --- BandName, newline
    --- DisplayCdList:
    ----- newline, "Cd List:", newline
    ----- for each Cd:
    ------- CdName, newline

    So if you lay that out with the newlines, you get (with line numbers added by me):

    01. <newline>
    02. List of Artist:<newline>
    03. BandName<newline>
    04. <newline>
    05. Cd List:<newline>
    06. CdName1<newline>
    07. CdName2<newline>
    08. CdName3<newline>
    09. BandName<newline>
    10. <newline>
    11. Cd List:<newline>
    12. CdName4<newline>
    13. CdName5<newline>

    The key is the transition between the end of DisplayCdList and the next iteration of the loop inside DisplayArtistList.

  10. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    131
    AHhhhahah.....I did not even take the endl; into consideration. I will go back and follow that through to see if I can make things output better. By the way putting things down on a paper as you follow the code through is something that is so simple but helps so much. Thanks for that tip.

    Anyways back to my for if loop.....

    Code:
    void Artist::FindCd()
    {
    	string find;
    
    	cin >> find;
    
    	list<CdInfo>::iterator iter ;
    
    		for(iter = myCdInfo.begin(); iter != myCdInfo.end; iter++)
    		{
    			if(iter == find)
    			{
    				cout << (*iter).getCdName << endl;
    			}
    		}		
    			
    }
    This is what I have coded out as of now. The first error I am getting is

    error C2475: 'CdInfo::getCdName' : forming a pointer-to-member requires explicit use of the address-of operator ('&') and a qualified name

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    You are missing () on the calls to the getCdName() function and the end() function. You also need to dereference you iterator in the if statement (if (*iter == find)).

  12. #12
    Registered User
    Join Date
    Jun 2005
    Posts
    131
    Opps I missed more then one (). I have to slow down a little.

    Code:
    void Artist::FindCd()
    {
    	string find;
    
    	cin >> find;
    
    	list<CdInfo>::iterator iter ;
    
    		for(iter = myCdInfo.begin(); iter != myCdInfo.end(); iter++)
    		{
    			if(*iter == find)
    			{
    				cout << (*iter).getCdName() << endl;
    			}
    		}		
    			
    }
    Now I am getting

    error C2676: binary '==' : 'std::allocator<_Ty>::value_type' does not define this operator or a conversion to a type acceptable to the predefined operator
    with
    [
    _Ty=CdInfo
    ]

    I thought the (*iter).getCdName() << endl; in the body of the if loop derefrenced iter. Do i have to have *iter in both the body and statment of the loop?

  13. #13
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Ok, that was my fault. You want to compare the cdname to the string input by the user, so your if statement should use the cdname function:
    Code:
    if ((*iter).getCdName() == find)
    You have to dereference iter only when you want to use the value that it holds (in this case the Cd object). So when you want the name, you dereference the iterator and call getCdName. When you are using the iterator as an iterator (like in your for loop), then you don't need to dereference it.

  14. #14
    Registered User
    Join Date
    Jun 2005
    Posts
    131
    So if that is suppose to be in the if statement, what goes in the body to display it back?

    Code:
    cout << iter.getCdName() << endl;
    ?

  15. #15
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Use the same format to call getCdName. Both should be (*iter).getCdName(). In both cases you are getting the CdName from the CdInfo object referred to by the iterator. Inside the if, you are comparing that string with the string input by the user. Inside the body of the if, you are displaying it. Either way you are doing the same thing, retrieving a string that holds the Cd name.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  2. deleting a node in linked list
    By BoneXXX in forum C Programming
    Replies: 18
    Last Post: 12-17-2007, 12:30 PM
  3. Recursion Revisited again, and again!
    By clegs in forum C++ Programming
    Replies: 93
    Last Post: 12-08-2007, 08:02 PM
  4. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM