Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Dynamic Storage Allocation: The Other Kind of Heap


In the preceding chapters when analyzing an algorithm involving dynamically allocated storage, we assume that the time taken to acquire or to release storage is bounded by a constant. Specifically, Axiom gif in Chapter gif states that the running time of operator new is a constant, tex2html_wrap_inline58579, and that the running time of operator delete is also a constant, tex2html_wrap_inline58581.

But is this really so? To answer this question, we consider in this chapter the dynamic management of a pool of memory. In particular, we consider several different implementations for the operators new and delete and we show that the assumptions of constant running times are not always valid.

next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.