[mpl] Implementing eraseVal
Since set seems to be broken, I find myself wanting to implement this metafunction. It need work only for vectors: // erase all occurrences of T in Seq template<typename Seq, typename T> struct eraseVal; After several hours and tens or hundreds of thousands of lines of error messages from three compilers, I am unable to get it working. My attempt to do it the "right" way looks like this, and I must warn you in advance that it's not pretty, unless you like an approach that calls find three times with the same arguments: template<typename Seq, typename T> struct eraseVal : mpl::eval_if< boost::is_same<typename mpl::find<Seq, T>::type, typename mpl::end<Seq>::type>, typename mpl::identity<Seq>::type, eraseVal<typename mpl::erase<Seq, typename mpl::find<Seq,T>::type, typename mpl::next<typename mpl::find<Seq,T>::type>::type >::type, T> > {}; My more procedural attempt looks better (to me), but it still doesn't compile: template<typename Seq, typename T> struct eraseVal { typedef typename mpl::find<Seq,T>::type iter; typedef typename mpl::eval_if< boost::is_same<iter, typename mpl::end<Seq>::type>, typename mpl::identity<Seq>::type, typename eraseVal<typename mpl::erase<Seq, iter, mpl::next<iter>::type >::type, T>::type > type; }; God I miss iteration. And I really wish emacs would match angle brackets in C++ mode, sigh. Can somebody please help me out? Thanks, Scott
Scott Meyers ha escrito:
Since set seems to be broken, I find myself wanting to implement this metafunction. It need work only for vectors:
// erase all occurrences of T in Seq template<typename Seq, typename T> struct eraseVal;
After several hours and tens or hundreds of thousands of lines of error messages from three compilers, I am unable to get it working.
My attempt to do it the "right" way looks like this, and I must warn you in advance that it's not pretty, unless you like an approach that calls find three times with the same arguments:
template<typename Seq, typename T> struct eraseVal : mpl::eval_if< boost::is_same<typename mpl::find<Seq, T>::type, typename mpl::end<Seq>::type>, typename mpl::identity<Seq>::type, eraseVal<typename mpl::erase<Seq, typename mpl::find<Seq,T>::type, typename mpl::next<typename mpl::find<Seq,T>::type>::type >::type, T> > {};
My more procedural attempt looks better (to me), but it still doesn't compile:
template<typename Seq, typename T> struct eraseVal { typedef typename mpl::find<Seq,T>::type iter; typedef typename mpl::eval_if< boost::is_same<iter, typename mpl::end<Seq>::type>, typename mpl::identity<Seq>::type, typename eraseVal<typename mpl::erase<Seq, iter, mpl::next<iter>::type >::type, T>::type > type; };
God I miss iteration. And I really wish emacs would match angle brackets in C++ mode, sigh.
Can somebody please help me out?
Hello Scott, I see several problems with your procedural approach: the first one is the ::type added to mpl::identity<Seq> and eraseVal<...> in the expression typedef typename mpl::eval_if< boost::is_same<...>, typename mpl::identity<Seq>::type, typename eraseVal<...>::type > type; Since eval_if is designed precisely to defer invocation of its argument metafunctions the correct mode of use is typedef typename mpl::eval_if< boost::is_same<...>, typename mpl::identity<Seq>, typename eraseVal<...> > type; so that infinite recursion on eraseVal is avoided. But even after dropping those ::type's you still get errors like this: [...]/boost/mpl/next_prior.hpp: In instantiation of `boost::mpl::next<mpl_::void_>': [...] [...]/boost/mpl/next_prior.hpp:31: no type named `next' in `struct mpl_::void_' The problem now is that, although the eraseVal<...> expression is only invoked (i.e. its nested ::type calculated) when strictly necessary --this is what eval_if is used for--, its first argument is computed *always*, regardless of what branch of the eval_if<...> expr is finally selected: typename eraseVal< typename mpl::erase<Seq,iter,mpl::next<iter>::type>, T> See the mpl::erase<...> thing? When no more T's are left in the sequence, iter points to the end of Seq, and mpl::next<iter>::type is an *invalid* expression (Incidentally, a ::type is missing for mpl::erase<...>, but this is not the root of the problem here.) So, what we need if to add a layer of indirection so as to not invoke the arguments to the recursive call to eraseVal except when strictly necessary, like for instance as follows: template<typename Seq,typename T> struct eraseVal { template<typename Iter> struct eraseValRecurse: eraseVal<typename mpl::erase<Seq,Iter>::type,T> {}; typedef typename mpl::find<Seq,T>::type iter; typedef typename mpl::eval_if< boost::is_same<iter,typename mpl::end<Seq>::type>, mpl::identity<Seq>, eraseValRecurse<iter> >::type type; }; This works, but it is quite inefficient, as mpl::find, which computes in linear time, is called for every element of Seq. The same thing can be done in one pass through the sequence as follows: template<typename Seq,typename T> struct eraseVal2:mpl::copy_if<Seq,mpl::not_<boost::is_same<mpl::_,T> > > {}; Please find attached a compilable snippet showing both algorithms at work. HTH, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Thu, March 29, 2007 09:28, Joaquín Mª López Muñoz wrote: [snip ...]
This works, but it is quite inefficient, as mpl::find, which computes in linear time, is called for every element of Seq. The same thing can be done in one pass through the sequence as follows:
template<typename Seq,typename T> struct eraseVal2:mpl::copy_if<Seq,mpl::not_<boost::is_same<mpl::_,T> > > {};
Please find attached a compilable snippet showing both algorithms at work.
HTH,
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Another approach would be to use the filter_view, without copying the elements. With Kind Regards, Ovanes Markarian
on Thu Mar 29 2007, "Ovanes Markarian" <om_boost-AT-keywallet.com> wrote:
On Thu, March 29, 2007 09:28, Joaquín Mª López Muñoz wrote: [snip ...]
This works, but it is quite inefficient, as mpl::find, which computes in linear time, is called for every element of Seq. The same thing can be done in one pass through the sequence as follows:
template<typename Seq,typename T> struct eraseVal2:mpl::copy_if<Seq,mpl::not_<boost::is_same<mpl::_,T> > > {};
Please find attached a compilable snippet showing both algorithms at work.
HTH,
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Another approach would be to use the filter_view, without copying the elements.
Yeah, why struggle? This problem looks tailor-made for filter_view. -- Dave Abrahams Boost Consulting www.boost-consulting.com Don't Miss BoostCon 2007! ==> http://www.boostcon.com
David Abrahams wrote:
Yeah, why struggle? This problem looks tailor-made for filter_view.
Skipping over the struggling comment (it's not like I'm deliberately choosing it), what makes filter_view a better choice? With both implementations, doesn't eraseVal::type yield a new sequence? If filter_view<Seq, Pred> is always better than copy_if<Seq, Pred>, why do we need both? Scott
on Thu Mar 29 2007, Scott Meyers <usenet-AT-aristeia.com> wrote:
David Abrahams wrote:
Yeah, why struggle? This problem looks tailor-made for filter_view.
Skipping over the struggling comment (it's not like I'm deliberately choosing it),
Sorry.
what makes filter_view a better choice? With both implementations, doesn't eraseVal::type yield a new sequence?
I didn't look too closely at what template<typename Seq, typename T> struct eraseVal : mpl::eval_if< boost::is_same<typename mpl::find<Seq, T>::type, typename mpl::end<Seq>::type>, typename mpl::identity<Seq>::type, eraseVal<typename mpl::erase<Seq, typename mpl::find<Seq,T>::type, typename mpl::next<typename mpl::find<Seq,T>::type>::type >::type, T> > {}; was doing, but it seemed like a much bigger struggle than template<typename Seq, typename T> struct eraseVal : filter_view<Seq, mpl::not_<boost::is_same<_, T> > > {};
If filter_view<Seq, Pred> is always better than copy_if<Seq, Pred>, why do we need both?
Oh, I didn't see copy_if anywhere. I'm not sure filter_view is always better, but the question of why we need both has definitely crossed my mind, and I don't have a good answer. -- Dave Abrahams Boost Consulting www.boost-consulting.com Don't Miss BoostCon 2007! ==> http://www.boostcon.com
Joaquín Mª López Muñoz wrote:
Hello Scott, I see several problems with your procedural approach: the first one is the ::type added to mpl::identity<Seq> and eraseVal<...> in the expression
Yes, I've mentioned in other threads that my understanding of when to use the ::type suffix is, um, incomplete at best. Thanks to postings by you and David and others, the matter is slowly becoming somewhat clearer, I think.
so that infinite recursion on eraseVal is avoided. But even after dropping those ::type's you still get errors like this:
[...]/boost/mpl/next_prior.hpp: In instantiation of `boost::mpl::next<mpl_::void_>':
Yes, those errors look familiar, as does the existence of infinite recursion. It turns out that infinite recursion tends to lead to lots of fairly unhelpful error messages.
The problem now is that, although the eraseVal<...> expression is only invoked (i.e. its nested ::type calculated) when strictly necessary --this is what eval_if is used for--, its first argument is computed *always*, regardless of what branch of the eval_if<...> expr is finally selected:
Is this sort of like saying that although a metafunction may not be invoked, it's arguments are always calculated? I'm probably still stuck in the procedural world, but my expectation was that the false branch would not be "taken" when the condition was false, but it's still murky to me what it means to "take" a branch, because where "taking" it entails some kind of template expansion along it. At least that's what I currently think.
expression (Incidentally, a ::type is missing for mpl::erase<...>
Sigh.
So, what we need if to add a layer of indirection so as to not invoke the arguments to the recursive call to eraseVal except when strictly necessary, like for instance as follows:
template<typename Seq,typename T> struct eraseVal { template<typename Iter> struct eraseValRecurse: eraseVal<typename mpl::erase<Seq,Iter>::type,T> {};
typedef typename mpl::find<Seq,T>::type iter;
typedef typename mpl::eval_if< boost::is_same<iter,typename mpl::end<Seq>::type>, mpl::identity<Seq>, eraseValRecurse<iter>
And this works because we evaluate only iter in this last statement, not eraseValRecurse<iter> -- is that correct?
template<typename Seq,typename T> struct eraseVal2:mpl::copy_if<Seq,mpl::not_<boost::is_same<mpl::_,T> > > {};
YOU ARE A GOD! Thank you very much! What's really embarrassing now that I see this is that it's morally akin to code I show in Effective STL for essentially the same operation on associative containers. There is a tiny chance I would have thought of this had I noticed the existence of copy_if in the MPL, so part of the moral of the story is that I need to familiarize myself better with the extent of the functionality in the MPL. Thank you so much, I really appreciate it. With help from you and the others on this list, I anticipate my MPL productivity skyrocketing to upwards of one line per day. Counting comments, of course :-) Scott
Scott Meyers <usenet <at> aristeia.com> writes:
Joaquín Mª López Muñoz wrote:
[...]
The problem now is that, although the eraseVal<...> expression is only invoked (i.e. its nested ::type calculated) when strictly necessary --this is what eval_if is used for--, its first argument is computed *always*, regardless of what branch of the eval_if<...> expr is finally selected:
Is this sort of like saying that although a metafunction may not be invoked, it's arguments are always calculated?
No, not exactly. The thing to watch for is the rules for implicit instantation of class templates in C++, which roughly boil down to "a mention of a class template specialization will implicit instantiate it only if necessary". In particular, the mere mention of a class template specialization X<...> does not cause instantiation, but the expression X<...>::Y causes the implicit instantiation of X<...> (although it does not cause the instantiation of Y in case Y is also a template specialization.) This applies recursively to arguments of X. So, if you consider again the eval_if expression mpl::eval_if< boost::is_same< iter, typename mpl::end<Seq>::type >, mpl::identity<Seq>, eraseVal< typename mpl::erase<Seq,iter>::type, typename mpl::next<iter>::type >
the mere mention of this expression causes the implicit instantation of the following (and only the following): mpl::end<Seq> mpl::erase<Seq,iter> mpl::next<iter> So the problem does not actually have much to do with metafunctions, we're talking pure C++ templates here.
I'm probably still stuck in the procedural world, but my expectation was that the false branch would not be "taken" when the condition was false, but it's still murky to me what it means to "take" a branch, because where "taking" it entails some kind of template expansion along it. At least that's what I currently think.
Of course, the instantation of eval_if<...> (when you add the ::type suffix) causes the instantiation of more types, namely those in the true or false branch depending on the condition, just as expected. But the problem lies in the implicit instantiations caused by C++ rules before eval_if is even invoked.
So, what we need if to add a layer of indirection so as to not invoke the arguments to the recursive call to eraseVal except when strictly necessary, like for instance as follows:
template<typename Seq,typename T> struct eraseVal { template<typename Iter> struct eraseValRecurse: eraseVal<typename mpl::erase<Seq,Iter>::type,T> {};
typedef typename mpl::find<Seq,T>::type iter;
typedef typename mpl::eval_if< boost::is_same<iter,typename mpl::end<Seq>::type>, mpl::identity<Seq>, eraseValRecurse<iter>
And this works because we evaluate only iter in this last statement, not eraseValRecurse<iter> -- is that correct?
This works because the mere mention of eraseValRecurse<iter> does not cause any implicit instantiation --it is only when the "false" branch is taken that the expression is instantatiated causing the instantiation in turn of mpl::erase<...>: but in this context this latter instantiation is correct and does not lead to infinite recursions or invalid uses of MPL end iterators. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Joaquin M Lopez Munoz wrote:
No, not exactly. The thing to watch for is the rules for implicit instantation of class templates in C++, which roughly boil down to "a mention of a class template specialization will implicit instantiate it only if necessary".
Thanks for your clear, patient, helpful explanation. Scott
participants (2)
-
David Abrahams -
Joaquin M Lopez Munoz -
Joaquín Mª López Muñoz
-
Ovanes Markarian -
Scott Meyers