binary search on vector of objects sorted by strings

qboy · #1 12-Oct-2006, 19:20

Hi I'm having problems sorting objects. I know how to sort a vector of strings but I have no clue on how to sort an object that consist of strings. My object is something like this:
=> KeyWord(string a, Set &b);
Now I have a vector of the KeyWord objects:
=> vector<KeyWord> key;

I want to be able to sort the KeyWord objects using binary search but I do not know how to implement it. Can someone show me an example? Here is my code for binary search to sort a vector of strings.... I need to sort a vector of objects...

CPP / C++ / C Code:

//Binary search method used to sort strings
int binarySearch(vector<string>& A, string& x, int first, int last)
{
	int mid;
	string midval;
	int result;

	if(first < last)
	{
		mid = (first+last)/2;
		midval = A[mid];
		if(x == midval)
			result = mid+1;
		else if(midval < x)
			result = binarySearch (A, x, mid+1, last);
		else
			result = binarySearch (A, x, first, mid);
	}
	else
	{
		if ((first == last) && (A[first] < x))
			result = first+1;
		else 
			result = first;
	}
	return result;
}

Kelidiau · #2 13-Oct-2006, 03:42

Your question is confusing:
Your sample code searches (looks for) a particular string in an already sorted (ordered) vector of strings. It does not sort (does not order) that vector.

Binary search cannot sort a collection of objects, it can only find one particular object in an already sorted collection.

You must make sure of what you want to do (search or sort) and what algorithm you really want to use, and then re-post your question to the forum.

If what you wanted to do is a search on an already sorted vector of KeyWord objects, you could re-use much of your binary search code, but in order for it to work you must overload the == and < operators for your KeyWord objects. Then simply replace "string" by "keyWord" in your code.

qboy · #3 13-Oct-2006, 08:48

Yes, sorry that I made the question confusing. I wanted to search for the right position in order to insert an item at the correct position. I figured last night that I would need to overload the < and == operator in order to get the code to work. So I did. Although the binary search works, I could not get my insert method to work. Here are parts of my code:

Here are my overloaded operators:

CPP / C++ / C Code:

bool KeyWordSetClass::operator < (KeyWordSetClass &K)
{
	if(keyword < K.keyword)
		return true;
	else
		return false;
}

bool KeyWordSetClass::operator ==(KeyWordSetClass &K)
{
	if(keyword == K.keyword)
		return true;
	else 
		return false;
}

Here is my binary search method in which I get the following error:
" see reference to class template instantiation 'std::vector<_Ty>' being compiled"

Where key is a vector of KeyWordSetClass.
vector<KeyWordSetClass>* key;

And here is the default constructor that initializes key:

CPP / C++ / C Code:

InvertedList::InvertedList()
{
	key = new vector<KeyWordSetClass>(0);
}

CPP / C++ / C Code:

int InvertedList::binarySearch(vector<KeyWordSetClass>& A, KeyWordSetClass& x, int first, int last)
{
	int mid=0;
	KeyWordSetClass* midval(0);
	int result=0;

	if(first < last)
	{
		mid = (first+last)/2;
		*midval = A[mid];

		if(x == *midval)
			result = mid+1;
		else if(*midval < x)
			result = binarySearch (A, x, mid+1, last);
		else
			result = binarySearch (A, x, first, mid);
	}
	else
	{
		if ((first == last) && (A[first] < x))
			result = first+1;
		else 
			result = first;
	}
	return result;
}

Here is my insertMethod:

CPP / C++ / C Code:

void InvertedList::insertInto(KeyWordSetClass &K)
{
	int position;

	vector<KeyWordSetClass>::iterator iter = (*key).begin();

	position = binarySearch((*key), K, 0, (*key).size()-1);

	(*key).insert(iter+position, K);
}

Kelidiau · #4 13-Oct-2006, 17:16

This now makes sense. You are trying to implement a "binary insertion sort".
You now also have a working binary search function for a vector of KeyWords.

As far as I can see the code you give here should compile. There is no template class instantiation in the binarySearch function. On what line do you get a compilation error and what is the message?

On another note altogether, a better declaration for your operators would be:

Code:

bool operator < (const KeyWordSetClass &K) const;
bool  ==(const KeyWordSetClass &K) const;

The "const" protect the integrity of your data, but that won't fix your problem.

Also you probably do not need to have a pointer to a vector in InvertedList. A vector will do the job and you will avoid having to dereference all the time:

CPP / C++ / C Code:

class InvertedList
{
public:
   ...
private:
   vector<KeyWordSetClass> key(0);
}

If you do this, you will also not need to have a default constructor, copy constructor or destructor, but again this is not related to your compilation problem.

qboy · #5 13-Oct-2006, 17:47

