On 05/26/2010 04:47 PM, Steven Schveighoffer wrote:
>> b) associative arrays can define c[a .. b] for a, b key types.
>> It's nontrivial but it can be done.
>
> I decided for dcollections that this only makes sense on sorted maps.

Yah, I meant sorted collections as well.

>> c) sentinel-terminated arrays (e.g. C stringz) can only define c[a
>> .. $] for an integral a.
>
> I really hope we are not considering null-terminated strings when
> deciding container functions...

I don't know. When working on an abstraction I find it very, very useful to anchor it in concrete incarnations that I know of. (Such an approach has led to taming the gnarly UTF-8 strings into nice bidirectional ranges.) I'm not crazy about null-terminated strings, but slists are also sentinel terminated, they just aren't contiguous. Comparing and contrasting these and other concrete instantiations is great exercise that only makes the abstraction better.

>> e) Any other cases?
>
> On a sorted AA, slicing using any two keys are possible (as long as
> the keys exist in the AA).

Great.


Andrei

On 05/26/2010 11:15 PM, Jonathan M Davis wrote:
> The fact that the operations in std.container carry specific performance
> constraints will make it work much better I think. Also, D's ability to
> alter how a function is defined based on the attributes of a given container
> makes it much easier to write algorithms which are efficient for each
> container type without having to worry about calling member functions in
> some cases and non-member functions in others or anything like that. So, I
> think that std.container really looks like it could lead me to write good,
> container-independent code. However, I don't have much experience with
> writing container-independent code because it doesn't work very well in C++,
> and it can be quite detrimental to performance in other languages like Java
> because the performance characteristics of different containers vary so
> much.

Yeah, exactly. We're all in the same boat really. Time will tell how that really goes.

Andrei

Andrei Alexandrescu:
> Done. removeAny was my choice as of a few months ago but I'd forgotten.

I suggest to call it just "pop".

Bye,
bearophile

Jonathan M Davis:

> Well, I've never needed to do that particular operation on _any_ container, so it does strike me as weird regardless. I've basically always been looking to remove a specific element or elements or to remove the element at a specific location.

You have probably missed my other answer. But I can add some more. That operation is common. You use it every time you have a container that doesn't define a deterministic order (like hash sets, hash associative arrays, and so on) and you want to process and consume its items. In such collection you can't ask to pop the last or first item because they are not defined. So you pop out one randomly. I have used it many times in my programs.

Bye,
bearophile

On Thu, 27 May 2010 00:20:24 -0400, Jonathan M Davis <jmdavisProg@gmail.com> wrote:

> Steven Schveighoffer wrote:
>
>> Jonathan M Davis Wrote:
>>
>>> Looks interesting overall. There is one function, however, which makes no
>>> sense to me: removeElement()/stableRemoveElement().
>>>
>>> So, it basically removes a random element from the container? It could be
>>> quite consistent as to which element it removes from the container (it
>>> being implementation-dependent), but effectively, it removes a random
>>> element? What's the point of that? I can't remember the last time - if
>>> ever - that I wanted to remove an element from a container and I didn't
>>> care which. Or am I misunderstanding what it does?
>>
>> I think you are misunderstanding.  Random element means you can't tell
>> which one is removed, but it doesn't *have* to be truly random :)  It most
>> likely will be the most convenient element to remove (maybe that would be
>> a better description).  In other words, you can't expect it to always be
>> the last element, or the first element, or the lowest element, or
>> whatever.
>>
>> So essentially, I think that's what you were asking for, and I think
>> that's what Andrei meant.
>>
>> -Steve
>
> I don't think that I misunderstood, but I may not have stated it well. No,
> the element is not _truly_ random, but it is removing an unspecified element
> which could be any element in the container, and is therefore random in the
> sense that you aren't telling it which one to remove. I've never been in a
> situation where it made any sense to do that. So, the function struck me as
> really weird.
>
> If you wanted truly random, you'd have to implement a function that actually
> did random number generation or whatnot to decide which element to pick, and
> presumably, it would be abnormal to use that here (though I think that doing
> so would still follow the API). So, no, removeElement() (now removeAny()) is
> not truly random, but it isn't deterministic from the perspective of the
> programmer having any clue which one will be removed, and it may or may not
> be deterministic from the container's perspective.

