Decision on container design

[Steven Schveighoffer]

On Fri, 28 Jan 2011 18:32:28 -0500, Michel Fortin  
<michel.fortin at michelf.com> wrote:

> On 2011-01-28 17:09:08 -0500, Andrei Alexandrescu  
> <SeeWebsiteForEmail at erdani.org> said:
>
>> On 1/28/11 3:05 PM, Michel Fortin wrote:
>>> Not my preferred choices (especially #1), but having containers in
>>> Phobos will certainly be an improvement over not having them. So go  
>>> ahead!
>>  Well if you brought forth some strong argument I'm all ears. What I  
>> see for now is that struct containers are just difficult to implement  
>> and need to have carefully explained semantics, whereas a lot of people  
>> know how classes behave from day one.
>
> We already argument this over and over in the past. First, I totally  
> acknowledge that C++ style containers have a problem: they make it  
> easier to copy the content than pass it by reference. On the other side  
> of the spectrum, I think that class semantics makes it too easy to have  
> null dereferences, it's easy to get lost when you have a container of  
> containers.
>
> I have some experience with containers having class-style semantics: in  
> Objective-C, I ended up creating a set of macro-like functions which I  
> use to initialize containers whenever I use them in case they are null.  
> And I had to do more of these utility functions to handle a particular  
> data structure of mine which is a dictionary of arrays of objects. In  
> C++, I'd have declared this as a "map< string, vector< Object > >" and  
> be done with it; no need for special care initializing each vector, so  
> much easier than in Objective-C.

I see value in this idiom, and I have ideas on how to solve this with  
class-based containers.  Essentially, I think we need a way to construct a  
"container of containers" where the owner container is the one who has  
class semantics, and the sub-containers only provide access through the  
owner.  I haven't fleshed out how this will work, but it solves another  
really important problem that dcollections currently has --  
over-allocation.

The issue is, if you have a nested container (say a map of strings to  
linked-lists), the map container pre-allocates a page of elements, to ease  
stress on the GC.  But so does each linked list!  However, since the lists  
all are part of the map, they could potentially share the same allocator.   
If you have few elements in each list, this could significantly reduce the  
over-allocation of memory.

-Steve