/My original question was whether or not Boost or some other generic /library provides facilities for implementing associations. The answer I /am hearing so far is 1) no, there are no such libraries, and 2) such a /capability might be a good addition to Boost. /Being a newbie to Boost, I guess my next question is: So how does one /go about exploring adding a new capability such as a general-purpose /association library to Boost? /Thanks, /Rob Zako Actually, such a functionality does exist in Boost. That is because an arbitrary many-to-many mapping with per-node and per-edge data can be represented by a graph which stores per-node and per-edge data. Moreover, the boost graph library is very general in having a lot of parameters, and there is potential for abitrary representations and storage. I have used it mostly as a ready-made storage device and for finding connected components. To get started I pasted and edited large amouts of example code just for the graph object declarations. In some cases the default storage rep (balanced tree list of edges) is not what was required. It some cases the connected components routine as supplied was also not exactly what was required. When neither storage nor function match, what is the advantage in using the library? Answer: If the semantics accompanying the library were simpler, I think that coding to boost::graph specs would be a good way to be sure that ones code was "pattern-compliant", here the pattern being the concept of a graph. But I didn't find that the documentation or example code made that particularly easy, although I intuit that is possible. I hope this isn't seen as gratitous criticism. I wrote to Eli about the graph library, and he remarked that there were plenty of cases where his admittedly specialized code was just what was required, and I agree. rzako23 wrote:
Thank you to Craig Hicks (#594) and Paul Dubuc (#601) for your thoughtful answers to my query (#592) re an Association Library.
And please pardon my slow reply: Deadlines at work have consumed my time.
Craig Hicks wrote:
I am not sure what you mean by "direct". Do you mean compile time? The STL provides an easy way to implement mutable associations at run time (as shown above);
Eli Tilevich in his excellent article in the C/C++ Users Journal (Sept. 2001, p. 40-52) explains the problem as well as I could.
In brief, I would like to see a library that allows a programmer to add, modify or remove associations between classes almost as easily as one can add, modify or remove data members, i.e., composition and aggregation relationships.
I want to be able to more-or-less directly declare, say, a one-to-many bidirectional relationship between class A and class B without have to rewrite all the boilerplate code for doing so. When requirements change, I want to be able to convert the assocation to a many-to-many association with minimal changes to my application code.
Moreover, I don't want to have to worry about the details of maintaining links in both directions, and doing so in an exception-safe manner. (An exception-unsafe implementation would allow a link to be created in one direction without creating a link in the other direction, because an exception -- a low memory condition -- prevented the creation of the reverse link.)
Tilevich explains the problem admirably, and his proposed solution is a good step in the right direction.
But I think the C++ community would want to extend his solution before adding it to a general-purpose library such as Boost or the STL.
In particular, Tilevich's solution uses non-intrusive multimaps to implement associations. While this solution is elegant and flexible, it results in sub-optimal performance compared to an intrusive solution of each object holding its own links to other objects. One of the design goals of the STL is to provide generic code that is close enough in efficiency to handcrafted code that there is rarely a need to handcraft code.
Thus if I have, say, a database of 100,000 employees in a large company, I want to be able to define an Employee class and then declare a one-to-many SupervisesAssociation between the Supervisor subclass and the Employee class.
(If we assume that each of 10,000 supervisors each supervise roughly 10 employees and that the multimap from supervisors to employees is implemented as some kind of balanced binary tree, then finding the subordinates of a particular supervisor will require O(log N) or roughly 17 accesses. While for most applications this level of performance is acceptable, is falls short of storing links to subordinates directly with each supervisor, which results in O(1) performance.)
The following pseudo-code suggests what I have in mind:
class Supervisor;
class Employee { string name; "Links(many-to-one)<...>" supervisorLinks; };
class Supervisor : public Employee { string department; "Links(one-to-many)<...>" subordinateLinks; };
typedef "One-To-Many<...>" SupervisesAssociation;
Here the items in double quotes are meant to be suggestive, not actual code. My intent is to suggest that one could implement this association using just three or so lines of code.
If others are interested, I can be more explicit.
Moreover, there are more sorts of associations than simply one-to-one, one-to-many and many-to-many. There are two-to-many associations (parent-child), ordered associations (inventor-patent with date, author-publication with date, etc.), undirected associations (for undirected graphs) with associated data, etc.
Also, one might not want to realize the time and space costs of using some sort of multimap. For example, if one knows in advance that one object is never assocatiated with more than, say, 4 other objects, then one reasonable approach would be to include a C-style array of 4 (possibly null) pointers with each object. One should be able to do so as an implementation detail -- an option when choosing what kind of association to have -- without having to change client code significantly. The STL already provides this sort of flexibility, for example, with its queue adapter: A queue can be implemented with either a vector or a list.
My original question was whether or not Boost or some other generic library provides facilities for implementing associations. The answer I am hearing so far is 1) no, there are no such libraries, and 2) such a capability might be a good addition to Boost.
Being a newbie to Boost, I guess my next question is: So how does one go about exploring adding a new capability such as a general-purpose association library to Boost?
Thanks, Rob Zako
Info: http://www.boost.org Wiki: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl Unsubscribe: mailto:boost-users-unsubscribe@yahoogroups.com
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/