STL find algorithm

[Christian Chrismann]

Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;

ClassA *ptrElement1 = ...;

myVector.push_f ront( ptrElement1 );
...

ClassA *ptrElement2 = *(myVector.begi n());

vector< ClassA* >::iterator it =
find( myVector.begin( ), myVector.end(), ptrElement2 );

...
}

What is used here in the 'find' algorithm for finding 'ptrElement2'?
Since 'ptrElement2' is just a pointer (so it's a variable storing an
address), I assume that each element (also pointers) in the list is
compared with 'ptrElement2' by using the operator== on the
addresses they represent, i.e. it is checked if

(address stored in any element in the list) ==
(address stored in 'ptrElement2')

Is my assumption correct?

However, this is probably rarely wanted. Usually one want to compare
the objects (and not their addresses). To achieve this, one must
dereference ptrElement2 in the 'find' algorithm and additionally make sure
that ClassA provides a proper operator==. Right?

Regards,
Chris

[Jens Theisen]

Christian Chrismann wrote:

Is my assumption correct?

Yes

Usually one want to compare
the objects (and not their addresses). To achieve this, one must
dereference ptrElement2 in the 'find' algorithm and additionally make sure
that ClassA provides a proper operator==. Right?

Yes, one way of doing this is to use find_if and provide a function as
the third argument defined as:

bool comp(ClassA const* lhs, ClassA const* rhs) { return *lhs == *rhs; }

Another one is to make your ClassA (cheaply) copyable:

class ClassA
{
public:
// ctor, functions, but no data members, which all live in impl

operator ==(ClassA const& other);
private:
boost::shared_p tr< Impl impl;
};

That way, it's cheap and feasible to use a vector of ClassAs directly
and thus you can search for it directly. Classes you use as types and
deal with very often are worth building that way.

Then there are some more bizarre alternatives, all of them require boost:

- boost::lambda

find_if(myVecto r.begin(), myVector.end(), *_1 == someClassA)

- boost::indirect _iterator

boost::indirect _iterator< ClassA const* >
indirect_first( myVector.begin( )), indirect_last(m yVector.end());
find(indirect_f irst, indirect_last, someClassA);

- boost::pointer_ container

boost::ptr_vect or< ClassA myPVector;
find(myPVector. begin(), myPVector.end() , someClassA);
I would use one of the first two solutions at first though.

Jens

[Bo Persson]

"Christian Chrismann" <pl*****@yahoo. deskrev i meddelandet
news:44******** **************@ newsspool1.arco r-online.net...

Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;

It is very unusual to store pointers in a vector. It leads to all
kinds of "interestin g" problems. The standard containers are designed
to be value based.

>
ClassA *ptrElement1 = ...;

myVector.push_f ront( ptrElement1 );
...

ClassA *ptrElement2 = *(myVector.begi n());

vector< ClassA* >::iterator it =
find( myVector.begin( ), myVector.end(), ptrElement2 );

...
}

What is used here in the 'find' algorithm for finding 'ptrElement2'?
Since 'ptrElement2' is just a pointer (so it's a variable storing an
address), I assume that each element (also pointers) in the list is
compared with 'ptrElement2' by using the operator== on the
addresses they represent, i.e. it is checked if

(address stored in any element in the list) ==
(address stored in 'ptrElement2')

Is my assumption correct?

Right. You store pointers in the vector, so the find() looks for a
specific pointer.

>
However, this is probably rarely wanted. Usually one want to compare
the objects (and not their addresses). To achieve this, one must
dereference ptrElement2 in the 'find' algorithm and additionally
make sure
that ClassA provides a proper operator==. Right?

Yes. There is another variant of std::find, find_if, that instead of a
value take a function or a function like object. That way you can get
any kind of comparison you like.

The easier way if of course to store the ClassA objects in the vector,
and not use pointers.
Bo Persson

[Markus Schoder]

Bo Persson wrote:

>
"Christian Chrismann" <pl*****@yahoo. deskrev i meddelandet
news:44******** **************@ newsspool1.arco r-online.net...

>Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;

It is very unusual to store pointers in a vector. It leads to all
kinds of "interestin g" problems. The standard containers are designed
to be value based.

