Re: Association Library?

From: rzako23 (rzako_at_[hidden])
Date: 2002-04-23 14:42:19

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