so, i'll be doing some console development again and one thing that puzzles me is the use of the STL. unfortunalty, using the STL is mostly considered evil in this area, since it constant memory (de-)allocations fragment the heap quickly. a possible solutions came to my mind, when i saw the boost::array container. it uses a template argument to control the size and doesn't need any dynamic heap allocations. i could imagine extending this approach to more sophisticated containers like strings, lists or maps with a template parameter controlling the maximum number of objects (who are internally stored in an fixed-size array). but one thing puzzles me: won't this introduce a massive template overhead? boost::array claims to introduce zero overhead over plain arrays, but after all the compiler has to make a new specialization not only for every type the container is used with (like with the STL containers), but also for every size used. while this may be not so dramatic for the rather small boost::array class, i could imagine a massive code bloat for more complex containers - maybe too much for smaller systems? i could also imagine a page-fault related performance penalty due to increased code size... any ideas on this? i also looked around for libs that implement this, but although embedded developers could make use of something like that (as opposed to plain fixed-size (char) arrays) i couldn't find anything in this direction.

i also looked at implementing custom allocators some time ago.
this approach is a little different as is would mean using memory pools for certain objects.
maybe i don't fully understand them (as they are complex indeed), but i don't see how they really solve the allocation problem.
take a string for example. you might write an allocator to make it use only a specific memory pool, but using the same allocator-type for different strings would introduce the fragmentation problem again as opposed to the boost:array approach, where every instance has it's own memory pool...

Or, if you're going to resort to a fixed-size, static allocation anyhow, just use STL vectors and reserve the static size up front. IIRC, STL containers don't down-size unless you tell them to, so they'll stay that size forever.

As a bonus, rather than an immediate problem being caused if you exceed the bounds of the array, the size will simply be increased. As the program ends, you can check whether the final size of the container is larger than the size you initialized it as (and by how much) to expose memory over-use. This would be generally more effective than an assert on overflow, because the program will have the opportunity to keep running and can expose more of such errors.

For other containers, such as lists, a custom, block-based allocator will do great things for fragmentation.

Quote:Original post by GenuineXP
But where are the individual "pools" for each string in this case? Isn't this fragmentation too, since the instantiation of each string requires creating a new "pool"?

yes, but in embedded world one usually clearly defines the point for allocating and deallocating memory. so usually, you'd create all containers with their maximum capacity at one spot, as apposed to "now and then, whenever you need them" in non-embedded world (PC etc.).

Quote:Original post by Ravyne
Or, if you're going to resort to a fixed-size, static allocation anyhow, just use STL containers and reserve the static size up front. IIRC, STL containers don't down-size unless you tell them to, so they'll stay that size forever.

afaik this is only true for vectors, but not for other containers.

I appended my above post to speak about other containers. Fragmentation of these other containers will benefit greatly from a custom block-based allocator.

Alternatively, some containers can be made to work with a vector as the back-end storage solution -- though I'm not sure how much control it will give you over setting the reserve size.

Quote:Original post by Zahlman
Practically speaking, it would be very unusual to know the size of several containers in the system at compile time, but also have many different sizes.

in my experience, it's normal to use some #define/constant to allocate some fixed-size array.

Quote:Original post by Zahlman
But anyway, template code generation is not quite as dumb as that description suggests.

thats basically the question. could you elaborate on that?

Quote:Original post by Zahlman
There aren't templated, static-size equivalents for other types of containers, because it wouldn't make sense: there's almost no reason to put things in a linked list if you know ahead of time how many of them there will be.

not how many items, the maximum number of items. when working with tight memory limitations you should know the maximum memory usage beforehand anyways, as you can't afford running out of memory because of a situation that didn't occur in your testing.
and a list still has completely other access characteristics than an array. in my experience, developers resort to plain arrays even if other containers might be faster simply because of allocation issues.