stack based string class
Author
my post should be rather added to this thread
Memory Allocator for string class
but its retired. (admin: maybe reopen it and add my following as a reply)
-------
if you have many small string, that serve just the purpose to deliver some short messages and stuff, and do NOT need to be concatenated till whatever length, i would suggest to just use the stack. why must all stuff be on the heap?
so i propose to supply a stack based "clone" of std::string. with a fixed size, simple c-array of some char type.
would this work? or is there any issues then with thread and whatever else safety one could run into?
i have , for example, implemented my own small stack based vector class.
vector_stack_allocated.hpp
it is based on the fine boost::array ( http://www.josuttis.com/cppcode, http://www.boost.org/doc/html/boost/array.html ). and i am using it without any troubles in my small game project ( www.gravytris.de ).
so, would this be possible with strings too? and if so, is there eventually already such a stack based, STL compatible string class implemented somewhere?
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.
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.
Author
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 ?
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<T>.
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.
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.
Author
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.
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.
Author
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 hercQuote: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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
