CODEWITHSUNDEEP
c++performancestlcontainers
Troskyvs
Troskyvs

Reputation: 8087

How could C++ Small String Optimized (SSO) work with containers?

The SSO explanation says the small strings are allocated on heap: OK, but when constructed inside containers, these contents shouldn't be on stack because containers can be created in function and return, while function stack goes stale.

So I guess SSO doesn't work with STL containers, does it?

Upvotes: 0

Views: 1133

Answers (3)

Marshall Clow
Marshall Clow

Reputation: 16690

You certainly could write a vector-like class that had a "small object optimization", where if the objects were small and few it would store them internally (inside the container object itself), and otherwise store them on the heap (like std::vector does now).

However, this is not currently possible for the containers in the standard library, because of the requirements placed on them. In particular, [container.requirements.general]/9 says:

Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap.

That's hard to do with the small-object optimization, and that requirement does not apply to basic_string.

Upvotes: 1

Ap31
Ap31

Reputation: 3324

The difference between "small string" and the "large string" is not the difference between storing it on the stack or on the heap. Instead what differs is the level of indirection.

What that means is std::string object can hold a pointer to the actual string data, which could be of (almost) any length, but has all the downsides of indirect dynamic memory - allocations, deallocations, cache misses etc.

Alternatively SSO allows std::string to store small strings "in place", right inside thestd::string object, wherever it is allocated. If the object is in some container (on the heap) that's where the string will be, but it won't require another indirection as the large string would.

Upvotes: 5

Pixelchemist
Pixelchemist

Reputation: 24956

Let's make an example with vector and string.

  1. See my answer to 'c++ Vector, what happens whenever it expands/reallocate on stack?' to see what a vector usually "looks like".

  2. If you store strings inside a vector, all string instances will be on the heap.

  3. The string instances themselves can either

    • contain the string data itself within the object instance (SSO) or
    • allocate memory on the heap to store the content.

  4. The vector class doesn't care where the string class stores its data. it just holds the objects which manage the data on their own.

SSO doesn't affect storing strings in containers.

PS: You can of course return stack objects from a function. The function stack will go 'out of scope' but the return value is preserved. You couldn't even return int otherwise.

SSO doesn't mean that the string content is on the stack no matter what. It just means that the data (of small strings) is stored within the string instances. It follows that the data is on the stack if the instance is on the stack. If the object is on the heap then the data is also on the heap.

Upvotes: 4

Related Questions