STL find a pointer in vector question.

[luza]

Would anyone know which is the 'best practice' to find a pointer in a vector.
i have these 3 solutions:

typedef std::vector<CBaseCalculation*> BaseCalculationVector;
typedef BaseCalculationVector::const_iterator BaseCalculationVectorIterator;

BaseCalculationVector	CalculationList;

void CBaseCondition::AddToList1(CBaseCalculation* pCalc)
{
	bool found  = false;
	if (!CalculationList.empty())
	{
		for (int  i=0; i<CalculationList.size(); i++)
		{
			if (CalculationList[i] == pCalc)
			{
				found = true;
				break;
			}
		}
	}

	if (!found)
	{
		CalculationList.push_back(pCalc);
	}
}

void CBaseCondition::AddToList2(CBaseCalculation* pCalc)
{
	bool found  = false;
	if (!CalculationList.empty())
	{
		BaseCalculationVectorIterator	it;
		BaseCalculationVectorIterator	begin	= CalculationList.begin();// location of first element of CalculationList
		BaseCalculationVectorIterator	end		= CalculationList.end(); // one past the location of last element of CalculationList

		for(it = begin; it != end; it++)
		{
			if (*it == pCalc)
			{
				found = true;
				break;
			}
		}
	}

	if (!found)
	{
		CalculationList.push_back(pCalc);
	}
}

void CBaseCondition::AddToList3(CBaseCalculation* pCalc)
{
	bool found  = false;
	if (!CalculationList.empty())
	{
		BaseCalculationVectorIterator	begin	= CalculationList.begin();// location of first element of CalculationList
		BaseCalculationVectorIterator	end		= CalculationList.end(); // one past the location of last element of CalculationList

		found = (find(begin, end, pCalc) != end);
	}

	if (!found)
	{
		CalculationList.push_back(pCalc);
	}
} 

[Peter87]

The last one starts looking good but it could look a bit shorter. You don't really need to check if CalculationList is empty because if that is the case find will return end and found will be false anyway. Instead of using all these variables you could just stuff everything inside the if condition.

if (std::find(CalculationList.begin(), CalculationList.end(), pCalc) != CalculationList.end())
{
	CalculationList.push_back(pCalc);
}

At least that's how I would do it.

[TheIdeasMan]

Hi luza,

I am intrigued as to why you want to find a pointer in a vector. You have named you functions AddToList, if that's what you want to do, why not use a built in function to find the thing in the vector? If you already have the pointer, then dereference it and add that to the list.

[Ivan Sidarau]

consider using std::set

[luza]

Hi,

Thank you for your responses.

@Ivan: std::set could be a nice alternative . thank you for the suggestion.

@peter: nice and short! thanks.

@ theIdeasMan: What do you mean with a built in function? What's the point in dereferencing it? Shouldn't i then have to change the typedef so the vector will have object references instead of pointers? i don't see why this is preferred?

[vlad from moscow]

I would use std::none_of. Its name is more clear in the task context.

if ( std::none_of( CalculationList.begin(), CalculationList.end(),
                   std::bind2nd( std::equal_to<CBaseCalculation*>(), pCalc ) ) )
{
	CalculationList.push_back(pCalc);
}

Also a lambda expression can be used instead of std::bind2nd and std::equal_to

if ( std::none_of( CalculationList.begin(), CalculationList.end(),
                   [] ( CBaseCalculation *x ) { return ( x == pCalc ); } ) )
{
	CalculationList.push_back(pCalc);
}

[luza]

@ peter, for convenience, i believe you made a typo (which i also missed at first glance)
should be

if (std::find(CalculationList.begin(), CalculationList.end(), pCalc) == CalculationList.end())
{
	CalculationList.push_back(pCalc);
}

@vlad: thank you, i believe none_of is not supported in versions before VS 2010?

[vlad from moscow]

You should check it. At least VS 2010 supports it. Maybe early versions as for example VC 2008 also support it. Include header <algorithm> and enter a test program.

[TheIdeasMan]

Vlad's solution is probably the way to go, if it is supported.

In relation to your original method, I have these thoughts.

What you are trying to do is a find function that looks for something in a vector, that may or may not be there. If it is, put it on the list.

I am saying this won't work using a raw pointer as the search value because the vector is going to have it's own pointers which will be different to pCalc. This could be verified by printing the value of pCalc, then printing the value of the iterator pointer as it goes round the loop.

So you need to dereference pCalc to get the search value, and compare that to the dereferenced iterator which is the value you want in the vector.

The other alternative is use an STL object with a built in find function.

I found this on the C++ reference pages - search C++ stl find vector.

Edit: It's not all of it, just the pertinent bit.

