Sign in to follow this  

Unity stack based string class

This topic is 3778 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
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
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].

Share this post


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

Share this post


Link to post
Share on other sites

This topic is 3778 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this