On Friday, 4 May 2012 at 13:22:47 UTC, Steven Schveighoffer wrote:
> Structs don't make very good containers.  A slice is not really a container.

Most containers in std.container are structs. A struct can do everything a class can do, for example, you can choose whether to use reference semantics or not. So I don't think the assertion that structs aren't good for containers is true, when they can do so much more than classes. There is still debate whether std.container's containers should be classes or structs, but even so, third-party containers might have different requirements.

> What exactly are you looking for?  I mean, you want the original type back, so you can reassign, is that all?  Something like this should work for that:
>
> c = makeContainer!typeof(c)(c.filter!(x => x < 3));
>
> Implementation left as an exercise.
>
> -Steve

It would obviously be a dead simple function, the question is whether it's generally useful enough for the standard library, which I personally don't see it being, at least not until I see at least one good example. I was just pointing out the fact that it would require a function to abstract away the construction for all reasonable containers T.

You would also have to decide on an explicit convention of construction when T is a user-defined type (e.g. define a constructor taking an input range), as such a function would effectively formalise it.

(By the way, the template instantiation shortcut syntax only works when the only argument has exactly one token; your example code has an error.)

On Fri, 04 May 2012 11:21:06 -0400, Jakob Ovrum <jakobovrum@gmail.com> wrote:

> On Friday, 4 May 2012 at 13:22:47 UTC, Steven Schveighoffer wrote:
>> Structs don't make very good containers.  A slice is not really a container.
>
> Most containers in std.container are structs. A struct can do everything a class can do, for example, you can choose whether to use reference semantics or not. So I don't think the assertion that structs aren't good for containers is true, when they can do so much more than classes. There is still debate whether std.container's containers should be classes or structs, but even so, third-party containers might have different requirements.

Non-reference semantics for containers are very bad.  Look at std::vector and how much inefficient code exists that passes it by value.

A container has one important property with regard to its elements, it *owns* the elements.  This screams reference semantics, because if you use value semantics, you need to *copy all the elements*.

Yes, a struct can do reference semantics, but it makes little sense to fight the type system and shoehorn it into reference semantics, when classes are reference types by default.

> It would obviously be a dead simple function, the question is whether it's generally useful enough for the standard library, which I personally don't see it being, at least not until I see at least one good example.

I think the use case is, instead of defining some transformation function X as a member of a container, you:

1. define X as a function that accepts a range and returns a range
2. define a way to obtain a range of all elements from a container
3. define a way to construct a new container from a range.

Then you only have to define X once, instead of on every container type.  And you can specialize some containers for X because of UFCS.  See Jacob's example.

> You would also have to decide on an explicit convention of construction when T is a user-defined type (e.g. define a constructor taking an input range), as such a function would effectively formalise it.

Most definitely.  I think any D-based container that can't be constructed from a range of values isn't worth implementing.

> (By the way, the template instantiation shortcut syntax only works when the only argument has exactly one token; your example code has an error.)

Yes, I realized this after posting, but figured the point would get across ;)  I sometimes miss being able to do this in my real code, the omission of parentheses for template instantiation is an awesome feature!

-Steve

On Friday, 4 May 2012 at 15:47:31 UTC, Steven Schveighoffer wrote:
> Yes, a struct can do reference semantics, but it makes little sense to fight the type system and shoehorn it into reference semantics, when classes are reference types by default.

It makes sense when you want something like reference counting.

> I think the use case is, instead of defining some transformation function X as a member of a container, you:
>
> 1. define X as a function that accepts a range and returns a range
> 2. define a way to obtain a range of all elements from a container
> 3. define a way to construct a new container from a range.
>
> Then you only have to define X once, instead of on every container type.  And you can specialize some containers for X because of UFCS.  See Jacob's example.

After a quick look over the thread again, I still don't see any real examples of use cases from Jacob (I admit I could still be missing it... somewhere...).

Here's one scenario I came up with just now, anyway:

T transmogrify(T)(T input) if(isInputRange!T)
{
    auto transformed = map!foo(input);
    return makeContainer!T(transformed);
}

So basically, a templated function which, for some reason, wants to return the same type it receives. I still can't think of a real example similar to the above toy example, though. If the input just has to be an input range, isn't the output fine as an input range too? Isn't it better to leave the decision to the caller (whichever function on the way up the stack has the concrete types) of whether to do the expensive reconstruction operation? The code smells, is all I can say.

So, I think the question is still whether such a function is appropriate for the standard library.


> Most definitely.  I think any D-based container that can't be constructed from a range of values isn't worth implementing.

I agree, and I think the most natural way to implement this abstract interface would be using the constructor, but Jacob mentioned functions like toList() etc. earlier in the thread. Using the constructor is more idiomatic if Phobos is any example, but I suppose there could be reasons for not using it.

(Obviously, array() only exists because there is no choice, slices being in-built).

