remove_if with a mask

[eLVa]

Hi !

I have a simple problem : you are given a container, let's say a
vector of some objects, and a vector of bool which is to be treated as
a mask. You have to remove every element from the container for which
the mask is true.

basically, two iterators (one over the container and one over the
mask) iterates through their respective containers, removing elements
from the first when the second is true. I tried a few solutions, using
remove_if but I was not succesful !

Does anybody have a solution that only uses stl, (i.e I don't want to
use boost) !

thanks

 

[Victor Bazarov]

I have a simple problem : you are given a container, let's say a
vector of some objects, and a vector of bool which is to be treated as
a mask. You have to remove every element from the container for which
the mask is true.

basically, two iterators (one over the container and one over the
mask) iterates through their respective containers, removing elements
from the first when the second is true. I tried a few solutions, using
remove_if but I was not succesful !

Post what you have, post what didn't work, post your explanation on how
you expected it to work. Otherwise this looks too much like homework,
and we don't do homework.

Does anybody have a solution that only uses stl, (i.e I don't want to
use boost) !

The solution involves a predicate that should keep the second iterator
(and increment it every time the operator() is called). The predicate
can probably be const, but has to keep non-const reference to the mask
iterator. Dereference the mask iterator to check and let the op() of
your predicate essentially return that dereferenced bit.

V

 

[Francesco S. Carta]

Hi !

I have a simple problem : you are given a container, let's say a
vector of some objects, and a vector of bool which is to be treated as
a mask. You have to remove every element from the container for which
the mask is true.

basically, two iterators (one over the container and one over the
mask) iterates through their respective containers, removing elements
from the first when the second is true. I tried a few solutions, using
remove_if but I was not succesful !

Does anybody have a solution that only uses stl, (i.e I don't want to
use boost) !

thanks

What about using a simple loop that conditionally pushes back on a new
vector and then swap the old vector with the new one?

 

[eLVa]

Ok ! Wait a minute there, it's not an homework, it's a question I'm
trying to resolve.
I thought that it was not wise to keep an iterator into a functor used
in remove_if. I wanted a direction, that's all.

So that's what I got :

template <class Z> struct maskChecker {
public:
maskChecker(const vector<bool> &mask) : it(mask.begin()) {}
bool operator()(Z &) const { return *it ++; }
private:
mutable vector<bool>::const_iterator it;
};

template <class T> template<class Z>
void Selector<T>::compact(vector<Z> &data, const vector<bool> &mask) {
if (data.size() != mask.size()) throw UnmatchedSize(data.size(),
mask.size());
typename vector<Z>::iterator end = remove_if(data.begin(),
data.end(), maskChecker<Z>(mask));
data.erase(end, data.end());
}

That's kinda working, what's your opinion ?

Fail.  Your solution will not work on all implementations, it will fail with
VC++ for example as VC++ first does a find_if to determine if it should
continue which results in more than N operator()'s being called.

I'm not sure I understand what you're saying, but I think it is what I
read somewhere about having an iterator inside a functor as not a very
good idea ... Is that it ?

 

[eLVa]

What about using a simple loop that conditionally pushes back on a new
vector and then swap the old vector with the new one?

I want to use the standard library algorithm if possible. It is an
easy solution and I want to compare both in term of efficiency !

 

[Francesco S. Carta]

I want to use the standard library algorithm if possible. It is an
easy solution and I want to compare both in term of efficiency !

Fine

I suppose it depends on the size of the input too: creating a new
vector and swapping (i.e. the quick and easy solution) should be
avoided when dealing with large amounts of data, while the solution
you're aiming at will be less memory-hungry for sure.

- just some obvious considerations to fill up the post ;-)

 

[Victor Bazarov]

Ok ! Wait a minute there, it's not an homework, it's a question I'm
trying to resolve.

Sure, I trust your word. Not a homework. Absolutely. And if you
*were* a student, you would definitely admit that it's homework, yes?
That's settled, then.

I thought that it was not wise to keep an iterator into a functor used
in remove_if.

I am not sure how to respond when somebody says that something "isn't
wise". You must be wiser than I am... It's probably wise for you not
to use my advice then.

> I wanted a direction, that's all.

OK. Did you get it? If you did, happy for you. If you didn't, sorry.
Better luck next time.

So that's what I got :

