using find_if/binary_function

[Dilip]

I have a vector of class object pointers that have 2 internal states
(USED or EMPTY). USED is just a way of indicating the element in that
slot has valid state. EMPTY means the element is available for re-use.

I was trying to write some code to locate an used element using find_if
with a custom predicate derived from unary_function. That was pretty
easy. I however wanted something else. If the element cannot be
located, I wanted to return the index of the first (or for that matter
*any*) empty slot. I am trying to do this in one pass without having
to write another predicate to test for empty slots. I was about to
write something like this:

struct no_op
{
string my_name;
no_op() : my_name("default_name") { }
no_op(string _my_name) : my_name(_my_name) { }
void cleanthyself() { my_name = "EMPTY_SLOT"; }
};

typedef vector<no_op*> vecNoOps;

struct oplocator : public binary_function<no_op, short, bool>
{
string _name;
explicit oplocator(const string& name) : _name(name) { }
bool operator()(const no_op* opobj, short& emptyslotIdx) const
{
static int i = 0;
++i;
if (opobj->my_name == _name) return true;
if (opobj->my_name == "EMPTY_SLOT") { emptyslotIdx = i; }
return false;
}
};

I thought on the client side I will just try to locate the element I am
interested in as usual and if I reach the end of the vector without
locating I will atleast have the index of the empty slot. I also
thought I'd use some kind of default value for emptyslotIdx to tell if
I was able to found an emptyslot at all. If nothing is available I
will simply create a new object.

After reading Meyers' Effective STL item 39 I am no longer sure. He
wants developers to avoid exactly this kind of programming (maintaining
a local static).

Is there a way to do what I want without having to make 2 passes at the
vector of no_ops?

thanks!

[Jonathan Mcdougall]

Dilip wrote:

I have a vector of class object pointers that have 2 internal states
(USED or EMPTY). USED is just a way of indicating the element in that
slot has valid state. EMPTY means the element is available for re-use.

I was trying to write some code to locate an used element using find_if
with a custom predicate derived from unary_function. That was pretty
easy. I however wanted something else. If the element cannot be
located, I wanted to return the index of the first (or for that matter
*any*) empty slot. I am trying to do this in one pass without having
to write another predicate to test for empty slots. I was about to
write something like this:

struct no_op
{
string my_name;
no_op() : my_name("default_name") { }
no_op(string _my_name) : my_name(_my_name) { }
void cleanthyself() { my_name = "EMPTY_SLOT"; }
};

typedef vector<no_op*> vecNoOps;

struct oplocator : public binary_function<no_op, short, bool>
{
string _name;
explicit oplocator(const string& name) : _name(name) { }
bool operator()(const no_op* opobj, short& emptyslotIdx) const
{
static int i = 0;
++i;
if (opobj->my_name == _name) return true;
if (opobj->my_name == "EMPTY_SLOT") { emptyslotIdx = i; }
return false;
}
};

I thought on the client side I will just try to locate the element I am
interested in as usual and if I reach the end of the vector without
locating I will atleast have the index of the empty slot. I also
thought I'd use some kind of default value for emptyslotIdx to tell if
I was able to found an emptyslot at all. If nothing is available I
will simply create a new object.

After reading Meyers' Effective STL item 39 I am no longer sure. He
wants developers to avoid exactly this kind of programming (maintaining
a local static).

Is there a way to do what I want without having to make 2 passes at the
vector of no_ops?

Do a manual loop in a separate function. Clean and simple.
Jonathan

[Daniel T.]

In article <11*********************@u72g2000cwu.googlegroups. com>,
"Dilip" <rd*****@lycos.com> wrote:

I have a vector of class object pointers that have 2 internal states
(USED or EMPTY). USED is just a way of indicating the element in that
slot has valid state. EMPTY means the element is available for re-use.

I was trying to write some code to locate an used element using find_if
with a custom predicate derived from unary_function. That was pretty
easy. I however wanted something else. If the element cannot be
located, I wanted to return the index of the first (or for that matter
*any*) empty slot. I am trying to do this in one pass without having
to write another predicate to test for empty slots. I was about to
write something like this:

