I want to implement this: // returns whether Seq1 includes each of the elements in Seq2 // using Pred to determine type equality template<typename Seq1, // the putative superset typename Seq2, // the putative subset typename Pred> // whether T1 from Seq1 == T2 from Seq2 struct includes_if; My ultimate goal is to be able to determine whether every element in Seq2 is either in Seq1 or has a base class in Seq1. So the predicate I'll be passing in is a metafunction class that invokes std::tr1::is_base_of. Here's my code, all but one line of which is supposed to be correct: template<typename Seq1, // the putative superset typename Seq2, // the putative subset typename Pred> // whether T1 from Seq1 == T2 from Seq2 struct includes_if : boost::is_same< typename mpl::find_if< Seq2, mpl::not_<mpl::contains_if<Seq1, lambda(T) is_base_of<mpl::_1, T> //!! > > >::type, typename mpl::end<Seq2>::type
{}; The line I don't know how to write is flagged, but the functionality I want to express is shown. In case it's relevant, here is the rest of my code: // metafunction class for TR1-conforming is_base_of struct is_base_of { template<typename T1, typename T2> struct apply: std::tr1::is_base_of<T1, T2> {}; }; // returns whether Seq contains an element satisfying Pred template<typename Seq, typename Pred> struct contains_if : mpl::not_< boost::is_same< typename mpl::find_if< Seq, mpl::apply<Pred, mpl::_1> >::type, typename mpl::end<Seq>::type >
{}; Thanks for all help, Scott
Scott Meyers wrote:
I want to implement this:
// returns whether Seq1 includes each of the elements in Seq2 // using Pred to determine type equality template<typename Seq1, // the putative superset typename Seq2, // the putative subset typename Pred> // whether T1 from Seq1 == T2 from Seq2 struct includes_if;
OK.
My ultimate goal is to be able to determine whether every element in Seq2 is either in Seq1 or has a base class in Seq1. So the predicate I'll be passing in is a metafunction class that invokes std::tr1::is_base_of.
Here's my code, all but one line of which is supposed to be correct:
template<typename Seq1, // the putative superset typename Seq2, // the putative subset typename Pred> // whether T1 from Seq1 == T2 from Seq2 struct includes_if : boost::is_same< typename mpl::find_if< Seq2, mpl::not_<mpl::contains_if<Seq1, lambda(T) is_base_of<mpl::_1, T> //!! > > >::type, typename mpl::end<Seq2>::type
{};
The line I don't know how to write is flagged, but the functionality I want to express is shown.
In case it's relevant, here is the rest of my code:
// metafunction class for TR1-conforming is_base_of struct is_base_of { template<typename T1, typename T2> struct apply: std::tr1::is_base_of<T1, T2> {}; };
Wouldn't it be nicer if 'is_base_of<_1,_2>' would just work for the predicate? I'll add it to our requirements.
// returns whether Seq contains an element satisfying Pred template<typename Seq, typename Pred> struct contains_if : mpl::not_< boost::is_same< typename mpl::find_if< Seq, mpl::apply<Pred, mpl::_1> >::type, typename mpl::end<Seq>::type >
{};
This is a nice starting point. Let's simplify away the mpl::apply and just pass on the predicate. Let's also be 'using namespace boost::mpl' here for readability. template<typename Seq, typename Pred> struct contains_if : not_< is_same<typename find_if<Seq,Pred>::type, typename end<Seq>::type> > { }; // test it typedef vector<int> v1; BOOST_MPL_ASSERT(( contains_if<v1,is_same<_1,int> > )); BOOST_MPL_ASSERT_NOT(( contains_if<v1,is_same<_1,char> > )); Now, includes_if would look roughly like an earlier version you posted, with pseudo code portions, for now: template<typename SuperSeq, typename SubSeq, typename Pred> struct includes_if : not_< contains_if< SubSeq, not_< contains_if< SuperSeq, apply< PRED, INNER_1, OUTER_1> > > > > { }; The problem comes down to that MPL can't know where one placeholder expression starts and where another one ends (denoted by uppercase identifiers, above): 1. how do we distinguish between the outer and inner '_1'? 2. 'Pred' should be allowed to be a placeholder expression, such as 'is_same<_1,_2>' Let's introduce another class template that encapsulates above 'contains_if' with a binary, partially bound predicate: namespace detail { template<typename S, typename T, typename Pred> struct contains_if_is : contains_if< S, bind<Pred,T,_1> > { }; } template<typename SuperSeq, typename SubSeq, typename Pred> struct includes_if : not_< contains_if< SubSeq, not_< detail::contains_if_is<SuperSeq,_1, Wait a minute! So far it solves problem 1. For problem 2 we have to remove the placeholders from the predicate by making sure it is a Metafunction Class using the lambda Metafunction. typename lambda<Pred>::type > > > > { }; // test it typedef vector<int> v1; typedef vector<int,char> v2; BOOST_MPL_ASSERT(( includes_if<v2, v1, is_same<_1,_2> > )); BOOST_MPL_ASSERT_NOT(( includes_if<v1, v2, is_same<_1,_2> > )); That's it. I've been toying with 'protect' to get everything done in one class template, but I couldn't quite figure it out. I remember several posts on this list with similar scenarios, but no one with a working answer. It seems 'protect' is exactly the right thing for these cases, but there's a "FIXME" comment in the reference, the description is very brief and trying things got me nowhere. So I'd be thankful if someone else would fill in this part (I'd be curious to know how 'protect' is supposed to be used even if it's not applicable in this particular case). Regards, Tobias
It will take me a few days to digest your comments (this is largely new territory for me), but I wanted to acknowledge your help now. Thanks very much.
The problem comes down to that MPL can't know where one placeholder expression starts and where another one ends (denoted by uppercase identifiers, above):
Yes, I ran into this problem playing around as a result of the help posted earlier. As I said, it will take me a while to get a grasp on what you've done. I have to look a lot of stuff up and write a lot of test cases :-) Scott
Scott Meyers wrote:
It will take me a few days to digest your comments
Hopefully not because they're confusing :-). I tried to increase conciseness with my second post.
(this is largely new territory for me), but I wanted to acknowledge your help now. Thanks very much.
Thanks too -- a reader who's new to the territory is most valuable to improve one's communication skills.
The problem comes down to that MPL can't know where one placeholder expression starts and where another one ends (denoted by uppercase identifiers, above):
Yes, I ran into this problem playing around as a result of the help posted earlier. As I said, it will take me a while to get a grasp on what you've done. I have to look a lot of stuff up and write a lot of test cases :-)
There's a slightly altered approach to this problem attached to this message for some additional fun. Regards, Tobias #include <boost/type_traits/is_same.hpp> #include <boost/mpl/not.hpp> #include <boost/mpl/end.hpp> #include <boost/mpl/find_if.hpp> #include <boost/mpl/placeholders.hpp> #include <boost/mpl/bind.hpp> #include <boost/mpl/lambda.hpp> #include <boost/mpl/apply.hpp> #include <boost/mpl/vector.hpp> #include <boost/mpl/assert.hpp> namespace mpl = boost::mpl; using namespace mpl::placeholders; using boost::is_same; // contains_if template<typename Seq, typename Pred> struct contains_if : mpl::not_< boost::is_same<typename mpl::find_if<Seq,Pred>::type, typename mpl::end<Seq>::type> > { }; // test it typedef mpl::vector<int> v1; BOOST_MPL_ASSERT(( contains_if<v1,is_same<_,int> > )); BOOST_MPL_ASSERT_NOT(( contains_if<v1,is_same<_,char> > )); // contains implemented on top of it // // other than mpl::contains this version takes a binary predicate to parametrize // comparison template<typename S, typename T, typename Compare = boost::is_same<_1,_2> > struct contains // uses 'lambda', because 'bind' requires a Metafunction Class instead of an // arbitrary Lambda Expressions : contains_if< S, mpl::bind<typename mpl::lambda<Compare>::type,T,_1> > { }; // test it BOOST_MPL_ASSERT(( ::contains<v1,int> )); BOOST_MPL_ASSERT_NOT(( ::contains<v1,char> )); // a facility that allows to sustain the evaluation of placeholder expressions template<typename PlaceholderExpr> struct defer { template<typename IgnoredPlaceholder> struct get { typedef PlaceholderExpr type; }; // return a dummy placeholder expression that evaluates to the // original one (without substitution applied) typedef typename defer<PlaceholderExpr>::template get<_> type; }; // test it BOOST_MPL_ASSERT(( is_same<mpl::apply< defer<_1>::type ,int>::type, _1> )); BOOST_MPL_ASSERT(( is_same<mpl::apply<mpl::apply< defer<_1>::type, int>::type,int>::type, int> )); // now implement includes on top of template<typename SuperSeq, typename SubSeq, typename Pred = boost::is_same<_1,_2> > struct includes : mpl::not_< contains_if< SubSeq, mpl::not_< contains<SuperSeq,_1, typename defer<Pred>::type > > > > { }; // test it typedef mpl::vector<int> v1; typedef mpl::vector<int,char> v2; BOOST_MPL_ASSERT(( includes<v2, v1> )); BOOST_MPL_ASSERT_NOT(( includes<v1, v2> ));
Tobias, I looked in your code and have an additional question. Compiletime complexity of the algorithm is exponential as I see it. Isn't it probably better to convert the first vector into a set and make set lookups with amortized constant time? Regards, Ovanes -----Original Message----- From: Tobias Schwinger [mailto:tschwinger@isonews2.com] Sent: Sonntag, 18. März 2007 14:55 To: boost-users@lists.boost.org Subject: Re: [Boost-users] [mpl] Implementing includes_if Scott Meyers wrote:
It will take me a few days to digest your comments
Hopefully not because they're confusing :-). I tried to increase conciseness with my second post.
(this is largely new territory for me), but I wanted to acknowledge your help now. Thanks very much.
Thanks too -- a reader who's new to the territory is most valuable to improve one's communication skills.
The problem comes down to that MPL can't know where one placeholder expression starts and where another one ends (denoted by uppercase identifiers, above):
Yes, I ran into this problem playing around as a result of the help posted earlier. As I said, it will take me a while to get a grasp on what you've done. I have to look a lot of stuff up and write a lot of test cases :-)
There's a slightly altered approach to this problem attached to this message for some additional fun. Regards, Tobias
Hi Ovanes, Ovanes Markarian wrote:
Tobias,
I looked in your code and have an additional question. Compiletime complexity of the algorithm is exponential as I see it.
Not quite - it's just quadratic in the worst case (I believe it's just about the wording: Although there's a constant exponent in O(N^2), "exponential complexity" is something with N being a factor of the exponent e.g. O(2^N)).
Isn't it probably better to convert the first vector into a set and make set lookups with amortized constant time?
Seems it's only possible to implement the "Pred = is_same<_1,_2> case", this way - not the "Pred = is_base_of<_1,_2> case" asked for by the OP. That issue aside, it seems an interesting idea. If you decide to give it a try I'd be interested to see your benchmarks! Regards, Tobias
on Sat Mar 17 2007, Tobias Schwinger <tschwinger-AT-isonews2.com> wrote:
The problem comes down to that MPL can't know where one placeholder expression starts and where another one ends (denoted by uppercase identifiers, above):
There is an inherent limitation in that regard. These kinds of problems come up repeatedly, so Aleksey and I agree the library should provide a solution. We had a long discussion on the boost-devel list where we talked about the same issues in terms of runtime lambda expressions: http://lists.boost.org/Archives/boost/2005/01/78409.php As I said, this thread is long (it contains a whole thread attached to one message in the outer thread -- how appropriate!) but it's worth a read. Incidentally, protect<> doesn't help as it does something different. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
on Sat Mar 17 2007, Tobias Schwinger <tschwinger-AT-isonews2.com> wrote:
The problem comes down to that MPL can't know where one placeholder expression starts and where another one ends (denoted by uppercase identifiers, above):
There is an inherent limitation in that regard. These kinds of problems come up repeatedly, so Aleksey and I agree the library should provide a solution. We had a long discussion on the boost-devel list where we talked about the same issues in terms of runtime lambda expressions:
Oh, thanks! Incidentally, I provided something very similar to 'outer' (discussed in that thread) in the follow-up, called 'defer' (inspired by Chaos). It's so easy, that it's almost provocative: // returns an unspecified placeholder expression whose evaluation // results in the original argument, no placeholder substitution // applied template<typename PlaceholderExpr> struct defer { template<typename IgnoredPlaceholder> struct get { typedef PlaceholderExpr type; }; typedef typename defer<PlaceholderExpr>::template get<_> type; }; BOOST_MPL_ASSERT(( is_same<mpl::apply< defer<_1>::type ,int>::type, _1> )); Of course it still needs "typename...type-clutter" in template context, otherwise the lambda facility would have to be aware of its existence. outer<_1> == typename defer<_1>::type
As I said, this thread is long (it contains a whole thread attached to one message in the outer thread -- how appropriate!) but it's worth a read.
Incidentally, protect<> doesn't help as it does something different.
Yes, namely nested binds - I figured that out, by now :-). Regards, Tobias
participants (4)
-
David Abrahams
-
Ovanes Markarian
-
Scott Meyers
-
Tobias Schwinger