Thread: linked list versus array

Thanks for all the great info - to everyone. I'm testing out different find options and making sure I understand as much as possible.

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;
}