Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net