using find_if/binary_function

Discussion in 'C++' started by Dilip, May 25, 2006.

  1. Dilip

    Dilip Guest

    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!
     
    Dilip, May 25, 2006
    #1
    1. Advertising

  2. 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
     
    Jonathan Mcdougall, May 25, 2006
    #2
    1. Advertising

  3. Dilip

    Daniel T. Guest

    In article <>,
    "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?


    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
     
    Daniel T., May 26, 2006
    #3
  4. Dilip

    Dilip Guest

    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, May 26, 2006
    #4
  5. 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
     
    Jonathan Mcdougall, May 26, 2006
    #5
  6. Dilip

    Daniel T. Guest

    In article <>,
    "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.


    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., May 26, 2006
    #6
  7. Dilip

    Daniel T. Guest

    In article <>,
    "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.
    >
    > 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...
     
    Daniel T., May 27, 2006
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Denis Remezov

    binary_function and bind1st

    Denis Remezov, May 19, 2004, in forum: C++
    Replies:
    6
    Views:
    773
    P.J. Plauger
    May 21, 2004
  2. news.online.no
    Replies:
    2
    Views:
    540
    Daniel T.
    Jan 30, 2006
  3. Christopher
    Replies:
    4
    Views:
    637
    James Kanze
    Nov 29, 2007
  4. yurec

    std::binary_function

    yurec, Mar 28, 2008, in forum: C++
    Replies:
    9
    Views:
    1,007
    Pete Becker
    Mar 31, 2008
  5. Frank Bergemann

    look-up table for std::binary_function's

    Frank Bergemann, Apr 23, 2008, in forum: C++
    Replies:
    0
    Views:
    330
    Frank Bergemann
    Apr 23, 2008
Loading...

Share This Page