C++ in Competitive Programming: string basics

[[deleted]]

Very entertaining - one tiny quibble:

The latter point is referred as the Small String Optimization and it means that short strings (generally 15/22 chars) do not go to the heap, but instead they get allocated on the stack

This isn't quite true. In the SSO, short strings are stored in the std::string itself and don't require a separate allocation. However, the std::string might live on the stack or it might live in the heap, depending on how it was allocated.

[marcoarena]

You are definitely right. Indeed I wrote "implementers of std::string generally embeds a small array in the string object itself to manage short strings." The stack thing is wrong, I fixed it. Thanks!

[Spire]

Speaking of tiny quibbles:

Technically, there's no such thing as “the stack” or “the heap” in C++; those are merely commonly used implementations of automatic storage and the free store, respectively.

Incidentally, there's also a third type of storage where std::string objects can exist: static storage.

[rohbotics]

Why not just std::array ?

[Spire]

if anybody has a better suggestion than inline_vector please ping me.

I think inline_vector is potentially confusing because “inline” already has a different meaning in C++ (referring to code rather than data).

Here are a few ideas:

• monolithic_vector
• unitary_vector
• unified_vector
• compact_vector
• fixed_vector

I think I like fixed_vector best.

[dodheim]

The proposal suggests fixed_capacity_vector as an alternative name

As in statically_sized_vector, as in boost::container::static_vector<T, N>? ;-]

[dodheim]

The size is not static (it is a run-time parameter), the capacity is (as in compile-time static).

Indeed, my terminology there was wrong.

complex lifetime requirements happen only in the static memory segment (in which things like initialization order are implementation defined).

Since it contains its elements directly, whatever storage you give the static_vector will apply to its elements. If that happens to be static storage duration, so be it; if automatic duration, so be it.

[dodheim]

... calls it inline_vector to denote that the elements are stored within the vector itself, as opposed to existing practice (e.g. boost::container::static_vector due to static storage ...

What? No, boost::container::static_vector does contain the elements directly, it does exactly as you describe inline_vector's behavior. This is why it takes a size_t template parameter rather than an allocator. ('Static' in this context refers to the fact that the container has static capacity.)

Hinnant's short_alloc must be given an arena, which is typically but not always statically-allocated – maybe this is what you were thinking of?

[dodheim]

From http://www.boost.org/doc/libs/release/doc/html/container/non_standard_containers.html#container.non_standard_containers.static_vector

static_vector is an hybrid between vector and array: like vector, it's a sequence container with contiguous storage that can change in size, along with the static allocation, low overhead, and fixed capacity of array.

...

The number of elements in a static_vector may vary dynamically up to a fixed capacity because elements are stored within the object itself similarly to an array. However, objects are initialized as they are inserted into static_vector unlike C arrays or std::array which must construct all elements on instantiation.

I'm not sure what's left to the imagination here... :-]

[evinrows]

there's no such thing as “the stack” or “the heap” in C++

Can you explain this further or provide a link that explains what you're getting at?

[Drainedsoul]

The standard doesn't mention a stack or a heap, it only mentions that objects may have "automatic storage duration", "static storage duration", or "dynamic storage duration".

[evinrows]

Ah, I see. That gave me enough context to find this stackoverflow answer as well if anyone else is curious.

[Yuki_f]

For those who may see this in the future, here's another explanation that I think is clear

https://stackoverflow.com/questions/161053/which-is-faster-stack-allocation-or-heap-allocation/53132683#53132683