Overview
Examples
Screenshots
Comparisons
Applications
Download
Documentation
Tutorials
Bazaar
Status & Roadmap
FAQ
Authors & License
Forums
Funding Ultimate++
Search on this site
Search in forums












SourceForge.net Logo
Home » Community » Newbie corner » Algorithms and Vectors
Algorithms and Vectors [message #28130] Tue, 17 August 2010 22:58 Go to next message
281264 is currently offline  281264
Messages: 270
Registered: June 2010
Location: Spain
Experienced Member
Hi,

I have a query regarding the usage of Vectors and U++ algorithms. The case is as follows: I am using Vector to manage a list of objects; the structure of the objects in question is rather simple: 3 double variables, one unsigned integer and a bool variable. Is it possible to use Find or FindBinary (or any other algorithm) to make a search within the Vector of structs?

Cheers,

Javier
Re: Algorithms and Vectors [message #28132 is a reply to message #28130] Tue, 17 August 2010 23:45 Go to previous messageGo to next message
mdelfede is currently offline  mdelfede
Messages: 1307
Registered: September 2007
Ultimate Contributor
Yep, you should use a predicate :

class Predicate
{
    public:
        bool operator() (const M& lhs, const M& rhs) {
            return lhs.somedata < rhs.somedata;
}


then

M myVar;  // M is your data class/struct
Vector<M> myVect;
FindBinary(myVect, myVar, Predicate())


Ciao

Max
Re: Algorithms and Vectors [message #28136 is a reply to message #28132] Wed, 18 August 2010 12:30 Go to previous messageGo to next message
281264 is currently offline  281264
Messages: 270
Registered: June 2010
Location: Spain
Experienced Member
Thanks. This is an easy example, but it does not work

struct A:Moveable<A>{
	
	int a;
	A(int x){a=x;}
};

class Predicate
{
	
public:	
	
	bool operator()(const A& lhs, const A& rhs){
		return lhs.a==rhs.a;	
	}
	
};


int main(){
	
	A vector_b(1);
	Vector<A> vector_a;
	
	vector_a.Add(1);
	vector_a.Add(2);
	
	FindBinary(vector_a,vector_b,Predicate());	
	
	return 0;	
}


why?

Cheers,

Javier
Re: Algorithms and Vectors [message #28138 is a reply to message #28136] Wed, 18 August 2010 16:06 Go to previous messageGo to next message
dolik.rce is currently offline  dolik.rce
Messages: 1789
Registered: August 2008
Location: Czech Republic
Ultimate Contributor

Hi Javier,

The predicate is basicaly a less than function, not equality. So the code should be
class Predicate{
public:		
	bool operator()(const A& lhs, const A& rhs){
		return lhs.a<rhs.a;	
	}
};


Honza
Re: Algorithms and Vectors [message #28142 is a reply to message #28138] Wed, 18 August 2010 17:20 Go to previous messageGo to next message
281264 is currently offline  281264
Messages: 270
Registered: June 2010
Location: Spain
Experienced Member
Hi Honza,

Roger ! however I have noticed the following:

1.- even with < in the class the code does not compile, why?
2.- if I replace the class by the function:
bool operator<(const A& lhs, const A& rhs){
		return lhs.a<rhs.a;	
}

then, it does compile but it does not behave as expected (it returns -1).So it does not work.

My query is how to “find” that an element within Vector<A> that complies with a criterion, for instance a==5;

Note: I have tested Sort algorithm and works fine.

Any suggestions?

Thanks,

Javier
Re: Algorithms and Vectors [message #28145 is a reply to message #28142] Wed, 18 August 2010 18:52 Go to previous messageGo to next message
dolik.rce is currently offline  dolik.rce
Messages: 1789
Registered: August 2008
Location: Czech Republic
Ultimate Contributor

Oh, ok, I see... Well, I don't have right now time to test compiling the code, but I can tell you right away, that you actually don't need this. Find(), FindBinary(), FindUpperBound() etc are doing something little else. They return index where the element should be inserted to keep the array sorted. Check the manual for details.

The simple way to find something, is to just go through the array in for cycle and look for the element you need. For simple struct like yours this should be pretty fast, especially if you check only value of one member.

If you need somewhat complex checking or exact equality of members, I would recommend you using ArrayIndex instead of Array. The only requirement is that you have to implement GetHashValue() function. If I remember correctly that is described quite good in Core Values Tutorial. Then you can search just using myindex.Find(myobject).

Sorry for not giving deeper explanation, I'm in hurry now Smile

Honza
Re: Algorithms and Vectors [message #28146 is a reply to message #28145] Wed, 18 August 2010 19:49 Go to previous messageGo to next message
281264 is currently offline  281264
Messages: 270
Registered: June 2010
Location: Spain
Experienced Member
Your explanation is fine. I agree with you in relation with the usage of a for-loop; it is the simplest way and it’ll work fast. Anyhow I shall test ArryIndex to see how it behaves.

Cheers!

Javier
Re: Algorithms and Vectors [message #28186 is a reply to message #28130] Fri, 20 August 2010 21:05 Go to previous messageGo to next message
mr_ped is currently offline  mr_ped
Messages: 825
Registered: November 2005
Location: Czech Republic - Praha
Experienced Contributor
The FindBinary actually should return index of the searched value, in your example "0", or -1 if the value is not found.

So something's wrong if it does not work.

But the vector must be already sorted by that less predicate before calling it (as far as I can tell, Vector {1,2} is sorted, so that piece of code still looks fine).

Maybe I should start TheIDE a try it myself... (reluctant to do it and compile, I'm on very slow PC)
Re: Algorithms and Vectors [message #28222 is a reply to message #28186] Mon, 23 August 2010 22:33 Go to previous message
281264 is currently offline  281264
Messages: 270
Registered: June 2010
Location: Spain
Experienced Member
To me, it is a bit weird why the code does not work.

Any volunteer to shed some light?

Cheers,

Javier
Previous Topic: Open An image upon startup
Next Topic: Assert failed in core/value.h line 464
Goto Forum:
  


Current Time: Fri Mar 29 10:49:13 CET 2024

Total time taken to generate the page: 0.01608 seconds