> Yes, I realized this after posting, but figured the point would get across ;)  I sometimes miss being able to do this in my real code, the omission of parentheses for template instantiation is an awesome feature!

It's always sad to see code failing to leverage it; often pops up with string tokens. It does make templates heaps less intimidating, and I applaud Andrei (sorry if this attribution is wrong!) for it :)

On Friday, May 04, 2012 11:47:31 Steven Schveighoffer wrote:
> Yes, a struct can do reference semantics, but it makes little sense to fight the type system and shoehorn it into reference semantics, when classes are reference types by default.

A struct makes a lot more sense than a class when you need deterministic destruction. IIRC, the last time that it was discussed, it was decided that we'd go with structs rather than classes, because it would work better with custom allocators, but it was a rather involved discussion, and I don't remember all of the details.

With a class though, you would _have_ to wrap it in a struct to be able to properly destroy it if it weren't garbage collected, or you'd have to manually free it, which would be far less safe and would make how you use the class vary widely based on the custom allocator. For instance, if your custom allocator used malloc and free, you'd need the container to be reference counted in order to clean itself up properly. The closest that you could get with classes without wrapping them in a struct would be to have the container allocated on the GC heap and have its guts allocated by the custom allocator. But if you used a struct, then the struct itself would be on the stack, avoiding the heap allocation and giving you the deterministic destruction that most allocators will need.

If you're just going to use the GC heap, then classes are going to generally be better for reference types, because they naturally have reference semantics, but if custom allocators are involved, as far as I can tell, you pretty much need structs to get deterministic destruction and thus have the allocators work properly.

- Jonathan M Davis

On Friday, May 04, 2012 13:46:33 Jacob Carlborg wrote:
> I give up. Apparently you don't think it's useful.

If you can come up with an example/reason why it would actually be useful, then great. But I don't see why it would ever matter what the original container type really was.

You need the original range type in cases like std.container's remove function, but then the range must _be_ the original range type from that exact container in order to work, and there's no way that you could turn a wrapped range into the proper range for that, since you'd have to create a new container, and then the resultant range would be for the wrong container. And that's the only situation that I can think of where it really matters what the original container type was. If you want to construct a new container out of a range, then great, but since it's a new container, I don't see how it matters what the original container was unless you intend to assign the result to the new container or somesuch, in which case, you would already have access to the type, because you'd have a variable to assign to.

- Jonathan M Davis

On Fri, 04 May 2012 13:09:06 -0400, Jonathan M Davis <jmdavisProg@gmx.com> wrote:

> On Friday, May 04, 2012 11:47:31 Steven Schveighoffer wrote:
>> Yes, a struct can do reference semantics, but it makes little sense to
>> fight the type system and shoehorn it into reference semantics, when
>> classes are reference types by default.
>
> A struct makes a lot more sense than a class when you need deterministic
> destruction. IIRC, the last time that it was discussed, it was decided that
> we'd go with structs rather than classes, because it would work better with
> custom allocators, but it was a rather involved discussion, and I don't
> remember all of the details.

Allocation and destruction are orthogonal to the problem.  For example, in working on the new std.io, I've had to make RefCounted!(class) work,  All I do is allocate the class data into the C heap.

The issue is, do you want pass by reference, or pass by value.  My opinion is that it should always be pass by reference for container types.  And classes make that *so* much easier.

With structs, you have to jump through hoops to get them to properly be reference types.

-Steve

On Friday, May 04, 2012 13:38:24 Steven Schveighoffer wrote:
> On Fri, 04 May 2012 13:09:06 -0400, Jonathan M Davis <jmdavisProg@gmx.com>
> 
> wrote:
> > On Friday, May 04, 2012 11:47:31 Steven Schveighoffer wrote:
> >> Yes, a struct can do reference semantics, but it makes little sense to fight the type system and shoehorn it into reference semantics, when classes are reference types by default.
> > 
> > A struct makes a lot more sense than a class when you need deterministic
> > destruction. IIRC, the last time that it was discussed, it was decided
> > that
> > we'd go with structs rather than classes, because it would work better
> > with
> > custom allocators, but it was a rather involved discussion, and I don't
> > remember all of the details.
> 
> Allocation and destruction are orthogonal to the problem. For example, in working on the new std.io, I've had to make RefCounted!(class) work, All I do is allocate the class data into the C heap.

It's not orthogonal if you want the allocation to be internal to the type and not have to worry about wrapping the container in a struct to actually get it to deallocate properly. For instance, you can allocate a class with malloc, but without a wrapper, you're going to have to keep track of the fact that it was allocated with malloc and make sure that you destroy it and free it. But if the container is a struct, then all of that can be internal, because the struct itself is on the stack rather than the heap. I don't see how you could use a custom allocator with a class and not have a wrapper, which means that using a custom allocator would affect the API of anything using containers that used them.

