C++ Memory Management – Producing Large Problems Without Filling Up Huge Arrays

You aren't using it now, but the next time you leak memory or get a double delete, you'll be begging to come back to std::vector<T>, std::unique_ptr<T, Del> and std::shared_ptr<T>, which can solve those problems easily- almost trivially. That's what happens to everyone who uses C over C++, eventually, and the smarter ones just don't wait for the bugs to pop up before moving over.

Code that uses new and delete directly doesn't really belong in C++, it belongs in that kind of half house that we refer to as "C with Classes". That's where the language was circa 1985. It's not particularly similar to C++, circa 2011. In all likelihood, wherever you learned C++ simply didn't teach it very well- something that is unfortunately rather common- and with a better education, you would find use of these features.

Specifically, as I listed above, C++'s generic data structures and the resource-managing classes simply are fundamentally massively superior to anything C has to offer. If you want a dynamically allocated array, then use std::vector<T>. That's a pretty common use case. If you aren't using them, then your code is at huge risk of error unnecessarily- especially resource management related. C++ can guarantee safety and re-use code in a way that C can never touch.

However, I think that you also might be expecting too much. Writing templates and operator overloads is not common for library consumers. If your code uses std::vector<T>, you don't need to write a template to make that happen. If your code uses std::string, nobody is forcing you to overload your operators. You only have to do those things to write std::vector<T> and std::string- but you can still take full advantage of them.

Polymorphism/inheritance also only has a specific use case. If your code happens to not require you to write any templates or use virtual functions, then it doesn't, and there are programs or segments of programs where you don't need to write your own templates.

Also, there's no gain in performance in C over C++.

Let's imagine for a moment all of your Items have the same size. A simple scheme would then be to have a pool of items, plus a bit for each one to mark whether it is allocated or not. Then the algorithm is simply "loop through the pool until you find an empty Item".

This is a bitmap allocation scheme.

A faster variation of this scheme is to have the free Items form a linked list. Then to allocate you remove a block from the free list (and you could even use the space for the pointer as data, since it isn't used when the block is allocated). To free you add it back to the linked list.

This is the free lists approach you mentioned.

Expanding that to variable-sized allocation, you have the entire memory area you're working with be a single "Item". When you need a smaller-sized space, you split it in half and run the algorithm recursively. When you have a fitting size, mark it as "allocated" and return it. To free, mark it as "unallocated" and merge the areas back as needed.

This is the buddy allocation scheme.

Most allocation algorithms don't do compaction, i.e. moving memory blocks around to make more space. They avoid fragmentation instead. And when their pool is full, they ask the system for more memory (the system normally allocates memory in whole pages (normally 4KB each), so they have to be subdivided).

Also, normally garbage collection is performed at a higher level (see munificent's garbage collector "tutorial" for more details).

A good representative of a "common" allocation scheme is Doug Lea's malloc. It is used by glibc and in several other places. It includes a little overview of the algorithm in its page.

The thing is that you need the right allocation scheme for the problem at hand. For example, Doug Lea's malloc is tailored and optimized to be reasonably fast, compact and safe (it can detect some usage errors), but if all you're doing is fixed block allocation, a linked list approach is probably going to be much more performant.

The wikipedia page on memory management has an overview of a few allocation schemes, but if you want all the details I really recommend Knuth's The Art of Computer Programming, which has a whole section of the second chapter (vol. 1) dedicated to this problem (considering the sheer size of the book, this really means something).