function template
find
<algorithm>

template <class InputIterator, class T>
   InputIterator find ( InputIterator first, InputIterator last, const T& value );

Find value in range
Returns an iterator to the first element in the range [first,last) that compares equal to value, or last if not found.

The behavior of this function template is equivalent to:

template<class InputIterator, class T>
  InputIterator find ( InputIterator first, InputIterator last, const T& value )
  {
    for ( ;first!=last; first++) if ( *first==value ) break;
    return first;
  }

You can see how it dereferences the iterator.

Hope this helps

[ne555]

@TheIdeasMan: for some unknown reason the OP is using a container of pointers. So it makes sense to search for a pointer.
If you want to search for an object then you will need to **it == *pCalc

[TheIdeasMan]

@ne555
I agree with this:

If you want to search for an object then you will need to **it == *pCalc

Because it dereferences and compares like I said earlier.

But not this:

So it makes sense to search for a pointer

.

Forgive me if I am missing something, but how can one legitimately do this? The pointers in the vector could be anything. The only way this would work would be if you knew what the pointer was in the vector, if that was the case then it negates the entire discussion, because you already have it , so put it on the list.

The way to finish this, is for the OP to test the code. I am going to stick my neck out and predict that it will never work if a search for raw pointer is used, and it will only work with dereferencing and comparing.

Furthermore, the find algorithm I posted above is a built in solution, so just use that.

I look forward to hearing from you all.

[ne555]

I don't understand what you are having trouble with.

By instance, you may want the neighbours of a region, and you do need pointers because you want to communicate with them.
Also you want the neighbours, not some nodes that compare equal to them.
It's a collection of pointers, ¿what's so weird?
Instead of that, I decide to store a unique ID for every node ¿what would be the difference?

The pointers in the vector could be anything

Don't understand what you mean. The vector will have what you put it in. The problem is that you don't want repeated elements.

[TheIdeasMan]

@ne555

Don't understand what you mean. The vector will have what you put it in.

A pointer is a variable that holds a memory address.

I meant the value of the pointer (A memory address) The OP's code was comparing a memory address with a memory address. I am saying that is wrong, because the memory addresses could be anything. The OP's code was almost right he just needed to dereference the pointers to compare them.Here's a simple example as to why it doesn't work:

string FirstString = "ABC";
string* pFirstString = &FirstString;

string SecondString = "ABC";
string* pSecondString = &SecondString;

if (pFirstString == pSecondString)
       cout << "The 2 pointer's  are equal? " << endl;  // execution never makes it to here
else
      cout << "The 2 pointer's  are not equal " << endl; // always true

if (*pFirstString == *pSecondString)  //dereference the pointers and compare
       cout << "The 2 string's  are equal " << endl;  // always true with these values
else
      cout << "The 2 string's are not equal " << endl; // never true with these values 

This was a trivial example I know maybe this is a better one.

string SearchString = "ABC";
string*  pSearchString = &SearchString;  //pointer to SearchString

string Array[] = {"abc", "DEF", "ABC"};
string* pArray = Array;  //pointer to the array


for (  ;   pArray < (pArray +3); pArray++) {  //loops through the array using pointers
  if (pArray == pSearchString)
       cout << "Found it " << endl; // never true
  
for (  ;   pArray < (pArray +3); pArray++) {  //loops through the array using pointers
  if (*pArray == *pSearchString)  //dereference the pointers and compare
       cout << "Found it " << endl;  //this works for these values
}

I hope this makes it clear.

By instance, you may want the neighbours of a region, and you do need pointers because you want to communicate with them.
Also you want the neighbours, not some nodes that compare equal to them.
It's a collection of pointers, ¿what's so weird?

I fully understand why everyone users pointers in programming, that is absolutely not the issue.

Instead of that, I decide to store a unique ID for every node ¿what would be the difference?

Then you can search for a given ID in the vector, like in the example above with the array.

The way to finish this, is for the OP to test the code.

Furthermore, the find algorithm I posted above is a built in solution, so just use that.

[luza]

@The IdeasMan

I agree with ne555.
I have a collection of pointers and i don't want repeated elements.
I don't want to compare objects, but pointers.

You say:

What you are trying to do is a find function that looks for something in a vector, that may or may not be there. If it is, put it on the list.

You mean if it is NOT there put it on the list.

I am saying this won't work using a raw pointer as the search value because the vector is going to have it's own pointers which will be different to pCalc. This could be verified by printing the value of pCalc, then printing the value of the iterator pointer as it goes round the loop.

Why would i compare the iterator pointer to the pCalc pointer? And where did i do that?
Obviously you can see in example AddToList2:
*it == pCalc

The pointers in the vector could be anything. The only way this would work would be if you knew what the pointer was in the vector, if that was the case then it negates the entire discussion, because you already have it , so put it on the list.

I don't understand this. The pointers in the vector could be anything and I already have it and put it on the list?
The pointers are not anything. I know they point to calculation objects. And i do not know if it's already in the list. If it's not ,then i will put it on the list.

I am going to stick my neck out and predict that it will never work if a search for raw pointer is used, and it will only work with dereferencing and comparing.

In the second example (AddToList3) i dereference the iterator pointer to get the stored pointer and compare this to the pointer i want to check if its already in the list. So what's all this about only working with dereferencing and comparing.

Furthermore, the find algorithm I posted above is a built in solution, so just use that.

In the third possible solution (AddToList3) i am already using the find algoritm! (but thanx anyway :) )