OK.  I think the point of removeAny is that it removes an element as fast as possible, however that can be implemented by the container.  I.e. removing the back or front element may not be the fastest operation, think about something like a tree, where the fastest element to remove is probably the top element.

-Steve

bearophile wrote:
> Jonathan M Davis:
> 
>> Well, I've never needed to do that particular operation on _any_ container, so it does strike me as weird regardless. I've basically always been looking to remove a specific element or elements or to remove the element at a specific location.
> 
> You have probably missed my other answer. But I can add some more. That operation is common. 

> You use it every time you have a container that doesn't define a deterministic order (like hash sets, hash associative arrays, and so on) and you want to process and consume its items. In such collection you can't ask to pop the last or first item because they are not defined. So you pop out one randomly. I have used it many times in my programs.

When is it better to do it that way, rather than just iterating over all elements, and then completely empty the container?
(Just curious -- I'm having trouble thinking of a use case for this feature).

Don:
> When is it better to do it that way, rather than just iterating over all
> elements, and then completely empty the container?
> (Just curious -- I'm having trouble thinking of a use case for this
> feature).

I'm having troubles understanding why two persons have troubles seeing use cases for this feature :-)

Iterating over the container and then emptying the container is two operations, you have to keep in mind to empty it, while if you pop items out of it progressively you just need to keep in mind to do one thing, and you avoid forgetting the final cleaning.

Also, the progressive popping out of items allows you to have a collection that is correct in every moment, there is no risk of "removing" two times an item, so you can pass around the data structure in any moment of this process of wearing it away.

This is what you suggest (Python code):

s = set(["ab", "bc", "de"])

def process_item(item):
    print item

for item in s:
    process_item(item)
s.clear() # removes all items


But this is better, you can print the correct collection in any moment and you can't forget the final clear:

s = set(["ab", "bc", "de"])

def process_item(item):
    print item

def show_data(items):
    print items

while s:
    process_item(s.pop())
    show_data(s)

Bye,
bearophile

bearophile wrote:
> Don:
>> When is it better to do it that way, rather than just iterating over all elements, and then completely empty the container?
>> (Just curious -- I'm having trouble thinking of a use case for this feature).
> 
> I'm having troubles understanding why two persons have troubles seeing use cases for this feature :-)
> 
> Iterating over the container and then emptying the container is two operations, you have to keep in mind to empty it, while if you pop items out of it progressively you just need to keep in mind to do one thing, and you avoid forgetting the final cleaning.

Yes, but if I understand correctly, the only reason to have removeAny _as a primitive_ is for speed. And iterating over the container followed by a single removal is almost always going to be much faster.

If, however, speed is not critical, removeAny can be a generic function -- call removeFront() if present, else call removeBack().
And your examples would work just fine with that.

I'm having trouble identifying a use case where it needs to be a primitive.

On 05/27/2010 06:49 AM, Don wrote:
> bearophile wrote:
>> Jonathan M Davis:
>>
>>> Well, I've never needed to do that particular operation on _any_
>>> container, so it does strike me as weird regardless. I've basically
>>> always been looking to remove a specific element or elements or to
>>> remove the element at a specific location.
>>
>> You have probably missed my other answer. But I can add some more.
>> That operation is common.
>
>> You use it every time you have a container that doesn't define a
>> deterministic order (like hash sets, hash associative arrays, and so
>> on) and you want to process and consume its items. In such collection
>> you can't ask to pop the last or first item because they are not
>> defined. So you pop out one randomly. I have used it many times in my
>> programs.
>
> When is it better to do it that way, rather than just iterating over all
> elements, and then completely empty the container?
> (Just curious -- I'm having trouble thinking of a use case for this
> feature).

Again, any worklist-based algorithm will remove and add work items without minding for a specific order.

http://cseweb.ucsd.edu/classes/sp00/cse231/report/node12.html


Andrei

On 27/05/2010 06:06, Andrei Alexandrescu wrote:
> std.container will not contain hot-swappable components. It will contain
> components that could be used in some of the hot swaps. It's just one
> level lower than what you are discussing.
>
> That doesn't make it any more or less incompatible with dcollections.
>
>
> Andrei

Thanks for taking the time to explain.
Whatever direction D collections will take, I think we all agree that collections are the "missing link" in D. Once done, I am convinced that a number of D2 add on libs will grow drastically.
Just can speak for myself, f.i.  creating a dock /undock, tabbed MDI GUI without having a solid collection lib is not really a pleasure..
Bjoern