Re: Only one end of a stack is dynamic, the oldest item is the last removed.
"Jeff?Relf" <Jeff_Relf@Yahoo.COM> wrote in message
news:Jeff_Relf_2007_Sep_25__6_21_Pr@Cotse.NET...
I told Messrs. Roberts and Voigt:
" If, for some --> really <-- odd reason,
your stack is huge and C.P.U. intensive, just give it its own heap;
so it's dynamic and you never have to move it. ".
And you ( Mr. Voigt ) insulted me and replied:
" But you will have to move it, because
if you add to the end and remove from the beginning... ".
I believe what I said is, in effect, that you don't accept software
engineering wisdom. You're proving my point yet again. If you find that
insulting, you may wish to do something to change the situation rather than
suggesting that I'm posting libel.
Huh ?
Only one end of a stack is dynamic, the oldest item is the last removed.
So far, Mr. Voigt, all I recall about you is:
1. You needlessly spam us with quotes.
( i.e. either you're lazy and/or you can't see the thread )
And you intentionally remove portions of posts that undermine your case. I
specifically mentioned queues. Now, it is not necessary to add to the end
of a queue and remove from the beginning, you could just as easily add to
the beginning and remove from the end. There are also priority queues where
you might add or remove from the middle.
2. You don't know what a stack is.
It's commonly used to refer to a LIFO queue. Generally it does not require
random indexed access, or scans across the whole content, so it doesn't
benefit from sequential placement of elements.
3. You imagine that link-lists are still a good idea, in 2007.
( Ever hear of a Memory Management Unit ? )
Yes, and so does a majority of professional software engineers, as
demonstrated by the fact that practically every language and library
supports them. Things weren't added to the C++ standard library by a single
person, they were discussed by some of the most brilliant programmers around
and they debated things you haven't ever thought of. Google for the
discussion on whether std::list::size should be made O(1) in the g++ library
and you'll find dozens of performance benefits to linked lists over a
dynamic array.
Furthermore, where do you think the MMU gets its mappings from? How does
VirtualAlloc decide what address space to give you? These are all almost
certainly done using linked lists, not "dynamic arrays". Did you know that
the reason that Linux never lets you kill the init process (pid 1) is to
guarantee that the process linked list is never empty, removing a lot of
conditional branches that in practice would never be taken?
Even in the case of large, dynamic, C.P.U.-intensive queues,
a dynamic array of pointers and dedicated, destroyable heaps
would be better than a linked list
( and/or C++'s automatic garbage collection ).
This is simply not true. A linked list and a free pool can be considerably
more efficient. The expense of allocation and deallocation are when you
have to search the free list of a heap for a block of appropriate size, if
you maintain a pool of correctly-sized blocks then there is no issue.
The only reason you call the queue "C.P.U.-intensive" is because yours would
be, from constantly copying all the elements around whenever the queue was
moved.