stack based string class

Instead of writing stack-based vectors, strings and the likes, the STL has the concept of an allocator.

Write a 'stack-based allocator' and pass your custom allocator to a vector class or to a string (basic_string) and then when the container wants to allocate memory it gets given pointers to the stack instead of the heap; the container itself doesnt even know.

The boost::array is in-fact a complete re-write of a vector using the stack, but it does this purely for raw efficiency, as a trade-off it's not fully STL compliant and it'll only ever be a static-array.
The beauty of using allocators is that you can pass your allocator to all of the STL types, so you can have stack-based lists or maps too. The containers don't need to change.

You might not be aware of this, but the STL forces no requirements on how a string is implemented, a std::string implementation is likely to use a combination of stack-based and heap-based allocations.

Please be aware that writing stack-based alternatives is really only any use if you know that dynamic allocation is too slow.

i am aware of ALL your points, i know that it MIGHT be that lists and strings use a pool-allocator, depending on implementation. in fact, at least for lists, i somewhere have read that microsoft stl implementation does use pool allocation.

i also know that you might supply a stack based allocator, but i know/suspect too that it is utterly difficult to write an allocator, instead of a rather simple, tiny stack based string / vector (that of course is then only partially compatible to STL).

but then - do you know any stack based allocator, ready to use ? that could be passed to std::string ?

Quote:

i also know that you might supply a stack based allocator, but i know/suspect too that it is utterly difficult to write an allocator, instead of a rather simple, tiny stack based string / vector (that of course is then only partially compatible to STL).

Writing an allocator isn't that hard, you could argue its actually the easier option.
For an allocator you just have to implement some functions for basic memory management (which in the case of stack-allocator would be trivial), if you wrote your own container without allocators then you'd still need to code up the memory management but also all the other functions that go with the container.

Allocators 'seem' mysterious to the uninitiated, but they're not so bad:

Tutorial on writing allocators

Presentation on custom allocators

Quote:

do you know any stack based allocator, ready to use ? that could be passed to std::string ?

No, sorry.
Google might hold the answer though.

Quote:

i also know that you might supply a stack based allocator, but i know/suspect too that it is utterly difficult to write an allocator, instead of a rather simple, tiny stack based string / vector (that of course is then only partially compatible to STL).

Let's see.

Writing an allocator (a mechanism, designed to be supplied by user in extensible fashion) vs. writing a complete string class (fully STL compliant, with all the hundreds of functions, fully templated to be compliant with STL container requirements).

Which is more viable?

Writing an allocator is tricky. But it's a 5 minute task compared to re-implementing all thousands of lines of code and several implementation files that comprise a std::basic_string.

The choice should be obvious (PPT)

1) Many implementations of std::string are optimized for the case of short strings, by adding a small char[] buffer to the data struct and using that when the string will fit.

2) If you really, definitely aren't going to perform any mutating operations, and you're really paranoid about overhead, you might as well just use string literals (horrors! [wink]). If you're not trying to change the data, then the only way you can really mess up is by disregarding what strlen() (or std::find() looking for a '\0', if you want to be bizarrely modern) tells you. (Of course, const correctness is your friend.) Unless you require strings with embedded '\0' characters, I guess.

for std::string, you people are completely right. that string class is so much more complex regarding the interface than the simple vector class. i would say that my stack based vector implementation is simpler than a custom memory allocator. by the way - do you have any comments on how i did my stack vector class? any obvious pitfalls visible by just inspecting the code?

here it is again, in syntax highlighted html:
vector_stack_allocated_hpp.html

but one can only really tell by trying. thanks for the links, i will try to fight my way through that "write my own mem alloc" stuff.

Quote:

Original post by Zahlman 1) Many implementations of std::string are optimized for the case of short strings, by adding a small char[] buffer to the data struct and using that when the string will fit.

interesting! i will check that with my debugger. ir do you know if it is the case for visual studio 8 ?

Quote:

Original post by dmatter You might not be aware of this, but the STL forces no requirements on how a string is implemented, a std::string implementation is likely to use a combination of stack-based and heap-based allocations.

Quote:

Original post by herc Quote: Original post by Zahlman 1) Many implementations of std::string are optimized for the case of short strings, by adding a small char[] buffer to the data struct and using that when the string will fit. interesting! i will check that with my debugger. ir do you know if it is the case for visual studio 8 ?

Yes, a stack buffer between 1 and 16 elements depending on the size of 1 element (typically a char type). Its defined by the size of _BUF_SIZE.

thanks, this is great news! most of my small strings are never longer than 16 chars.

Quote:

Original post by herc any obvious pitfalls visible by just inspecting the code?

I glanced over it, it looks ok.
One issue to keep in mind is that because its a stack-based array when you call erase on an element it isnt actually destructed. If you had it storing objects that were very sensitive to when they're destroyed this might cause unforseen complications, but that's not a problem with your code that's just what happens with the stack anyway.

Quote:

thanks, this is great news! most of my small strings are never longer than 16 chars.

Good for you [smile]

This is why trying to second-guess the STL is usually a waste of time, its highly optimised in the first place. Just imagine if you'd spent all that time coding up a stack based string class when all you ever do is use it for 10-char strings [wink].

Quote:

Original post by herc for std::string, you people are completely right. that string class is so much more complex regarding the interface than the simple vector class. i would say that my stack based vector implementation is simpler than a custom memory allocator. by the way - do you have any comments on how i did my stack vector class? any obvious pitfalls visible by just inspecting the code?

I have the following comments.

(1) This is almost identical to the standard container designed to do exactly the same job (tr1::array, or std::array in C++09). Not surprising: it's filling the same need.

(2) One of the guidelines following in designing the standard containers was that functionality that could onlt be imeplemented poorly should not be implemented at all. Some of the functions you've carried across from std::vector can not be implemented properly in a stack-based vectorlike container. For example, resize(), reserve(), and swap(). This is why the standards committee came up with std::array: a different name for a different set of requirements and functionality.

--smw