linked list versus array

[FoodDude]

I have a text file that can contain a random number of entry lines. I'll use names to make it easy.
bobsmith
carlrigers
etc...

This file can grow to contain hundreds of lines. I don't see a thousand being reason.

My program checks an input against the list of lines. if value = listname do something else do something else.

I don't want to read that file in everytime so I was thinking place the list in an array. Then I read about linked lists.

What's the best method to use? The program would probably store the list/array globally as the look up can run every minute to every few seconds.

[Zach L.]

Depends on your exact requirements.

A list is very easy to insert things into (no massive reallocation). You can use insertion sort to order your elements, but you will need to use a linear search to see if a record exists.

An array occasionally requires massive reallocation (usually, you will allocate more space than you currently need, to avoid doing it again too soon. However, an array can be quickly sorted, and you can use binary search to look through it faster.

Since you are reading things in once, and then presumably, looking through them many times, I would recommend an array. Even better, I would recommend a std::vector, and use the reserve() function to reserve a "best guess" number of spaces ahead of time to help minimize reallocation while reading things in.

You might even consider using a balanced tree to store your records in.

However, if you use std::vector and std::list, along with STL algorithms, then you will be able to swap the container out fairly easily, and do performance comparisons for yourself.

Cheers

[Boomba]

Well a two dimensional array would be useful here if all your doing is checking against only hundreds of names

array[number of names in list][max num of characters in name]

A linked list is better when dealing with large amount of names, because they're nicer to use with faster searching algorithms like a binary tree...but since the data isnt that much i'd suggest a two dimensional array...if speed is an issue for you..then use a linked list...but I doubt that it will make that much of a difference with only hundres of names

[Zach L.]

Correction: Here is a brief summary of advantages and disadvantages (by no means comprehensive), and I really do recommend using STL.

Linked List
- Pro: Very easy to expand. Space is allocated for the new node, and it is inserted where it needs to go with only a constant number of temporaries (for sorting out "previous" and "next" pointers).
- Pro: Building off of the last one, if you have a lot of data, but no good guess as to how much, you do not have to allocate large blocks of memory and then move everything every time you expand beyond the current bounds.
- Pro: If you have a lot of records or very little memory, and don't think you'll have large enough contiguous blocks, then an array cannot be used, so a linked list would be advantageous.
- Con: Limited to linear search, and hence, this is a slow operation.

Array / Vector
- Pro: Random access of elements allows for operations such as binary search, and hence, searching is much quicker than with a linked list.
- Pro: If you have enough memory, and know about how many elements you'll have (to avoid more allocations), then inserting elements is fairly quick.
- Con: Sorting elements is not fairly quick, especially when you have to shove a lot of elements around (you can't just fixup pointers). This is more a problem if you are trying to use insertion sort as you are reading values in (however, you can find where your element is supposed to go quicker because of the faster searching).
- Con: Requires large blocks of contiguous memory, and some memory can be wasted if you allocate more than necessary in order to save time.

A binary tree (particularly, a balanced binary tree) is a very nice structure to use, because of fast insertion, and fast searching. There are guarantees in the standard on the rate-of-growth of operations for the standard containers such as std::maps, etc, but I do not know them right off. Perhaps someone will come along later with the information.

If you are:
- Reading in data once, and hence, only sorting once.
- Searching for data many times.

Between a list and a vector, I would go with the vector.

To avoid memory issues with the vector, make the vector keep only pointers to your records, and make sure you deal with sorting/searching comparisons (less-than, equal-to) appropriately (e.g. comparing the data pointed to, not the pointers themselves).

Cheers

[FoodDude]

Ok, I've read a bunch on vectors but haven't found how to search a vector.

Also, you stated I should store pointers to my data, in the vector....so my vector is full of pointers and my actual data is stored in? an array? a linked list?

[Stoned_Coder]

For searching vectors there is algorithms defined in the header <algorithm>. find is the most common one used but there are others.
As for your data I suggest dum dum dah....... std::vector<std::string>. This can hold all your data and then you have the power of algorithms to help you sort,search,replace etc.

[FoodDude]

Thanks, I found a bunch at http://www.cppreference.com/cppalgorithm/all.html

Two vectors? One for pointers and one for data?

[Zach L.]

A very good STL reference site is: www.sgi.com/tech/stl

I'm assuming that your data is more than a string (I'm presuming this relates to your other post). If it is just a string, then, as Stoned_Coder said, std::vector<std::string>. If there is more, I would do something like the following:

struct record
{
   std::string username;
   std::string realname;
   // etc...
};

void initialize_vector(std::vector<record*>& vec)
{
   record* tmp;
   while( ... there is more data to read in ...)
   {
      tmp = new record;
      record->username = ... read in data ...;
      // etc...
      
      vec.push_back(tmp);
   }
}

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

Of course, it is better if this is all encapsulated in a class, and the initialization is done when appropriate, and the cleanup is done in the destructor. This will keep you from ever trying to use the NULL pointers.

For comparison with your sorting and searching (for STL), you will need functors, typically derived from binary_function, although all that is important is that they have the proper interface.

[FoodDude]

Zach, I'm working on such a class based on your last post. Here is where I'm stumped...
within my class, I has a function for finding a match. (struct has a string and an int.) I want to search the vector for the string and grab the associated int value.

#include <iostream>
#include <vector>
#include <algorithm>

//using namespace std;

struct record
{
   std::string domain_name;
   int site_type;
};

std::vector<record> sitevector;

class csSite_Vector
{
private:

public:

	int get_site_type(std::vector<record*>& vec, std::string domainname_to_find)
	{
		std::vector<int>::iterator result;
		result = std::find( vec.begin(), vec.end(), domainname_to_find );
		if( result == vec.end() ) 
		{
			return 0;
			//cout << "Did not find any element matching " << num_to_find << endl;
		}
		else 
		{
			return *result;
			//cout << "Found a matching element: " << *result << endl;
		}
		
	}
	
	void initialize_vector(std::vector<record*>& vec)
	{
		record* tmp;
		std::ifstream fin;
		fin.open("test.txt", 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;
			tmp = new record;
			record->domain_name = trim(sdetailline.substr(10,40));
			record->site_type = trim(sdetailline.substr(0,10));
			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()
{
	int sitetype;
	csSite_Vector SV;
	SV.initialize_vector(sitevector);
	sitetype = SV.get_site_type(sitevector, "cprogramming.com");
	SV.cleanup_vector(sitevector);

	return 0;
}

how do I modify the find line to point to the first column of the struct, the string?

Oh, wait...in this code, the vector is a pointer to a struct so I can't search the vector. So then why use a vector with a struct?

[elad]

The primary reason is so you don't have to write code to "resize" an array on your own; it's a tedious process. Resizing arrays has been standardized within the std::vector class, so use it.

To search a vector of structs for the desired value of a given data member, I'd write a custom "find" function:

void findDesiredValue(vector<structName> & vec, typeName desiredValue)
{
  vector<structName>::iterator start = vec.begin();
  vector<structName>::iterator stop = vec.end();
 
  for( ; start != stop; ++start)
  {
	 if(start->dataMember == desiredValue)
	   //do this;
	 else
	   //do that;
  }
}

It's a little bit longer than std::find(), but more flexible in what it let's you look for.

Alternatively you could try overloading the == operator for the struct such that a given struct is equal to a given data member, and then you might be able to use std::find(), but you might regret it later, if you have a need to use the == operator in other regards relating to the struct, so it seems to be a poor design option, even if it would work.

Writing your own find function seems to be the better option.

Moral of the story: If you know there is standard code (class or algorithm) that will work for you, use it; but don't be afraid to write your own when needed.

[FoodDude]

Thanks elad.

Ok, my code and my compile error. I can't believe how long this is taking me today...

#include <iostream>
#include <vector>
#include <algorithm>

#include <fstream>
#include <string>
#include "common.h"

struct record
{
   std::string domain_name;
   int site_type;
};

struct read_exception { };

std::vector<record*> sitevector;

class csSite_Vector
{
private:

public:

	int 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();

		for( ; start != stop; ++start)
		{
		 if(start->domain_name == domainname_to_find)
		   return start->site_value;
		 else
		   return 0;
		}
		
	}
	
	void initialize_vector(std::vector<record*>& vec)
	{
		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;
			tmp = new record;
			record->domain_name = trim(sdetailline.substr(10,40));
			record->site_type = trim(sdetailline.substr(0,10));
			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()
{
	int sitetype;
	csSite_Vector SV;
	SV.initialize_vector(sitevector);
	sitetype = SV.get_site_type(sitevector, "cprogramming.com");
	SV.cleanup_vector(sitevector);

	return 0;
}

--------------------Configuration: vector1 - Win32 Debug--------------------
Compiling...
vectorcomplex.cpp
C:\...\vectorcomplex.cpp(32) : error C2227: left of '->domain_name' must point to class/struct/union
C:\...\vectorcomplex.cpp(33) : error C2227: left of '->site_value' must point to class/struct/union
C:\...\vectorcomplex.cpp(56) : error C2143: syntax error : missing ';' before '->'
C:\...\vectorcomplex.cpp(56) : error C2143: syntax error : missing ';' before '->'
C:\...\vectorcomplex.cpp(57) : error C2143: syntax error : missing ';' before '->'
C:\...\vectorcomplex.cpp(57) : error C2143: syntax error : missing ';' before '->'
Error executing cl.exe.

vector1.exe - 6 error(s), 0 warning(s)

[Daved]

start->domain_name

should be:

(*start)->domain_name

You have to dereference the iterator to get the pointer stored in the vector, then use -> to access the data held by the pointer.

[Zach L.]

Moral of the story: If you know there is standard code (class or algorithm) that will work for you, use it; but don't be afraid to write your own when needed.

Ahh... but there is an STL algorithm that'll work: std::find_if

An example:

#include <algorithm>  // find_if and bind2nd
#include <functional> // binary_function
#include <iostream>
#include <string>
#include <vector>

struct record
{
   record(std::string _fld, int _a) : name(_fld), age(_a) { }
   std::string name;
   int age;
};

struct rec_ptr_eq_string : public std::binary_function<record*, std::string, bool>
{
   bool operator()(record* lhs, std::string rhs) const
   {
      return lhs->name == rhs;
   }
};

void populate(std::vector<record*>& vec)
{
   vec.push_back(new record("Victor", 24));
   vec.push_back(new record("Bob", 29));
   vec.push_back(new record("Elmer", 43));
   vec.push_back(new record("Marvin", 36));
}

int main()
{
   std::vector<record*> vec;
   populate(vec);
   
   std::vector<record*>::iterator result =
      std::find_if(vec.begin(), vec.end(), 
                   std::bind2nd(rec_ptr_eq_string(), "Marvin"));
                   
   if(result == vec.end())
      std::cout << "Marvin not found" << std::endl;
   else
      std::cout << "Marvin found\n" << "Age : " << (*result)->age << std::endl;
}

[Zach L.]

As a side note, find and find_if are both linear in complexity. If you use a std::map, which is a model of a sorted associative container, it's find function is logarithmic.

[elad]

Ahh... but there is an STL algorithm that'll work: std::find_if

Fair enough, though, I think it is easier to understand the custom find function than it is to inherit from the std::binary_function class, then overload the () operator, which would then be used by an embedded std algorhithm within the desired std algorithm. But...to each their own.