STL: writing “where” operator for a vector

问题:

I need to find the indexes in the vector based on several boolean predicates.

ex:

vector<float> v;
vector<int> idx;

idx=where( bool_func1(v), bool_func2(v), ... );

What is the way to declare **where** function, in order to use the several user defined boolean functions over the vector?

thanks Arman.

Edit after one week

I did some complex solutions with templates. But in reality one can use already predefined valarray for my tasks. Here is the code snippet maybe one can find it useful:

  double dr=Rc/(double)Nbins, r;
  sigma.resize(Nbins);
  rr=sigma;
  valarray<double> vz(&data.vz[0], data.vz.size());
  double mvel=vz.sum()/(double)vz.size();
  for(size_t i=0l;i<Nbins;i++)
   {
   r=dr*i;
   valarray<bool> ids = (dist < r+dr) && (dist > r);//The magic valarray<bool>
   if(ids.max())
    {
    valarray<double> d=vz[ids];//we can use indirect operation.
    d-=mvel;
    d=pow(d,2.0);
    sigma[i]= sqrt(d.sum()/(double)d.size());
    rr[i]=r;
    cout<<i<<") "<<r<<" "<<sigma[i]<<endl;
    }
   }

回答1:

Make your bool_xxx functions actually functors of a specific kind of type (tag dispatching would be enough). Then override || and && for them such that these operators return a bool_and, or bool_or. Then you can use your bool_ predicates like so:

std::find_if(vect.begin(), vect.end(), bool_x1() || bool_x2() && (bool_x3() || bool_x4() && bool_x5()));

If you're tempted to write a "where" function then you apparently want to do this more than once with a different set of bool_xxx functions. Even if you know that you want a certain type of composition now, you may as well make it as universal as possible. This is how I'd do it.

Edit:

Based on this comment: @Jerry: For example I need to know: id=where(v < 10.0 && v>1.0); and somewhere later I would like to know: id=where(v < fun(v)); you may be better off with boost::lambda:

namespace l = boost::lambda;
std::find_if(vect.begin(), vect.end(), l::_1 < 10.0 && l::_1 > 1.0);
std::find_if(vect.begin(), vect.end(), l::_1 < l::bind(fun, l::_1));

Or, if you hate lambda or aren't allowed to use it...or just want a very slightly nicer syntax (but inability to use functions directly) then just make your own placeholder type and override it to return bool_xxx functors on operators <, >, etc...

Edit2: Here's an untested where that returns a vector of iterators to all objects matching:

template < typename ForwardIter, typename Predicate >
std::vector<ForwardIter> where(ForwardIter beg, ForwardIter end, Predicate pred)
{
  ForwardIter fit = std::find_if(beg,end,pred);
  if (fit == end) return std::vector<ForwardIter>();

  ForwardIter nit = fit; ++nit;
  std::vector<ForwardIter> collection = where(nit,end,pred);
  collection.push_front(fit);
  return collection;
}

It's recursive and could be slow on some implementations but there's one way to do it.

回答2:

You could use a predicated version of transform, if there were one. There's not one, but it is very easy to write:

template<class InputIterator, class OutputIterator, class UnaryFunction, class Predicate>
OutputIterator transform_if(InputIterator first, 
                            InputIterator last, 
                            OutputIterator result, 
                            UnaryFunction f, 
                            Predicate pred)
{
    for (; first != last; ++first)
    {
        if( pred(*first) )
            *result++ = f(*first);
    }
    return result; 
}

Then you would need a way to make a composite of multiple predicates, so that you could express something like find_if( begin, end, condition1 && condition2 ). This, again, is easy to write:

template<typename LHS, typename RHS> struct binary_composite : public std::unary_function<Gizmo, bool>
{
    binary_composite(const LHS& lhs, const RHS& rhs) : lhs_(&lhs), rhs_(&rhs) {};

    bool operator()(const Gizmo& g) const
    {
        return lhs_->operator()(g) && rhs_->operator()(g);
    }
private:
    const LHS* lhs_;
    const RHS* rhs_;
};

Finally you need a gizmo that transform_if uses to convert an object reference to an object pointer. Surprise, surprise, easy to write...

template<typename Obj>  struct get_ptr : public std::unary_function<Obj, Obj*>
{
    Obj* operator()(Obj& rhs) const { return &rhs; }
};

Let's put this all together with a concrete example. Gizmo below is the object that you have a collection of. We have 2 predicates find_letter and find_value that we want to search for matches to in our main vector. transform_if is the predicated version of transform, get_ptr converts an object reference to a pointer, and binary_composite strings together the two composites.

#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
using namespace std;

struct Gizmo
{
    string name_;
    int value_;
};

