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_front( ptrElement1 );
...

ClassA *ptrElement2 = *(myVector.begin());

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]

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_ptr< 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(myVector.begin(), myVector.end(), *_1 == someClassA)

- boost::indirect_iterator

boost::indirect_iterator< ClassA const* >
indirect_first(myVector.begin()), indirect_last(myVector.end());
find(indirect_first, indirect_last, someClassA);

- boost:ointer_container

boost:tr_vector< ClassA > myPVector;
find(myPVector.begin(), myPVector.end(), someClassA);


I would use one of the first two solutions at first though.

Jens

 

[Bo Persson]

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 "interesting" problems. The standard containers are designed
to be value based.

ClassA *ptrElement1 = ...;

myVector.push_front( ptrElement1 );
...

ClassA *ptrElement2 = *(myVector.begin());

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]

It is very unusual to store pointers in a vector. It leads to all
kinds of "interesting" 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]

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()(const ClassA *const q) {return *q == *p_;}

private:
const ClassA *p_;
};

 

[red floyd]

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]

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]

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]

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]

red floyd wrote:

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).

 

[Kai-Uwe Bux]

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).

So what? A straight forward implementation of a simple reference counted
shared pointer template is a little more than 100 lines of code. A simple
smart pointer with deep-copy semantics has the same complexity. Clearly
worth the effort when your shop has a policy banning third-party code.

Anyway, shared_ptr is part of tr1. So it's practically standard.


Best

Kai-Uwe Bux