On Sat, Nov 15, 2014 at 02:02:29AM +0300, Dmitry Olshansky via Digitalmars-d wrote: > 15-Nov-2014 01:38, Steven Schveighoffer пишет: > >On 11/14/14 5:25 PM, Dmitry Olshansky wrote: > >>15-Nov-2014 01:16, IgorStepanov пишет: > >>>Recently I encountered the following problem. > >>>I need a simple stack of uint. > >>>I want to push uints back and pop it. I don't want to copy this stack > >>>and I want it to work fast. > >>> > >>>In a first approximation, the problem seems easy. > >>> > >>>uint[] my_stack; > >>>my_stack.reserve(256); > >>> > >>>my_stack ~= 1; //push > >>>uint head = my_stack[$ - 1]; //top > >>>my_stack.length--; //pop > >> > >>Just make push into: > >> > >>my_stack.assumeSafeAppend(); > >>my_stack ~= value; > >> > >>To avoid relocations. > >> > > > >In actuality, you do not need this before every push. You only need > >it between a pop and a push. > > > >I highly recommend not doing arrays-as-stacks, because you end up > >writing your own type. > > +1 > > >At that point, you may as well remove the funky array/slice > >semantics, and store the capacity yourself. > > > > That's the second approximation ;) > The third goes to C's malloc. > The 4-th starts with some small array on stack, then goes to C's malloc. [...]
This smells like it should be a Phobos module. ;-) No, seriously, I've reimplemented this myself a few times already. Mostly I've only gotten as far as assumeSafeAppend, but at least one instance seems to be pushing towards the second/third stage. T -- Trying to define yourself is like trying to bite your own teeth. -- Alan Watts