struct find_letter : public std::unary_function<Gizmo, bool>
{
    find_letter(char c) : c_(c) {}
    bool operator()(const Gizmo& rhs) const { return rhs.name_[0] == c_; }
private:
    char c_;
};

struct find_value : public std::unary_function<Gizmo, int>
{
    find_value(int v) : v_(v) {};
    bool operator()(const Gizmo& rhs) const { return rhs.value_ == v_; }
private:
    int v_;
};

template<typename LHS, typename RHS> struct binary_composite : public std::unary_function<Gizmo, bool>
{
    binary_composite(const LHS& lhs, const RHS& rhs) : lhs_(&lhs), rhs_(&rhs) {};

    bool operator()(const Gizmo& g) const
    {
        return lhs_->operator()(g) && rhs_->operator()(g);
    }
private:
    const LHS* lhs_;
    const RHS* rhs_;
};

template<typename LHS, typename RHS> binary_composite<LHS,RHS> make_binary_composite(const LHS& lhs, const RHS& rhs)
{
    return binary_composite<LHS, RHS>(lhs, rhs);
}


template<class InputIterator, class OutputIterator, class UnaryFunction, class Predicate>
OutputIterator transform_if(InputIterator first, 
                            InputIterator last, 
                            OutputIterator result, 
                            UnaryFunction f, 
                            Predicate pred)
{
    for (; first != last; ++first)
    {
        if( pred(*first) )
            *result++ = f(*first);
    }
    return result; 
}

template<typename Obj>  struct get_ptr : public std::unary_function<Obj, Obj*>
{
    Obj* operator()(Obj& rhs) const { return &rhs; }
};


int main()
{   
    typedef vector<Gizmo> Gizmos;
    Gizmos gizmos;
    // ... fill the gizmo vector

    typedef vector<Gizmo*> Found;
    Found found;
    transform_if(gizmos.begin(), gizmos.end(), back_inserter(found), get_ptr<Gizmo>(), binary_composite<find_value,find_letter>(find_value(42), find_letter('a')));

    return 0;

}

---

EDIT:

Based on sbi's iterative approach, here's a predicated version of copy, which is more in line with the general STL paradigm, and can be used with back_insert_iterator to accomplish what's wanted in this case. It will give you a vector of object, not iterators or indexes, so the transform_if I posted above is still better for this use than copy_if. But here it is...

template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator copy_if(InputIterator first, 
                       InputIterator last, 
                       OutputIterator result, 
                       Predicate pred)
{
    for (; first != last; ++first)
    {
        if( pred(*first) )
            *result++ = *first;
    }
    return result;
}

回答3:

This seems like a problem that could much easier be solved in an declarative language like Prolog. I gave it a try in C++ anyway:

typedef float type;
typedef bool (*check)(type);

std::vector<int> where(const std::vector<type>& vec,
                       const std::vector<check>& checks)
{
    std::vector<int> ret;

    for (int i = 0; i < vec.size(); i++)
    {
        bool allGood = true;

        for (int j = 0; j < checks.size(); j++)
        {
            if (!checks[j](vec[i]))
            {
                allGood = false;
                break;
            }
        }

        if (allGood)
            ret.push_back(i);
    }

    return ret;
}

回答4:

I am not sure which indexes you want. Is this what you are trying to acheive:

//Function pointer declaration
typedef bool (*Predicate)(const std::vector<float>& v);

//Predicates
bool bool_func1(const std::vector<float>& v)
{
    //Implement
    return true;
}

bool bool_func2(const std::vector<float>& v)
{
    //Implement
    return true;
}


std::vector<int> where_func(const std::vector<float>& v,
                const std::vector<Predicate>& preds)
{
    std::vector<int>  idxs;
    std::vector<Predicate>::const_iterator iter = preds.begin();
    std::vector<Predicate>::const_iterator eiter = preds.end();
    for(; iter != eiter; ++iter)
    {
        if((*iter)(v))
        {
            idxs.push_back(eiter - iter);
        }   
    }

    return idxs;
}

回答5:

template<typename Vector, typename T> std::vector<int> where(const std::vector<Vector>& vec, T t) {
    std::vector<int> results;
    for(int i = 0; i < vec.size(); i++) {
        if (t(vec[i])
            results.push_back(i)
    }
    return results;
}

Overload for additional function object arguments as you wish. Use:

template<typename T> struct AlwaysAccept {
    bool operator()(const T& t) { return true; }
};
std::vector<float> floats;
// insert values into floats here
std::vector<int> results = where(floats, AlwaysAccept<float>());

Noah Robert's solution is nice, but I'm not wholly sure how I could make that work.