[TheIdeasMan]

@luza:

We were replying to each other at the same time! Can you read my latest post?

Even so

In the third possible solution (AddToList3) i am already using the find algoritm! (but thanx anyway :) )

Yes, but I am saying that you can't compare two memory addresses, because it depends on when the pointers to the objects were put into the memory addresses. (That is when the pointers were initialised)

Anyway, have you tested the code? Does it work?

[luza]

@The IdeasMan

Just missed your last post.

Your examples are missing the point.

I want to check if the stored pointer is pointing to the same object. Not an object which happens to have the same value.

string FirstString = "ABC"; //first object
string* pFirstString = &FirstString;

string SecondString = "ABC"; //second object
string* pSecondString = &SecondString;

if (pFirstString == pSecondString) //different objects, so never be equal
       cout << "The 2 pointer's  are equal? " << endl;  // execution never makes it to here
else
      cout << "The 2 pointer's  are not equal " << endl; // always true 

if (*pFirstString == *pSecondString)  //same value, so true (but still DIFFERENT objects, so i will be very much in trouble using this)
       cout << "The 2 string's  are equal " << endl;  // always true with these values
else
      cout << "The 2 string's are not equal " << endl; // never true with these values  

[luza]

@The IdeasMan

:) yep. Again at the same time.
btw. Code Tested. It works like a charm.

[TheIdeasMan]

but still DIFFERENT objects

Ok I see where you are going with this, but I am still not getting it. So just for my education :) can you explain:

So you have a vector which you fill with pointers to objects. Easy.

So how is pCalc initialised?

Am I right when I say it must be a pointer from the vector? How could it not be ? And you are looking for duplicate values?

If those last 3 answers are true, then the find will find the first one. How does this help?

Maybe your solution is valid but it don't know enough about how you have gone about it.

Again, I am curious to see if it works.

Well I am out to get some food, I look forward to your reply.

Edit: Is RTTI a solution to test for objects of the same type?

[luza]

the vector is only used for 'viewing'. Its not the 'owner' of the objects.

The calculation object will 'subscribe' to the condition object and gives it his adress (pCalc). The condition object will add it to the vector.

When adding the objectpointer it makes sure there will only be unique pointers.
So std::find does not need to check if there is more than 1 (same) pointer(s) in the vector.

Is RTTI a solution to test for objects of the same type?

i don't need it as the vector already knows the type.

[TheIdeasMan]

Ok, now I get it :D

It works because the vector is a subset of all the Calculation pointers.

Perhaps in my defence it was a bit tricky to work out the explanation with the information given.

However, did Confuscis say anything about -- "Man who makes predictions.........." ?

Also, because I look like a complete ass right now, I mention how I might have done the same thing - maybe naively.

I would have a member variable in the Calculation class that records the condition status. Either

bool mConditionFlag;  //for good / bad
enum mConditionStatus = {LooksFishy, ThinkAboutItFor1Day, HeIsWrong, HeIsStillWrong, 
OtherPeopleGetIt, HowCanIBeWrong, IAmRight, IAmStillRight, WhyDoOtherPeopleGetIt, 
IAmConfused, IAmStillConfused, SeeingSomeLight, IfHeWasHereHeWouldPunchMeInTheArm, 
IStillDontGetIt, NowIGetIt, CrikeyWhatASaga, Apologies, ItsNotAllMyFault, ConfuscisSays, 
MyWayOfDoingIt,   LotsOfLaughs, ItsNearlyOver, AllFinishedNow }

Then you could iterate through the Calculations setting the conditons, and make your final calculation list based on the mConditionStatus or mConditionFlag. That way you wouldn't need the vector at all and all the info is in the Calculation object list. And there would be no pointer comparisons, which is what scared me.

What do you think, especially about the enum? :D :D :D :D