When I changed the vector to an actual vector like you said instead of a pointer to a vector, I cannot access the methods that come with a vector. Perhaps I wanted to access the key.begin() in the binary search, it does not allow me to do so.

Kelidiau · #6 13-Oct-2006, 18:08

Remove the dereferencing of "key" (the *) everywhere in that function. It'll compile OK and you will be able to access the vector member functions.

You can have a vector, or a pointer to a vector, or a reference to a vector. They all work if you use the appropriate syntax.

But there was a mistake in my code for the declaration of key. Remove the "(0)", in the private section of the class declaration it should read:
vector<Rational> key;

qboy · #7 13-Oct-2006, 19:10

I changed everything to what you told me to do. I'm still having problems working on the vector... this is the error message I got:

Code:

c:\program files\microsoft visual studio 8\vc\include\xutility(2726) : error C2679: binary '=' : no operator found which takes a right-hand operand of type 'const KeyWordSetClass' (or there is no acceptable conversion)
        c:\documents and settings\sony_user\my documents\visual studio 2005\projects\project3\project3\project3.cpp(249): could be 'KeyWordSetClass &KeyWordSetClass::operator =(KeyWordSetClass &)'
        while trying to match the argument list '(KeyWordSetClass, const KeyWordSetClass)'
        c:\program files\microsoft visual studio 8\vc\include\xutility(2754) : see reference to function template instantiation 'void std::_Fill<KeyWordSetClass*,_Ty>(_FwdIt,_FwdIt,const _Ty &)' being compiled
        with
        [
            _Ty=KeyWordSetClass,
            _FwdIt=KeyWordSetClass *
        ]
        c:\program files\microsoft visual studio 8\vc\include\vector(1187) : see reference to function template instantiation 'void std::fill<KeyWordSetClass*,_Ty>(_FwdIt,_FwdIt,const _Ty &)' being compiled
        with
        [
            _Ty=KeyWordSetClass,
            _FwdIt=KeyWordSetClass *
        ]
        c:\program files\microsoft visual studio 8\vc\include\vector(1117) : while compiling class template member function 'void std::vector<_Ty>::_Insert_n(std::_Vector_iterator<_Ty,_Alloc>,__w64 unsigned int,const _Ty &)'
        with
        [
            _Ty=KeyWordSetClass,
            _Alloc=std::allocator<KeyWordSetClass>
        ]
        c:\documents and settings\sony_user\my documents\visual studio 2005\projects\project3\project3\project3.cpp(350) : see reference to class template instantiation 'std::vector<_Ty>' being compiled
        with
        [
            _Ty=KeyWordSetClass
        ]

This is the code I changed:

CPP / C++ / C Code:

//Method used to insert KeyWordSetClass in sorted order
void InvertedList::insertInto(KeyWordSetClass K)
{
	int position;

	vector<KeyWordSetClass>::iterator iter = key.begin();

	position = binarySearch(key, K, 0, key.size()-1);
	cout << "\n" << position;

	key.insert(iter+position, K);
}

How I declared the vector:
vector<KeyWordSetClass> key;

I did not write an assignment operator for KeyWordSetClass, is that the reason why? I don't know when I need to and when I don't need to write an assignment operator.

Kelidiau · #8 13-Oct-2006, 20:10

.. It seems that Visual Studio is asking for an assignment operator for KeyWordSetClass, but I cannot see why.

It tells you the error is on line 249 of project3.cpp. What is there on line 249?

Also insertInto() should really take a const reference to a KeyWordSetClass, not an object.

qboy · #9 13-Oct-2006, 20:14

Line 249 is just the end of the KeyWordSetClass class. I wrote an assignment operator and it is now working. Thanks a lot for your help Kelidiau, it really helped me learn how to use pointers and when not to use it. Now I can move on and struggle through the rest of the program.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Deleting a node from binary search tree	earachefl	C++ Forum	3	28-Jun-2006 07:26
Binary Search Tree in C++	rpg3	C++ Forum	5	02-Apr-2006 09:53
Linear Search	eccoflame	C Programming Language	3	19-Apr-2005 08:36
printing binary search tree	nkhambal	C Programming Language	2	26-Mar-2005 03:01
Search Engine Positioning 101 and 201 "How To" Tips...	000	Search Engine Optimization Forum	0	29-May-2003 10:34

binary search on vector of objects sorted by strings

Re: binary search on vector of objects sorted by strings

Re: binary search on vector of objects sorted by strings

Re: binary search on vector of objects sorted by strings

Re: binary search on vector of objects sorted by strings

Re: binary search on vector of objects sorted by strings

Re: binary search on vector of objects sorted by strings

Re: binary search on vector of objects sorted by strings

Re: binary search on vector of objects sorted by strings