As I understand it, Andrei intends for the custom allocators to be dynamic, which means that the type of the container will be the same regardless of the allocator used. And if that's the case, I don't see how you can safely use classes as containers without always wrapping them in structs. And if you're going to do that, why whould you make them classes in the first place?

> The issue is, do you want pass by reference, or pass by value. My opinion is that it should always be pass by reference for container types. And classes make that *so* much easier.
> 
> With structs, you have to jump through hoops to get them to properly be reference types.

Yes. std.container's container types will most definitely be reference types, and yes, in general, that means that using classes would be better, but custom allocators throw a major wrench in that, because you need to control where the class is (which doesn't work very well without a wrapper, since without one you have to worry about freeing it manually), and many custom allocators need deterministic destruction, which classes don't provide.

I believe that this was the most recent discussion on the issue:

http://forum.dlang.org/post/mailman.1543.1323832143.24802.digitalmars- d@puremagic.com

We'll have to see what Andrei actually proposes though, since he's been working on the custom allocators, and I don't know what has and hasn't changed as he's been working on them.

- Jonathan M Davis

On Fri, 04 May 2012 13:59:02 -0400, Jonathan M Davis <jmdavisProg@gmx.com> wrote:

> On Friday, May 04, 2012 13:38:24 Steven Schveighoffer wrote:
>>
>> Allocation and destruction are orthogonal to the problem. For example, in
>> working on the new std.io, I've had to make RefCounted!(class) work, All
>> I do is allocate the class data into the C heap.
>
> It's not orthogonal if you want the allocation to be internal to the type and
> not have to worry about wrapping the container in a struct to actually get it
> to deallocate properly.

Allocation of the container itself is a different problem than allocation of its internals.  I think you are confusing the two.

For example, I can have a red black tree that allocates all its elements using malloc, then allocate the class itself on the stack using scoped so it becomes deallocated after exiting the scope.

Or I can use malloc for internal allocation, and use new to allocate on the heap, and let the GC clean up the tree (and the malloc-based allocator stored in the class cleans up its elements).

> For instance, you can allocate a class with malloc,
> but without a wrapper, you're going to have to keep track of the fact that it
> was allocated with malloc and make sure that you destroy it and free it.

Yes, and this has nothing to do with the custom allocator needed to allocate its elements.  The container owns the elements, it doesn't own itself.  Even a struct can be allocated on the GC heap.

> As I understand it, Andrei intends for the custom allocators to be dynamic,
> which means that the type of the container will be the same regardless of the
> allocator used. And if that's the case, I don't see how you can safely use
> classes as containers without always wrapping them in structs. And if you're
> going to do that, why whould you make them classes in the first place?

Again, these are orthogonal problems.  Who allocates and owns the container is different than who allocates and owns the elements.

The container is responsible for cleaning up the elements (via the allocator it is handed), someone else is responsible for cleaning up the container.  It could potentially be the same allocator, but it also could potentially be something completely different.

The only requirement is that the allocator *must* live at least as long as the type itself (if you are going to do dynamic allocators).  This rules out a simple GC-allocated reference type as an allocator, but the container itself can be GC allocated.

Dcollections does not currently use dynamic allocators, although it could be made to do so.  Currently, the allocator is a struct which is stored inside the container.

-Steve

On 2012-05-04 14:28, Chris Cain wrote:
> On Friday, 4 May 2012 at 11:46:34 UTC, Jacob Carlborg wrote:
>> I give up. Apparently you don't think it's useful.
>
> I'm not seeing it either, but it might help if you gave a concrete
> example of where it could/should be used and what benefits it might
> have. I think it'll be rather hard to come up with an example where the
> programmer wouldn't know what the original type was and have it actually
> matter.

What I actually want is to perform some operations on a collection and to have those return a collection. That's not how ranges work, I know, but I think it's more useful to get back a collection of than a range.

-- 
/Jacob Carlborg

On Fri, 04 May 2012 12:32:39 -0400, Jakob Ovrum <jakobovrum@gmail.com> wrote:

> On Friday, 4 May 2012 at 15:47:31 UTC, Steven Schveighoffer wrote:
>> I think the use case is, instead of defining some transformation function X as a member of a container, you:
>>
>> 1. define X as a function that accepts a range and returns a range
>> 2. define a way to obtain a range of all elements from a container
>> 3. define a way to construct a new container from a range.
>>
>> Then you only have to define X once, instead of on every container type.  And you can specialize some containers for X because of UFCS.  See Jacob's example.
>
> After a quick look over the thread again, I still don't see any real examples of use cases from Jacob (I admit I could still be missing it... somewhere...).

This one:

Collection c = new Collection();
c = c.filter!(x => x < 3).toCollection();

filter isn't a property of c, it's a range-producing function.  So I only have to define filter once, as a range accepting, range producing function.  And any container type, as long as it can produce a range, can use this as a pseudo method (via UFCS) to make a filtered copy of itself.

-Steve