Re: [boost] BOOST_NO_EXPLICIT_FUNCTION_TEMPLATE_ARGUMENTS and gcc
John Maddock ha escrito:
Currently, BOOST_NO_EXPLICIT_FUNCTION_TEMPLATE_ARGUMENTS
is not defined for gcc. However, the following URL in the gcc bug
database
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=7676
leads me to believe that the macro should be set on for the appropriate
versions of gcc. Matter of fact, I run with this problem myself and it
can be
workedaround with techniques similar to those employed for MSVC. See
for instance definitions of get() and workaround_holder in
boost/tuple/detail/tuple_basic_no_partial_spec.hpp
Thanks,
The issue with gcc seems to be a little more specific than we normally set
the macro for, but I don't see any reason why we shouldn't set it. Am I
right in thinking that this is specific to gcc 3.1 and 3.2? Also do you
So it seems from the bug report. I've checked the bug to be present
for gcc version 3.2 20020927 (prerelease) in cygwin. From some 3.2.x
version on the bug is reportedly fixed, but I couldn't determine the value of x.
have a test case that can be added to the appropriate config test?
I've just written the following. It (correctly) fails for MSVC 6.5 and gcc 3.2 for
cygwin,
but I cannot test it in a conforming compiler.
Regards,
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
**BEGIN CODE**
// (C) Copyright Joaquín M López Muñoz 2003. Permission to copy, use, modify,
// sell and distribute this software is granted provided this copyright notice
// appears in all copies. This software is provided as is without express or
// implied warranty, and with no claim as to its suitability for any purpose.
// MACRO: BOOST_NO_EXPLICIT_FUNCTION_TEMPLATE_ARGUMENTS
// TITLE: explicit function template arguments
// DESCRIPTION: Member template functions not fully supported.
namespace boost_no_explicit_function_template_arguments{
#ifndef BOOST_NO_MEMBER_TEMPLATES
struct foo
{
templateclass T int bar(){return 0;}
templateint I int bar(){return 1;}
};
int test_0()
{
foo f;
int a=f.template foochar();
int b=f.template foo2();
if(a!=0||b!=1)return -1;
return 0;
}
#else
int test_0()
{
return 0;
}
#endif
typedef char type_a;
struct type_b{char m[2];};
template typename T unsigned fox(){return (unsigned)sizeof(T);}
int test_1()
{
unsigned a=foxtype_a();
unsigned b=foxtype_b();
if(a!=(unsigned)sizeof(type_a)||b!=(unsigned)sizeof(type_b))return -1;
return 0;
}
int test()
{
if(test_0()!=0)return -1;
if(test_1()!=0)return -1;
return 0;
}
}
**END CODE**
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] BOOST_NO_EXPLICIT_FUNCTION_TEMPLATE_ARGUMENTS and gcc
Currently, BOOST_NO_EXPLICIT_FUNCTION_TEMPLATE_ARGUMENTS is not defined for gcc. However, the following URL in the gcc bug database http://gcc.gnu.org/bugzilla/show_bug.cgi?id=7676 leads me to believe that the macro should be set on for the appropriate versions of gcc. Matter of fact, I run with this problem myself and it can be workedaround with techniques similar to those employed for MSVC. See for instance definitions of get() and workaround_holder in boost/tuple/detail/tuple_basic_no_partial_spec.hpp Regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] About member extraction
Daryle Walker ha escrito:
But doesn't the PtrToMember template parameter already imply the
Type and Class parameters? So specifying all three would be
redundant. Could we reduce it by:
//
template typename PtrToMember
struct member_extractor
{
// Don't know if this is a real type-traits class
BOOST_STATIC_ASSERT(is_pointer_data_memberPtrToMember::value);
// The extractor traits classes aren't real (yet, maybe)
typedef get_class_typePtrToMember argument_type;
typedef get_member_typePtrToMember return_type;
return_type const operator ()( argument_type const c ) const
{ return c.*PtrToMember; }
return_type operator ()( argument_type c ) const
{ return c.*PtrToMember; }
};
Of the approaches you propose, this is the one that I like best, but
I'm afraid it cannot be implemented: Note that PtrToMember is a
*type* (something like int A::*), not a pointer to member.
member_extractor would have to defined as
template typename PtrToMember, PtrToMember ptr
struct member_extractor
and used as
member_extractorint A::*,A::x; // x is an int member of A
which takes us again to the redundancy we were trying to avoid.
Something in the way of eliminating this redundancy, however, would be
a boon. Maybe some metaprogramming gurus here can think of
something.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] About member extraction
John Torjo ha escrito:
Subject: Re: [boost] About member extraction
From: Joaquín Mª López Muñoz [EMAIL PROTECTED]
Date: Mon, 14 Jul 2003 14:24:37 +0200
To: Boost mailing list [EMAIL PROTECTED]
Daryle Walker ha escrito:
But doesn't the PtrToMember template parameter already imply the
Type and Class parameters? So specifying all three would be
redundant. Could we reduce it by:
//
template typename PtrToMember
struct member_extractor
{
// Don't know if this is a real type-traits class
BOOST_STATIC_ASSERT(is_pointer_data_memberPtrToMember::value);
// The extractor traits classes aren't real (yet, maybe)
typedef get_class_typePtrToMember argument_type;
typedef get_member_typePtrToMember return_type;
return_type const operator ()( argument_type const c ) const
{ return c.*PtrToMember; }
return_type operator ()( argument_type c ) const
{ return c.*PtrToMember; }
};
Of the approaches you propose, this is the one that I like best, but
I'm afraid it cannot be implemented: Note that PtrToMember is a
*type* (something like int A::*), not a pointer to member.
member_extractor would have to defined as
template typename PtrToMember, PtrToMember ptr
struct member_extractor
and used as
member_extractorint A::*,A::x; // x is an int member of A
Actually, I think it's worse (I don't have a C++ compiler with me right now:-( )
Something in the lines of:
template typename type, typename result, result type::* ptr
struct member_extractor
Actually, extracting A and int from int A::* is easy:
#include boost/static_assert.hpp
#include boost/type_traits.hpp
using namespace std;
struct A
{
int x;
};
template typename PtrToMember
struct ptr_to_member_descriptor;
template typename Class,typename Member
struct ptr_to_member_descriptorMember Class::*
{
typedef Class class_type;
typedef Member member_type;
};
int main()
{
BOOST_STATIC_ASSERT((
boost::is_same
ptr_to_member_descriptorint A::*::class_type,
A::value));
BOOST_STATIC_ASSERT((
boost::is_same
ptr_to_member_descriptorint A::*::member_type,
int::value));
return 0;
}
The really hard part is how to obtain int A::* from A::x. I don't
think this is possible, but then again people here sometimes do magic :)
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Interest in multiindex_set?(again)
Jeremy Maitin-Shepard ha escrito: [...] find(key) and related search memfuns are already supported in the way you suggest! Look for special lookup operations in the documentation. Matter of fact, the operations provided are even more powerful in that they allow for alternative arguments and comparison predicates. It does not appear, however, that they support automatically detecting the index based on the type of the key. This functionality seems useful, although in general it is only a syntactic convenience.. Specifically, if a table has two indices, one with a key type of int, the other with key type of std::string, with this functionality, the following syntax could be used: (note that the operator [] I show here could not have the semantics of std::map; rather it would need to throw an exception or have undefined behavior if an existing element is not found) No, I guess my design is very far away from having the ability to provide automatic index selection based on the arg type. Nevertheless, this ability wouldn't be so useful when you have severalmembers with the same type, which is expectedly not uncommon. Anyway, I underestand the lack of this feature is not a showstopper for you. table[somekey].whatever; The above statement would use the std::string index, because the type of the argument (char const *) is convertible to std::string. table[3].whatever I did something similar in the past in a bidirectional map of mine, but here the stituation is far more complicated. Unless some brilliant mind comes here with an implementation approach, this feature won't go into the library. The above statement would use the int index, because the type of the argument is int. A similar syntax could be used for find, equal_range, count, erase. Additionally, something like the following could be supported, where table_type is the type of the table: table_type::index_with_keystd::string::iterator it = table.find(something); Same comment as above, clashes in index deduction are likely to occur for moderately coplex tables having indices over elements with the same type. Tagged indices, OTOH, are nice to have. Please read at the bottom of this post. Note that you provide a version of equal_range that is not provided by std::map or set, namely, a two-argument version, with the semantics of returning the range between the two arguments. It is not possible to implement this for a hash table index. Under a policy-based interface, this could be supported by the view of an index that is a binary search tree, while not being supported by the table class itself. This is an error in the docs :) I fixed the example a few days ago, please download the .zip again. Actually, equal_range has a standard signature, just like other assoc containers. Similarly, finding using a weaker ordering predicate is only supported by binary-search-tree-based indices, and thus it seems this should be supported on a per-index basis only. Even if it is decided that automatically detecting the index based on the key type is not useful, I think it is advantageous to decouple key extraction from key comparison. Couldn't a `composite index' be supported by a key which is a tuple of some number of references? I guess you're taking inspiration here from your own library's design. This implementation of composite indices simply doesn't fit here. You can consider things are the other way around with respect to indices and dependent keys: every index is composite. Those that happen to depend on a single member of the element can be conveniently built by resorting to less_by. I'm not sure I'm being clear enough. If not, please tell me so. On a side note, taking composite indices as indices over a tuple of members does not cover the full spectrum of what an index can do. Imagine an index whose associated comparison predicate depend on the result of an external function, say int f(const element e); f() won't accept a tuple of members of element, but the actual element. To make it fit one would be forced to construct a new element on the fly out of the provided parts. Although you have not specified the semantics of f(), it seems that f() is effectively a key extractor, and the key type would be int. In order to use this with your current system of integrating key extractor with key comparison, an additional functor would be needed that effectively composed this function f() with some comparison predicate. In order to allow the user to use an int value (rather than an element value) as a key, this composition functor would also have to provide a number of overloads some of which bypass this key extraction functor for one of the arguments. For a hash-table-based index, it becomes even more complicated, because a second composition functor must be provided that deals with hash codes. In constrast, if key extractors are supported by the
Re: [boost] Re: Interest in multiindex_set?(again)
Jeremy Maitin-Shepard ha escrito: Joaquín Mª López Muñoz wrote: This is a no-no policy. Collision can happen with more than one element. Following this approach could result in an single update sweeping off half the elements of the container :) I don't think users of the library want this. What are the current semantics of your insert? In order to be consistent with std::map, the behavior has to be to overwrite (delete) an existing element with the same key. The number of elements deleted by an insert or modify or update operation under the semantics I suggest is at most the number of unique indices. These are the semantics I would expect anyway, although I suppose it is a matter of opinion. The semantics of std::map (or any other STL associative container) are not overwriting on insertion: instead, if an equivalent element is found, no insertion occurs. This is what my library does, too. Maybe you're confusing here map::operator[] with map::insert. I think the analysis is not precise enough. In the modify approach you're proposing, modifying (by way of the user-provided functor) takes place *before anything*. If this functor throws, we got nothing else to do but let the exception propagate. It is the responsibility of the user to guarantee that the modyfing functor does not leave things in a bad state. An acceptable (IMHO) approach for modify would be as follows: a. Call the user-provided modifying functor. If it throws, let the exception propagate. Okay, now that I reconsider, this seems most consistent with standard containers, since it follows the idiom of exception thrown means nothing happened. b. Attempt reordering. b1. If there's a collision, delete the modified element (this can be done in a no-throw way) and return false I still think it is better to delete the older elements rather than the new one, consistent with my proposed semantics for insert (and consistent with standard container insert). same comment about insertion semantics as above. b2. If there's an exception (by some comparison predicate), delete the modified element and rethrow. Okay, this seems reasonable, and would be consistent with insert. So, to sum it up, if we both agree that insertion will not overwrite (as it is the semantics of STL assoc. containers), then is this approach for modify OK with you? I've included the new memfun modify following your indications and those of Fernando, and it works right. It'll go in next release, which I hope it'll be submitted for preformal review. [...] There are various advantages to separating key extraction from key comparison: 1) It allows the use of more generic key extraction and key comparison functors. Specifically, for an ordered index, the key comparison function in many cases would be std::lessKeyType, and can default to that. For unordered (hash-table-like) indices, it is necessary, at least internally, to separate key comparison and key extraction because the hash function must also operate on the key value; otherwise, the hash function must also be very specialized, when in many cases a default library-provided hash function can be used (and thus not specified). A small utility class named less_by is used for precisely this purpose. You can see it in action in the example accompanying the library. As for hashing, an analogous device can be written (when hashes get included). 2) It is necessary in order to support certain convenient interfaces; specifically, I think it is very convenient to allow the syntax: table[key], find(key), and equal_range(key). In order for the front-end to deteremine which index corresponds to the key type, it must know about keys. find(key) and related search memfuns are already supported in the way you suggest! Look for special lookup operations in the documentation. Matter of fact, the operations provided are even more powerful in that they allow for alternative arguments and comparison predicates. [...] Couldn't a `composite index' be supported by a key which is a tuple of some number of references? I guess you're taking inspiration here from your own library's design. This implementation of composite indices simply doesn't fit here. You can consider things are the other way around with respect to indices and dependent keys: every index is composite. Those that happen to depend on a single member of the element can be conveniently built by resorting to less_by. I'm not sure I'm being clear enough. If not, please tell me so. On a side note, taking composite indices as indices over a tuple of members does not cover the full spectrum of what an index can do. Imagine an index whose associated comparison predicate depend on the result of an external function, say int f(const element e); f() won't accept a tuple of members of element, but the actual element. To make it fit one would
Re: [boost] Re: Interest in multiindex_set?(again)
Jeremy Maitin-Shepard ha escrito: [...] How about indexed_table? This container is *not* a set, since there can be duplicates, but it *does* resemble a relational database table. Then it can be defined in namespace boost::table, and additionally promoted to namespace boost. Seems good to me, it'd be great to know others' opinion. [...] Actually, using partial specialization, you can avoid re-specifying the default/unique. multiple would possibly be a better name than non_unique. Additionally, I would recommend allowing a specification of the default uniqueness of the indices. Seems good too :) I think I got an idea of how to implement this, I'll put myself to work on it. (I plan to add hash indices sometime by the end of 2003). A policy-based approach seems the best way to support different types of indices. Currently, I am working on a policy-based equivalent to this class which will support an ordered (binary search tree-based) index and an unordered (hash-table-based) index, as well as any user-defined index policies (which would allow a different hash table or tree implementation). This should be completed within a week or two. Do you intend to submit that to Boost? If so, then there's some collision between the two libraries, maybe we can cooperate somehow. If not, maybe you can lend some ideas to (re-baptised) indexed_table. Please drop me a mail if you feel like discussing this. I don't think it is a question of how smartly update() is coded, but an actual conceptual impossibility. If we are to provide strong exception-safety, then no fail or throw is permitted after the element has changed its value. So, there are three scenarios: 1. Updating can possibly fail (because of collision with some other element) or reorder the updated element: no other soluction but to incur a copy of the element, as the actual updating has to take place *after* the reordering is done. It seems the best behavior in the case of a collision is to delete the old element with which there is a collision. This would be consistent with the semantics of insert. This is a no-no policy. Collision can happen with more than one element. Following this approach could result in an single update sweeping off half the elements of the container :) I don't think users of the library want this. I think current update() has some value as it is now. I keep discussing the alternate memfun modify you propose below. Instead of an update method, a modify method that takes an iterator and a one-argument (a reference to value_type) functor which it executes on the value to which the iterator points. Combined with boost.lambda and boost.bind, this system can be very convenient. This is similar to what Fernando Cacciola proposed some days ago. In the case that the modification functor (or copy constructor, in the case of the existing update method) throws an exception, the semantics could be one of the following: 1. The container is left in an undefined state, and the exception is propogated to the caller. 2. The exception is caught, reordering is attempted; if an exception is thrown while reordering, by one of the comparison, etc. functors, the container is left in an undefined state and the exception is propogated to the caller; if reordering succeeds, the original exception thrown the by modification functor is rethrown to the caller. Thus, in either case an exception is propogated to the caller, and by the type of the exception whether the container is in an undefined state. 3. Same as (2), except that in the case that the reordering filas, before the exception thrown by a comparison function is propogated to the caller, the would-be-modified element is erased from the container, leaving it in a well-defined state. The exception thrown by the comparison function is still propogated to the user. (3) seems like the most desirable solution, thus that is the behavior I would recommend. I think the analysis is not precise enough. In the modify approach you're proposing, modifying (by way of the user-provided functor) takes place *before anything*. If this functor throws, we got nothing else to do but let the exception propagate. It is the responsibility of the user to guarantee that the modyfing functor does not leave things in a bad state. An acceptable (IMHO) approach for modify would be as follows: a. Call the user-provided modifying functor. If it throws, let the exception propagate. b. Attempt reordering. b1. If there's a collision, delete the modified element (this can be done in a no-throw way) and return false b2. If there's an exception (by some comparison predicate), delete the modified element and rethrow. What dou you think about it? [...] 3. Updating does not alter the order of the updated element (because the programmer knows it). One can just change the value in-place and forget
Re: [boost] Re: Interest in multiindex_set?(again)
Beman Dawes ha escrito: [...] I'm more interested in the class name than the namespace name. One problem at a time. If you weren't worrying about the namespace name, would you then like indexed_set as the class name? What are some other alternatives? If we forget about the namespace name, then I have no objections against indexed_set (though std::sets are indexed by nature, but this is probably not a common perception between users). I thought long and hard about name candidates and come up with none except multiindex_set. If no one says anything against it, I'll change it to indexed_set. The problem remains of how to name its associated namespace. [...] Yes, I think so. It is a bit of a judgement call, but since the library is a very general purpose tool, and assuming the library only adds a few names to the namespace it lives in, I'd rather see it in namespace boost. Others may disagree; a lot of people like tall and deep namespace hierarchies even when the components are very general purpose. OK, next installment will have the container promoted to boost::indexed_set. There are some auxiliary classes which I don't know exactly where to put, I'll think it over. I don't see any acceptable (non-invasive) way to implement marking only one class. But the unique/non_unique two template approach seems perfectly acceptable. You could even argue that it forces the user to consciously make the critical unique/non_unique decision for each index, so may reduce user error. I agree with you. The all-predicates-are-marked approach is even better in the light of future change (I plan to add hash indices sometime by the end of 2003). [...] I understand the rationale for that, but am still concerned. There are many applications where the cost of a copy to apply a minor update is prohibitive. The user is then forced to add a layer of indirection, or use a home-made container. Ugh. This is one of the few cases I run into where a safe design is so inefficient compared to a traditional unsafe design that in real production code I might be forced to use the unsafe design. That makes me uncomfortable. I don't think it is a question of how smartly update() is coded, but an actual conceptual impossibility. If we are to provide strong exception-safety, then no fail or throw is permitted after the element has changed its value. So, there are three scenarios: 1. Updating can possibly fail (because of collision with some other element) or reorder the updated element: no other soluction but to incur a copy of the element, as the actual updating has to take place *after* the reordering is done. 2. Updating won't fail (because the progammer knows it) but can result in reordering. Here a no-throw update is possible that doesn't require an additional copy. 3. Updating does not alter the order of the updated element (because the programmer knows it). One can just change the value in-place and forget about it. 1 is taken care of by current multiindex_set::update. 3 can be solved with appropriate const_casting: this is dangerous as any cast is, but then again the programmer *knows* what she's doing. Furthermore, this is exactly the same situation as in std::set. We are left with 2: please note that it is extremely error-prone to trust the programmer in her implicit knowing that no collision will happen (checking 3, on the other hand, is much easier, as probably what the programmer is changing are auxiliary members that no comparison predicate depend on). Now, if the no-collision guarantee is assumed, the updating can be performed without throwing. To sum it up, as it stands now mutiindex_set allows for updating in scenarios 1 and 3. Scenario 2 (programmer knows the updated element won't clash with some other element) can be realized (Fernando suggested a nice way to do it), but my opinion is that this facility would be extremely dangerous to handle. I'd rather leave things as they are now, but I'm open to suggestions, maybe I'm missing something obvious that will solve the whole problem in a fell swoop. Open issues: * Name will change to indexed_set if no one complains. What name to use for the associated namespace? * Is it advisable to provide an no-copy update facility relying on the assumption that updating won't clash with other elements in the set? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Re: Re: [In response to FernandoCacciola]Re:Interestinmultiindex_set?(again)
Hi Fernando (and all others) Please find some preliminary documentation for multiindex_set at: http://groups.yahoo.com/group/boost/files/multiindex.zip The documentation is far from complete, but a reasonably complete rationale is given which hopefully will guide the reader through the design considerations that shaped multiindex_set. The rest of the docs (usage, reference) will probably we written only if there's some heat around the library (writing is not one of my best skills, and I'll go through that bore only if there's some potential audience). I hope we've got now a better starting point to discuss multiindex_set. As always, all sorts of comments are most welcome. Regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo Fernando Cacciola ha escrito: Hi Joaquín, I'm probably just misunderstanding your class. So I'll wait for you to upload the documentation and I will repost the issues then. Best Fernando Cacciola ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Interest in multiindex_set? (again)
Arkadiy Vertleyb ha escrito: [...] The reason we are interested in the multiindex_set is that we want to provide a more efficient implementation for our table, that is currently implemented with std::vector, although Ed Brey already suggested an alternative with std::set(that we need to examine). Regards, Arkadiy I suggest you download multiindex.zip from the files section and play with it to see if it fits your needs. If you need assistance with the usage of the library don't hesitate to contact me. Next week some sort of preliminary documentation should be prepared, anyway. Regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Re: [In response to Fernando Cacciola] Re:Interestinmultiindex_set?(again)
Hi Fernando, Fernando Cacciola ha escrito: [...] I understand the current design but I'm not sure if it defines the concepts correctly, which is IMO the first important thing to get right. So let's see: From a C++ user perspective, your class is an Associative Container. An associative container associates contained elements with a key. The 'key' _identifies_ the element by means of some 'relation' (or association). Since the key is the element identifier, keys are used to look up elements. In a std 'set', the relation which associates keys and elements is the 'identity'. It means that to identify (look up) an element of type 'E' with value 'e', the user needs to use the value 'e' itself, of the same type, as a key. In a std 'map', the relation is the explicit bijection expressed by a 'pairKey,Data. It means that to identify an element of type 'Data' whith value 'd', the user needs to use a value 'k' of type 'Key' as the key. Hence, the 'key' of an associative container is the (typed) value which is used to identify elements in the container. In your class, the elements look like keys simply because you choose to model the predicates as black-boxes which extract keys in some indeterminate way. That is, an _entire_ element value does not identify a contained element. It is a 'part' of the element value which acts as a key, but not the element (not the whole of it). It is not really necessary to melt the concepts of key and value using a black-box predicate over an entire element. You can use separate KeyExtractor and KeyCompare. This would better reflect the fact that your container stores values (elements) along with mutiple keys, which by default just happen to be different parts of the stored values. This can certainly be done but * It complicates the instantiation of a multiindex_set type (you've got to provide more info). * I cannot see its usefulnes. Maybe you've got in mind something different to me. Please read below. [...] One last concern: keys are related hierarchycally? Only for implementation purposes: derivation from one key (or index) to another is protected. From the user's point of view, keys/indices are structurally unrelated types obtained via get() from the source multiindex_set object. I see. Depending on the application, this independece might not be a good property. How do I 'cluster' (that is, get all of) elements which share some primary key and some secondary key, and so on? BTW: I figure that there is some clustering and ordering invariant. That is, elements sharing some key-related property are placed together (clustered), and clusters are ordered in some way. But I can't tell how is this exactly and which operations maintain these invariants. For example: can I expect a specific arrangement with a lineal traversal (as with set/map), or only via 'get()'? Now I'm totally missing your point. Each index (or cluster if you prefer) defines an independent set-like interface by which you can access all the elements contained (though in different orders depending on the index). When you insert an element through an index say i1, it becomes visible from all other indices. Indices behave as views, if you want to see it that way. There's some kind of facility for horizontal traversal, i.e, for getting an iterator of index M given an iterator of index N. It is called project() and can be used like this: typedef multiindex_set... mx_set; mx_set ms; mx_set::index_type1::type::iterator it1=...; mx_set::index_type3::type::iterator it3=project3(ms,it1); This obtains an index-3 iterator from an index-1 iterator so that both iterators point to the same element. project() has been recently added, check last version on http://groups.yahoo.com/group/boost/files/multiindex.zip I don't know if this answer your lineal traversal question. An interesting question is whether project() or similar stuff can be used to allow for searches based on different indices, à la SQL. On this point I haven't thought out anything yet. I really value your contributions, but I think withouth some minimal docs we'll keep going round and round just defining the basic concepts. If I have time, I'll try to write something down by next week, please stay tuned. Besides, no one except you seems to be interested in multiindex_type :( If only some boosters jump into this discussion I'm sure many interesting insights would be provided. Regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] [In response to Fernando Cacciola] Re: Interest in multiindex_set?(again)
(My mail server was down yesterday so your post didn't get through to me and I cannot answer it properly). Fernando wrote: This looks fine in general. I've needed something like it so I'm intereseted on seeing this on boost. Some issues: (1) Why 'index' instead of 'key'? Associative containers use the term key instead of index, since index is typically related with random access instead of look up access. Well, 'index' is borrowed from database technology meaning an internal sorting on a given key of a record. I haven't used 'key' instead because, in general, the whole element serves as a key (the comparison predicate for a given index need not be based on a particular member of the element, but can be any functor with bool operator(const element,const element) signature; less_by is just a convenient facility for the usual case in which the comparison depends solely on a single member of the element. Also, as every index has a std::set-like interface, its key_type typedef must be equal to the type of the elements contained, which contributes to the confusion. On earlier versions, I used 'view' instead of 'index', but I don't like that either. I'm open to suggestions on more convenient terminology. (2) I would explore a friendlier interface. For instance: (2.1) key uniqueness could be specified along with the key itself and not with a separate template parameter. Do you have an idea of how the interface can be like? I could try this approach. (2.2) keys could be tagged so that 'get' could be parametrized by key tag instead of number. I'd do it if I only knew how. Basically I'm using the same technique as get() member functions in boost::tuple, which don't have tags either. I really don't know how this could be done. (3) This is a showstopper for me: The key mutating operations should use a higher level interface which protects clustering and ordering invariants. With the current interface, if I understood correctly, I could forget to call update() which would break such invariants. A better setup would be to use something along the lines of the 'modifiers' used by the CGAL Library. [stuff deleted] Maybe I'm not explaining myself clearly enough, or else I'm not catching your point. update() does not break the integrity of multiindex_set. Semantically, update(it,new_element) is equivalent to the following: element original=*it; erase(it); if(!insert(new_element).second) insert(original); with the added guarantees that: * strong exception-safety (all-or-nothing operation) is provided. * the process is done optimally (constant time if no internal reordering is necessary) * iterator and reference validity is preserved (an iterator pointing to the original element will point to the new one after update() ). This does satisfy your concerns? If it doesn't I'd appreciate if you could explain a little further what you have in mind. Regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] [In response to Arkadiy] Re: Interest in multiindex_set?(again)
(My mail server was down yesterday so your post didn't get through to me and I cannot answer it properly). Arkadiy wrote: We may use this to provide a better table implementation for the Relational Template Library, we are currently working on. Right now we are using a sorted vector instead of a set, to implement our relational tables, because set doesn't allow us to search on a prefix of a key. Like if a table is indexed on a, b, c, we are not able to use equal_range on a, b with the set. Sorted vector allows us to do this, but sorted vector has obvious problems with inserts/deletes. Do you think your library can provide both search on a key prefix and fast inserts/deletes? Arkadiy Search methods are extended to allow for compatible comparison predicates. If if understood your request right, having a multiindex_set sorted by lexicographical order on (a,b,c) allows the user to perform searches based on lexicographical (a,b), since this order is compatible (weaker) than the former. Insertions are O(M log N) where N is the length of the set and M the number of indices it is instantiated with. Deletions are constant time --O(M), to be precise. Regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: [In response to Fernando Cacciola] Re: Interestinmultiindex_set?(again)
Fernando Cacciola ha escrito:
(1)
Why 'index' instead of 'key'? Associative containers use the term key
instead of index,
since index is typically related with random access instead of look up
access.
[...]
C++ already has the concept of an Associative Container, and this
concept includes that of a 'Key'. In std terms, a 'key' can be
integrated with the value type (ala 'set') or not (ala 'map');
so this particularity shouldn't indicate the need for another term.
multiindex_set follows the à la set way. The whole element is the
key. For instance:
struct element{int a;int b;int c;};
struct comp_element{
bool operator()(const element e1,const element e2)const
{
return e1.a+e1.b+e2.ce2.a+e2.b+e2.c;
}
};
typedef multiindex_setelement,comp_element mx_set;
Here you can see that the comparison predicate reads from all the
members of element, so basically multiindex_set makes no assumption
(it cannot) about which parts of the element are keys or not. This is
useful for constructing composite indices, following database terminology.
less_by is used for comparison predicates depending upon one single
member, but this is not the general case.
So, every index has the same implicit key (the whole element), so calling
the indices keys seems to me confusing. An index is just a sorting
criterium. I'm not sure I've explained myself clearly enough (if I haven't
please tell me so). Now the question of how to name the indices
remain open, though maybe this discussion has made you lean towards
my preferences. This is by no means a critical aspect, if someone comes
with a more appropriate name I'll happily adopt it.
I think that following the std associative containers as much
as possible is the way to go.
For example: if possible, having both 'set' and 'map' variants
would be great (that is, with integrated or external keys).
Also, having 'hash' variants would also be great, that is,
with equal_key clustering but no particular ordering.
From the discussion above, I hope it is clear now that
multiindex_set regards the entire element as the key. A map
variant can be built on top of it, but it is not clear to me
whether such a construct is useful enough. Maybe we can delay
this decision after some stable set-only version is stabilized.
Hashing of user-specified indices is a very good option to have.
I'm currently exploring it, but given the little amount of time I
can devote to this I'd prefer to leave this out for the moment.
[...]
(2.2) keys could be tagged so that 'get' could be parametrized by
key tag instead of number.
I'd do it if I only knew how. Basically I'm using the same technique
as get() member functions in boost::tuple, which don't have tags
either. I really don't know how this could be done.
I see.
I'm pretty sure this can be done, though I'm not sure how exactly :)
Named template parameters mechanisms come to mind.
Perhaps other boosters can suggest something.
If someone else jumps into the thread (s)he may shed some light on this.
[...]
Wait...
I read your original example as if you were mutating
the element in-place though the iterator,
then calling update().
But you're not, update() takes a _copy_ of the
possibly mutated element, so I figure that
iterators are non-mutable (as should).
OK, I grant this interface is invariant-safe,
but it strikes me as inneficient, not because of
the update per see but because of the element
copy (which has to be done twice)
An alternative would be something like this:
class multiindex {
...
templateclass Modifier
Modifier update ( const_iterator it, Modifier Mod )
{
// iterator is private, so is access()
iterator mit = access(it);
Mod(*it);
update(*it);
}
...
} ;
Modifier is a user-suplied function object
which signature of the form:
void operator() ( element e ) ;
Ummm... I'm afraid this cannot be done. What happens if the updated
element does not fit into the multiindex_set due to collision with some
other element? For instance:
multiindex_setint ms;
ms.insert(0);
ms.insert(1);
ms.update(ms.begin(),increment_by_one);
The last call will call increment_by_one() on the first element with
value 0, changing it to 1. When reordering of the element is tried,
a collision with the second element will ensue. What's worse, one
cannot revert to the original situation, because the element has been
already rewritten.
At least, I hope current update() is no longer a showstopper for you.
One last concern: keys are related hierarchycally?
Only for implementation purposes: derivation from one key
(or index) to another is protected. From the user's point of
view, keys/indices are structurally unrelated types obtained via
get() from the source multiindex_set object.
Just to summarize, the following points remain open:
* How to name indices in a more appropriate form.
* Is it worthwile to make a map-like variant? It can be done,
but I'm not sure whether such a construct is
[boost] Interest in multiply indexed set container?
Hi all, I'm (slowly) working on multiindex_set, an std::set-like container supporting multiple indices, much in the spirit of a relational table. On instantiation time, a tuple of comparison predicates is provided as well as information on which of them are to be treated as unique (no duplicates). The container provides views on each index that behave (to the maximum extent possible) as regular sets sorted by the corresponding comparison predicate. A small utility is provided, named less_by, for the (supposedly) usual case in which a comparison predicate depends on only one of the fields of the value, which allows for emulation of map-like containers. Different instantiantion parameters yield containers behaving like all the STL associative containers (though the power of the library does not lie in this, of course). If the compiler supports partial specialization, the suite of lookup methods is duplicated to allow for compatible comparisons: for instance, one can find an element giving only the field on which the comparison depends, or, if some comparison depends on say names then a compatible predicate can be feed that looks for initials (an example of this is provided). So far, the library is say 75% complete, at least from my initial specification, so I thinked it could be of interest to Boosters in its actual form. Please look for multiindex.zip for the library and a rather extensive example of use. It compiles and works in MSVC 6.0sp5 and g++ 3.2 under Cygwin. No docs yet, sorry. Comments on the library are most welcome. Best regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Interest in multiply indexed set container?
I forgot to say it, multiindex.zip is in the Files section. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo Joaquín Mª López Muñoz ha escrito: Hi all, I'm (slowly) working on multiindex_set, an std::set-like container supporting multiple indices, much in the spirit of a relational table. On instantiation time, a tuple of comparison predicates is provided as well as information on which of them are to be treated as unique (no duplicates). The container provides views on each index that behave (to the maximum extent possible) as regular sets sorted by the corresponding comparison predicate. A small utility is provided, named less_by, for the (supposedly) usual case in which a comparison predicate depends on only one of the fields of the value, which allows for emulation of map-like containers. Different instantiantion parameters yield containers behaving like all the STL associative containers (though the power of the library does not lie in this, of course). If the compiler supports partial specialization, the suite of lookup methods is duplicated to allow for compatible comparisons: for instance, one can find an element giving only the field on which the comparison depends, or, if some comparison depends on say names then a compatible predicate can be feed that looks for initials (an example of this is provided). So far, the library is say 75% complete, at least from my initial specification, so I thinked it could be of interest to Boosters in its actual form. Please look for multiindex.zip for the library and a rather extensive example of use. It compiles and works in MSVC 6.0sp5 and g++ 3.2 under Cygwin. No docs yet, sorry. Comments on the library are most welcome. Best regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Problems compiling MPL sample in MSVC 6.5
http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/*checkout*/boost/boost/libs/mpl/example/inherit_linearly.cpp?rev=HEADcontent-type=text/plain This sample (which Gennadiy provided in a post from his a few days ago) does not compile in MSVC++ 6.5. The compiler says: error C2039: 'index' : is not a member of 'arg-1' If I remove all the 'index' stuff, the program compiles, but sizeof(t) is 1 --it should be at least sizeof(int)+sizeof(char const *)+sizeof(bool). Ideas? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Bidirectional map preliminary submission
First of all, congratulations to all for the new 1.30.0 baby.
I've boostified my bimap library so that it can be more easily
reviewed. Now bimap lives into namespace boost and some
metastuff have been removed in favor of utilities already
provided by Boost itself.
The bimap.hpp header has been uploaded to the Files Section,
under the folder bimap. A sample test is provided as well as
a draft of the documentation, coming from the one I wrote for
CodeProject.
All suggestions and comments are most welcome. I feel that
in its present form boost has no severe barriers to be accepted,
but I'm sure there's lots of room for improvement. In preparation
for critiques, I've compiled a list of several hot topics that may arise
during the prelminary review:
1. Syntax and semantics
Since bimap follows as closely as possible the interface of std::map,
there's little IMHO to add or remove from here. The added constraint
of bidirectionality imposes some behavior that diverges from regular
maps, though. I don't think there's an alternate way to handle the
following
issues:
* operator[], when used for inspection on a non-existent value, throws
bimap_base::value_not_found. std::maps, on the other hand, automatically
insert a default value. This I cannot do in bimap, since it would
violate
the bidirectionality.
* bimap_base::duplicate_value is thrown whenever an assignment is
attempted to a value already present in the bimap: this again stems from
the preservation of the bidirectionality invariant.
2. Pollution of namespace boost.
Apart from bimap, the following types and functions are already defined
inside boost namespace:
* direct_pair
* inv_pair
* make_inv_pair
* bimap_base
* prebimap
* bimap_equal_types
* bimap_different_types
* prebimap_identity
Apart from bimap_base and possibly make_inv_pair, I'd like to have all
of these
defined in an auxiliary namespace, but MSVC++, which is my work
compiler,
chokes at one point or another when tyring to do so.
3. Nonconformances
To the best of my knowledge, there are two non-conformances in the code:
* It is assumed that for these two classes (in simplified form here):
templatetypename A,typename B
struct direct_pair
{
A first;
B second;
};
templatetypename C,typename D
struct inv_pair
{
D second;
C first;
};
it is asummed, I was saying, than a direct_pairA,B can be
reinterpret_cast'ed
to a inv_pairC,D (and vice versa) whenever A=D and B=C. I cannot
imagine
how on earth this couldn't be so for any conceivable compiler, but I'm
afraid a
strict interpretation of the standard does not guarantee this.
* offsetof() is used for non-POD types. The types on which it is used
are
arguably simple enough to be treated as POD (no virtual methods or
anything), but
then again the standard bans it. G++ complains at this, an ugly
workaround has
been applied for this case.
I'd like to know whether these two points could prevent bimap from
entering
Boost, or, in the contrary, they can be tolerated. Standard workarounds
are most
welcome, of course.
3. Compiler support
The version submitted works for MSVC++6.0sp5 and GNU CC 3.2 (cygwin).
Non-boost bimap also worked for the follwing:
* VC++ 7.0 (aka .NET)
* GNU GCC 3.0, 3.0.2, 3.0.4 (Linux 2.4.18, SunOS 5.8)
* GNU GCC 3.1 (Linux 2.4.18, SunOS 5.8)
* GNU GCC 3.2 (Cygwin 1.3.18-1, Linux 2.4.18, SunOS 5.8), 3.2.1 (Linux
2.4.18,
SunOS 5.8)
* Metrowerks CodeWarrior 8.3 (Mac OS 9.2.2, Mac OS X 10.2.3)
As only minor changes have been made, I guess all of these will still
merrily
compile the thing. Strictly speaking, though, I haven't tested it.
4. Compiler workarounds
There's non-surprising worarounds to cope with several well known
defficiencies
of MSVC++. For GNU CC, the illegal use of offsetof has been masked with
a dubious workaround; more interestingly, there's a compiler bug with
respect
to a constructs I call memberspaces (see
http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-traildatabase=gccpr=9159
for details). This has been fixed in a satisfactory manner (IMHO).
Finally,
CodeWarrior seems to have a hard time with some dependent typenames, the
patches applied might deserve some thinking over.
Regards,
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] RE: bidirectional map
jeff ha escrito: On Wed, 12 Mar 2003 17:07:54 -0600, David B. Held wrote I'd say 6 or 7 people expressing interest is more than enough to justify Boostifying the code at this stage. I agree. Since you have written an article which clearly describes the concept and provides an example it seems to me that you should be able to as for preliminary review from interested parties before you boostify the documentation. OK, so how I ask for preliminary review? Posting a mail here? I don't really know how to start this process, whether some formality is required or not. [stuff deleted] Also, it looks like the early consensus is that multi-key/value support is desired, so I think we should have a good look at your implementation/design to see if it is general enough. While a few folks have asked for this, it is up to you if you really want to take on the additional burden. Submitting, going thru the review, porting and maintaining a boost library is a huge amount of effort. While I think a generic multi-key container would be really cool, it is up to you to accept that scope. I, for one, would rather see a good bi-directional map sooner rather than waiting for a more general solution. I honestly can't think of a case where I would have needed the more general solution and I there is always a complexity tradeoff. To the best of my knowledge, it is very difficult to fit an n-key container, where n2, into the interface of a map. IMHO such a container resembles more a set (I'm slowly working on this BTW). So, I guess I'll try to Boost this alone. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo Jeff ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] RE: bidirectional map
Jeff Garland ha escrito: OK, so how I ask for preliminary review? Posting a mail here? Yes, you can just ask for preliminary feedback on this list. Another thing you can do is put the code in the boost-sandbox. This helps get things into the boost structure and allows other boosters to keep up with changes as the library is evolving towards formal submission. Ask one of the moderators of the boost sandbox for CVS access if you want to do this. OK, I don't know if uploading non-boostified code to the sandbox is a proper way to do. If so, please some moderator help me do it (if not, the code is in the Files section aka the vault). So, I guess I'll have to wait for comments about the library to pour in :) Maybe when the dust of 1.30.0 has settled down. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] RE: bidirectional map
jeff ha escrito: On Wed, 12 Mar 2003 17:07:54 -0600, David B. Held wrote I'd say 6 or 7 people expressing interest is more than enough to justify Boostifying the code at this stage. I agree. Since you have written an article which clearly describes the concept and provides an example it seems to me that you should be able to as for preliminary review from interested parties before you boostify the documentation. OK, so how I ask for preliminary review? Posting a mail here? I don't really know how to start this process, whether some formality is required or not. [stuff deleted] Also, it looks like the early consensus is that multi-key/value support is desired, so I think we should have a good look at your implementation/design to see if it is general enough. While a few folks have asked for this, it is up to you if you really want to take on the additional burden. Submitting, going thru the review, porting and maintaining a boost library is a huge amount of effort. While I think a generic multi-key container would be really cool, it is up to you to accept that scope. I, for one, would rather see a good bi-directional map sooner rather than waiting for a more general solution. I honestly can't think of a case where I would have needed the more general solution and I there is always a complexity tradeoff. To the best of my knowledge, it is very difficult to fit an n-key container, where n2, into the interface of a map. IMHO such a container resembles more a set (I'm slowly working on this BTW). So, I guess I'll try to Boost this alone. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo Jeff ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] RE: bidirectional map
Eric Martel wrote: Hi, After a quick Google search, I found out that Joaquín M López, the author of a bidirectionnal map hosted on codeproject sent a message (Mon, 21 Oct 2002 21:29:18) on the boost mailing list to promote his library. David B. Held replied about using his work to include the bidirectionnal map to boost, to avoid library proliferation. So now, here's my question : Nearly 5 months later, did anyone work on this bimap? Will it be included anytime soon in an official distribution of boost? Thanks a lot for your time Cheers, Eric Well, it was my intention then to probe the Boost community for interest in the library, and my impression was it raised little impetus. In the meantime I've polished the code so that now it runs in a handful of compilers. I guess I can try again. For easy access the code is now in the Files section, in the folder bimap, as well as a pointer to the docs in CodeProject. The library is not boostified, but I feel I should only carry out that work if people here likes the library. I do no visit this site so often, so please someone correct me is this is not the way to go -- I guess some sort of pre-acceptance is required, since the Files section is crowded with stuff and presumably not all of it will make it into Boost. Looking forward to your comments, regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] RE: bidirectional map
The multiply indexed set seems a most interesting container, and
as a matter of fact I'm working on something like that, but progress
is slow.
There's an issue I guess I should comment here before advancing
with this. The code is non-conformant in (at least) two points, neither
of which I've found a conformant replacement for:
* It is assumed that for these two classes (in simplified form here):
templatetypename A,typename B
struct direct_pair
{
A first;
B second;
};
templatetypename C,typename D
struct inv_pair
{
D second;
C first;
};
it is asummed, I was saying, than a direct_pairA,B can be reinterpret_cast'ed
to a inv_pairC,D (and vice versa) whenever A=D and B=C. I cannot imagine
how on earth this couldn't be so for any conceivable compiler, but I'm afraid a
strict interpretation of the standard does not guarantee this.
* offsetof() is used for non-POD types. The types on which it is used are
arguably simple enough to be treated as POD (no virtual methods or anything), but
then again the standard bans it. G++ complains at this, an ugly workaround has
been applied for this case.
I'd like to know whether these two points could prevent bimap from entering
Boost, or, in the contrary, they can be tolerated. Standard workarounds are most
welcome, of course.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Daniel Frey ha escrito:
David Abrahams wrote:
It's similar for me. It's one of those things that you don't need
every day, but when you need it, you really need it. That may be why
there's not more vociferous interest. Anyhow, while bidirectional
maps are the most common case, they're not the most general:
N-directional maps, which I've sometimes needed.
I'd also be interested in a 'set' of 'tuples' with a user-defined set of
'views', where a view has its own sort-criterion and its own iterators,
find-functions, etc. At least this is what I imagine but I haven't
worked on it, so I don't know whether it's a realistic approach.
Regards, Daniel
PS: And yes, *if* you need them, you really *need* them.
--
Daniel Frey
aixigo AG - financial training, research and technology
Schloß-Rahe-Straße 15, 52072 Aachen, Germany
fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99
eMail: [EMAIL PROTECTED], web: http://www.aixigo.de
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
