linked list versus array

This is a discussion on linked list versus array within the C++ Programming forums, part of the General Programming Boards category; Well, there is really no need to inherit from the binary_function class; I do that for consistency (as a sort ...

  1. #16
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Well, there is really no need to inherit from the binary_function class; I do that for consistency (as a sort of "promise" to keep the correct interface).

    It certainly is nice to be able to see exactly what is going on, however, I think that making good use of STL is a definite advantage, as it is often faster, and usually much safer than hand made code. I'll grant you that in this particular case, however, it is not hard to make safe code.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  2. #17
    Registered User
    Join Date
    Aug 2005
    Posts
    128
    Thanks for all the great info - to everyone. I'm testing out different find options and making sure I understand as much as possible.

  3. #18
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    I'm testing out different find options and making sure I understand as much as possible.
    Excellent decision.

    If you have access to a library with it (or feel like picking it up for that matter), I recommend looking into Introduction to Algorithms by Cormen, Leiserson and Rivest. A really good book with lots of info about different algorithms and data structures.

    Cheers
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  4. #19
    Registered User
    Join Date
    Aug 2005
    Posts
    128
    Here's the whole thing using two different find options. find_if and the custom find function. if anyone wants, they can create large txt files and add timer logic to see which is faster. My understanding is they should be about the same.

    vector.cpp
    Code:
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <functional> // binary_function
    
    #include <fstream>
    #include <string>
    
    // common.h stores trim function and and other common functions.
    #include "common.h"
    
    //struct record stores values for struct-based vector.
    //adding new columns would require changes to struct
    //and initialize vector, assuming finds would be created
    //for other distinct queries into the vector.
    struct record
    {
       std::string domain_name;
       std::string site_value;
    };
    
    //associated with find_site_type
    struct rec_ptr_eq_string : public std::binary_function<record*, std::string, bool>
    {
       bool operator()(record* lhs, std::string rhs) const
       {
          return lhs->domain_name == rhs;
       }
    };
    
    //exception struct
    struct read_exception { };
    
    //create instance of vector which points to record struct.
    std::vector<record*> sitevector;
    
    //class for storing record struct data and 
    //running appropriate queries.
    class csSite_Vector
    {
    private:
    
    public:
    
    	//fn to get sitetype from record struct.
    	//note pointer to domain_name loop.
    	std::string get_site_type(std::vector<record*>& vec, std::string domainname_to_find)
    	{
    		std::vector<record*>::iterator start = vec.begin();
    		std::vector<record*>::iterator stop = vec.end();
    		std::string returnst;
    
    		for( ; start != stop; ++start)
    		{
    		 if((*start)->domain_name == domainname_to_find)
    			{
    			 return  (*start)->site_value;
    			exit(0);
    			}
    		 else
    		   returnst = "0";
    		}
    		return returnst;
    		
    	}
    
    	//fn to get sitetype from record struct.
    	//note uses find_if.
    	std::string find_site_type(std::vector<record*>& vec, std::string domainname_to_find)
    	{
    		std::vector<record*>::iterator result =
    		std::find_if(vec.begin(), vec.end(), 
                       std::bind2nd(rec_ptr_eq_string(), domainname_to_find));
    		if(result == vec.end())
    			return 0;
    		else
    			return (*result)->site_value;
    
    	}
    
    
    	//assign values to vector
    	void initialize_vector(std::vector<record*>& vec)
    	{
    		//assign tmp as pointer to record struct
    		record* tmp;
    		std::ifstream fin;
    		fin.open ("test.txt", std::ios::in);    
    		if(fin.fail())
    			{
    			throw read_exception();
    			}
    		char detailline[50];
    		std::string sdetailline;
    		while(!fin.fail() && !fin.eof())
    			{
    			fin.getline(detailline, 50, '\n');
    			sdetailline = detailline;
    			//assign tmp as new pointer to record struct
    			tmp = new record;
    			tmp->domain_name = trim(sdetailline.substr(10,40));
    			tmp->site_value = trim(sdetailline.substr(0,10));
    			//assign record struct pointer to vector.
    			vec.push_back(tmp);
    			}
    		fin.close();
    	}
    
    	void cleanup_vector(std::vector<record*>& vec)
    	{
    	   // Delete all of the pointers...
    	   std::vector<record*>::iterator it = vec.begin();
    	   for(; it != vec.end(); ++it)
    	   {
    		  delete *it;
    		  *it = 0;
    	   }
    	}
    
    
    };
    
    
    int main()
    {
    	//define sitetype to hold return value
    	std::string sitetype1;
    	std::string sitetype2;
    	//define SV as an instance of class csSiteVector
    	csSite_Vector SV;
    	//initialize SV with instance of vector sitevector
    	//which points to the record struct.
    	SV.initialize_vector(sitevector);
    	//retrieve value of sitetype where domainname = x
    	sitetype1 = SV.get_site_type(sitevector, "cprogramming.com");
    	sitetype2 = SV.find_site_type(sitevector, "cprogramming.com");
    
    
    
    
    
    
    	//remove vector.  (if 'get_site_type to be called repeatedly, 
    	//place initialize and cleanup higher up
    	//in the program logic so only called on program start and end)
    	SV.cleanup_vector(sitevector);
    	//display returned value for sake of viewing in a dos prompt.
    	std::cout<<sitetype1<< std::endl;
    	std::cout<<sitetype2<< std::endl;
    	std::cin;
    
    	return 0;
    }
    common.h
    Code:
    std::string trim(std::string const& source, char const* delims = " \t\r\n") {
    	std::string result(source);
    	std::string::size_type index = result.find_last_not_of(delims);
    	if(index != std::string::npos)
    		result.erase(++index);
    
    	index = result.find_first_not_of(delims);
    	if(index != std::string::npos)
    		result.erase(0, index);
    	else
    		result.erase();
    	return result;
    }

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Passing an array to linked list
    By bar338 in forum C Programming
    Replies: 7
    Last Post: 04-08-2009, 10:15 PM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 11:10 AM
  3. Linked list versus malloc and realloc.
    By Bajanine in forum C Programming
    Replies: 2
    Last Post: 06-20-2005, 09:08 PM
  4. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  5. Replies: 5
    Last Post: 11-20-2001, 12:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21