Jump to content
  • Advertisement
Sign in to follow this  
herc

Unity stack based string class

This topic is 3988 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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 ?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.


Share this post


Link to post
Share on other sites
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 ?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
thanks, this is great news! most of my small strings are never longer than 16 chars.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!