Is it possible to create class String without using heap in C++?

Question

I would like to write me own class String which will have interface similar to std::string. String class shall not use dynamic memory allocation.

I need to have a c-tor:

String(char* ptrToFirstCharInTab, char* ptrToLastElementInTab);

And there should be tab which contains different (not know) number of element, so I do not know size while compiling.

In my opinion it's impossible, because if we do not know size of our array before compilation we can not create it without dynamic allocation - of course creating buffer for 500 char and then String class can be only 500 it' not my expections.

Do you have any idea? Maybe is any way to create buffor wchich I will shrink to fit? Thanks for help!

Your question is more or less akin to "Is it possible to create class String without using memory in C++?" — Robert Harvey, Nov 21 '18 at 18:35
There is no way to avoid dynamic allocation unless you have some sort of limit. Is there a reason you want to avoid the dynamic allocation? Also, you may want to look into Small String Optimization — NathanOliver, Nov 21 '18 at 18:37
@RobertHarvey, I don't. I was trying to get clarification on your comment. — R Sahu, Nov 21 '18 at 18:39
Declare a large static array as your heap and manage it like there's no tomorrow. That's the short answer. — PaulMcKenzie, Nov 21 '18 at 19:01
Ok maybe I would like to simplify my problem (it's only academic thinking about memory managment): I need create class which will have represent NULL-terminated character array can not use HEAP memory, can use only STACK, do not want to use too big (or too small) buffer -> wasting of memory on stack, SSO still use dynamic allocation on heap for bigger strings — mnurzyns, Nov 21 '18 at 19:03
@MarcinNurzyński see my answer, it is possible to 'dynamicly' allocate memory on the stack. — darune, Nov 21 '18 at 19:05
What's the scenario you have these requirements for? Maybe it actually is an [XY-problem](https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem). — Aconcagua, Nov 21 '18 at 19:09
It's not XY-problem, because it's only contemplation about memory managment. — mnurzyns, Nov 21 '18 at 19:14

score 4 · Answer 1 · answered Nov 21 '18 at 18:44

4

You asked:

Do you have any idea? Maybe is any way to create buffor wchich I will shrink to fit?

In theory, yes you can. You can use a pre-allocated buffer as your heap memory. However, you'll have to write your own code to manage that buffer. Doable but not something I would recommend.

answered Nov 21 '18 at 18:44

R Sahu

204,454
14
159
270

1

What happens if the string needs to be bigger than the buffer? – NathanOliver Nov 21 '18 at 18:47
+1 I was just about to make some convoluted example with placement new into a global `int8_t mem[1024*1024];`. – Ted Lyngmo Nov 21 '18 at 18:48
@NathanOliver I guess it should throw – Ted Lyngmo Nov 21 '18 at 18:48
5

@NathanOliver Same thing as if your dynamically allocated string needs to be bigger than your heap :P – Lightness Races in Orbit Nov 21 '18 at 18:50
So if for example I create buffer for 500 char and then use only 23 of them, then I could shrink buffer to only 23? Rest of memory can be used by program - or only for other String objects? – mnurzyns Nov 21 '18 at 19:06
1

@MarcinNurzyński, shrinking is not the right thing to do. When you use that buffer as heap memory of only `String` or other objects also is entirely up to you. – R Sahu Nov 21 '18 at 20:14
Problem with buffer, if small enough: It might get fragmented, if you often create and destroy strings. A level of indirection might help: Maintain a separate pointer array, array pointers point into buffer whereas string pointers into the array. Then you could move around strings within the buffer, if need be. C# does something similar under the hoods. Drawback: You need *additional* memory, indirection is slightly slower and meeting real time condition gets much harder. So it might or not be suitable, and you need to find a good compromise between buffer size and maximum number of strings. – Aconcagua Nov 22 '18 at 05:56

darune · Accepted Answer · 2018-11-22T09:06:21.063

2

You asked:

Is it possible to create class String without using heap in C++?

In fact, yes, it possible to dynamicly allocate memory on the stack by using _alloca or similiar platform dependent function. See this other answer for more details: C++ How to allocate memory dynamically on stack?

I would recommend against it and be absolutely sure that was the best alternative before commencing.

Update: I created an example with inlined constructer for demonstration purpose using gcc:

Compiler explorer Link: https://godbolt.org/z/M1F5VD

Full code:

#include <alloca.h>

struct String {
  __attribute__((always_inline)) inline String(size_t size) {
     bytes= static_cast<char*>(alloca( size ));// alloca() memory gets allocated here
  }
  char* bytes;
};

int workWithString( ) 
{
   //std::string teststr("test");
   String mystrclass(1000);
   mystrclass.bytes[0] = 'a';
   mystrclass.bytes[1] = 0;
   return 0;
}  // alloca() memory only gets freed here



int main() {
    return workWithString();
   }

edited Nov 22 '18 at 09:06

answered Nov 21 '18 at 18:56

darune

10,480
2
24
62

1

But usability is quite limited - how would you return the string to calling function? – Aconcagua Nov 21 '18 at 19:08
I saw this question before, but still I'm not sure that _alloca will solve this problem? If I use _alloca inside my c-tor it will "frees its memory when you leave a function". How I will get this char array afer c-tor end? – mnurzyns Nov 21 '18 at 19:10
@Aconcagua on the stack i suppose ? – darune Nov 21 '18 at 20:01
@MarcinNurzyński Im not sure, you just need the allocation to happend outside - everything else can be handled inside c-tor, perhaps if its always inlined - I have, myself, zero experience in using _alloca though. – darune Nov 21 '18 at 20:06
@darune If function f shall determine size by itself and then create the string appropriately? You'd have to split any such function into two parts ('f_init` to determine size, then alloca, then `f_fini` to fill the object). In worst case, you'd need a double hierarchy of function calls. In doubt if this is really practicable... – Aconcagua Nov 21 '18 at 20:28
@darune *'you just need the allocation to happend outside'* - almost yells for a combination of `alloca` and placement new. We'd yet need a way to make sure the destructor gets called before the stack-allocated memory is given back. Perhaps via some helper object created together with alloca? Suppose we'd not get around macros if we don't want to have to do every single step again and again by hand. – Aconcagua Nov 21 '18 at 20:32
I tried to create a dynamic array class using `alloca` and came to the conclusion it was impossible. I forget why but I have encountered at least one other person who came to the same conclusion for the same reason. Something about `alloca` only keeping memory until the end of the function that calls it. If a constructor calls it the memory disappears at the end of the constructor. I think I cobbled something together with macros in the end. But nothing like a string really. – Galik Nov 21 '18 at 22:37
Side note: if string contents are allocated on stack, move semantics definitely get impossible... – Aconcagua Nov 22 '18 at 05:40
@Galik and those who say its impossible - see my example in my updated answer. I wonder for what reason you came to the conclusion it wasn't possible ? – darune Nov 22 '18 at 09:09

score 1 · Answer 3 · answered Nov 21 '18 at 20:26

I'm a bit confused with your question. You want to have std:: string without a heap and without size restrictions. Sorry to bring this to you: you can't have infinite memory.

If you have an pool of memory you want to dedicate to strings without it being fixed size for each string, an allocator can do so. The default allocator for the containers does new, however you can replace it without having to duplicate the internals of string.

Is it possible to create class String without using heap in C++?

3 Answers3