container stuff

[Steven Schveighoffer]

On Thu, 27 May 2010 00:20:24 -0400, Jonathan M Davis  
<jmdavisProg at 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