Re: [Boost-Users] Re: Association Library?

From: hicks (hicks_at_[hidden])
Date: 2002-04-24 00:42:41

/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_at_[hidden]>
> 
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
>
>
>
>
>