This question already has an answer here:
- How do malloc() and free() work? 14 answers
There's no simple, standard answer. Most implementations of
operator delete ultimately forward to
free, but there are a
lot of different algorithms which can be used for those. The only thing that's
more or less universal is that allocation will typically allocate a little bit
more than requested, and use the extra memory (normally in front of the address
actually returned) to maintain some additional information: either the actual
size allocated or a pointer to the end of the block (or the start of the next
block). Except that some algorithms will keep allocations of the same size
together, and be able to determine the size from the address. There is no
single answer to your question.
new is oftentimes implemented on basis of malloc/free.
How does malloc/free implement it? The answer is: It depends on the implementation. Surprisingly: Malloc oftentimes does not keep track of the allocated blocks at all! The only thing, malloc is doing most of the time, is adding a little bit of information containing the size of the block "before" the allocated block. Meaning, that when you allocate 40 bytes, it will allocate 44 bytes (on 32bit machines) and writes the size in the first 4 bytes. It will return the address of this chunk+4 to you.
Malloc/free keeps track of a freelist. A freelist is a list of freed memory chunks that is not (yet) be given back to the operating system. Malloc searches the freelist, when a new block is needed and when a fitting block is available uses that.
But a more exhausting answer about malloc/free, I have given here: How do malloc() and free() work?
One additional information:
One implication of the fact, that many allocators don't track allocated blocks: When you return memory by free or delete and pass a pointer in, that was not allocated before, you will corrupt your heap, since the system is not able to check if the pointer is valid. The really ugly thing about it is, that in such a case, your program will not dump immediately, but any time after the error-cause occured ... and thus this error would be really ugly to find. That is one reason, memory handling in C/C++ is so hard!
new maintains a data structure to keep track of individually allocated blocks. There are plenty of ways for doing that. Usually, some kind of linked list is used.
Here a small article to illustrate this.