[bimap] Creating a bimap fom a std::map
I would have thought, naively enough, that one of the common uses of a bimap was that one should be able to create a bimap from a std::map as long as the relation between the two types was unique both ways. I was disconcerted when I did not see a bimap constructor that accepted a std::map of the same types, but then I saw the constructor which takes two iterators and decided to try that, like so: std::map<int,std::string> myMap; // ... fill myMap boost::bimap<int,std::string> myBimap(myMap.begin(),myMap.end()); I was met with, in VC9 using Boost 1.40: "c:\utilities\boost\boost_1_40_0\boost\multi_index_container.hpp(232) : error C2664: 'std::pair<_Ty1,_Ty2> boost::multi_index::multi_index_container<Value,IndexSpecifierList,Allocator>::insert_(const Value &,boost::multi_index::detail::ordered_index_node<Super> *)' : cannot convert parameter 1 from 'std::pair<_Ty1,_Ty2>' to 'const boost::bimaps::relation::mutant_relation<TA,TB,Info,force_mutable> &' 1> with 1> [ 1> _Ty1=boost::multi_index::detail::ordered_index_node<boost::multi_index::detail::ordered_index_node<boost::multi_index::detail::index_node_base<boost::bimaps::relation::mutant_relation<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info,true>,std::allocator<boost::bimaps::relation::mutant_relation<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info,true>>>>> *, 1> _Ty2=bool, 1> Value=boost::bimaps::relation::mutant_relation<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info,true>, 1> IndexSpecifierList=boost::bimaps::detail::bimap_core<int,TString,boost::mpl::na,boost::mpl::na,boost::mpl::na>::core_indices, 1> Allocator=std::allocator<boost::bimaps::relation::mutant_relation<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info,true>>, 1> Super=boost::multi_index::detail::ordered_index_node<boost::multi_index::detail::index_node_base<boost::bimaps::relation::mutant_relation<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info,true>,std::allocator<boost::bimaps::relation::mutant_relation<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info,true>>>> 1> ] 1> and 1> [ 1> _Ty1=const int, 1> _Ty2=TString 1> ] 1> and 1> [ 1> TA=boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>, 1> TB=boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>, 1> Info=boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info, 1> force_mutable=true 1> ] 1> Reason: cannot convert from 'std::pair<_Ty1,_Ty2>' to 'const boost::bimaps::relation::mutant_relation<TA,TB,Info,force_mutable>' 1> with 1> [ 1> _Ty1=const int, 1> _Ty2=TString 1> ] 1> and 1> [ 1> TA=boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>, 1> TB=boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>, 1> Info=boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info, 1> force_mutable=true 1> ] 1> No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called 1> c:\utilities\boost\boost_1_40_0\boost\bimap\bimap.hpp(247) : see reference to function template instantiation 'boost::multi_index::multi_index_container<Value,IndexSpecifierList,Allocator>::multi_index_container<InputIterator>(InputIterator,InputIterator,const boost::tuples::cons<HT,TT> &,const std::allocator<_Ty> &)' being compiled 1> with 1> [ 1> Value=boost::bimaps::relation::mutant_relation<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info,true>, 1> IndexSpecifierList=boost::bimaps::detail::bimap_core<int,TString,boost::mpl::na,boost::mpl::na,boost::mpl::na>::core_indices, 1> Allocator=std::allocator<boost::bimaps::relation::mutant_relation<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info,true>>, 1> InputIterator=std::_Tree<std::_Tmap_traits<int,TString,std::less<int>,std::allocator<std::pair<const int,TString>>,false>>::iterator, 1> HT=boost::tuples::tuple<boost::multi_index::member<boost::bimaps::relation::detail::relation_storage<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,true>,std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,pointer-to-member(0x4)>,std::less<std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>>>, 1> TT=boost::tuples::cons<boost::tuples::tuple<boost::multi_index::member<boost::bimaps::relation::detail::relation_storage<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,true>,int,pointer-to-member(0x0)>,std::less<int>>,boost::multi_index::detail::index_base<boost::bimaps::relation::mutant_relation<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info,true>,boost::bimaps::detail::bimap_core<int,TString,boost::mpl::na,boost::mpl::na,boost::mpl::na>::core_indices,std::allocator<boost::bimaps::relation::mutant_relation<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info,true>>>::ctor_args_list>, 1> _Ty=boost::bimaps::relation::mutant_relation<boost::bimaps::tags::tagged<const int,boost::bimaps::relation::member_at::left>,boost::bimaps::tags::tagged<const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>,boost::bimaps::relation::member_at::right>,boost::bimaps::detail::manage_additional_parameters<boost::mpl::na,boost::mpl::na,boost::mpl::na>::case_NNN::additional_info,true> 1> ] 1> c:\programming\programs\vc9\xxx\current\yyyyyyyyyy\zzzzzzzzzzzzzzzz.cpp(338) : see reference to function template instantiation 'boost::bimaps::bimap<KeyTypeA,KeyTypeB>::bimap<std::_Tree<_Traits>::iterator>(InputIterator,InputIterator)' being compiled 1> with 1> [ 1> KeyTypeA=int, 1> KeyTypeB=TString, 1> _Traits=std::_Tmap_traits<int,TString,std::less<int>,std::allocator<std::pair<const int,TString>>,false>, 1> InputIterator=std::_Tree<std::_Tmap_traits<int,TString,std::less<int>,std::allocator<std::pair<const int,TString>>,false>>::iterator 1> ]" So evidently that does not work. What is the problem with creating a bimap from the data in a std::map ? It seems as if it should be a no-braine and one of the chief selling points of using a bimap.
Hello Edward, On Wed, Nov 25, 2009 at 10:40 AM, Edward Diener <eldiener@tropicsoft.com> wrote:
I would have thought, naively enough, that one of the common uses of a bimap was that one should be able to create a bimap from a std::map as long as the relation between the two types was unique both ways.
Yes, this is a very common scenario.
I was disconcerted when I did not see a bimap constructor that accepted a std::map of the same types,
The library does not have this constructor by design. A bimap can be viewed as a map (if you choose the left or the right view) but it is not directly compatible with a map to enforce the idea that both values are at the same level in the container. You explicitly have to choose the left view to do what you are trying to achieve: std::map<int,std::string> myMap; // ... fill myMap boost::bimap<int,std::string> myBimap; myBimap.left.insert(myMap.begin(),myMap.end()); The extra line helps to maintain the symmetry, and I think that in the end makes the code less cryptic. Imagine now that you have the data in a reverse map, you should write something along the following lines: std::map<std::string,int> myRMap; // ... fill myMap boost::bimap<int,std::string> myBimap; myBimap.right.insert(myRMap.begin(),myRMap.end()); I hope that this works for you. Best regards Matias
Matias Capeletto wrote:
Hello Edward,
On Wed, Nov 25, 2009 at 10:40 AM, Edward Diener <eldiener@tropicsoft.com> wrote:
I would have thought, naively enough, that one of the common uses of a bimap was that one should be able to create a bimap from a std::map as long as the relation between the two types was unique both ways.
Yes, this is a very common scenario.
I was disconcerted when I did not see a bimap constructor that accepted a std::map of the same types,
The library does not have this constructor by design. A bimap can be viewed as a map (if you choose the left or the right view) but it is not directly compatible with a map to enforce the idea that both values are at the same level in the container. You explicitly have to choose the left view to do what you are trying to achieve:
std::map<int,std::string> myMap; // ... fill myMap boost::bimap<int,std::string> myBimap; myBimap.left.insert(myMap.begin(),myMap.end());
My opinion is that you should have a constructor which takes a std::map, where the types of the map are the types of the bimap. If the types of the map are the same as the types of the bimap, then the constructor should do exactly the equivalent to what you show just above. If the types of the map are the reverse of the types of the bimap, then the constructor should be the equivalent of: std::map<std::string,int> myMap; // ... fill myMap boost::bimap<int,std::string> myBimap; myBimap.right.insert(myMap.begin(),myMap.end()); This is an ease of use issue and I really do not see why you can not make the use of bimap easier to use in this way. Especially since you also agree that this is a very common scenario. Can I really be the first person who has suggested this regarding bimap ? Nonetheless thanks for pointing out to me how it is done.
The extra line helps to maintain the symmetry, and I think that in the end makes the code less cryptic. Imagine now that you have the data in a reverse map, you should write something along the following lines:
std::map<std::string,int> myRMap; // ... fill myMap boost::bimap<int,std::string> myBimap; myBimap.right.insert(myRMap.begin(),myRMap.end());
Yes, of course. See above. I just do not agree that not providing the obvious constructor is good because it "maintains symmetry". Many things in programming are good because they provide ease-of-use and my suggestion is an obvious case of that.
On Wed, Nov 25, 2009 at 1:24 PM, Edward Diener <eldiener@tropicsoft.com> wrote:
Matias Capeletto wrote: My opinion is that you should have a constructor which takes a std::map, where the types of the map are the types of the bimap. If the types of the map are the same as the types of the bimap, then the constructor should do exactly the equivalent to what you show just above. If the types of the map are the reverse of the types of the bimap, then the constructor should be the equivalent of:
std::map<std::string,int> myMap; // ... fill myMap boost::bimap<int,std::string> myBimap; myBimap.right.insert(myMap.begin(),myMap.end());
This is an ease of use issue and I really do not see why you can not make the use of bimap easier to use in this way. Especially since you also agree that this is a very common scenario.
I understand your easy-of-use point, but you have just wrote down here why it is not a good idea to provide this constructor. Not only it breaks the symmetry, the real problem is that following your idea of automatic conversion between pairs and relations we bump into ambiguities. Imagine you now have a bimap<A,A>, and you use your constructor with a map<A,A>... it is not clear which side is the left and which side is the right. I thought about this issues and it was decided that it is better not to surprise the user with this kind of ambiguities. Thanks for your suggestion and interest. Best regards Matias
Matias Capeletto wrote:
On Wed, Nov 25, 2009 at 1:24 PM, Edward Diener <eldiener@tropicsoft.com> wrote:
Matias Capeletto wrote: My opinion is that you should have a constructor which takes a std::map, where the types of the map are the types of the bimap. If the types of the map are the same as the types of the bimap, then the constructor should do exactly the equivalent to what you show just above. If the types of the map are the reverse of the types of the bimap, then the constructor should be the equivalent of:
std::map<std::string,int> myMap; // ... fill myMap boost::bimap<int,std::string> myBimap; myBimap.right.insert(myMap.begin(),myMap.end());
This is an ease of use issue and I really do not see why you can not make the use of bimap easier to use in this way. Especially since you also agree that this is a very common scenario.
I understand your easy-of-use point, but you have just wrote down here why it is not a good idea to provide this constructor. Not only it breaks the symmetry, the real problem is that following your idea of automatic conversion between pairs and relations we bump into ambiguities. Imagine you now have a bimap<A,A>, and you use your constructor with a map<A,A>... it is not clear which side is the left and which side is the right.
Are you saying that if I insert map items on the left side of a bimap I can not access them from the right side of the bimap, or vice versa ? That would seem to make the bimap fairly useless. If not, in your example of bimap<A,A> and map<A,A> it should make no difference whatever into which side the map pairs are originally inserted.
I thought about this issues and it was decided that it is better not to surprise the user with this kind of ambiguities. Thanks for your suggestion and interest.
On Wed, Nov 25, 2009 at 6:08 PM, Edward Diener <eldiener@tropicsoft.com> wrote:
Matias Capeletto wrote:
... you have just wrote down here why it is not a good idea to provide this constructor. Not only it breaks the symmetry, the real problem is that following your idea of automatic conversion between pairs and relations we bump into ambiguities. Imagine you now have a bimap<A,A>, and you use your constructor with a map<A,A>... it is not clear which side is the left and which side is the right.
Are you saying that if I insert map items on the left side of a bimap I can not access them from the right side of the bimap, or vice versa ? That would seem to make the bimap fairly useless. If not, in your example of bimap<A,A> and map<A,A> it should make no difference whatever into which side the map pairs are originally inserted.
I am not saying that. The problem is that If you have a std::map<int,int> m; with the elements (1,10), (2,20), (3,30), (4,40), and you code: boost::bimap<int,int> bm( m ); It is ambiguous, you just have to choose to view the map as the left view of the bimap or as the right one, and the only way to get out of this problem is to give one of the views priority over the other one which goes against the design of the library... or to ask the users to explicitly show their intention: boost::bimap<int,int> bm(); bm.left.insert( m.begin(), m.end() ); Regards Matias
Matias Capeletto wrote:
On Wed, Nov 25, 2009 at 6:08 PM, Edward Diener <eldiener@tropicsoft.com> wrote:
... you have just wrote down here why it is not a good idea to provide this constructor. Not only it breaks the symmetry, the real problem is that following your idea of automatic conversion between pairs and relations we bump into ambiguities. Imagine you now have a bimap<A,A>, and you use your constructor with a map<A,A>... it is not clear which side is the left and which side is the right. Are you saying that if I insert map items on the left side of a bimap I can not access them from the right side of the bimap, or vice versa ? That would seem to make the bimap fairly useless. If not, in your example of bimap<A,A> and map<A,A> it should make no difference whatever into which side the map
Matias Capeletto wrote: pairs are originally inserted.
I am not saying that. The problem is that If you have a std::map<int,int> m; with the elements (1,10), (2,20), (3,30), (4,40), and you code:
boost::bimap<int,int> bm( m );
It is ambiguous, you just have to choose to view the map as the left view of the bimap or as the right one, and the only way to get out of this problem is to give one of the views priority over the other one which goes against the design of the library... or to ask the users to explicitly show their intention:
boost::bimap<int,int> bm(); bm.left.insert( m.begin(), m.end() );
But if I do the above I can still access the bimap from either the left or right views. So it little matters which one I use to actually insert my map entries. Whether I go: bm.left.insert( m.begin(), m.end() ); or bm.right.insert( m.begin(), m.end() ); ,when both types are the same, is totally irrelevant to further use of the bimap. Is this not correct ? So therefore if you create a bimap constructor which takes a map, and both types are exactly the same, it is irrelevant if internally you use bm.left.insert( m.begin(), m.end() ); or bm.right.insert( m.begin(), m.end() ); to populate the bimap. Therefore your argument that having to decide how to populate the bimap from a map, when both types are the same, is a reason not to create a constructor which takes a map is not valid to me.
On Wed, Nov 25, 2009 at 5:35 PM, Edward Diener <eldiener@tropicsoft.com> wrote:
Whether I go:
bm.left.insert( m.begin(), m.end() );
or
bm.right.insert( m.begin(), m.end() );
,when both types are the same, is totally irrelevant to further use of the bimap. Is this not correct ?
No, it is not correct. A bimap is a mapping between two sets of elements (named the left set, and the right set) that can be viewed as a std map<L,R> or as a std map<R, L>. In this particular example both sets hold elements of the same type but which one is the left and which one is the right matters. Imagine that you need a mapping between names and surnames (bimap<tagged<string,name>,tagged<string,surname> >), and you want to insert from a std::map<string,string> that maps from surnames to names. I hope it is more clear now. Regards Matias
I am not sure wether I understand this whole discussion, but I think that I do so I would like Edward to consider this: Suppose you have a std::map<int, int> m with the elements (1,10), (2,20), (3,20), (4,20), (5,30), and you code: Boost::bimap<int,int> bm(m); Now what?? Regards Lex
-----Oorspronkelijk bericht----- Van: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] Namens Matias Capeletto Verzonden: Wednesday, 25 November 2009 23:50 Aan: boost-users@lists.boost.org Onderwerp: Re: [Boost-users] [bimap] Creating a bimap fom a std::map
Whether I go:
bm.left.insert( m.begin(), m.end() );
or
bm.right.insert( m.begin(), m.end() );
,when both types are the same, is totally irrelevant to further use of
On Wed, Nov 25, 2009 at 5:35 PM, Edward Diener <eldiener@tropicsoft.com> wrote: the
bimap. Is this not correct ?
No, it is not correct. A bimap is a mapping between two sets of elements (named the left set, and the right set) that can be viewed as a std map<L,R> or as a std map<R, L>. In this particular example both sets hold elements of the same type but which one is the left and which one is the right matters. Imagine that you need a mapping between names and surnames (bimap<tagged<string,name>,tagged<string,surname> >), and you want to insert from a std::map<string,string> that maps from surnames to names. I hope it is more clear now. Regards Matias _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Lex Wassenberg wrote:
I am not sure wether I understand this whole discussion, but I think that I do so I would like Edward to consider this:
Suppose you have a std::map<int, int> m with the elements (1,10), (2,20), (3,20), (4,20), (5,30), and you code: Boost::bimap<int,int> bm(m);
Now what??
Bimap automatically adds the map data to the left side of the bimap. If any data can not be added, such as the (3,20), (4,20), it acts in exactly the same fashion as it normally would when one tries to insert a data pair which is not distinct both ways. My point is that I wanted a constructor as above: Boost::bimap<int,int> bm(m); to do essentially: bm.left.insert(m.begin(),m.end()); Evidently the implementor of bimap does not agree so I have chosen not to pursue this suggestion any further. But I doubt I will be the last person suggesting this.
Regards
Lex
-----Oorspronkelijk bericht----- Van: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] Namens Matias Capeletto Verzonden: Wednesday, 25 November 2009 23:50 Aan: boost-users@lists.boost.org Onderwerp: Re: [Boost-users] [bimap] Creating a bimap fom a std::map
Whether I go:
bm.left.insert( m.begin(), m.end() );
or
bm.right.insert( m.begin(), m.end() );
,when both types are the same, is totally irrelevant to further use of
On Wed, Nov 25, 2009 at 5:35 PM, Edward Diener <eldiener@tropicsoft.com> wrote: the
bimap. Is this not correct ? No, it is not correct. A bimap is a mapping between two sets of elements (named the left set, and the right set) that can be viewed as a std map<L,R> or as a std map<R, L>. In this particular example both sets hold elements of the same type but which one is the left and which one is the right matters. Imagine that you need a mapping between names and surnames (bimap<tagged<string,name>,tagged<string,surname> >), and you want to insert from a std::map<string,string> that maps from surnames to names. I hope it is more clear now. Regards Matias
Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
2009/11/25 Edward Diener <eldiener@tropicsoft.com>
Yes, of course. See above. I just do not agree that not providing the obvious constructor is good because it "maintains symmetry". Many things in programming are good because they provide ease-of-use and my suggestion is an obvious case of that.
In my opinion the constructor you propose is not obvious, but rather very subtle. Explicit 'left' or 'right' during the conversion from std::map makes the intent more explicit and thus improves readability. I do understand that it might be a matter of personal preference. Roman Perepelitsa.
participants (4)
-
Edward Diener -
Lex Wassenberg -
Matias Capeletto -
Roman Perepelitsa