struct no_op
{
string my_name;
no_op() : my_name("default_name") { }
no_op(string _my_name) : my_name(_my_name) { }
void cleanthyself() { my_name = "EMPTY_SLOT"; }
};

typedef vector<no_op*> vecNoOps;

struct oplocator : public binary_function<no_op, short, bool>
{
string _name;
explicit oplocator(const string& name) : _name(name) { }
bool operator()(const no_op* opobj, short& emptyslotIdx) const
{
static int i = 0;
++i;
if (opobj->my_name == _name) return true;
if (opobj->my_name == "EMPTY_SLOT") { emptyslotIdx = i; }
return false;
}
};

I thought on the client side I will just try to locate the element I am
interested in as usual and if I reach the end of the vector without
locating I will atleast have the index of the empty slot. I also
thought I'd use some kind of default value for emptyslotIdx to tell if
I was able to found an emptyslot at all. If nothing is available I
will simply create a new object.

After reading Meyers' Effective STL item 39 I am no longer sure. He
wants developers to avoid exactly this kind of programming (maintaining
a local static).

Is there a way to do what I want without having to make 2 passes at the
vector of no_ops?

You are just looking for the first place to put something right?

find_if( vec.begin(), vec.end(), is_available() );

struct is_available : unary_function< no_op, bool >
{
bool operator()( const no_op* o ) const {
bool result = false;
if ( !o || o->my_name == "EMPTY_SLOT" )
result = true;
return result;
}
};

QED

[Dilip]

Daniel T. wrote:

You are just looking for the first place to put something right?

find_if( vec.begin(), vec.end(), is_available() );

struct is_available : unary_function< no_op, bool >
{
bool operator()( const no_op* o ) const {
bool result = false;
if ( !o || o->my_name == "EMPTY_SLOT" )
result = true;
return result;
}
};

Daniel
Thanks for your efforts.
Actually I am trying to:

1) locate an element first
2) if that element is not found, find first empty slot
3) if empty slot is also not found, don't bother with anything in the
functor -- the client will simply add a new element in to the vector.

i want to do all of this in one pass.

it may not be possible in which case i will simply make 2 passes with
the functor. one to find the element and another to locate an empty
slot if the element is not found.

locating an element would involve searching for it by name -- just like
I search for "EMPTY_SLOT".
i would never have a need to check with pointer validity (!o) because I
have arranged for my pointers to always be valid with some zombie state
to differentiate them from objects with real state.

[Jonathan Mcdougall]

Dilip wrote:

Daniel T. wrote:

You are just looking for the first place to put something right?

find_if( vec.begin(), vec.end(), is_available() );

struct is_available : unary_function< no_op, bool >
{
bool operator()( const no_op* o ) const {
bool result = false;
if ( !o || o->my_name == "EMPTY_SLOT" )
result = true;
return result;
}
};

Daniel
Thanks for your efforts.
Actually I am trying to:

1) locate an element first
2) if that element is not found, find first empty slot
3) if empty slot is also not found, don't bother with anything in the
functor -- the client will simply add a new element in to the vector.

i want to do all of this in one pass.

it may not be possible in which case i will simply make 2 passes with
the functor. one to find the element and another to locate an empty
slot if the element is not found.

It is possible:

# include <algorithm>
# include <string>
# include <vector>

struct s
{
enum states
{
empty,
used
};

std::string name;
states state;
};

typedef std::vector<s> cont;

// returns an iterator to the element of name
// 'name' or, if it is not found, an iterator to
// the first empty element. if there is none, it
// returns c.end()
//
cont::iterator find(cont& c, const std::string& name)
{
cont::iterator empty_element = c.end();
for (cont::iterator itor=c.begin();
itor!=c.end();
++itor)
{
if (itor->name == name)
return itor;

if ((empty_element == c.end()) &&
(itor->state == s::empty))
{
empty_element = itor;
}
}

return empty_element;
}
Jonathan

