[Fusion] Views of Associative Sequences
I'm trying to find a solution to the following problem. If I have an associative sequence such as a fusion::set and I make a filter view of it, the view is not a model of an associative sequence and does not support the has_key and at_key functions. I can use fusion::as_set on the view to get an associative sequence again, but this doesn't really have the effect I want as it results in a set holding copies of the original data whereas the view referenced the original data. Example below. Would it be possible to create a view which supported the associative sequence interface? Any suggested alternative approaches? Thanks Nate ~~~~~~~~~~~~~~~~~ #include <boost/fusion/include/set.hpp> #include <boost/fusion/include/intrinsic.hpp> #include <boost/fusion/include/filter_view.hpp> #include <string> #include <boost/type_traits/is_arithmetic.hpp> #include <boost/mpl/placeholders.hpp> namespace fusion = boost::fusion; using boost::mpl::_; int main() { typedef fusion::set<int,double,std::string> set_t; set_t s(1,2.0,"hello"); fusion::filter_view<set_t,boost::is_arithmetic<_>> filtered_view(s); fusion::front(filtered_view) = 4; //modifies s fusion::result_of::as_set<fusion::filter_view<set_t,boost::is_arithmetic<_>
::type filtered_set(filtered_view); fusion::at_key<int>(filtered_set) = 16; // modifies the copied data in filtered_set. }
James Knight schrieb:
I'm trying to find a solution to the following problem. If I have an associative sequence such as a fusion::set and I make a filter view of it, the view is not a model of an associative sequence and does not support the has_key and at_key functions. I can use fusion::as_set on the view to get an associative sequence again, but this doesn't really have the effect I want as it results in a set holding copies of the original data whereas the view referenced the original data. Example below.
Would it be possible to create a view which supported the associative sequence interface? Any suggested alternative approaches?
Thanks Nate
There is already a feature request for associative views (ticket 3473). I will get down to it once I am granted write access to the trunk. For now you could use my c++0x port of fusion. It correctly preserves the category of the underlying sequence's for all views. The port is fully backwards compatible, in terms of both features and compiler (non-0x compiler are supported). You can find the code in the sandbox (/sandbox/SOC/2009/fusion/). -Christopher
Christopher Schmidt wrote:
James Knight schrieb:
I'm trying to find a solution to the following problem. If I have an associative sequence such as a fusion::set and I make a filter view of it, the view is not a model of an associative sequence and does not support the has_key and at_key functions. I can use fusion::as_set on the view to get an associative sequence again, but this doesn't really have the effect I want as it results in a set holding copies of the original data whereas the view referenced the original data. Example below.
Would it be possible to create a view which supported the associative sequence interface? Any suggested alternative approaches?
Thanks Nate
There is already a feature request for associative views (ticket 3473). I will get down to it once I am granted write access to the trunk. For now you could use my c++0x port of fusion. It correctly preserves the category of the underlying sequence's for all views. The port is fully backwards compatible, in terms of both features and compiler (non-0x compiler are supported). You can find the code in the sandbox (/sandbox/SOC/2009/fusion/).
And in case you are wondering, Christopher Schmidt's wonderful c++0x port will be the future of fusion. Regards, -- Joel de Guzman http://www.boostpro.com http://spirit.sf.net http://www.facebook.com/djowel Meet me at BoostCon http://www.boostcon.com/home http://www.facebook.com/boostcon
Joel de Guzman <joel <at> boost-consulting.com> writes:
And in case you are wondering, Christopher Schmidt's wonderful c++0x port will be the future of fusion.
Regards,
Cool. The port looks really nice. After looking through the code, I've got a couple of questions. The most direct one regards the implementation of at_key for set and map. The implementation seems to have changed considerably from the 1.40 version. If I'm reading things correctly at_key is now implemented using a new find_key algorithm whereas the 1.40 version used some function overloading mechanism. Is there any run-time performance difference between the two approaches? It looks as if find_key is a constant time algorithm. Am I correct in my understanding? Thanks
Nate Knight wrote:
Joel de Guzman <joel <at> boost-consulting.com> writes:
And in case you are wondering, Christopher Schmidt's wonderful c++0x port will be the future of fusion.
Regards,
Cool. The port looks really nice. After looking through the code, I've got a couple of questions. The most direct one regards the implementation of at_key for set and map. The implementation seems to have changed considerably from the 1.40 version. If I'm reading things correctly at_key is now implemented using a new find_key algorithm whereas the 1.40 version used some function overloading mechanism. Is there any run-time performance difference between the two approaches? It looks as if find_key is a constant time algorithm. Am I correct in my understanding?
I'd guess it would be the same. I'm not so sure about compile rime performance though. I'll let Christopher provide details. At any rate, I'd urge Christopher to add more benchmarks. I started one a long time ago, but it needs to be beefed up, especially with the upcoming 0x port. Regards, -- Joel de Guzman http://www.boostpro.com http://spirit.sf.net http://www.facebook.com/djowel Meet me at BoostCon http://www.boostcon.com/home http://www.facebook.com/boostcon
Joel de Guzman schrieb:
Nate Knight wrote:
Joel de Guzman <joel <at> boost-consulting.com> writes:
And in case you are wondering, Christopher Schmidt's wonderful c++0x port will be the future of fusion.
Regards,
Cool. The port looks really nice. After looking through the code, I've got a couple of questions. The most direct one regards the implementation of at_key for set and map. The implementation seems to have changed considerably from the 1.40 version. If I'm reading things correctly at_key is now implemented using a new find_key algorithm whereas the 1.40 version used some function overloading mechanism. Is there any run-time performance difference between the two approaches? It looks as if find_key is a constant time algorithm. Am I correct in my understanding?
I'd guess it would be the same. I'm not so sure about compile rime performance though. I'll let Christopher provide details. At any rate, I'd urge Christopher to add more benchmarks. I started one a long time ago, but it needs to be beefed up, especially with the upcoming 0x port.
Regards,
My implementation introduces associative iterators. An associative forward sequence shall provide an iterator that allows direct mapping from the iterator (type) to the underlying element (type), key type and the actual value (type) associated with the key. I split fusion::find up in fusion::find_key and a new fusion::find. My fusion::find does not care about the associative-ness of the sequence. It searches for a plain element type. That is it returns the first iterator for which is_same<fusion::result_of::value_of<mpl::_1>, Elem> evaluates to true, or an end-iterator. fusion::find_key returns the first iterator for which is_same<fusion::result_of::key_of<mpl::_1>, Key> evaluates to true, or an end-iterator. The compile-time evaluation of a fusion::(result_of::)find_key-invocation should scale linear to the number of elements of the sequence being searched on. The fusion::find_key implementation uses fusion::detail::static_seq_find_if, which is 4-unrolled optimized. This should be slightly faster compared to the unoptimized implementation of fusion::map<...>/set<...>::(meta_)find_impl(_const), which are plain recursive metafunctions/n-overloaded functions. The runtime performance of my port should be better if the compiler supports rvalue references. If not, there should not be a difference in any case at all. For fusion::find, the run-time performance is of course constant. The "old" implementation uses a distinct intrusive (meta-)function, analogue to find, to implement at_key. I implemented fusion::at_key based on fusion::find_key. For more information on my port, have a look at the posts over at the development mailing list. http://article.gmane.org/gmane.comp.lib.boost.devel/194322 -Christopher
Christopher Schmidt wrote:
My implementation introduces associative iterators. An associative forward sequence shall provide an iterator that allows direct mapping from the iterator (type) to the underlying element (type), key type and the actual value (type) associated with the key. I split fusion::find up in fusion::find_key and a new fusion::find. My fusion::find does not care about the associative-ness of the sequence. It searches for a plain element type. That is it returns the first iterator for which is_same<fusion::result_of::value_of<mpl::_1>, Elem> evaluates to true, or an end-iterator. fusion::find_key returns the first iterator for which is_same<fusion::result_of::key_of<mpl::_1>, Key> evaluates to true, or an end-iterator.
The compile-time evaluation of a fusion::(result_of::)find_key-invocation should scale linear to the number of elements of the sequence being searched on. The fusion::find_key implementation uses fusion::detail::static_seq_find_if, which is 4-unrolled optimized. This should be slightly faster compared to the unoptimized implementation of fusion::map<...>/set<...>::(meta_)find_impl(_const), which are plain recursive metafunctions/n-overloaded functions. The runtime performance of my port should be better if the compiler supports rvalue references. If not, there should not be a difference in any case at all. For fusion::find, the run-time performance is of course constant. The "old" implementation uses a distinct intrusive (meta-)function, analogue to find, to implement at_key. I implemented fusion::at_key based on fusion::find_key.
For more information on my port, have a look at the posts over at the development mailing list.
That's a well-thought and very nice design, Christopher! Regards, -- Joel de Guzman http://www.boostpro.com http://spirit.sf.net http://www.facebook.com/djowel Meet me at BoostCon http://www.boostcon.com/home http://www.facebook.com/boostcon
There is already a feature request for associative views (ticket 3473). I will get down to it once I am granted write access to the trunk.
I see that the ticket is closed and the changes implemented in the trunk : many thanks! I wonder if I should wait for v1.41 (when : is there an estimate?) or if I can already remove joint_view.hpp from my current copy of boost and replace it with the new one : do you remember if the changes in joint_view standalone?
er schrieb:
I wonder if I should wait for v1.41 (when : is there an estimate?) or if I can already remove joint_view.hpp from my current copy of boost and replace it with the new one : do you remember if the changes in joint_view standalone?
Unfortunately the changes in <boost/fusion/view/joint_view/*> are not stand-alone, and I was too late to merge them into the 1.41 release branch. I suggest you to work with a copy of the HEAD of the trunk. -Christopher
Christopher Schmidt wrote:
Unfortunately the changes in <boost/fusion/view/joint_view/*> are not stand-alone, and I was too late to merge them into the 1.41 release branch.
OK.
I suggest you to work with a copy of the HEAD of the trunk.
Sorry for troubling you with more trivialities, but by HEAD do you mean the latest update? Could you please confirm if this is the link from which I should copy fusion to my current release so I can start using the new facilities you have provided: http://svn.boost.org/svn/boost/trunk/boost/fusion/ Thanks.
er schrieb:
Sorry for troubling you with more trivialities, but by HEAD do you mean the latest update? Yeah, the most up-to-date revision of the fusion trunk.
Could you please confirm if this is the link from which I should copy fusion to my current release so I can start using the new facilities you have provided:
http://svn.boost.org/svn/boost/trunk/boost/fusion/ That's correct.
svn co http://svn.boost.org/svn/boost/trunk/boost/fusion fusion -Christopher
Christopher Schmidt wrote:
er schrieb:
Sorry for troubling you with more trivialities, but by HEAD do you mean the latest update? Yeah, the most up-to-date revision of the fusion trunk. Could you please confirm if this is the link from which I should copy fusion to my current release so I can start using the new facilities you have provided:
http://svn.boost.org/svn/boost/trunk/boost/fusion/ That's correct.
svn co http://svn.boost.org/svn/boost/trunk/boost/fusion fusion
Many thanks for working on this, Christopher! Regards, -- Joel de Guzman http://www.boostpro.com http://spirit.sf.net http://www.facebook.com/djowel Meet me at BoostCon http://www.boostcon.com/home http://www.facebook.com/boostcon
participants (4)
-
Christopher Schmidt -
er -
James Knight -
Joel de Guzman -
Nate Knight