Container hierarchy vs. container types

[Andrei Alexandrescu]

Michel Fortin wrote:
> On 2010-03-05 16:09:08 -0500, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org> said:
> 
>> A range is a view on a container. As such, popping off a range does 
>> not affect the topology of the underlying container. Consider, for 
>> contrast, a balanced binary tree. Removing an element triggers a 
>> rebalance of the tree, but popping an element off an iterator in that 
>> tree does not affect the tree itself.
>>
>> Fair enough?
> 
> That's a fine definition, except for the word "topology".
> 
> Whether it changes the topology should be an implementation detail. 
> Popping of a C++ vector or a hash table doesn't change the topology, 
> will you make them ranges? That doesn't make much sense.

It's essential. The way ranges work, they can never change the topology 
of the collection they operate on. That is a fundamental aspect. A 
container operation may or may not affect its topology.

> Also, do you consider that popping off a stream affects its topology?

A stream has no topology I can think of. Within this context, I define 
topology loosely as the way the data of a container is stored and 
interconnected in memory.

> If 
> your stream is buffered, you're probably advancing a pointer through a 
> buffer with 'pop', and deallocating old buffers from time to time. So 
> this definition would forbid a stream from being a range. That doesn't 
> make much sense.
> 
> And similarly you could have a queue container where you insert things 
> at the back and pop things from the front. But that's basically the same 
> thing as a stream. Is a queue a container or a range?
> 
> I think this definition is more on the spot: a range is something you 
> consume, a container is something used to hold data. Those definition 
> are not mutually exclusive, but is this really a problem?

I think it is. For starters, copying a forward range copies its state, 
whereas copying a container and then removing stuff from it results in 
two containers with less net state.

By and large, clearly there are important distinctions between ranges 
and containers. My perception is that you do have that understanding, 
but are doing a Plato on me. I'm a bit tired of having a Plato done on 
me, particularly in this case when I don't have the answers. Would be 
great to strengthen the weak definitions we have now instead of 
challenging them.


Andrei