Deque impl.

[Dmitry Olshansky]

31-Jan-2013 21:47, Andrei Alexandrescu пишет:
> On 1/31/13 12:12 PM, Dmitry Olshansky wrote:
>> IMHO we need both kinds of containers: small value semantics a-la STL
>> (with the usual samll string optimization and whatnot) and the large
>> bulky ones with clean reference semantics.
>
> I don't see much use case for the small value semantics containers.
>

Even if we had safe and clean stack allocator consider ref-semantic array:

struct Array{
	struct Payload{
		T* data;
		size_t len;
		//... other stuff
	}
	Payload* payload;
	Allocator alloc; //a reference most likely
	...
}


Now you want to replace this C-ish (but effective) code:

T[SIZE] data;
size_t data_size;
...
{
	...
	//push zis
	data[data_size++] = new_item;
	//and reiteration of the theme
}

(keeping in mind that an allocation might cost more then the whole code 
in question in the majority of cases)

The other variation of the above that doesn't have the upper bound is 
use alloca for starters, then fallback to malloc/free on demand.
I've seen quite a few of cases like this throughout the phobos and boy 
those are all ugly. The primitive for clean small-scale throw-away 
containers is a dire need.

I grant you that there is a lot of cases where arrays are tiny 90% of 
time and small in 99% of time e.g. identifiers are tiny < 16, small < 
64, so are relative file paths etc. Yet there is always some measly 
percent (say 1% or 0.1%, it exists) of rare larger cases to handle.

IRC bearophile once shown us how these types of small vectors used 
extensively in LLVM with great benefit (they replaced std:vectors).
In other words the use case is niche but is frequently reinvented badly.

-- 
Dmitry Olshansky