[Daniel T.]

In article <11*********************@u72g2000cwu.googlegroups. com>,
"Dilip" <rd*****@lycos.com> wrote:

Daniel T. wrote:

You are just looking for the first place to put something right?

find_if( vec.begin(), vec.end(), is_available() );

struct is_available : unary_function< no_op, bool >
{
bool operator()( const no_op* o ) const {
bool result = false;
if ( !o || o->my_name == "EMPTY_SLOT" )
result = true;
return result;
}
};
Daniel
Thanks for your efforts.
Actually I am trying to:

1) locate an element first
2) if that element is not found, find first empty slot
3) if empty slot is also not found, don't bother with anything in the
functor -- the client will simply add a new element in to the vector.

i want to do all of this in one pass.

If you use the above functor, that will happen as a matter of course.
Think about it, the vector starts with all NULLs so the functor will
return the 1st slot. The second time through, it will either return the
first slot (if "EMPTY_SLOT" is true) or the 2nd slot (if "EMPTY_SLOT" is
false on the first element.)

i would never have a need to check with pointer validity (!o) because I
have arranged for my pointers to always be valid with some zombie state
to differentiate them from objects with real state.

Well, I'm not so sure how useful that is, but I thought "EMPTY_SLOT" was
the zombie state. OK, I see what you want. This can work if you move all
the EMPTY_SLOTs to the back of the container first.

struct has_name_or_empty : unary_function< no_op, bool >
{
string name;
has_name_or_empty( const string& name_ ): name( name_ ) { }
bool operator()( const no_op* o ) const {
return o->my_name == "EMPTY_SLOT" || o->my_name == name;
}
};
remove( vec.begin(), vec.end(), has_name_or_empty( "EMPTY_SLOT" ) );
find_if( vec.begin(), vec.end(), has_name_or_empty( theName ) );

That will move all the "empty" elements to the end then get what you
want. However, this is effectively going through the container twice.

There is probably something you can do with for_each, you are allowed to
use statefull functors in it... However, it's sounding like you should
just write your own algorithm:

template < typename FwIt >
FwIt find_name_or_empty( FwIt first, FwIt last, const string& name )
{
typename FwIt candidate = last;
while ( first != last ) {
if ( (*first)->my_name == name ) return first;
if ( candidate == last && (*first)->my_name == "EMPTY_SLOT" )
candidate = first;
++first;
}
return candidate;
}

You might want to work to make that a little more generic.

[Daniel T.]

In article <11*********************@u72g2000cwu.googlegroups. com>,
"Dilip" <rd*****@lycos.com> wrote:

Daniel T. wrote:

You are just looking for the first place to put something right?

find_if( vec.begin(), vec.end(), is_available() );

struct is_available : unary_function< no_op, bool >
{
bool operator()( const no_op* o ) const {
bool result = false;
if ( !o || o->my_name == "EMPTY_SLOT" )
result = true;
return result;
}
};

Daniel
Thanks for your efforts.
Actually I am trying to:

1) locate an element first
2) if that element is not found, find first empty slot
3) if empty slot is also not found, don't bother with anything in the
functor -- the client will simply add a new element in to the vector.

i want to do all of this in one pass.

it may not be possible in which case i will simply make 2 passes with
the functor. one to find the element and another to locate an empty
slot if the element is not found.

locating an element would involve searching for it by name -- just like
I search for "EMPTY_SLOT".
i would never have a need to check with pointer validity (!o) because I
have arranged for my pointers to always be valid with some zombie state
to differentiate them from objects with real state.

Dilip,

I was at dinner wondering why I never had this kind of problem myself
and it occurs to me that you are making things much harder on yourself
by insisting on keeping zombie objects around. Why is that? If you just
removed the objects, things will be much easer.

Another option that I just thought of. When an object goes zombie, swap
it with the last non-zombie in the vector. That way, all the zombies
will be kept at the end of the vector and the find_if functor will be
easy to do without having to go through the container twice. Of course
this would only work if the order of the objects is unimportant...