Hi Matias, First of all I would like to say it's nice to see how well the SoC went. Since I was one who pushed for this library, I guess I should do a review. And it has been a pleasure to do so. I think this library really shows the benefit of wrapping a fairly difficult library (now we just need someone to do it for boost.graph :-)). ******************************************************** ** I think this library should be accepted into boost! * ******************************************************** Here's a list of things I feel strongly about changing (see below for info): - relation should have the same members as std::pair - types should lie with members, so map::left_type::iterator i = m.left.begin() instead of map::left_iterator i = m.left.begin() - operator()[] seems way to complicatedly specified and does not follow the promise of mirroring STL. Keep the mutable operator()[] and then add value& map.at( const key& ); const value& map.at( const key& ) const; which throws on lookup failure. - reconsider modify/replace design: I suggest that you provide three functions: replace( it, key, value ); replace_key( it, key ); replace_value( it, value ); the last two should be optimally efficient and strongly exception-safe. Great work Matias! * -Thorsten - What is your evaluation of the design? ---------------------------------------- Generally clean, sound and intuitive. - What is your evaluation of the implementation? ------------------------------------------------ Did not look much. - What is your evaluation of the documentation? ----------------------------------------------- Really nice, maybe even a tad too graphical compared to the rest of boost. Very thorough. - What is your evaluation of the potential usefulness of the library? --------------------------------------------------------------------- High. - Did you try to use the library? With what compiler? Did you have any problems? ---------------------------------------------------------------------- No. - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? --------------------------------------------------------------------- Several hours study of the documentation. - Are you knowledgeable about the problem domain? ------------------------------------------------- Fairly. I know a lot about datastructures and good design. General comments ---------------- 1. This statement: "The relation class is a generalization of std::pair. The two values are named left and right to express the symmetry of this type." It might be better to stay signature compatible with std::pair if you can. Boost.PtrMap initially started out without signature compatibility, but is now fixed to be that after user complaints. Subsequently there is no need for a relation nested type as one can simply use value_type. 2. using namespace bimap; should be boost::bimap. 3. consider adding insert( const key&, const key2& ) for performance and ease-of-use reasons. 4. In "Standard mapping framework" "Note that the type of the collection of X is a set because we have chosen a map for the example" This is somewhat comfusing to use "type". "The X (key) values form a set of unique values" or something. The terminology could be sharper here. 5. "The two collections are then at the same level, so it is incorrect to name them as first`second` or `a`b. These names clearly impose an ordering on the two values." Again, I think it is more imporant for generic algortihms ect to stay with the std::pair layout. 6. Consider adding support for lookup/inserttion with types that are convertible to the key type (as a performance improvement). 7. "HashFunctor converts a T object into an integer value". Shouldn't that be "unsigned integer"? 8. "The code produced in this fashion tends ". It is not explained what "this fasion means". Put the definition earlier. 9. I find it somewhat assymetrical that in people.right.insert( People::right_value_type("Marta Smith",30215692) ); the types come from People, but the function is called from .right. Why are these types not avaiable as People::LeftType::value_type etc?? 10. Could map_by<id>(people)[28928546] be spelled people.by<id>()[28928546] ? It seems simpler to use and specify to me. 11. In " // Search the queried word on the from index (Spanish) */ iterator_type_by<spanish,translator_bimap>::type is = map_by<spanish>(d).find(word); " where is d declared??? 12. Should bool operator()(Rel ra, Rel rb) not be bool operator()(Rel ra, Rel rb) const ?? 13. In set_of_relation< RelOrder<_relation> > _relation is not explained? 14. Consider addding value& map.at( const key& ); const value& map.at( const key& ); to complement operator[]() (The C++ language draft already has these) 15. Should typedef bimap< int, std::string > bm_type; bm_type bm; bm[1] = "one"; bm[2] = "two"; not be bm.left[1] = ...; etc?? 16. replace: "The complexity is constant time if the changed element retains its original order with respect to all views; it is logarithmic otherwise." Does the cimplexity not depend on the left and right type??? 17. use namespace prefix foe boost::assign::list_of to avoid confusion.
Thorsten Ottosen wrote:
Here's a list of things I feel strongly about changing (see below for info):
- relation should have the same members as std::pair
Maybe, I quite like the systematic use of left and right personally.
- types should lie with members, so
map::left_type::iterator i = m.left.begin()
instead of
map::left_iterator i = m.left.begin()
Isn't that true now? Or rather that both are possible currently? My only comment is that it's a lot easier to write: typedef typename map::left_iterator it_type; than: typedef typename map::left_type left_type; typedef typename left_type::iterator it_type; So I would go with both.
- operator()[] seems way to complicatedly specified and does not follow the promise of mirroring STL. Keep the mutable operator()[] and then add
value& map.at( const key& ); const value& map.at( const key& ) const;
which throws on lookup failure.
I found that section confusing as well, anything simpler would be welcome. John.
John Maddock wrote:
Thorsten Ottosen wrote:
Here's a list of things I feel strongly about changing (see below for info):
- relation should have the same members as std::pair
Maybe, I quite like the systematic use of left and right personally.
Isn't the members required if we want to be signature compatible with std containers? As it stands now, we are signature compatible for a certain set f member functions, but not for iterators.
- types should lie with members, so
map::left_type::iterator i = m.left.begin()
instead of
map::left_iterator i = m.left.begin()
Isn't that true now? Or rather that both are possible currently?
My only comment is that it's a lot easier to write:
typedef typename map::left_iterator it_type;
than:
typedef typename map::left_type left_type; typedef typename left_type::iterator it_type;
So I would go with both.
Perhaps that is ok. -Thorsten
On 2/22/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Hi Matias,
First of all I would like to say it's nice to see how well the SoC went. Since I was one who pushed for this library, I guess I should do a review. And it has been a pleasure to do so. I think this library really shows the benefit of wrapping a fairly difficult library (now we just need someone to do it for boost.graph :-)).
I am pleased you enjoy it.
******************************************************** ** I think this library should be accepted into boost! * ********************************************************
Nice vote!
Here's a list of things I feel strongly about changing (see below for info):
- relation should have the same members as std::pair
What are the use cases where left/right will not be appropriate?
- types should lie with members, so
map::left_type::iterator i = m.left.begin()
instead of
map::left_iterator i = m.left.begin()
It is implemented in this way. typedef bimap<int, float> bm_type; bm_type bm; ... bm_type::left_map_type::iterator i = bm.left.begin(); bimap defines shortcuts to make life easier. bm_type::left_iterator i = bm.left.begin(); ¿Do you see this as interface bloat? You can use the following metafunction too: iterator_type_by<menber_at::left,bm_type>::type i = bm.left.begin(); This is very handy with the aid of tags iterator_type_by<phone_number,bm_type>::type i = map_by<phone_number>(bm).begin();
- operator()[] seems way to complicatedly specified and does not follow the promise of mirroring STL.
I repost some thoughts about this: "In the STL unique associative containers (like std::map), operator[] first makes an insertion if the key element was not in the container. In addition, the container has no constraints in the data types, so it is an operation that never fails. We want to maintain a coherent behaviour between the extended mapping framework and the quite established STL one-side-oriented one, and that imply respecting in the best possible way each operation. For example, an insertion in a map view of a bimap may failed because the there are conflicts with the constraints from the other side. The standard insertion returns false when it fails, so it is very straight forward to extend it to the new framework. operator[] on the other hand, is quite a challenge. There are several possible ways to extend it. We (In fact, my mentor make me change my original implementation) opted for the most conservative implementation. When operator[] does not behaves exactly as the original counterpart, an exception is thrown." What are the things about it you feel complicated? If you try to add a new relation to the bimap using: bm.left[a] = b; If b breaks the invariants in the right set, you have various options: 1) reject the new relation and don´t let the user know about that. 2) insert the new relation and eliminate others to fulfill the bimap invariants. The user is not informed of this. 3) throw a "duplicate_value" exception. Either of this option are compatible with the STL behaviour and the last one is the only one where the user is not allowed to use the bimap in a way different from the standard maps. If you try to use it with a value that is not present in the bimap, if you follow the STL and add a default value there are chances that you get a "duplicate_value" exception which would be very confusing.
Keep the mutable operator()[] and then add
value& map.at( const key& ); const value& map.at( const key& ) const;
which throws on lookup failure.
Ok, this function must be added but I think that in the case of bimap operator[]() and at() will work in the same way.
- reconsider modify/replace design: I suggest that you provide three functions:
replace( it, key, value ); replace_key( it, key ); replace_value( it, value );
the last two should be optimally efficient and strongly exception-safe.
Let me think about how you they can be implemented.
General comments ----------------
1. This statement: "The relation class is a generalization of std::pair. The two values are named left and right to express the symmetry of this type."
It might be better to stay signature compatible with std::pair if you can. Boost.PtrMap initially started out without signature compatibility, but is now fixed to be that after user complaints.
In general you can use the left view to achieve std::pair compatibility. I feel that this change will make the interface
Subsequently there is no need for a relation nested type as one can simply use value_type.
That is true and it can be eliminated. It is another shortcut. I like how this code looks bm.insert( bm_t::relation(1,"one") ); But the other way is not that bad either bm.insert( bm_t::value_type(1,"one") );
2. using namespace bimap; should be boost::bimap.
Ok.
3. consider adding
insert( const key&, const key2& )
for performance and ease-of-use reasons.
It may be a good idea but to insert the the relation I have to use Boost.MultiIndex functions, so the performance will be the same. About ease-of-use, I agree with you. bm.insert( 1 , "one" ); bm.insert( bm_t::relation(1,"one") ); But we must ask ourselves why standard maps do not define this function.
4. In "Standard mapping framework"
"Note that the type of the collection of X is a set because we have chosen a map for the example"
This is somewhat comfusing to use "type". "The X (key) values form a set of unique values" or something. The terminology could be sharper here.
Yes, maybe -type of the collection- could be replaced by -set type-
5. "The two collections are then at the same level, so it is incorrect to name them as first`second` or `a`b. These names clearly impose an ordering on the two values." Again, I think it is more imporant for generic algortihms ect to stay with the std::pair layout.
6. Consider adding support for lookup/inserttion with types that are convertible to the key type (as a performance improvement).
That is in my TODO (and wish) list but it is not easy.
7. "HashFunctor converts a T object into an integer value". Shouldn't that be "unsigned integer"?
It has to be size_t, that will be corrected.
8. "The code produced in this fashion tends ". It is not explained what "this fasion means". Put the definition earlier.
Yep, It will be changed.
9. I find it somewhat assymetrical that in
people.right.insert( People::right_value_type("Marta Smith",30215692) );
the types come from People, but the function is called from .right.
Why are these types not avaiable as
People::LeftType::value_type
You can write it as: people.right.insert( People::right_map_type::value_type("Marta Smith",30215692) ); The other way is provided as a shortcut.
10. Could
map_by<id>(people)[28928546]
be spelled
people.by<id>()[28928546]
? It seems simpler to use and specify to me.
Maybe we can provided both of them. mmmm... It can be interface bloat. I prefer the use of free functions. Let see what other people think about this.
11. In
" // Search the queried word on the from index (Spanish) */
iterator_type_by<spanish,translator_bimap>::type is = map_by<spanish>(d).find(word); "
where is d declared???
It is a typo. I will correct it.
12. Should
bool operator()(Rel ra, Rel rb)
not be
bool operator()(Rel ra, Rel rb) const
Yes. Will correct it.
13. In
set_of_relation< RelOrder<_relation> >
_relation is not explained?
14. Consider addding
value& map.at( const key& ); const value& map.at( const key& );
to complement operator[]() (The C++ language draft already has these)
Ok.
15. Should
typedef bimap< int, std::string > bm_type; bm_type bm; bm[1] = "one"; bm[2] = "two";
not be
bm.left[1] = ...;
etc??
Yes, thanks for spotting that typo.
16. replace:
"The complexity is constant time if the changed element retains its original order with respect to all views; it is logarithmic otherwise."
Does the cimplexity not depend on the left and right type???
That statement is about the bidirectional map of the example. It is confusing to leave it that way. The complexity depends on the selected set types, I will include a pointer to the following section where it is explained how to calculate the complexity of an operation: http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/boost_bimap/referen... For example, when you insert an element in a left set_of view you have O(I(n)) complexity, where I(n) = i_lelf(n) + i_right(n) i_left(n) = log(n) because it is a set_of i_right(n) depends on the other side.
17. use namespace prefix foe boost::assign::list_of to avoid confusion.
Ok. That is a good idea. Thanks a lot for your review Best Regards Matias
Matias Capeletto wrote:
On 2/22/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Here's a list of things I feel strongly about changing (see below for info):
- relation should have the same members as std::pair
What are the use cases where left/right will not be appropriate?
It all boils down to reuse of existing algorithms/code/functions that assumes the existing of .first/.second etc. All this code has to wrap code from this library. I personally don't feel the use of std::pair in the standard is very well-thought out, but it is standard, and it is is easier for users to remember one ugly way than one ugly way and N good ways.
- types should lie with members, so
map::left_type::iterator i = m.left.begin()
instead of
map::left_iterator i = m.left.begin()
It is implemented in this way.
typedef bimap<int, float> bm_type; bm_type bm; ... bm_type::left_map_type::iterator i = bm.left.begin();
bimap defines shortcuts to make life easier.
bm_type::left_iterator i = bm.left.begin();
¿Do you see this as interface bloat?
I was slightly thinking that. Whenever I meet a new name, I'm certain that it requires a look into the documentation to see if this is a new type of iterator or whatever it it is.
- operator()[] seems way to complicatedly specified and does not follow the promise of mirroring STL.
I repost some thoughts about this:
"In the STL unique associative containers (like std::map), operator[] first makes an insertion if the key element was not in the container. In addition, the container has no constraints in the data types, so it is an operation that never fails. We want to maintain a coherent behaviour between the extended mapping framework and the quite established STL one-side-oriented one, and that imply respecting in the best possible way each operation. For example, an insertion in a map view of a bimap may failed because the there are conflicts with the constraints from the other side. The standard insertion returns false when it fails, so it is very straight forward to extend it to the new framework. operator[] on the other hand, is quite a challenge. There are several possible ways to extend it. We (In fact, my mentor make me change my original implementation) opted for the most conservative implementation. When operator[] does not behaves exactly as the original counterpart, an exception is thrown."
What are the things about it you feel complicated?
The fact that return types are very different from mutable to const version. And the specification of the operator seems way too complicated.
If you try to add a new relation to the bimap using:
bm.left[a] = b;
If b breaks the invariants in the right set, you have various options: 1) reject the new relation and don´t let the user know about that. 2) insert the new relation and eliminate others to fulfill the bimap invariants. The user is not informed of this. 3) throw a "duplicate_value" exception.
Either of this option are compatible with the STL behaviour and the last one is the only one where the user is not allowed to use the bimap in a way different from the standard maps.
If you try to use it with a value that is not present in the bimap, if you follow the STL and add a default value there are chances that you get a "duplicate_value" exception which would be very confusing.
I think I'm ok with your mutable version of operator[](). Keep that, but seek to simplify .... more below.
Keep the mutable operator()[] and then add
value& map.at( const key& ); const value& map.at( const key& ) const;
which throws on lookup failure.
Ok, this function must be added but I think that in the case of bimap operator[]() and at() will work in the same way.
Well, the standard did not add const_reference operator[]( key ) const because it can't behave the same way as the mutable version. Neither can it in the bimap. But the lookup function is useful, so therefore the stdnard draft added st(). If the mutable version of at() is impossible/breaks invariants in bimap, then only provide non-mutable at() that throws value_not_found. Now for operator[](). It might be ok to return a proxy "reference" for the mutable version. But the more I look at it, the less inelegant I find the specification. Reading should be taken care of by at(), so the conversion is not needed anymore. That leaves only assignment. This makes me wonder why you said this:
if you follow the STL and add a default value there are chances that you get a "duplicate_value" exception which would be very confusing.
Why is that particularly confusing compared to the whole proxy-reference business? I think I'm leaning slightly towards not providid operatot[]() at all. Perhaps you can simply add mapped_type& insert( const key_type& key, const mapped_type& value ); ?
General comments ----------------
1. This statement: "The relation class is a generalization of std::pair. The two values are named left and right to express the symmetry of this type."
It might be better to stay signature compatible with std::pair if you can. Boost.PtrMap initially started out without signature compatibility, but is now fixed to be that after user complaints.
In general you can use the left view to achieve std::pair compatibility. I feel that this change will make the interface
bad? Maybe I missed how one would use this view. How exactly (and which page in the documentation?)
3. consider adding
insert( const key&, const key2& )
for performance and ease-of-use reasons.
It may be a good idea but to insert the the relation I have to use Boost.MultiIndex functions, so the performance will be the same.
Well, not if Boost.MultiIndex adds this function too :-)
About ease-of-use, I agree with you. bm.insert( 1 , "one" ); bm.insert( bm_t::relation(1,"one") ); But we must ask ourselves why standard maps do not define this function.
In some sense it is redundant, and you can do without it. The standard tried to minimize such redundacy for easy of specification, not for ease of use IMO. Thus they don't provide container.contains( value ); , but only container.count( value ); I also assume that the most frequent types are built-in ones where the penalty is not high for copying. But it certainly is for many user-defined types. To make matters worse, std::make_pair() takes it's arguments by value.
6. Consider adding support for lookup/inserttion with types that are convertible to the key type (as a performance improvement).
That is in my TODO (and wish) list but it is not easy.
I can imagine :-)
10. Could
map_by<id>(people)[28928546]
be spelled
people.by<id>()[28928546]
? It seems simpler to use and specify to me.
Maybe we can provided both of them. mmmm... It can be interface bloat.
It would be kinda bloat if both are provided.
I prefer the use of free functions. Let see what other people think about this.
Right. I just asked myself what other arguments than a bimap does this function takes? If the answer is none, then it serves no purpose to make it a free function. -Thorsten
On 2/23/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Matias Capeletto wrote:
On 2/22/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Here's a list of things I feel strongly about changing (see below for info):
- relation should have the same members as std::pair
What are the use cases where left/right will not be appropriate?
It all boils down to reuse of existing algorithms/code/functions that assumes the existing of .first/.second etc.
All this code has to wrap code from this library.
I personally don't feel the use of std::pair in the standard is very well-thought out, but it is standard, and it is is easier for users to remember one ugly way than one ugly way and N good ways.
The above view it is not provided to work smoothly with std::maps. It is a new way of viewing a mapping using set semantics. That is why I think we are not forced to use first/second for it. What is more, we should use a notation that express the difference between the above and side views. Side views are signature compatible with standard map containers. In side views we use first/second notation. That is why I said you can reuse your algorithms and generic code.
"The relation class is a generalization of std::pair. The two values are named left and right to express the symmetry of this type."
It might be better to stay signature compatible with std::pair if you can. Boost.PtrMap initially started out without signature compatibility, but is now fixed to be that after user complaints.
In general you can use the left view to achieve std::pair compatibility. I feel that this change will make the interface bad?
sorry for the missed words... I feel that this change will make the interface of the above view be confused with the side views.
Maybe I missed how one would use this view. How exactly (and which page in the documentation?)
Maybe I have introduce noise here. The left view is the bidirectional mapping view from the left, the one obtained with bm.left bimap<X,Y>::left_map_type is signature compatible with std::map<X,Y>. bimap<X,Y>::left_map_type::value_type is signature-compatible with std::pair<X,Y> and bimap<X,Y>::right_map_type::value_type is signature-compatible with std::pair<Y,X> So you can use this view or the right one with generic algorithms that need first/second members.
typedef bimap<int, float> bm_type; bm_type bm; ... bm_type::left_map_type::iterator i = bm.left.begin();
bimap defines shortcuts to make life easier.
bm_type::left_iterator i = bm.left.begin();
¿Do you see this as interface bloat?
I was slightly thinking that. Whenever I meet a new name, I'm certain that it requires a look into the documentation to see if this is a new type of iterator or whatever it it is.
In this particular case I think that the shortcut is worthy.
- operator()[] seems way to complicatedly specified and does not follow the promise of mirroring STL.
(...)
What are the things about it you feel complicated?
The fact that return types are very different from mutable to const version. And the specification of the operator seems way too complicated.
I am starting to think that you are right about this.
If you try to add a new relation to the bimap using:
bm.left[a] = b;
If b breaks the invariants in the right set, you have various options: 1) reject the new relation and don´t let the user know about that. 2) insert the new relation and eliminate others to fulfill the bimap invariants. The user is not informed of this. 3) throw a "duplicate_value" exception.
Either of this option are compatible with the STL behaviour and the last one is the only one where the user is not allowed to use the bimap in a way different from the standard maps.
If you try to use it with a value that is not present in the bimap, if you follow the STL and add a default value there are chances that you get a "duplicate_value" exception which would be very confusing.
I think I'm ok with your mutable version of operator[](). Keep that, but seek to simplify .... more below.
Keep the mutable operator()[] and then add
value& map.at( const key& ); const value& map.at( const key& ) const;
which throws on lookup failure.
Ok, this function must be added but I think that in the case of bimap operator[]() and at() will work in the same way.
Well, the standard did not add
const_reference operator[]( key ) const
because it can't behave the same way as the mutable version. Neither can it in the bimap. But the lookup function is useful, so therefore the stdnard draft added st(). If the mutable version of at() is impossible/breaks invariants in bimap, then only provide non-mutable at() that throws value_not_found.
Ok, you are right. I think we can provide the non-mutable version of at() without any problem. The mutable version of at() can be provided only for bimaps where the other view is a list_of, vector_of or unconstrained_set_of because the mapped elements can be modified with out breaking invariants.
Now for operator[](). It might be ok to return a proxy "reference" for the mutable version. But the more I look at it, the less inelegant I find the specification.
Reading should be taken care of by at(), so the conversion is not needed anymore. That leaves only assignment. This makes me wonder why you said this:
if you follow the STL and add a default value there are chances that you get a "duplicate_value" exception which would be very confusing.
Why is that particularly confusing compared to the whole proxy-reference business?
I felt it odd that the following line could throw duplicate_value. if( bm.left[1] != "two" ) { ... } But it is wrong because at() has to be used here instead of operator[]. The non-mutable version of operator[] will be eliminated.
I think I'm leaning slightly towards not providid operatot[]() at all. ?
I have to think which will be the destiny of the mutable one, IMO users will expect it to be there. Now that at() will be included it maybe easier to convince them that they are better with out operator[]. It is a big decision, let me think about it.
Perhaps you can simply add
mapped_type& insert( const key_type& key, const mapped_type& value );
This function will be dificult to specifie too, it may throw for example. IMO it is not necesary to include anything else if we decided to eliminate operator[].
3. consider adding
insert( const key&, const key2& )
for performance and ease-of-use reasons.
It may be a good idea but to insert the the relation I have to use Boost.MultiIndex functions, so the performance will be the same.
Well, not if Boost.MultiIndex adds this function too :-)
That will not be possible, because Boost.MultiIndex works with general structures not with two values. :( This maybe one of the exotic places of bimap where you feel the price of wrapping a generic component. But it is a very small price to pay.
About ease-of-use, I agree with you. bm.insert( 1 , "one" ); bm.insert( bm_t::relation(1,"one") ); But we must ask ourselves why standard maps do not define this function.
In some sense it is redundant, and you can do without it. The standard tried to minimize such redundacy for easy of specification, not for ease of use IMO. Thus they don't provide
container.contains( value );
, but only
container.count( value );
I also assume that the most frequent types are built-in ones where the penalty is not high for copying. But it certainly is for many user-defined types.
To make matters worse, std::make_pair() takes it's arguments by value.
But std::make_pair can not be used with bimaps. The pairs that bimap uses in its side views have a member named first and a member named second, so they can be used in generic algorithms/code/functions that works with map iterators or generic pairs. To be sure we are talking about the same thing, it does not impose that std::pairs and bimap pairs can be converted between each other.
10. Could
map_by<id>(people)[28928546]
be spelled
people.by<id>()[28928546]
? It seems simpler to use and specify to me.
Maybe we can provided both of them. mmmm... It can be interface bloat.
It would be kinda bloat if both are provided.
I prefer the use of free functions. Let see what other people think about this.
Right. I just asked myself what other arguments than a bimap does this function takes? If the answer is none, then it serves no purpose to make it a free function.
Do you want to put all the free functions inside bimap? map_by<>() xxx_iterator_by<>() We have functions like reverse_iterator_by<Side>(Bimap) that have no meaning in all the cases, and may be trickier to implement. If we go down this way, we will maybe think that it is better to write rel.get<id>() instead of get<id>(rel) In this case the get function works for relations and for the pairs of the bimap views. You can write: get<id>( *bm.begin() ) get<id>( *bm.left.begin() ) get<id>( *bm.right.begin() ) In the end, it may be simpler to implement it with member function instead of free functions. I do not think that the interface is cleaner with them, but it is an idea we can play with. Best Regards Matias
Matias Capeletto wrote:
On 2/23/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Maybe I missed how one would use this view. How exactly (and which page in the documentation?)
Maybe I have introduce noise here. The left view is the bidirectional mapping view from the left, the one obtained with bm.left
bimap<X,Y>::left_map_type is signature compatible with std::map<X,Y>. bimap<X,Y>::left_map_type::value_type is signature-compatible with std::pair<X,Y> and bimap<X,Y>::right_map_type::value_type is signature-compatible with std::pair<Y,X>
So you can use this view or the right one with generic algorithms that need first/second members.
I missed that. It seems like there is less to worry about then :-) I'm still slightly sceptical about the benefit of having both typedef bimap::relation relation; and typedef bimap::left_value_type; is the potential confusion really worth the trouble? Take this example: typedef bimap<std::string,int> results_bimap; typedef results_bimap::relation position; results_bimap results; results.insert( position("Argentina" ,1) ); results.insert( position("Spain" ,2) ); results.insert( position("Germany" ,3) ); results.insert( position("France" ,4) ); I could not find any documentation on direct members of a bimap. Should it read results.left.insert()???
I think I'm ok with your mutable version of operator[](). Keep that, but seek to simplify .... more below.
Keep the mutable operator()[] and then add
value& map.at( const key& ); const value& map.at( const key& ) const;
which throws on lookup failure.
Ok, this function must be added but I think that in the case of bimap operator[]() and at() will work in the same way.
Well, the standard did not add
const_reference operator[]( key ) const
because it can't behave the same way as the mutable version. Neither can it in the bimap. But the lookup function is useful, so therefore the stdnard draft added st(). If the mutable version of at() is impossible/breaks invariants in bimap, then only provide non-mutable at() that throws value_not_found.
Ok, you are right. I think we can provide the non-mutable version of at() without any problem. The mutable version of at() can be provided only for bimaps where the other view is a list_of, vector_of or unconstrained_set_of because the mapped elements can be modified with out breaking invariants.
Seems right.
Now for operator[](). It might be ok to return a proxy "reference" for the mutable version. But the more I look at it, the less inelegant I find the specification.
Reading should be taken care of by at(), so the conversion is not needed anymore. That leaves only assignment. This makes me wonder why you said this:
if you follow the STL and add a default value there are chances that you get a "duplicate_value" exception which would be very confusing.
Why is that particularly confusing compared to the whole proxy-reference business?
I felt it odd that the following line could throw duplicate_value. if( bm.left[1] != "two" ) { ... } But it is wrong because at() has to be used here instead of operator[].
The non-mutable version of operator[] will be eliminated.
I think I'm leaning slightly towards not providid operatot[]() at all. ?
I have to think which will be the destiny of the mutable one, IMO users will expect it to be there. Now that at() will be included it maybe easier to convince them that they are better with out operator[]. It is a big decision, let me think about it.
Right, it's a rather important decision. At least consider not making the proxy convertible to mapped_type& (that requires an independent lookup, right).
Perhaps you can simply add
mapped_type& insert( const key_type& key, const mapped_type& value );
This function will be dificult to specifie too, it may throw for example. IMO it is not necesary to include anything else if we decided to eliminate operator[].
3. consider adding
insert( const key&, const key2& )
for performance and ease-of-use reasons.
It may be a good idea but to insert the the relation I have to use Boost.MultiIndex functions, so the performance will be the same.
Well, not if Boost.MultiIndex adds this function too :-)
That will not be possible, because Boost.MultiIndex works with general structures not with two values. :(
I would like to hear Joaquin's take on this. I have trouble understanding why you can't delay construction/assignment of a pair until it is actually needed.
This maybe one of the exotic places of bimap where you feel the price of wrapping a generic component. But it is a very small price to pay.
About ease-of-use, I agree with you. bm.insert( 1 , "one" ); bm.insert( bm_t::relation(1,"one") ); But we must ask ourselves why standard maps do not define this function.
In some sense it is redundant, and you can do without it. The standard tried to minimize such redundacy for easy of specification, not for ease of use IMO. Thus they don't provide
container.contains( value );
, but only
container.count( value );
I also assume that the most frequent types are built-in ones where the penalty is not high for copying. But it certainly is for many user-defined types.
To make matters worse, std::make_pair() takes it's arguments by value.
But std::make_pair can not be used with bimaps.
Right.
The pairs that bimap uses in its side views have a member named first and a member named second, so they can be used in generic algorithms/code/functions that works with map iterators or generic pairs. To be sure we are talking about the same thing, it does not impose that std::pairs and bimap pairs can be converted between each other.
Right. std::make_pair() aside, you are often forced to constructing a pair object, only to copy its data once again upon insertion into the map. This is justification enough for me to add the function. Further justification is then ease of use, the main justification of operator[]().
10. Could
map_by<id>(people)[28928546]
be spelled
people.by<id>()[28928546]
? It seems simpler to use and specify to me.
Maybe we can provided both of them.er der mmmm... It can be interface bloat.
It would be kinda bloat if both are provided.
I prefer the use of free functions. Let see what other people think about this.
Right. I just asked myself what other arguments than a bimap does this function takes? If the answer is none, then it serves no purpose to make it a free function.
Do you want to put all the free functions inside bimap? map_by<>() xxx_iterator_by<>()
We have functions like reverse_iterator_by<Side>(Bimap) that have no meaning in all the cases, and may be trickier to implement.
If we go down this way, we will maybe think that it is better to write rel.get<id>() instead of get<id>(rel)
In this case the get function works for relations and for the pairs of the bimap views.
You can write: get<id>( *bm.begin() ) get<id>( *bm.left.begin() ) get<id>( *bm.right.begin() )
In the end, it may be simpler to implement it with member function instead of free functions. I do not think that the interface is cleaner with them, but it is an idea we can play with.
I don't feel strongly about it. I did however always find it slightly harder to locate members. But the free-standing are more generic in the sense that they accept a bimap concept, should snybody implement their own compatible bimap. -Thorsten
----- Mensaje original ----- De: Thorsten Ottosen <thorsten.ottosen@dezide.com> Fecha: Sábado, Febrero 24, 2007 3:38 pm Asunto: Re: [boost] [Review][bimap] Para: boost@lists.boost.org [...]
3. consider adding
insert( const key&, const key2& )
for performance and ease-of-use reasons.
It may be a good idea but to insert the the relation I have to use Boost.MultiIndex functions, so the performance will be the same.
Well, not if Boost.MultiIndex adds this function too :-)
That will not be possible, because Boost.MultiIndex works with general> structures not with two values. :(
I would like to hear Joaquin's take on this. I have trouble understanding why you can't delay construction/assignment of a pair until it is actually needed.
Hello Thorsten, As Matías says, the more generic nature of Boost.MultiIndex makes it difficult (though probably not impossible) to implement a delayed construction insertion facility. Let me explain the situation: Boost.MultiIndex indices can be classified into key-based (ordered, hashed) and non key-based (sequenced, random access). Among the former, there are unique flavors that don't allow duplicate keys to be entered into the container. Key-based indices have an associated key extractor which can be roughly though of as a functor taking an element and returning its key information. In the case of a bimap consisting of two key-based indices, you have key1(v)==v.left; key2(v)==v.right; where v is of the relation type associated to the bimap. Now consider how we'd have to implement a delayed construction insert facility for B.MI that could particularize well for the bimap case. A first approach to this problem could be to provide an insert member function like this: insert(const key1_type& k1,...,const keym_type& km); where k1,...,km stand for the keys of the m key-based indices of a multi-index container. Leaving aside practical difficulties of how to metaprogram this, there is a fundamental problem: you don't have any guarantee that the actual element value can be constructed from these keys alone; in fact, in general this is not the case (unlike in the case of bimap). A more suitable approach would be the following: template<typename ConstructionInfo> insert( const key1_type& k1,...,const keym_type& km, const ConstructionInfo& info); where info is such that the expression value_type v(info) is well defined. The idea is that info can be used to construct the element once it is determined by using the provided keys that the insertion is not banned and the insertion points have been calculated. In the particular case of bimap, insert(const key1& k1,const key2& k2); would be translated roughly to the following call to B.MI API: insert(k1,k2,std::make_pair(cref(k1),cref(k2)); where there are provisions to convert the pair of references to an actual relation type. Even so, this mechanism implies unwanted temporaries, if you analyze it carefully. So, the problem is far (IMHO) from simple and involves other important and as of yet not completely settled issues like move constructors and extended allocators (see http://www.open- std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html, problem #5). It is something I would love to address, but currently I can't think of a satisfactory way to do it. Suggestions are most welcome :) Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
JOAQUIN LOPEZ MU?Z wrote:
----- Mensaje original ----- De: Thorsten Ottosen <thorsten.ottosen@dezide.com> Fecha: Sábado, Febrero 24, 2007 3:38 pm Asunto: Re: [boost] [Review][bimap] Para: boost@lists.boost.org
[...]
3. consider adding
insert( const key&, const key2& )
for performance and ease-of-use reasons.
It may be a good idea but to insert the the relation I have to use Boost.MultiIndex functions, so the performance will be the same.
Well, not if Boost.MultiIndex adds this function too :-)
That will not be possible, because Boost.MultiIndex works with
general> structures not with two values. :(
I would like to hear Joaquin's take on this. I have trouble understanding why you can't delay construction/assignment of a pair until it is actually needed.
Hello Thorsten,
As Matías says, the more generic nature of Boost.MultiIndex makes it difficult (though probably not impossible) to implement a delayed construction insertion facility. Let me explain the situation: Boost.MultiIndex indices can be classified into key-based (ordered, hashed) and non key-based (sequenced, random access). Among the former, there are unique flavors that don't allow duplicate keys to be entered into the container. Key-based indices have an associated key extractor which can be roughly though of as a functor taking an element and returning its key information. In the case of a bimap consisting of two key-based indices, you have
key1(v)==v.left; key2(v)==v.right;
where v is of the relation type associated to the bimap. Now consider how we'd have to implement a delayed construction insert facility for B.MI that could particularize well for the bimap case. A first approach to this problem could be to provide an insert member function like this:
insert(const key1_type& k1,...,const keym_type& km);
where k1,...,km stand for the keys of the m key-based indices of a multi-index container. Leaving aside practical difficulties of how to metaprogram this, there is a fundamental problem: you don't have any guarantee that the actual element value can be constructed from these keys alone; in fact, in general this is not the case (unlike in the case of bimap).
A more suitable approach would be the following:
template<typename ConstructionInfo> insert( const key1_type& k1,...,const keym_type& km, const ConstructionInfo& info);
where info is such that the expression value_type v(info) is well defined. The idea is that info can be used to construct the element once it is determined by using the provided keys that the insertion is not banned and the insertion points have been calculated. In the particular case of bimap,
insert(const key1& k1,const key2& k2);
would be translated roughly to the following call to B.MI API:
insert(k1,k2,std::make_pair(cref(k1),cref(k2));
where there are provisions to convert the pair of references to an actual relation type. Even so, this mechanism implies unwanted temporaries, if you analyze it carefully.
So, the problem is far (IMHO) from simple and involves other important and as of yet not completely settled issues
I guess my ignorance about the internals of Boost.MI is evident here. Anyway, I can't help think about it this way: 1. boost::bimap<T,U> is implemented in terms of Boost.MI 2. somewhere in this data-structure lies a bunch of T objects and U object 3. upon map.insert( bimap::relation( T(), U() ) ), the T and U object is copied to their respective objects inside the datastructure If that is true, I have a hard time seing how creating a temporary relation() object can make a difference. But, anyway, I believe you JOAQUIN. cheers -Thorsten
----- Mensaje original ----- De: Thorsten Ottosen <thorsten.ottosen@dezide.com> Fecha: Sábado, Febrero 24, 2007 7:49 pm Asunto: Re: [boost] [Review][bimap] Para: boost@lists.boost.org [...]
Anyway, I can't help think about it this way:
1. boost::bimap<T,U> is implemented in terms of Boost.MI
2. somewhere in this data-structure lies a bunch of T objects and U object
The internal data structure stores a bunch of objects of type relation<T,U>. Ts and Us are not allocated separately.
3. upon map.insert( bimap::relation( T(), U() ) ), the T and U object is copied to their respective objects inside the datastructure
B.MI accepts an object, say x, of type relation<T,U>, as an atomic entity, and copies it to its final destination. The positioning of this object in both "views" of the bimap is done according to key extractors such that key1(x)==x.left, key2(x)==x.right. So to speak, B.MI does not know about the internal structure of relation<T,U>: the element object is treated as an unanalyzed entity from which keys are extracted using the appropriate key extractors.
If that is true, I have a hard time seing how creating a temporary relation() object can make a difference.
I hope the above clarifies the situation. If this is not the case, please don't hesitate to come back to me. I know my English is a barrier to explaning subtle concepts clearly. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
JOAQUIN LOPEZ MU?Z wrote:
----- Mensaje original -----
So, the problem is far (IMHO) from simple and involves other important and as of yet not completely settled issues like move constructors and extended allocators (see http://www.open- std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html, problem #5).
Ok, so the problem is essentially cause by the lack of contruction functions for the allocator. And placement new + ~T() + allocate() + deallocate() is not a viable approach to avoid using construct()/destroy()? -Thorsten
Thorsten Ottosen wrote:
JOAQUIN LOPEZ MU?Z wrote:
----- Mensaje original -----
So, the problem is far (IMHO) from simple and involves other important and as of yet not completely settled issues like move constructors and extended allocators (see http://www.open- std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html, problem #5).
Ok, so the problem is essentially cause by the lack of contruction functions for the allocator.
And placement new + ~T() + allocate() + deallocate() is not a viable approach to avoid using construct()/destroy()?
JOAQUIN, Do you know why placement new is insufficient? -Thorsten
Thorsten Ottosen ha escrito:
Thorsten Ottosen wrote:
JOAQUIN LOPEZ MU?Z wrote:
----- Mensaje original -----
So, the problem is far (IMHO) from simple and involves other important and as of yet not completely settled issues like move constructors and extended allocators (see http://www.open- std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html, problem #5).
Ok, so the problem is essentially cause by the lack of contruction functions for the allocator.
And placement new + ~T() + allocate() + deallocate() is not a viable approach to avoid using construct()/destroy()?
JOAQUIN,
Do you know why placement new is insufficient?
Hello Thorsten, excuse my skipping your previous mail, I didn't notice it. Umm... yes, the problem boils down to lack of extended construction functions and could be in principle overcome by not using the allocator and relying on placement new instead. Let me consider this with care. I'll put this issue of delayed construction insertion in my "to study" list. Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On 2/24/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Matias Capeletto wrote:
On 2/23/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Maybe I missed how one would use this view. How exactly (and which page in the documentation?)
Maybe I have introduce noise here. The left view is the bidirectional mapping view from the left, the one obtained with bm.left
bimap<X,Y>::left_map_type is signature compatible with std::map<X,Y>. bimap<X,Y>::left_map_type::value_type is signature-compatible with std::pair<X,Y> and bimap<X,Y>::right_map_type::value_type is signature-compatible with std::pair<Y,X>
So you can use this view or the right one with generic algorithms that need first/second members.
I missed that. It seems like there is less to worry about then :-)
Take this example:
typedef bimap<std::string,int> results_bimap; typedef results_bimap::relation position;
results_bimap results; results.insert( position("Argentina" ,1) ); results.insert( position("Spain" ,2) ); results.insert( position("Germany" ,3) ); results.insert( position("France" ,4) );
I could not find any documentation on direct members of a bimap. Should it read results.left.insert()???
No, there is some confusion here. The documentation will have to be changed to help grasp the essence of bimap easier. Fernando Cacciola has proposed some useful changes to the docs. A bimap is a data structure that can be used from various point of view. Suppose we have: typedef bimap<X,Y> bm_type; bm_type bm; The whole idea of bimap is to be able to use the container as a std::map<X,Y> *and* a std::map<Y,X>. To use the bimap as a directed mapping you use "bm.left" and "bm.right". As an additional feature, you can use bm directly to view the mapping as a std::set< relation<X,Y> >. (1) bm.left - The "left side view", that is compatible with std::map<X,Y>. It uses first/second notation. You are viewing the mapping from the left, the first element you see is the left one and the second one is right one. bm.left.insert( bm_type::left_map_type::value_type(x,y) ); ... for(bm_type::left_map_type::iterator i = bm.left.begin(), e = bm..left.end() ; i != e ; i++ ) { std::cout << (*i).first << "---->" << (*i).second << std::endl; } This will output x1 ----> y1 x2 ----> y2 x3 ----> y3 x4 ----> y4 (2) bm.right - The "right side view", that is compatible with std::map<Y,X>. It uses first/second notation too, but now you are viewing the mapping from the right, the first element you see is the right one and the second one is left one. bm.left.insert( bm_type::right_map_type::value_type(x,y) ); ... for(bm_type::right_map_type::iterator i = bm.left.begin(), e = bm..left.end() ; i != e ; i++ ) { std::cout << (*i).first << "---->" << (*i).second << std::endl; } This will output y1 ----> x1 y2 ----> x2 y3 ----> x3 y4 ----> x4 (3) bm - The "above view", that behaves as a set< relation<X,Y> >. This is a complementary way of working with the mapping. This view works with left/right notation to show in the code that we are using the mapped values in a way where both are equally important. bm.insert( bm_type::value_type(x,y) ); bm.size() ... for(bm_type::iterator i = bm.begin(), e = bm.end() ; i != e ; i++ ) { std::cout << (*i).left << "<--->" << (*i).right << std::endl; } This will output x1 <---> y1 x2 <---> y2 x3 <---> y3 x4 <---> y4
I'm still slightly sceptical about the benefit of having both
typedef bimap::relation relation;
and
typedef bimap::left_value_type;
is the potential confusion really worth the trouble?
Do you still see confusion here? bimap_type::relation is the same as bimap_type::value_type. bimap_type::left_value_type is a shortcut for bimap_type::left_map_type::value_type. They are very different from each other bimap_type::value_type ------------------> relation<X,Y> bimap_type::left_map_type::value_type ---> pair<X,Y>
But std::make_pair can not be used with bimaps.
Right.
The pairs that bimap uses in its side views have a member named first and a member named second, so they can be used in generic algorithms/code/functions that works with map iterators or generic pairs. To be sure we are talking about the same thing, it does not impose that std::pairs and bimap pairs can be converted between each other.
Right.
std::make_pair() aside, you are often forced to constructing a pair object, only to copy its data once again upon insertion into the map.
Can you give an example?
This is justification enough for me to add the function.
Further justification is then ease of use, the main justification of operator[]().
Easy-of-use is out of the question.
Do you want to put all the free functions inside bimap? map_by<>() xxx_iterator_by<>()
We have functions like reverse_iterator_by<Side>(Bimap) that have no meaning in all the cases, and may be trickier to implement.
If we go down this way, we will maybe think that it is better to write rel.get<id>() instead of get<id>(rel)
In this case the get function works for relations and for the pairs of the bimap views.
You can write: get<id>( *bm.begin() ) get<id>( *bm.left.begin() ) get<id>( *bm.right.begin() )
In the end, it may be simpler to implement it with member function instead of free functions. I do not think that the interface is cleaner with them, but it is an idea we can play with.
I don't feel strongly about it. I did however always find it slightly harder to locate members. But the free-standing are more generic in the sense that they accept a bimap concept, should snybody implement their own compatible bimap.
In this case it will be a little difficult that other bimap appear in the game, but it is true that it is more generic. If there is a strong argument against free functions we can convert them to member functions. Best Regards Matias
On 2/24/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Matias Capeletto wrote:
On 2/23/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Maybe I missed how one would use this view. How exactly (and which
in the documentation?)
Maybe I have introduce noise here. The left view is the bidirectional mapping view from the left, the one obtained with bm.left
bimap<X,Y>::left_map_type is signature compatible with std::map<X,Y>. bimap<X,Y>::left_map_type::value_type is signature-compatible with std::pair<X,Y> and bimap<X,Y>::right_map_type::value_type is signature-compatible with std::pair<Y,X>
So you can use this view or the right one with generic algorithms
Matias Capeletto wrote: page that need
first/second members.
I missed that. It seems like there is less to worry about then :-)
Take this example:
typedef bimap<std::string,int> results_bimap; typedef results_bimap::relation position;
results_bimap results; results.insert( position("Argentina" ,1) ); results.insert( position("Spain" ,2) ); results.insert( position("Germany" ,3) ); results.insert( position("France" ,4) );
I could not find any documentation on direct members of a bimap. Should it read results.left.insert()???
No, there is some confusion here. The documentation will have to be changed to help grasp the essence of bimap easier. Fernando Cacciola has proposed some useful changes to the docs.
I looked in the reference section under bimap and it only stated constructors and types. Have I found some old documentation on the net somehow? Anyway, I think I get it.
std::make_pair() aside, you are often forced to constructing a pair object, only to copy its data once again upon insertion into the map.
Can you give an example?
Well, the rvalue position objects created above is a good example: 1. creare rvalue string (non-trivial) and int (trivial) arguments 2. copy string and int in position constructor 3. upon insertion, copy string and int again So the above takes 1 constructor call 2 copy-constructor calls per argument, Removing 1 copy-constructor call is the goal here. -Thorsten
On 2/25/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Matias Capeletto wrote:
view from the left, the one obtained with bm.left
bimap<X,Y>::left_map_type is signature compatible with std::map<X,Y>. bimap<X,Y>::left_map_type::value_type is signature-compatible with std::pair<X,Y> and bimap<X,Y>::right_map_type::value_type is signature-compatible with std::pair<Y,X>
So you can use this view or the right one with generic algorithms
Maybe I have introduce noise here. The left view is the bidirectional mapping that need
first/second members.
I missed that. It seems like there is less to worry about then :-)
Take this example:
typedef bimap<std::string,int> results_bimap; typedef results_bimap::relation position;
results_bimap results; results.insert( position("Argentina" ,1) ); results.insert( position("Spain" ,2) ); results.insert( position("Germany" ,3) ); results.insert( position("France" ,4) );
I could not find any documentation on direct members of a bimap. Should it read results.left.insert()???
No, there is some confusion here. The documentation will have to be changed to help grasp the essence of bimap easier. Fernando Cacciola has proposed some useful changes to the docs.
I looked in the reference section under bimap and it only stated constructors and types. Have I found some old documentation on the net somehow?
No. In that page of the reference it is state in the code box that the bimap class is derived from a set of relation view. Each set of relation is documented in the next sections because they are have almost exactly the same interface that the maps, except for the value_type and some typedefs and functions. Each function that is only valid for maps said that in the docs. I was trying to keep the docs from getting to big, but maybe it will be better if we have separate docs for the maps and the sets.
Anyway, I think I get it.
I have started a thread so we can all talk together about this and the first/second left/right issue.
std::make_pair() aside, you are often forced to constructing a pair object, only to copy its data once again upon insertion into the map.
Can you give an example?
Well, the rvalue position objects created above is a good example:
1. creare rvalue string (non-trivial) and int (trivial) arguments 2. copy string and int in position constructor 3. upon insertion, copy string and int again
So the above takes
1 constructor call 2 copy-constructor calls
per argument, Removing 1 copy-constructor call is the goal here.
I understand. The problem is bigger in the side views because another copy construction is taking place. From the inserted pair to relation, and then to the stored relation inside Boost.MultiIndex. I think I can change the current implementation to avoid the first conversion if the compiler support the mutant_relation (you can read about this in the rationale), because a reinterpret_cast can be used to convert between bimap pairs and relation. In general mutant_relation is supported. But your copy constructor call will continue to be there. I really do not know how to get ride of it. Regards Matias
Matias Capeletto wrote:
On 2/25/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Well, the rvalue position objects created above is a good example:
1. creare rvalue string (non-trivial) and int (trivial) arguments 2. copy string and int in position constructor 3. upon insertion, copy string and int again
So the above takes
1 constructor call 2 copy-constructor calls
per argument, Removing 1 copy-constructor call is the goal here.
I understand. The problem is bigger in the side views because another copy construction is taking place. From the inserted pair to relation, and then to the stored relation inside Boost.MultiIndex.
Oh, that's bad. Another consequence of not using the same underlying pair type.
I think I can change the current implementation to avoid the first conversion if the compiler support the mutant_relation (you can read about this in the rationale), because a reinterpret_cast can be used to convert between bimap pairs and relation.
I'm somewhat uncomfortable about this casting. Is it provable legal by the standard? (What works fine for pair<int,int>, might crash for pair<Foo,Bar>.) -Thorsten
In 2/26/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Matias Capeletto wrote:
On 2/25/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Well, the rvalue position objects created above is a good example:
1. creare rvalue string (non-trivial) and int (trivial) arguments 2. copy string and int in position constructor 3. upon insertion, copy string and int again
So the above takes
1 constructor call 2 copy-constructor calls
per argument, Removing 1 copy-constructor call is the goal here.
I understand. The problem is bigger in the side views because another copy construction is taking place. From the inserted pair to relation, and then to the stored relation inside Boost.MultiIndex.
Oh, that's bad. Another consequence of not using the same underlying pair type.
Yes, but this problem is there independently of the using of left/right in the right view because in it the pair members are inverted. Do you think it will be better that the right view has X as first and Y as second, this will not allow us to use it like a std::map<Y,X>.
I think I can change the current implementation to avoid the first conversion if the compiler support the mutant_relation (you can read about this in the rationale), because a reinterpret_cast can be used to convert between bimap pairs and relation.
I'm somewhat uncomfortable about this casting. Is it provable legal by the standard? (What works fine for pair<int,int>, might crash for pair<Foo,Bar>.)
Yep... the reinterpret cast works in almost every actual compiler. It uses a non standard feature. It assumes that: struct Pair_AB { TA first; TB second; }; have the same structure that struct Pair_BA { TB first; TA second; }; In the standard this is true if TA and TB are POD types. But in the real world this is generally implemented this way for non POD types too. In boost/bimap/relation/relation.cpp the library checks if it can use the mutant_relation for the types in question and if not it uses a standard_relation, that is implemented using references to the types. It is impossible to achieve zero overhead performance over Boost.MultiIndex if the mutant_relation is not supported. This is explained here: http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/boost_bimap/rationa... Comments about it are welcome, this is one of the difficult points of the library. Matias
Matias Capeletto wrote:
In 2/26/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Matias Capeletto wrote:
The problem is bigger in the side views because another copy construction is taking place. From the inserted pair to relation, and then to the stored relation inside Boost.MultiIndex.
Oh, that's bad. Another consequence of not using the same underlying pair type.
Yes, but this problem is there independently of the using of left/right in the right view because in it the pair members are inverted. Do you think it will be better that the right view has X as first and Y as second, this will not allow us to use it like a std::map<Y,X>.
I was actually thinking that the views merely stored references. Reading on, it seems like that is what you do.
I think I can change the current implementation to avoid the first conversion if the compiler support the mutant_relation (you can read about this in the rationale), because a reinterpret_cast can be used to convert between bimap pairs and relation.
I'm somewhat uncomfortable about this casting. Is it provable legal by the standard? (What works fine for pair<int,int>, might crash for pair<Foo,Bar>.)
Yep... the reinterpret cast works in almost every actual compiler. It uses a non standard feature. It assumes that:
struct Pair_AB { TA first; TB second; };
have the same structure that
struct Pair_BA { TB first; TA second; };
In the standard this is true if TA and TB are POD types. But in the real world this is generally implemented this way for non POD types too.
I'm certainly confused here. What do you mean by "same structure"? If you had written struct Pair_BA { TA first; TB second; }; I might have understood it.
In boost/bimap/relation/relation.cpp the library checks if it can use the mutant_relation for the types in question and if not it uses a standard_relation, that is implemented using references to the types.
Right. How it sucks that std::pair did not go for reference returning functions instead of members!. What if you make the members of the view pairs something like template< class Pair& > struct get_first { Pair& p_; operator typename Pair::first_type&() const { return p_.first; } }; ? -Thorsten
On 2/26/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Matias Capeletto wrote:
In 2/26/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Matias Capeletto wrote:
I think I can change the current implementation to avoid the first conversion if the compiler support the mutant_relation (you can read about this in the rationale), because a reinterpret_cast can be used to convert between bimap pairs and relation.
I'm somewhat uncomfortable about this casting. Is it provable legal by the standard? (What works fine for pair<int,int>, might crash for pair<Foo,Bar>.)
Yep... the reinterpret cast works in almost every actual compiler. It uses a non standard feature. It assumes that:
struct Pair_AB { TA first; TB second; };
have the same structure that
struct Pair_BA { TB first; TA second; };
In the standard this is true if TA and TB are POD types. But in the real world this is generally implemented this way for non POD types too.
I'm certainly confused here. What do you mean by "same structure"? If you had written
struct Pair_BA { TA first; TB second; };
I might have understood it.
I was referring to the same storage layout. The correct structures are: struct Pair_AB { TA first; TB second; }; struct Pair_BA { TA second; TB first; };
In boost/bimap/relation/relation.cpp the library checks if it can use the mutant_relation for the types in question and if not it uses a standard_relation, that is implemented using references to the types.
Right. How it sucks that std::pair did not go for reference returning functions instead of members!.
Yes, life will be easier.
What if you make the members of the view pairs something like
template< class Pair& > struct get_first { Pair& p_; operator typename Pair::first_type&() const { return p_.first; } };
?
It is a possible way to achieve the same results. The problem with it is that the size of the resulting pair will be two references bigger. This option was analyze and discarded for that reason. Regards Matias
Matias Capeletto wrote:
On 2/26/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
What if you make the members of the view pairs something like
template< class Pair& > struct get_first { Pair& p_; operator typename Pair::first_type&() const { return p_.first; } };
?
It is a possible way to achieve the same results. The problem with it is that the size of the resulting pair will be two references bigger. This option was analyze and discarded for that reason.
Not understood. A pair of references pair<T&,U&> requires one to store 2 references. My skecth above would also require 2 references. A smart compiler might know it is the same reference store twice snd do some optimization. -Thorsten
On 2/26/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Matias Capeletto wrote:
On 2/26/07, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
What if you make the members of the view pairs something like
template< class Pair& > struct get_first { Pair& p_; operator typename Pair::first_type&() const { return p_.first; } };
? It is a possible way to achieve the same results. The problem with it is that the size of the resulting pair will be two references bigger. This option was analyze and discarded for that reason.
Not understood. A pair of references pair<T&,U&> requires one to store 2 references. My skecth above would also require 2 references.
A smart compiler might know it is the same reference store twice snd do some optimization.
Could you give me more information about your skecth? The problem is to construct a relation<X,Y> class that can be viewed as a pair<X,Y> and as a pair<Y,X>. IMO the most efficient way to achieve this behaviour is to use the mutant idiom in every compiler that supported it. Is your proposal intended to improve this case?, or the case where the compiler do not support this idiom and we must roll back our pretensions and use references? It is something like this template< class Relation > struct get_left { Relation & rel; get_left(Relation&r) : rel(r) {} operator Relation::left_value_type & () { return rel.left; } }; ... template< class Relation > left_pair_view { get_left<Relation> first; get_right<Relation> second; ... }; ... ? Regards Matias
participants (5)
-
"JOAQUIN LOPEZ MU?Z" -
Joaquín Mª López Muñoz
-
John Maddock -
Matias Capeletto -
Thorsten Ottosen