template<class Z> struct maskChecker {
public:
maskChecker(const vector<bool> &mask) : it(mask.begin()) {}
bool operator()(Z&) const { return *it ++; }
private:
mutable vector<bool>::const_iterator it;

Instead of keeping a mutable iterator by value, I'd probably keep a
reference to an iterator. But, yes, that's the general idea.

};

template<class T> template<class Z>
void Selector<T>::compact(vector<Z> &data, const vector<bool> &mask) {
if (data.size() != mask.size()) throw UnmatchedSize(data.size(),
mask.size());
typename vector<Z>::iterator end = remove_if(data.begin(),
data.end(), maskChecker<Z>(mask));
data.erase(end, data.end());
}

That's kinda working, what's your opinion ?

I would do almost exactly the same, except for the iterator (I just
don't like 'mutable' for some reason). If it works, then you're OK, I
think.

[lib.alg.remove/5] says that the complexity is *exactly* (last-first)
applications of the corresponding predicate. If you had a reference to
the mask iterator, you could compare the iterator to mask.end() after
the call to 'remove_if' as well (and even assert on that).

[..]

Since you weren't really replying to my post, I only can answer *my*
questions and continue discussion on the points *I* raised.

V

 

[eLVa]

would it be a good idea to make the iterator static then ?

You might be able to get it to work if your store a *reference* to an
iterator which is then shared across all copies of the predicate made but I
am unsure as to what the standard guarantees wrt remove_if so I am unsure if
it is a good idea.

it seems that the standard library is not meant to be use this way.
however, IMHO, filtering a container based on a mask is extremely
useful, isn't it ?

what would be a good, portable way to do something similiar, if
everything fails ??

 

[eLVa]

Sure, I trust your word.  Not a homework.  Absolutely.  And if you
*were* a student, you would definitely admit that it's homework, yes?
That's settled, then.

I'm a student This is not a homework ^^

I am not sure how to respond when somebody says that something "isn't
wise".  You must be wiser than I am...  It's probably wise for you not
to use my advice then.

Not what I was trying to say, pardon my english.
Storing states in a predicate (a reference to an iterator) is
dangerous, that's what I read. I said unwise but meant dangerous.

 > I wanted a direction, that's all.

OK.  Did you get it?  If you did, happy for you.  If you didn't, sorry.
  Better luck next time.

Yeah, I came up with a working solution half an hour later. So yeah,
that's what I call a good direction, an helping hand.
I'm learning C++ the right way, and it's not easy to get it right the
first time, yesterday, functors and predicates were still a mistery to
me ...

So that's what I got :

template<class Z>  struct maskChecker {
     public:
         maskChecker(const vector<bool>  &mask) : it(mask.begin()) {}
         bool operator()(Z&) const { return *it ++; }
     private:
         mutable vector<bool>::const_iterator it;

Instead of keeping a mutable iterator by value, I'd probably keep a
reference to an iterator.  But, yes, that's the general idea.

};

template<class T>  template<class Z>
void Selector<T>::compact(vector<Z>  &data, const vector<bool>  &mask) {
     if (data.size() != mask.size()) throw UnmatchedSize(data.size(),
mask.size());
     typename vector<Z>::iterator end = remove_if(data.begin(),
data.end(), maskChecker<Z>(mask));
     data.erase(end, data.end());
}

That's kinda working, what's your opinion ?

I would do almost exactly the same, except for the iterator (I just
don't like 'mutable' for some reason).  If it works, then you're OK, I
think.

[lib.alg.remove/5] says that the complexity is *exactly* (last-first)
applications of the corresponding predicate.  If you had a reference to
the mask iterator, you could compare the iterator to mask.end() after
the call to 'remove_if' as well (and even assert on that).

Perfect, that's what I'll use.
Thank you very much

[..]

Since you weren't really replying to my post, I only can answer *my*
questions and continue discussion on the points *I* raised.

V

 

[eLVa]

Apologies Victor I didn't see your use of reference in your original reply,
but to clarify you *must* use a reference as an implementation is free to
make copies of a predicate.  The complexity requirements imply that this
should work on most (if not all) implementations, I still feel nervous about
it though as some algorithms are free to parallelize operations on a
sequence for example.  Storing state in a predicate should be approached
with caution.

/Leigh

Ok, I understand about the reference to the iterator, that's what I'll
use.
As you said, an implementation is free to parallelise, so there's
still the possibility that it could fail, right ?

Is there a safer way to do this ?

 

[Victor Bazarov]

I'm a student This is not a homework ^^


Not what I was trying to say, pardon my english.
Storing states in a predicate (a reference to an iterator) is
dangerous, that's what I read. I said unwise but meant dangerous.

Storing states *is* what predicates implemented as objects are for. If
you didn't need to store any state, you would use a function as your
predicate (possibly a *lambda* function).

So that's what I got :

template<class Z> struct maskChecker {
public:
maskChecker(const vector<bool> &mask) : it(mask.begin()) {}
bool operator()(Z&) const { return *it ++; }
private:
mutable vector<bool>::const_iterator it;

Instead of keeping a mutable iterator by value, I'd probably keep a
reference to an iterator. But, yes, that's the general idea.

};

template<class T> template<class Z>
void Selector<T>::compact(vector<Z> &data, const vector<bool> &mask) {
if (data.size() != mask.size()) throw UnmatchedSize(data.size(),
mask.size());
typename vector<Z>::iterator end = remove_if(data.begin(),
data.end(), maskChecker<Z>(mask));
data.erase(end, data.end());
}

That's kinda working, what's your opinion ?

I would do almost exactly the same, except for the iterator (I just
don't like 'mutable' for some reason). If it works, then you're OK, I
think.

[lib.alg.remove/5] says that the complexity is *exactly* (last-first)
applications of the corresponding predicate. If you had a reference to
the mask iterator, you could compare the iterator to mask.end() after
the call to 'remove_if' as well (and even assert on that).

Perfect, that's what I'll use.
Thank you very much

You're welcome very much! :*)

V

 

[Paul Bibbings]

Ok ! Wait a minute there, it's not an homework, it's a question I'm
trying to resolve.
I thought that it was not wise to keep an iterator into a functor used
in remove_if. I wanted a direction, that's all.

So that's what I got :

template <class Z> struct maskChecker {
public:
maskChecker(const vector<bool> &mask) : it(mask.begin()) {}
bool operator()(Z &) const { return *it ++; }
private:
mutable vector<bool>::const_iterator it;
};

template <class T> template<class Z>
void Selector<T>::compact(vector<Z> &data, const vector<bool> &mask) {
if (data.size() != mask.size()) throw UnmatchedSize(data.size(),
mask.size());
typename vector<Z>::iterator end = remove_if(data.begin(),
data.end(), maskChecker<Z>(mask));
data.erase(end, data.end());
}

That's kinda working, what's your opinion ?

I threw together something similar to what you have and it *doesn't*
appear to be working.

16:15:35 Paul Bibbings@JIJOU
/cygdrive/d/CPPProjects/CLCPP $cat vector_mask.cpp
// file: vector_mask.cpp

#include <vector>
#include <algorithm>
#include <iostream>

template<typename T>
class MaskFunctor {
public:
explicit MaskFunctor(std::vector<bool>& mask)
: mask_(mask)
, mask_iter_(mask_.begin())
{ }
bool operator()(const T&)
{
if (mask_iter_ == mask_.end())
return false;
else
return *mask_iter_++;
}
private:
std::vector<bool>& mask_;
std::vector<bool>::const_iterator mask_iter_;
};

int main()
{
std::vector<bool> mask;
for (int i = 0; i < 4; ++i)
{
mask.push_back(true);
mask.push_back(false);
}

std::vector<int> i_vec;
for (int i = 0; i < 8; ++i)
i_vec.push_back(i);

std::vector<int>::iterator end =
std::remove_if(i_vec.begin(), i_vec.end(), MaskFunctor<int>(mask));

i_vec.erase(end, i_vec.end());

for (std::vector<int>::const_iterator ci = i_vec.begin();
ci != i_vec.end();
++ci)
{
std::cout << *ci << ' ';
}
std::cout << '\n';
}

16:15:41 Paul Bibbings@JIJOU
/cygdrive/d/CPPProjects/CLCPP $./vector_mask
2 4 6

Regards

Paul Bibbings

 

[Victor Bazarov]

[..]
I threw together something similar to what you have and it *doesn't*
appear to be working.

16:15:35 Paul Bibbings@JIJOU
/cygdrive/d/CPPProjects/CLCPP $cat vector_mask.cpp
// file: vector_mask.cpp

#include<vector>
#include<algorithm>
#include<iostream>

template<typename T>
class MaskFunctor {
public:
explicit MaskFunctor(std::vector<bool>& mask)
: mask_(mask)
, mask_iter_(mask_.begin())
{ }
bool operator()(const T&)
{
if (mask_iter_ == mask_.end())
return false;
else
return *mask_iter_++;
}
private:
std::vector<bool>& mask_;
std::vector<bool>::const_iterator mask_iter_;
};

int main()
{
std::vector<bool> mask;
for (int i = 0; i< 4; ++i)
{
mask.push_back(true);
mask.push_back(false);
}

std::vector<int> i_vec;
for (int i = 0; i< 8; ++i)
i_vec.push_back(i);

std::vector<int>::iterator end =
std::remove_if(i_vec.begin(), i_vec.end(), MaskFunctor<int>(mask));

i_vec.erase(end, i_vec.end());

for (std::vector<int>::const_iterator ci = i_vec.begin();
ci != i_vec.end();
++ci)
{
std::cout<< *ci<< ' ';
}
std::cout<< '\n';
}

16:15:41 Paul Bibbings@JIJOU
/cygdrive/d/CPPProjects/CLCPP $./vector_mask
2 4 6

The implementation makes a copy of the predicate. It's important that
the predicate keeps the iterator by reference. Try rewriting it with
that in mind.

V

 

[eLVa]

[..]
I threw together something similar to what you have and it *doesn't*
appear to be working.

    16:15:35 Paul Bibbings@JIJOU
    /cygdrive/d/CPPProjects/CLCPP $cat vector_mask.cpp
    // file: vector_mask.cpp

    #include<vector>
    #include<algorithm>
    #include<iostream>

    template<typename T>
    class MaskFunctor {
    public:
       explicit MaskFunctor(std::vector<bool>&  mask)
          : mask_(mask)
          , mask_iter_(mask_.begin())
       { }
       bool operator()(const T&)
       {
          if (mask_iter_ == mask_.end())
            return false;
          else
            return *mask_iter_++;
       }
    private:
       std::vector<bool>&  mask_;
       std::vector<bool>::const_iterator mask_iter_;
    };

    int main()
    {
       std::vector<bool>  mask;
       for (int i = 0; i<  4; ++i)
       {
          mask.push_back(true);
          mask.push_back(false);
       }

       std::vector<int>  i_vec;
       for (int i = 0; i<  8; ++i)
            i_vec.push_back(i);

       std::vector<int>::iterator end =
          std::remove_if(i_vec.begin(), i_vec.end(), MaskFunctor<int>(mask));

       i_vec.erase(end, i_vec.end());

       for (std::vector<int>::const_iterator ci = i_vec.begin();
              ci != i_vec.end();
              ++ci)
       {
          std::cout<<  *ci<<  ' ';
       }
       std::cout<<  '\n';
    }

    16:15:41 Paul Bibbings@JIJOU
    /cygdrive/d/CPPProjects/CLCPP $./vector_mask
    2 4 6

The implementation makes a copy of the predicate.  It's important that
the predicate keeps the iterator by reference.  Try rewriting it with
that in mind.

I tried :

template <class Z> struct maskChecker {
public:
maskChecker(const vector<bool> &mask) : it(mask.begin()) {}
bool operator()(Z &) const { return *it ++; }
private:
vector<bool>::const_iterator &it;
};

template <class T> template<class Z>
void Selector<T>::compact(vector<Z> &data, const vector<bool> &mask) {
if (data.size() != mask.size()) throw UnmatchedSize(data.size(),
mask.size());
typename vector<Z>::iterator end = remove_if(data.begin(),
data.end(), maskChecker<Z>(mask));
data.erase(end, data.end());
}

This does not compile ...
I know this is about it being initialized by a temporary variable
returned by mask.begin() ..
Should I directly pass a reference to the iterator to the constructor
of maskChecker rather than the vector itself ?

 

[Victor Bazarov]

[..] I tried :

template<class Z> struct maskChecker {
public:
maskChecker(const vector<bool> &mask) : it(mask.begin()) {}
bool operator()(Z&) const { return *it ++; }
private:
vector<bool>::const_iterator&it;
};

template<class T> template<class Z>
void Selector<T>::compact(vector<Z> &data, const vector<bool> &mask) {
if (data.size() != mask.size()) throw UnmatchedSize(data.size(),
mask.size());
typename vector<Z>::iterator end = remove_if(data.begin(),
data.end(), maskChecker<Z>(mask));
data.erase(end, data.end());
}

This does not compile ...
I know this is about it being initialized by a temporary variable
returned by mask.begin() ..
Should I directly pass a reference to the iterator to the constructor
of maskChecker rather than the vector itself ?

Yes, the iterator has to be created outside (next to the call to
'remove_if'), and it needs to be an lvalue. Only then you can
initialize a ref to non-const with it.

V

 

[Keith H Duggar]

Hi !

I have a simple problem : you are given a container, let's say a
vector of some objects, and a vector of bool which is to be treated as
a mask. You have to remove every element from the container for which
the mask is true.

basically, two iterators (one over the container and one over the
mask) iterates through their respective containers, removing elements
from the first when the second is true. I tried a few solutions, using
remove_if but I was not succesful !

Does anybody have a solution that only uses stl, (i.e I don't want to
use boost) !

I would try using boost::zip_iterator

http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

to zip the two containers together, define a predicate on the sipped
tuple, and pass those to remove_if. The result will be that BOTH the
data and mask vectors will be reordered (thus remaining consistent)
and ready for culling if desired.

KHD

 

[eLVa]

Yes, assign the result of begin() to a variable and pass the variable to the
constructor (by reference).  However I mentioned else-thread that using a
reference wrapper is probably a superior solution.
std::tr1::ref(predicate).

/Leigh

I can't seem to find your post. I tried with a std::tr1::ref(pred) but
it does not compile, complaining about no class template named
'result' in my predicate struct.

In what would it be superior ??

I got it right with a reference to an iterator, so I'm glad I already
have something working

 

[eLVa]

Derive your predicate from std::unary_function<Z, bool>




No need to have a temporary for the reference and predicates are not copied
about.

Predicates are not copied, so it is only a gain in memory in this
case, right ?

A temporary for the reference is still required, no ? You don't change
the constructor, so the same problem of initialization from .begin()
arises ? Am I right ? not quite sure ..

 

[eLVa]

If you use a reference wrapper than you just store an iterator in the
predicate (not a reference):

Ok that was the catch !
Thank you Leigh, I think I got it definitely right now

 

[Keith H Duggar]

I would try using boost::zip_iterator

   http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

to zip the two containers together, define a predicate on the sipped
tuple, and pass those to remove_if. The result will be that BOTH the
data and mask vectors will be reordered (thus remaining consistent)
and ready for culling if desired.

Below is an example program. Pipe in (string bool) pairs and it
will filter out strings paired with 1. (Fingers crossed that the
formatting at least partly survives posting to google groups):

<code>

#include <vector>
#include <iostream>
#include <boost/iterator/zip_iterator.hpp>

using std::string ;
using std::vector ;

typedef
boost::zip_iterator <
boost::tuple <

>

zipiter ;

struct Pred
{
bool
operator ( ) (
zipiter::reference const x
) const {
return x.get<1>() ;
}
} ;

int
main ( )
{
vector<string> names ;
vector<bool> masks ;

string name ;
bool mask ;

while ( std::cin >> name >> mask )
{
names.push_back(name) ;
masks.push_back(mask) ;
}

{ zipiter i (boost::make_tuple(names.begin(),masks.begin())) ;
zipiter e (boost::make_tuple(names.end(),masks.end())) ;
zipiter r = std::remove_if(i,e,Pred()) ;

names.erase(
r.get_iterator_tuple().get<0>() ,
e.get_iterator_tuple().get<0>() ) ;
masks.erase(
r.get_iterator_tuple().get<1>() ,
e.get_iterator_tuple().get<1>() ) ;
}

{ zipiter i (boost::make_tuple(names.begin(),masks.begin())) ;
zipiter e (boost::make_tuple(names.end(),masks.end())) ;
for ( ; i != e ; ++i ) {
std::cout
<< i->get<0>() << ' '
<< i->get<1>() << '\n' ;
}
}

return 0 ;
}

</code>

KHD