Why would it be unusual? Storing pointers to objects that are owned by
some other entity in a vector is fairly common and there is nothing
wrong with it.

[Markus Schoder]

Jens Theisen wrote:

Christian Chrismann wrote:

>Is my assumption correct?

Yes

>Usually one want to compare
the objects (and not their addresses). To achieve this, one must
dereference ptrElement2 in the 'find' algorithm and additionally make
sure that ClassA provides a proper operator==. Right?

Yes, one way of doing this is to use find_if and provide a function as
the third argument defined as:

bool comp(ClassA const* lhs, ClassA const* rhs) { return *lhs == *rhs;
}

Doesn't work. find_if expects a predicate as its third argument not a
comparison function. You would need something like (not tested):

class Comp
{
public:
Comp(const ClassA *const p) : p_(p) {}
bool operator()(cons t ClassA *const q) {return *q == *p_;}

private:
const ClassA *p_;
};

[red floyd]

Markus Schoder wrote:

Bo Persson wrote:

>"Christian Chrismann" <pl*****@yahoo. deskrev i meddelandet
news:44******* *************** @newsspool1.arc or-online.net...

>>Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;

It is very unusual to store pointers in a vector. It leads to all
kinds of "interestin g" problems. The standard containers are designed
to be value based.

Why would it be unusual? Storing pointers to objects that are owned by
some other entity in a vector is fairly common and there is nothing
wrong with it.

Not to mention that storing pointers in a vector (or any other
container) is the only way to store polymorphic objects in it.

[Markus Schoder]

red floyd wrote:

Markus Schoder wrote:

>Bo Persson wrote:

>>"Christian Chrismann" <pl*****@yahoo. deskrev i meddelandet
news:44****** *************** *@newsspool1.ar cor-online.net...
Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;
It is very unusual to store pointers in a vector. It leads to all
kinds of "interestin g" problems. The standard containers are
designed to be value based.

Why would it be unusual? Storing pointers to objects that are owned
by some other entity in a vector is fairly common and there is
nothing wrong with it.

Not to mention that storing pointers in a vector (or any other
container) is the only way to store polymorphic objects in it.

Fortunately not the only way. I happen to use smart pointer objects for
that mostly.

[Bo Persson]

"Markus Schoder" <a3************ *@yahoo.deskrev i meddelandet
news:44******** **************@ newsspool1.arco r-online.net...

Bo Persson wrote:

>>
"Christian Chrismann" <pl*****@yahoo. deskrev i meddelandet
news:44******* *************** @newsspool1.arc or-online.net...

>>Hi,

I've a question on the STL find algorithm:
My code:

int main( void )
{
vector< ClassA* myVector;

It is very unusual to store pointers in a vector. It leads to all
kinds of "interestin g" problems. The standard containers are
designed
to be value based.

Why would it be unusual? Storing pointers to objects that are owned
by
some other entity in a vector is fairly common and there is nothing
wrong with it.

Ok, I take back the "very" from "very unusual".

We have had several posters today that attempt to store pointers or
references in a vector or a list, to try to gain some perceived
efficiency. Instead they got all kinds of problems, like lifetimes,
ownership, and extra indirections. Not to mention additional code to
compensate for the "efficiency " of not copying their objects.

The standard way is to store values in the containers, and let them
manage lifetimes, etc.

If you know what you are doing, and are extra careful, you can store
pointers as well, but it is generally not a good idea. This is where
you have the option of blowing your leg off.
Bo Persson
"In C++ it's harder to shoot yourself in the foot, but when you do,
you blow off your whole leg."
- Bjarne Stroustrup.

[Jens Theisen]

Markus Schoder wrote:

Doesn't work. find_if expects a predicate as its third argument not a
comparison function. You would need something like (not tested):

True

Jens

[red floyd]

Markus Schoder wrote:

red floyd wrote:

>Not to mention that storing pointers in a vector (or any other
container) is the only way to store polymorphic objects in it.

Fortunately not the only way. I happen to use smart pointer objects for
that mostly.

The Standard doesn't provide any smart pointers (no, auto_ptr<doesn' t
count), and some of us don't have access to Boost (for various reasons).