DEV Community: Stupid Dev

Optimization? ;P

Stupid Dev — Fri, 02 Oct 2026 18:41:06 +0000

So from my previous blog I had this very specific piece of code:

template<typename T>
concept CharType = std::integral<T>;

template<CharType C>
inline constexpr std::size_t chseqlen1(const C* pbuf) {
    std::size_t len = 0;
    while (pbuf[len] != 0) {
        len++;
    }
    return len;
}

Appended the 1 in the name, to create distinction.

And it vectorizes PERFECTLY in g++. But then I somehow came up with a second version of chseqlen which literally does the same thing BUT DOES NOT VECTORIZE, despite having the same optimization flags as the original one.

This is version 2:

template<CharType C>
inline constexpr std::size_t chseqlen2(const C* pbuf) {
    std::size_t len = 0;
    while (*pbuf != 0) {
        pbuf++;
        len++;
    }
    return len;
}

Why did it NOT vectorize? Well, we gotta explore!

Also the way I came up with version-2 is genuinely funny! Like I wanted to show my friends in college about how g++ optimizes and vectorizes a very simple loop into hundreds of SIMD instructions! Just for my muscle memory to kick in, and I typed out the standard and usual crappy C version with pointer arithmetic — and g++ just refused to vectorize!!

GCC LITERALLY HAD 1 JOB! 1 PLACE TO SHINE! AND IT DIDN'T!!

But why?? We shall explore 😏😏

Implementation Pipeline

We defined them as templates, so we gotta implement them to get actual code! Here's the implementation:

void getlen1(const int* s, std::size_t& l) {
    l = chseqlen1(s);
}
void getlen2(const int* s, std::size_t& l) {
    l = chseqlen2(s);
}

I intentionally used const int* over here. If we had used const char* then gcc would have yeeted the whole thing with a strlen 🫠... But we gotta see vectorization!

Compiler flags

Pretty small section but extremely important (which is why it deserved its own section!). We use this compiler flags for all the code:

-std=c++20 -O3 -mavx2

Yea, we're using AVX2 machinery over here!

Generated Assembly

Generated assembly for version 1:

"getlen1(int const*, unsigned long&)":
        mov     r10d, DWORD PTR [rdi]
        mov     r8, rsi
        test    r10d, r10d
        je      .L22
        lea     rdx, [rdi+4]
        shr     rdx, 2
        neg     rdx
        mov     rax, rdx
        and     eax, 7
        je      .L3
        mov     r9d, DWORD PTR [rdi+4]
        test    r9d, r9d
        je      .L23
        test    dl, 6
        je      .L24
        mov     esi, DWORD PTR [rdi+8]
        test    esi, esi
        je      .L25
        cmp     rax, 2
        jbe     .L26
        mov     ecx, DWORD PTR [rdi+12]
        test    ecx, ecx
        je      .L27
        and     edx, 4
        je      .L28
        mov     r11d, DWORD PTR [rdi+16]
        test    r11d, r11d
        je      .L29
        cmp     rax, 4
        je      .L3
        mov     r10d, DWORD PTR [rdi+20]
        test    r10d, r10d
        je      .L30
        cmp     rax, 5
        je      .L3
        mov     r9d, DWORD PTR [rdi+24]
        test    r9d, r9d
        je      .L31
        cmp     rax, 7
        jne     .L32
        mov     esi, DWORD PTR [rdi+28]
        test    esi, esi
        je      .L2
.L3:
        mov     rsi, rax
.L4:
        lea     rcx, [rdi+4+rax*4]
        vpxor   xmm1, xmm1, xmm1
        xor     eax, eax
.L7:
        vpcmpeqd        ymm0, ymm1, YMMWORD PTR [rcx+rax*4]
        mov     rdx, rax
        add     rax, 8
        vptest  ymm0, ymm0
        je      .L7
        add     rsi, rdx
        lea     rax, [rsi+1]
        mov     ecx, DWORD PTR [rdi+rax*4]
        lea     rdx, [0+rax*4]
        test    ecx, ecx
        je      .L41
        mov     r11d, DWORD PTR [rdi+4+rdx]
        test    r11d, r11d
        je      .L43
        mov     r10d, DWORD PTR [rdi+8+rdx]
        test    r10d, r10d
        je      .L44
        mov     r9d, DWORD PTR [rdi+12+rdx]
        test    r9d, r9d
        je      .L45
        mov     ecx, DWORD PTR [rdi+16+rdx]
        test    ecx, ecx
        je      .L46
        mov     eax, DWORD PTR [rdi+20+rdx]
        test    eax, eax
        je      .L47
        mov     eax, DWORD PTR [rdi+24+rdx]
        test    eax, eax
        je      .L48
        mov     eax, DWORD PTR [rdi+28+rdx]
        test    eax, eax
        je      .L49
        mov     eax, DWORD PTR [rdi+32+rdx]
        test    eax, eax
        je      .L50
        mov     eax, DWORD PTR [rdi+36+rdx]
        test    eax, eax
        je      .L51
        mov     r11d, DWORD PTR [rdi+40+rdx]
        test    r11d, r11d
        je      .L52
        mov     r10d, DWORD PTR [rdi+44+rdx]
        test    r10d, r10d
        je      .L53
        mov     r9d, DWORD PTR [rdi+48+rdx]
        test    r9d, r9d
        je      .L54
        mov     ecx, DWORD PTR [rdi+52+rdx]
        test    ecx, ecx
        je      .L55
        mov     edx, DWORD PTR [rdi+56+rdx]
        lea     rax, [rsi+16]
        test    edx, edx
        je      .L56
.L41:
        vzeroupper
.L2:
        mov     QWORD PTR [r8], rax
        ret
.L24:
        mov     esi, 1
        jmp     .L4
.L26:
        mov     esi, 2
        jmp     .L4
.L28:
        mov     esi, 3
        jmp     .L4
.L32:
        mov     esi, 6
        jmp     .L4
.L46:
        lea     rax, [rsi+5]
        vzeroupper
        jmp     .L2
.L29:
        mov     eax, 4
        jmp     .L2
.L22:
        xor     eax, eax
        mov     QWORD PTR [r8], rax
        ret
.L43:
        lea     rax, [rsi+2]
        vzeroupper
        jmp     .L2
.L23:
        mov     eax, 1
        jmp     .L2
.L44:
        lea     rax, [rsi+3]
        vzeroupper
        jmp     .L2
.L25:
        mov     eax, 2
        jmp     .L2
.L45:
        lea     rax, [rsi+4]
        vzeroupper
        jmp     .L2
.L27:
        mov     eax, 3
        jmp     .L2
.L47:
        lea     rax, [rsi+6]
        vzeroupper
        jmp     .L2
.L30:
        mov     eax, 5
        jmp     .L2
.L54:
        lea     rax, [rsi+13]
        vzeroupper
        jmp     .L2
.L56:
        lea     rax, [rsi+15]
        vzeroupper
        jmp     .L2
.L48:
        lea     rax, [rsi+7]
        vzeroupper
        jmp     .L2
.L31:
        mov     eax, 6
        jmp     .L2
.L49:
        lea     rax, [rsi+8]
        vzeroupper
        jmp     .L2
.L50:
        lea     rax, [rsi+9]
        vzeroupper
        jmp     .L2
.L51:
        lea     rax, [rsi+10]
        vzeroupper
        jmp     .L2
.L52:
        lea     rax, [rsi+11]
        vzeroupper
        jmp     .L2
.L53:
        lea     rax, [rsi+12]
        vzeroupper
        jmp     .L2
.L55:
        lea     rax, [rsi+14]
        vzeroupper
        jmp     .L2

Generated assembly for version 2 🫠:

"getlen2(int const*, unsigned long&)":
        mov     ecx, DWORD PTR [rdi]
        xor     eax, eax
        test    ecx, ecx
        je      .L58
.L59:
        add     rax, 1
        mov     edx, DWORD PTR [rdi+rax*4]
        test    edx, edx
        jne     .L59
.L58:
        mov     QWORD PTR [rsi], rax
        ret

Yea, we're getting scalar for version 2.

Diagnosing GCC

To diagnose gcc, we gotta look at exactly what it is doing for optimization! And these flags will help us in that:

-fopt-info-vec-missed
-fdump-tree-vect-details

Okay, I'll leave this blog unfinished right here, cuz I actually need to read through the vect-details to understand what exactly gcc is doing. But I'd definitely update the blog. Just publishing it like this — take it as a teaser!

Anyway, see you later oomfie~!

Simple SSO

Stupid Dev — Fri, 02 Oct 2026 15:58:04 +0000

Simple Implementation of a Basic String in C++ 20 (with SSO)

In this basic tutorial, we will explore one of the simpler ways to implement a kind of functional Basic String class in C++ 20 which makes use of Small String Optimisation (SSO).

I'll try to explain everything from scratch, so it will take both time and length. If you already know something, feel free to just skip it.

Assumptions and Constraints

Before delving into anything, I must make it VERY CLEAR as to what you may encounter in this tutorial, so that you leave early instead of unmet expectation and rage.

Using C++ 20: We will use many C++ 20 features such as concepts and bit_ceil, among others. Makes code easier to write.
Using a 64-bit little endian desktop platform.
Other typedef s in C++ 20
Only handling a subset of the functionality of std::basic_string of C++
Using some custom definitions of functions, which may not be strictly C++ compliant
Keeping the underlying string representation strictly C-style (therefore, NULL terminated.)
NOT using any custom allocator, NOR custom char_traits for our implementation (It is meant to be simple!)
Using the simpler implementation of SSO which can be done with a simple union
Code which works & tests properly with at least g++ or clang++ (or that's what I am sure of)

And if I miss anything over here, just get angry and move on.

SSO

So what is SSO?

SSO stands for Small String Optimization, which means to optimise out the representation, reads, and writes to the string if it is sufficiently small.

It is often done by having a statically allocated array on each string object to store the small string inline.

Which brings us to the pros and cons of using SSO.

Pros of SSO

Small/Short strings do not need an extra heap memory allocation/free.
Small strings are allocated right at object construction and therefore, do not need further allocator calls.
Given that the small string is inside the object's storage, operations on it require much less memory indirection and reduce allocator pressure.
It allows the string to stay in the processor cache (also known as “cache locality”).
It adds a minute cost of SSO checking but a heap memory operation is much more costly than that, so that’s not something to “worry” about. One single branch misprediction is much faster than heap memory operation.

Cons of SSO

Comparatively complex management of the internal string buffer.
Debugging is equal to fighting a war.
You eventually lose your sanity, humanity, empathy and your being.
The String object itself becomes much bigger, which puts pressure on the stack memory and it may be harmful on embedded devices or other custom low-end devices.
The API contract may be stable & portable but the object layout may not be portable.

Wait… So equal number of pros & cons… YES! So why are we even implementing this? Because the ENDS JUSTIFY THE MEANS!

Though, it must be noted that the SSO buffer is not stack-memory exclusive. It is a part of the object's memory itself and resides wherever the object resides. There can be two scenarios:

BasicString str("Hello"); — The object is allocated on stack memory. Given that the buffer is a part of this memory, the SSO buffer is on stack memory.
auto str = new BasicString("Hello"); — The object is allocated on heap memory. Therefore, the SSO buffer is on heap memory.

SSO Implementations

There are various ways in which SSO has been implemented throughout the C++ stdlib world. If we have to explore, two of them are:

GCC implementation:

Uses a simpler version of SSO of a single union and a separate buffer & length. It takes up 32 bytes of memory with 15 characters in the SSO buffer. This is close to what we will implement. Uses a very simple mechanism of an internal pointer switching between the local SSO buffer and heap memory.
Clang Implementation:

Uses a much more complex version of SSO where the lower bits represent “modes” and the upper bits must be interpreted separately depending on the “mode”. This is comparatively very very complex but allows BOTH smaller string objects at 24 bytes while also allowing up to 22 characters in the SSO buffer.

Initial Assumptions

For a fairly simple and straightforward start, we must take the following assumptions:

Using char as the only type to deal with, despite using templates.
Getting the very basic version up and running, and not caring about edge cases (at least for now!).
Avoiding some functionality.

SSO Structure

We will use the following conceptual structure for SSO:

struct BasicString {
    char* buffer; // shown as mbuf
    size_t length; // shown as mlen
    union {
        size_t capacity; // shown as mcap
        char local_buffer[16]; // shown as mlocalbuf
    };
}

Which consequentially will have this exact memory layout (we're only considering 64-bit machines):

+----------------+-----------+-----------------+
| buffer pointer | length    | [SSO union]     |
|   (8 bytes)    | (8 bytes) | 16 bytes        |
+----------------+-----------+-----------------+

Now the most important part is to understand the structure of the SSO union, which is where the real meat of storing char in SSO lies.

Remember, union is nothing but a chunk of memory, with size equal to the element with biggest size, and the other members merely interpret their memory region! The underlying memory is just bytes, and how you access/read/write them gives them meaning!

This becomes the memory of the union:

Zoom in to [SSO Union] = 16 bytes
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 | 13 | 14 | 15 |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|<------------- capacity -------------->|
|<-------------------------------- local_buffer ------------------------------->|

Now what if we have this block of memory filled with data? If we filled the cells with "hello!!\0", then it looks like this:

Note: The Hexadecimal ASCII values of each byte/char of the string is shown

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|  68|  65|  6C|  6C|  6F|  21|  21|  00|    |    |    |    |    |    |    |    |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|<------------- capacity -------------->|
|<-------------------------------- local_buffer ------------------------------->|

If we access the local buffer:

[union]->local_buffer — it gives us a clean NULL terminated C-string saying "hello!!\0".

But if we access the capacity:

[union]->capacity — it interprets byte 0 to 7 as a size_t!! Since, we're in a little-endian 64-bit machine, the value of capacity is:

capacity = 0x00'21'21'6f'6c'6c'65'68;

So... How do we deal with this?

Well, the answer is in the usage of buffer!!

We know with absolute certainty that the memory address of the union will ALWAYS be one and unique, and that no other buffer will have that same memory address!

Hence, we establish a contract:

If buffer == local_buffer — we know with absolute certainty that the string is being stored in SSO!
Otherwise — we know that buffer is pointing to another memory location, which we got via heap allocation, therefore, string is not in SSO!

But the obvious downside being, if buffer == local_buffer and we interpret the union as capacity it will read garbage capacity, and modifying capacity then will absolutely destroy the string stored as SSO!

And this is the very foundational and delicate contract on which this whole BasicString class will be based!

Implementation v1

We will still use templates to make it from the ground up, so that later on we don't need to replace everything inside the class to add more data types.

The implementation will reside inside a header file (.hpp).

But initially we will constrain the template to only char and we can do it by using concepts in C++.

Template

#include <concepts>

template<typename T>
concept CharType = std::same_as<T, char>;

Now we need a couple of helper functions to aid our implementation.

Helper Functions

#include <cstddef>

template<CharType C>
inline constexpr std::size_t chseqlen(const C* pbuf) {
    std::size_t len = 0;
    while (pbuf[len] != 0) {
        len++;
    }
    return len;
}

We have the helper function chseqlen which returns a std::size_t. This helper function takes a NULL terminated C-string and returns its length. Essentially it acts as a strlen but with templates so that we can scale it to take other definitions of strings later on.

The name comes from ch = character, seq = sequence, len = length. The implementation "could" be of less lines but it still produces the exact same assembly/binary, so it doesn't matter. Also, this version is much much easier to read than any of those bullshit you may find somewhere else.

It is defined with constexpr specifically because we want it to resolve at compile time if the string provided to it is statically present at compilation.

Optimisation Note: GCC/Clang will eventually replace this with strlen in the underlying assembly, and will vectorise the hell out of this if we use other types.

Base Structure of the Class

We will define the basic structure of the BasicString class:

template<CharType CharT>
class BasicString {
public:
    // Segment 1 (S1)
private:
    // Segment 2 (S2)
private:
    // Segment 3 (S3)
public:
    // Segment 4 (S4)
private:
    // Segment 5 (S5)
public:
    // Segment 6 (S6)
};

The class is divided into six segments. Such is done to make the implementation a bit easier to follow. Though as a whole, there's almost no clean separation among some of these segments.

Class Constants

The class constants are compile time constants which belong to the class itself (not the object instance). They are going to be defined in Segment 1 and will have public visibility.

The class constants:

    // Segment 1
    static constexpr std::size_t npos = -1;
    static constexpr std::size_t ssoCapacity = 15 + 1; // bytes
    static constexpr std::size_t ssoItems = ssoCapacity / sizeof(CharT);

These constants are declared with constexpr, which—for variables—means that their value MUST be evaluated at compile time.

Discussing each of the constants:

std::size_t npos = -1: This is used as a sentinel value, which means "no position" or "invalid position". Since std::size_t is unsigned, -1 wraps to its maximum value: 0xffff'ffff'ffff'ffff. Since such a value cannot practically represent a valid index or object size.
std::size_t ssoCapacity = 15 + 1: Defines the SSO buffer size in bytes: 15 bytes for ASCII characters + 1 byte for the terminating NULL character (\0), giving a total capacity of 16 bytes.
std::size_t ssoItems = ssoCapacity / sizeof(CharT): Defines the number of CharT elements that can fit in the SSO buffer based on the byte capacity. Currently, it evaluates to ssoCapacity because CharT is constrained to char, which is exactly 1 byte in size.

Class Instance State

The "class instance state" implies the "state" (or member variables) which belong to the object instance. The state is going to be defined in Segment 2 and is going to have private visibility.

    // Segment 2
    CharT* mbuf = mlocalbuf;
    std::size_t mlen = 0;
    union {
        std::size_t mcap;
        CharT mlocalbuf[ssoItems];
    };

The state has been extensively discussed and covered in the SSO Structure section.

What stays a bit different is that mbuf is default initialized to mlocalbuf, therefore, on any constructor the string at the very initial moment is guaranteed to be in SSO for us.

Note—This MAY look like Undefined Behaviour (UB) given that class members are initialized according to their order of declaration but this is NOT UB! mbuf takes the address of mlocalbuf, which does not depend on it being initialised or not! It's just a simple offset calculation and hence, NOT UB! This would be UB if we accessed the contents of mlocalbuf but we are not doing that.

Class Helpers

"Class Helpers" refers to static helper functions. They are going to be defined in Segment 3 and will have private visibility.

    // Segment 3
    static inline constexpr std::size_t m_getCapFromLen(std::size_t plen) {
        return std::bit_ceil((plen + 1) * sizeof(CharT));
    }

    static inline constexpr bool m_isLenSmall(std::size_t plen) {
        return plen < ssoItems;
    }

Note: These are declared as constexpr, which means that, if these functions can be evaluated at compile time, they will be. This is fundamentally different from constexpr with variable, but hey, that's WG21 for you 🫠!

Explaining each of these helpers:

std::size_t m_getCapFromLen(std::size_t): Get the capacity from the supplied length (plen) and accounts for the terminal null. The capacity (in bytes) returned is the next highest power-of-2 which can hold the length. Technically, this can overflow but only when plen > 2^63-1 and we will never hit that limit (genuinely stupid statement considering reality but you will always have those comments!).
bool m_isLenSmall(std::size_t): Checks if the length supplied can fit inside SSO buffer. Note that this already considers the terminating NULL as the condition checks plen < ssoItems!

Class Primitive Helpers

"Class Primitive Helpers" refers to helper functions with public visibility, which act as a public APIs into the class/object's state/info. These are defined in Segment 4.

    // Segment 4
    inline bool isSmall() const { return mbuf == mlocalbuf; }

    inline std::size_t strByteCapacity() const {
        return (mlen + 1) * sizeof(CharT);
    }

    static inline consteval std::size_t maxlength() {
        // return std::numeric_limits<ssize_t>::max(); // only in POSIX
        return std::numeric_limits<std::ptrdiff_t>::max();
        // equivalent...
    }

    inline std::size_t byteCapacity() const {
        if (isSmall()) return ssoCapacity;
        else return mcap;
    }

    inline std::size_t capacity() const {
        return ((isSmall() ? ssoCapacity : mcap) / sizeof(CharT)) - 1;
    }

    inline std::size_t length() const { return mlen; }

    inline std::size_t size() const { return mlen; }

Going through these helpers:

bool isSmall(): Checks if the general buffer (mbuf) points to SSO buffer (mlocalbuf) or not.
std::size_t strByteCapacity(): Returns the net bytes required to store the string.
std::size_t maxlength(): A static function, returns the maximum length of a string possible. Note the comment, initially we intended to use ssize_t for the maximum length but it is available on POSIX only. Therefore, it is substituted with std::ptrdiff_t. Functionally, it should be the same.
std::size_t byteCapacity(): Returns the capacity of buffer allocated for the string in bytes. Note that when the string is in SSO, we return the capacity of the local SSO buffer (mlocalbuf). Whereas, when it is NOT in SSO, we return the value of mcap because it is properly readable then! (hopefully)
std::size_t capacity(): Returns the number of characters that can be held in the current buffer (SSO or heap) of the string. Excludes null terminating character. Note — it returns the number of characters, not bytes.
std::size_t length(): Returns the length of the string.
std::size_t size(): Same as length(). Point your fingers at WG21 not me.

Class Internal Helpers

"Class Internal Helpers" refers to functions that are convenience functions for larger implementations. They are defined in Segment 5 and have private visibility.

    // Segment 5
    inline void m_initEmpty() {
        // to initialize as empty, put it in SSO
        // DO NOT TOUCH mcap!
        mbuf = mlocalbuf; // in SSO Mode
        mbuf[0] = 0; // CharT{} also works, but for integral types they're the same
        mlen = 0;
    }

    inline void m_assignNew(const CharT* pbuf, std::size_t plen) {
        mlen = plen;
        // check if length fits in SSO
        if (m_isLenSmall(plen)) {
            mbuf = mlocalbuf; // in sso
        } else {
            // not in sso
            mcap = m_getCapFromLen(mlen);
            mbuf = (CharT*)std::malloc(mcap);
        }
        std::memcpy(mbuf, pbuf, mlen * sizeof(CharT));
        mbuf[plen] = 0;
    }

    inline void m_clearString() noexcept {
        mbuf[0] = 0;
        mlen = 0;
    }

Explanation for these helpers:

void m_initEmpty(): Initialise the object to an empty state. Puts the string in SSO mode, assigns the first byte as 0, sets length to 0.
void m_assignNew(const CharT* pbuf, std::size_t plen): Initializes the object from pbuf with length plen. Uses SSO if the string fits; otherwise, sets mcap and allocates storage. Copies plen * sizeof(CharT) bytes to mbuf and explicitly null-terminates it at index plen. Assumes pbuf need not be null-terminated and is called during object construction.
void m_clearString(): Clears the string. Only puts the string to a state of an empty string, the buffer and capacity are not changed. Therefore, if there's heap allocation, it does not shrink it or brings it back to SSO.
void m_reassign(const CharT* pbuf, std::size_t plen):

Constructors

Put in Segment 6 with public visibility. Important to note - We are not doing move constructor right now.

    // Segment 6

    // init an empty string
    // C1
    BasicString() noexcept { m_initEmpty(); }

    // copy constructor
    // C2
    BasicString(const BasicString& pstr) {
        // just assign from the other string
        m_assignNew(pstr.mbuf, pstr.mlen);
    }

    // C3
    BasicString(const BasicString& pstr,
            std::size_t ppos,
            std::size_t plen = npos
    ) {
        if (ppos == pstr.mlen) {
            m_initEmpty();
        } else if (ppos > pstr.mlen) {
            throw std::out_of_range("Starting position > length of other string");
        }
        else {
            m_assignNew(
                pstr.mbuf + ppos,
                std::ranges::min(pstr.mlen - ppos, plen)
            );
        }
    }

    // C4
    BasicString(const CharT* s) {
        if (s == nullptr || s[0] == 0) {
            m_initEmpty();
            return;
        }
        // assume C string
        m_assignNew(s, chseqlen(s));
    }

    // C5
    BasicString(const CharT* s, std::size_t n) {
        if (n == 0 || s == nullptr) {
            m_initEmpty();
            return;
        }
        m_assignNew(s, n);
    }

    // C6
    BasicString(std::size_t n, CharT c) {
        if (n == 0) {
            m_initEmpty();
            return;
        }
        mlen = n;
        if (m_isLenSmall(mlen)) {
            mbuf = mlocalbuf;
        } else {
            mcap = m_getCapFromLen(mlen);
            mbuf = (CharT*)std::malloc(mcap);
        }
        std::ranges::fill_n(mbuf, mlen, c);
        mbuf[mlen] = 0;
    }

    // C7
    // STL doesn't have this overload
    BasicString(std::size_t n, const CharT* s) {
        if (n == 0 || s == nullptr || s[0] == 0) {
            m_initEmpty();
            return;
        }
        // must be non-empty string
        auto buflen = chseqlen(s);
        mlen = buflen * n;
        if (m_isLenSmall(mlen)) {
            mbuf = mlocalbuf; // in sso
        } else {
            // out of sso
            mcap = m_getCapFromLen(mlen);
            mbuf = (CharT*)std::malloc(mcap);
        }

        for (std::size_t i = 0; i < mlen; i += buflen) {
            std::ranges::copy_n(s, buflen, mbuf + i);
        }
        mbuf[mlen] = 0;
    }

The constructors have been numbered as C1 to C7 for better navigation.

Explaining these constuctors one by one:

BasicString() (C1): Initializes the object to an empty string. Defined as noexcept since it should not throw an exception.
BasicString(const BasicString& pstr) (C2): Copy constructor. Copies the string from another BasicString.
BasicString(const BasicString& pstr, std::size_t ppos, std::size_t plen = npos) (C3): Constructs the object as a substring of pstr, starting at index ppos and copying up to plen characters, or the remaining length of pstr if shorter. If ppos > pstr.mlen, throws an std::out_of_range exception.
BasicString(const CharT* s) (C4): Constructs the object by copying the null-terminated string s. If s == nullptr, initializes the object as an empty string.
BasicString(const CharT* s, std::size_t n) (C5): Constructs the object by copying up to the first n characters of the null-terminated string s. If n exceeds the length of s, it is Undefined Behaviour. If s == nullptr or n == 0, initializes the object as an empty string.
BasicString(std::size_t n, CharT c) (C6): Constructs the object with the character c repeating n times. If n == 0, initializes the object as an empty string.
BasicString(std::size_t n, const CharT* s) (C7): Constructs the object with the null-terminated string s repeating n times. If n == 0, or s == nullptr, or s[0] == 0, then initialized the object as an empty string.

A very important note: You may have noticed in C4, C5, and C7, we put the s == nullptr condition before s[0] == 0! This is very important here, since it makes use of short-circuiting in logical operators (||)! In the condition s == nullptr || s[0] == 0, if s is nullptr, then the rest of the condition of accessing the element is not evaluated.

Destructor

An extremely simple destructor. Defined in Segment 6.

    ~BasicString() {
        if (!isSmall()) { // important! Don't free static buffer!
            std::free(mbuf);
        }
    }

If the string is NOT in SSO, then free mbuf.

Assignment Helper

To help with re-assignment, we need to design a helper function. Defined in Segment 5 with private visibility:

    inline void m_reassign(const CharT* pbuf, std::size_t plen) {
        if (pbuf == mbuf) {
            mlen = plen;
            mbuf[mlen] = 0;
            return;
        }

        if (isSmall()) {
            // if currently in SSO
            if (!m_isLenSmall(plen)) {
                // the assignment needs heap
                mcap = m_getCapFromLen(plen);
                mbuf = (CharT*)std::malloc(mcap);
                // NOTE: THIS IN SSO, but assignment needs heap
                // => pbuf CANNOT BE IN CURRENT OBJECT'S SSO, NOR ANY SSO
                // so there's NO OVERLAP WITH THIS.SSO POSSIBLE
                // so write to mcap, mlocalbuf is garbage anyway...
            }
            // else, assignment needs SSO, no need to call malloc
            // can be overlapping
        }
        else if (plen > mlen) { // hehe!
            // if currently in heap, don't move back to SSO
            // just like gcc implementation, a reassignment doesn't move back to SSO if already in heap
            // a greater newcap matters only when plen > mlen
            // if plen <= mlen, no need to care about a newer capacity
            // totally skip the scenario when mcap not power of 2 due
            // to a shrink, and then subsequent overlapping buffer re-assign
            auto newcap = m_getCapFromLen(plen);
            if (newcap > mcap) { // can access mcap, cuz in heap
                // don't even shrink size
                mcap = newcap; // in heap, can use mcap
                std::free(mbuf); // free it now
                mbuf = (CharT*)std::malloc(newcap);
            }
        }

        mlen = plen;
        std::memmove(mbuf, pbuf, plen * sizeof(CharT));
        mbuf[mlen] = 0; // separately set the last NULL
    }

Reassigns the object with a new string. If pbuf == mbuf, only length is copied and the NULL terminator is placed. If the current SSO buffer cannot hold the new string, SSO mode is discarded and heap storage is allocated. If already in heap mode, storage is expanded only when the new string exceeds the current capacity. Uses std::memmove() to handle overlapping buffers while remaining optimized for non-overlapping copies.

Notice the else if(plen > mlen) condition there, it ensures that a new capacity check happens only when we need to assign a string of bigger length. This helps in avoiding overlapping buffer edge cases involving a future shrink_to_fit().

If we didn't have the else if(plen > mlen) condition, instead we kept a simple else, this would lead to a use-after-free error. If we remove the condition, then the edge case can be demonstrates as follows:

BasicString<char> str = "0123456789ABCDEF-ABC"; // heap allocation
// mlen = 20
// mcap = 32
str.shrink_to_fit(); // mlen = 20, mcap = 21
str = str.data() + 1; // assign from its own buffer+1 aka "1234..."
// calls m_reassign(pbuf = "1234...", plen = 19), this->mcap == 21

Since we don't have length check in this demo, it directly calculates newcap which is 32, and 32 > 21 is true. Therefore, it frees mbuf, BUT pbuf is a part of mbuf! So the memory of pbuf is freed! Then new memory is allocated to mbuf but the memory at pbuf is freed! When we do a std::memmove(mbuf, pbuf, plen * sizeof(CharT)), we're reading from pbuf. That's the use-after-free bug that the length check prevents, since 19 > 20 is false, newcap is not calculated, neither is mbuf freed!

Note: SSO is retained when both the current object and new string fit in SSO. Once in heap mode, the object remains in heap mode and never shrinks or reallocates when the new string requires less capacity. Thus, once the object leaves SSO, all subsequent reassignments remain heap-backed.

Assignment

Does the work of re-assignment. Defined in Segment 6.

    BasicString& operator=(const BasicString& pstr) {
        m_reassign(pstr.mbuf, pstr.mlen);
        return *this;
    }

    BasicString& operator=(const CharT* s) {
        // UB: if s is non-null terminated
        if (s == nullptr) {
            m_clearString();
        } else {
            m_reassign(s, chseqlen(s));
        }
        return *this;
    }

    BasicString& operator=(CharT c) {
        const CharT buf[] = { c, 0 };
        m_reassign(buf, 1);
        return *this;
    }

Going through each of the assignment overloads:

BasicString& operator=(const BasicString& pstr): Re-assigns another pstr to the object.
BasicString& operator=(const CharT* s): Re-assigns a null-terminated string s to the object. If s == nullptr then assign an empty string.
BasicString& operator=(CharT c): Re-assigns a character to the object. The implementation creates a static array as a null-terminated string and re-assigns with the length of 1.

Implementation v2

Since we have established a fairly coherent BasicString construction, now we should try to make it usable, at least in the most minimal form. In version 2, we will explore move semantics, initializer lists, iterators, and some selected functions from the stdlib with regards to capacity, element access, and data operations.

Move Semantics

What is moving or move semantics in C++?

Move semantics in C++ is a way to transfer ownership of resources of an object to another without copying them. Move semantics in C++ conventionally include two ways of moving—

Move constructor
Move assignment operator

In each case, we deal with an rvalue reference while moving. To put it simply, rvalue reference is a way for C++ to bind a specific overload of the constructor/operator to the operation. And in this case, the operation conventionally chosen is resource ownership transfer aka moving. (Though, it must be noted, this is a "convention" — no one is "stopping" you from just copying the resources if you feel like it. It goes the other way round too: you could implement move semantics without an rvalue reference.)

An rvalue reference is denoted by && in the type. So if the type is T, then an rvalue reference to it is T&&. What binds to T&& is an rvalue expression — typically a temporary, something with no name of its own at the point of use. This is a subtle but important distinction: T&& describes a type, while "rvalue" describes a value category, a property of expressions, not variables. You can absolutely have a named variable of type T&& (e.g., a parameter T&& x in a move constructor) — but once it has a name, using that name is itself an lvalue expression, even though the variable's type is still T&&. This is the classic rule: "a named rvalue reference is an lvalue".

The key tool to move is std::move(x). This function itself doesn't move anything — it just casts x into an rvalue reference expression (technically an xvalue) so the compiler binds the respective overload to it. Its rough signature is T&& move(T&& t), taking its argument by reference, not by value. We can understand the "no name" aspect here by the fact that the result of std::move(x) — the expression itself — is unnamed, even though x itself may well be a named variable. That's what lets it bind to a move constructor or move assignment overload, which expect an unnamed rvalue-like expression on the other side.

Yea, rvalue, lvalue, xvalues, and then there's actually another thing called prvalue, let's just not get carried away by these right now.

For move semantics in BasicString, we will implement it via a move constructor and a move assignment. These will require a move helper function.

Move Helper

Put this function in Segment 5 with private visibility:

    template<bool onReassign>
    inline void m_moveToSelf(BasicString&& poth) noexcept {
        mlen = poth.mlen; // copy the other's length
        // we need to save it BEFORE we modify poth.mlen!
        if (poth.isSmall()) {
            // if other in SSO
            if constexpr (onReassign) {
                // on reassignment
                if (!isSmall()) {
                    // if this in heap
                    std::free(mbuf); // free heap
                    mbuf = mlocalbuf; // set this to SSO
                }
            }
            std::memcpy(mbuf, poth.mbuf, ssoCapacity);
        }
        else {
            // if other in heap
            if constexpr (onReassign) {
                // on reassignment
                if (!isSmall()) {
                    // if this in heap
                    std::free(mbuf);
                }
            }
            mbuf = poth.mbuf; // get the other buffer
            mcap = poth.mcap; // copy the capacity

            // put other in SSO
            poth.mbuf = poth.mlocalbuf;
        }
        // "empty" the other
        poth.mbuf[0] = 0;
        poth.mlen = 0;
    }

This move helper is marked as noexcept because in usual implementations, it is expected for a move operation to not produce any exceptions.

This function itself has a template, which takes a boolean argument bool onReassign to distinguish between a freshly contructed move object v/s a move assignment. It uses an if constexpr, which checks at compile time if we are reassigning or not, and removes/adds the if constexpr code. To be noted, if constexpr is a strict compile time construct, it does NOT produce any runtime branches. (Though, the pitfall with constexpr being... here it MUST be evaluated in compile time, compared to constexpr with function... Oh WG21!)

Such is done because the core mechanism of moving is basically the same, just in reassignment, we have to deal with a previous state to discard.

To walk through the function:

We save the value of poth.mlen to mlen
We check if poth is in SSO, if YES
1. The compile time check if we're reassigning, if YES
  1. If current object is ON HEAP, then std::free the heap buffer and set mbuf to SSO (pointing to mlocalbuf)
  2. Otherwise, mbuf stays in SSO as usual
2. COPY the contents of poth.mbuf into current object's SSO! Note: we are COPYING the SSO content on move because we cannot transfer ownership of poth's SSO buffer!
Otherwise, poth is in heap
1. Compile time check on reassignment, if yes
  1. If current object is on heap, then free the heap buffer.
  2. Otherwise, mbuf stays in SSO but it doesn't matter, SSO buffer is useless now since poth is in heap.
2. Set mbuf pointing to poth.mbuf, and copy mcap from poth.mcap
3. Set poth into a valid state of an empty string on SSO, therefore poth "loses ownership" of its original heap memory. It is crucial to set poth.mbuf to poth.mlocalbuf because otherwise its destructor would call free() on poth.mbuf, and we DO NOT WANT THAT!
Set the first character of poth.mbuf to NULL terminator, and set poth.mlen to 0. It is usual practice to "empty" out the other string. Even though, it is kinda unnecessary if poth is in SSO as it still owns its local buffer, since the standard says that poth must be left in a "valid but unspecified state". It is still done for behavioural consistency.

That was pretty simple! Now to design the interface for its use.

Move Interface

Pretty small functions, so thought of bolting them in one header. Put in Segment 6 with public visibility.

The Move Constructor. We do set mbuf to mlocalbuf explicitly just to make sure that we don't accidentally mess up in the future.

    // C8
    // move constructor
    BasicString(BasicString&& poth) noexcept : mbuf(mlocalbuf) {
        m_moveToSelf<false>(std::move(poth));
    }

Then the Move Assignment Operator. We skip reassignment if some lunatic supplied the same object for reassignment.

    BasicString& operator=(BasicString&& poth) noexcept {
        if (this == &poth) {
            return *this;
        }
        m_moveToSelf<true>(std::move(poth));
    }

Initializer List Interface

Again pretty small functions, so bolted them in one header. Put in Segment 6 with public visibility.

What is Initializer List?

Simply, std::initializer_list is a C++ standard library type that provides access to a fixed-size list of elements initialized using braces {}. It enables convenient initialization of containers, objects, and function parameters.

But C++ also has "initializer list" in constructors, which is a special syntax to initialize member variables in C++. That is different from the initializer list we're discussing now. We're dealing with std::initializer_list! Talk to WG21!

Initializer list constructor:

    // C9
    BasicString(std::initializer_list<CharT> pil) {
        if (pil.size() == 0) {
            m_initEmpty();
            return;
        }
        m_assignNew(pil.begin(), pil.size());
    }

Initializer list assignment:

    BasicString& operator=(std::initializer_list<CharT> pil) {
        if (pil.size() == 0) {
            m_clearString();
        } else {
            m_reassign(pil.begin(), pil.size());
        }
        return *this;
    }

Iterator Aliases

To properly implement iterators, we're gonna be creating some descriptive aliases to these names first! Put these right back in Segment 1 with public visibility.

    using iterator = CharT*;
    using const_iterator = const CharT*;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

Iterators

Using these aliases, we will create the iterator functions. Put these in Segment 6 with public visibility.

    // ---------- iterators -----------
    // forward, begin
    iterator begin() noexcept { return mbuf; }
    const_iterator begin() const noexcept { return mbuf; }
    const_iterator cbegin() const noexcept { return mbuf; }
    // forward, end
    iterator end() noexcept { return mbuf + mlen; }
    const_iterator end() const noexcept { return mbuf + mlen; }
    const_iterator cend() const noexcept { return mbuf + mlen; }

    // backward, rbegin
    reverse_iterator rbegin() noexcept
        { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const noexcept
        { return const_reverse_iterator(end()); }
    const_reverse_iterator crbegin() const noexcept
        { return const_reverse_iterator(cend()); }
    // backward, rend
    reverse_iterator rend() noexcept
        { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const noexcept
        { return const_reverse_iterator(begin()); }
    const_reverse_iterator crend() const noexcept
        { return const_reverse_iterator(cbegin()); }

Returns forward and reverse iterators to the internal string buffer.

Capacity Interface

Functions which are related to the capacity of the class.

    // ----------- capacity -----------

    inline constexpr std::size_t max_size() const noexcept {
        return maxlength();
    }

    void clear() noexcept {
        m_clearString();
        // preserves capacity
    }

    bool empty() const noexcept { return mlen == 0; }

    void shrink_to_fit() {
        // if in SSO, just skip it...
        if (isSmall()) return;

        if (m_isLenSmall(mlen)) {
            // if length fits in SSO
            std::ranges::copy_n(mbuf, mlen + 1, mlocalbuf);
            // also copy the NULL terminator
            std::free(mbuf); // free the heap
            mbuf = mlocalbuf; // put as SSO
        }
        else {
            auto newcap = (mlen + 1) * sizeof(CharT);
            auto newbuf = (CharT*)std::realloc(mbuf, newcap);
            if (newbuf != nullptr) {
                mbuf = newbuf;
                mcap = newcap;
            }
            // meh, if failure, just skip it...
            // honestly, if it fails, there's bigger
            // fish to catch...
        }
    }

Many are pretty self-explanatory but we should properly go over void shrink_to_fit() in details.

shrink_to_fit() function shrinks the extra memory allocated for the string. The only function which brings a heap string back to SSO if it fits there. And totally skips the whole function call if the string is in SSO because there's nothing to "shrink" over there. So the rest of the function only works if it is in heap.

If the length of the string fits within SSO, it is copied into mlocalbuf, the heap mbuf is freed and mbuf is set to point to mlocalbuf to enable SSO Mode. Otherwise, the appropriate capacity is calculated and realloc is called on it to shrink it, if possible... It realloc fails, well, its fine, we can ignore it since shrink_to_fit() itself is non-binding, and realloc makes sure the previous buffer is still fine.

Element Access Interface

    // --------- element access ---------
    CharT& operator[](std::size_t ppos) noexcept { return mbuf[ppos]; }
    const CharT& operator[](std::size_t ppos) const noexcept { return mbuf[ppos]; }

    CharT& at(std::size_t ppos) {
        if (ppos >= mlen) {
            throw std::out_of_range("Out of range index access!");
        }
        return mbuf[ppos];
    }
    const CharT& at(std::size_t ppos) const
        { return const_cast<BasicString*>(this)->at(ppos); }

    CharT& front() { return mbuf[0]; }
    const CharT& front() const
        { return const_cast<BasicString*>(this)->front(); }

    CharT& back() { return mbuf[mlen - 1]; }
    const CharT& back() const
        { return const_cast<BasicString*>(this)->back(); }

Basically character getters and setters with bad decision making. Each operation is designed as couplets, one useful for modification & access (non const counterpart), the other allowing read-only access (const counterpart).

Going through each:

operator[](std::size_t ppos) noexcept: Access any character from the string, does not throw. Any out of bounds access is UB.
at(std::size_t ppos): Access any character from the string. Any out of bounds access, including accessing the last null terminator, results in throwing a std::out_of_range exception. The exception message could have been made more descriptive but I'm tired.
front(): Access the first character. UB on empty strings.
back(): Access the last character (right before the null terminator). UB on empty strings.

It can be seen that I have only implemented the non-const versions, and then used a const_cast<>() within the const functions.

Why this? Since both have literally the same implementation, just the const-ness is changed.

But WHAT is that nonsense const_cast line? In the const overload of at(), the data type of this is const BasicString*, so it cannot directly call the non-const at(). const_cast removes the const modifier from this to reuse the existing implementation.

Why do we even need the casting?

So, hypothetically, if we did:

// previous non const definition
const CharT& at(std::size_t ppos) const { return at(ppos); }

This results in a recursion! The return at(ppos); translates to return this->at(ppos); and we know that this is a const BasicString* which is exactly why the non-const overload which needs a BasicString* would not be called!

Therefore, casting this to a BasicString* before call is mandatory!

I must state, there's nasty problems with this way of implementing — mainly being, we're calling a non-const function from within a const function by casting it. So there could be a place where the non-const version actually modifies the data, which is propagated through the const function!!

Another way to do the implementation — would be to define the function as const form, and then cast this to a const BasicString* to call the const function from within the non-const overload. But is is also VERY nasty! Because the non-const version returns a modifiable reference, so the trace of the modification goes back to the original const overload via the non-const version!! As in the source of modification is in a const function call but from an outside context! (And this would require more ugly casting code!)

A third way is to rewrite the function... but again, we ain't gonna do that!

Data Operation Interface

    // ------------ operations ---------
    CharT* data() noexcept { return mbuf; }
    const CharT* data() const noexcept { return mbuf; }

    const CharT* c_str() const noexcept { return mbuf; }

Again, very simple! We're not using the casting over here for data() because simple return does the job!

In c_str() we don't need to do anything special because the string is stored as a null terminated C string!

Finishing Touches

Before be present the final form of the class (after the v2 saga) we should try to "formalize" some definitions and expland them to make the class elegant!

String Definition

What is a string? We'll keep it straight and simple:

A contiguous block of memory containing homogeneous elements of integral data type and ending in a zero-valued NULL terminating element.

And let's make "character sequence" synonymous to a "string".

This now allows us to expand our template-concept to data types beyond char.

Better Concepts

template<typename T>
concept CharType = std::integral<T>;

And now, everything else just fits into place! We don't even need to change anything in the class since everything was made such that it stays relative to CharType!

Final Implementation

#pragma once

#include <algorithm>
#include <bit>
#include <cstddef>
#include <concepts>
#include <cstdlib>
#include <cstring>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <stdexcept>
#include <utility>

template<typename T>
concept CharType = std::integral<T>;

template<CharType C>
inline constexpr std::size_t chseqlen(const C* pbuf) {
    std::size_t len = 0;
    while (pbuf[len] != 0) {
        len++;
    }
    return len;
}

template<CharType CharT>
class BasicString {
public:
    // Segment 1
    static constexpr std::size_t npos = -1;
    static constexpr std::size_t ssoCapacity = 15 + 1; // bytes
    static constexpr std::size_t ssoItems = ssoCapacity / sizeof(CharT);

    using iterator = CharT*;
    using const_iterator = const CharT*;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

private:
    // Segment 2
    CharT* mbuf = mlocalbuf;
    std::size_t mlen = 0;
    union {
        std::size_t mcap;
        CharT mlocalbuf[ssoItems];
    };

private:
    // Segment 3
    static inline constexpr std::size_t m_getCapFromLen(std::size_t plen) {
        return std::bit_ceil((plen + 1) * sizeof(CharT));
    }

    static inline constexpr bool m_isLenSmall(std::size_t plen) {
        return plen < ssoItems;
    }

public:
    // Segment 4
    inline bool isSmall() const { return mbuf == mlocalbuf; }

    inline std::size_t strByteCapacity() const {
        return (mlen + 1) * sizeof(CharT);
    }

    static inline consteval std::size_t maxlength() {
        // return std::numeric_limits<ssize_t>::max(); // only in POSIX
        return std::numeric_limits<std::ptrdiff_t>::max();
        // equivalent...
    }

    inline std::size_t byteCapacity() const {
        if (isSmall()) return ssoCapacity;
        else return mcap;
    }

    inline std::size_t capacity() const {
        return ((isSmall() ? ssoCapacity : mcap) / sizeof(CharT)) - 1;
    }

    inline std::size_t length() const { return mlen; }

    inline std::size_t size() const { return mlen; }

private:
    // Segment 5
    inline void m_initEmpty() {
        // to initialize as empty, put it in SSO
        // DO NOT TOUCH mcap!
        mbuf = mlocalbuf; // in SSO Mode
        mbuf[0] = 0; // CharT{} also works, but for integral types they're the same
        mlen = 0;
    }

    inline void m_assignNew(const CharT* pbuf, std::size_t plen) {
        mlen = plen;
        // check if length fits in SSO
        if (m_isLenSmall(plen)) {
            mbuf = mlocalbuf; // in sso
        } else {
            // not in sso
            mcap = m_getCapFromLen(mlen);
            mbuf = (CharT*)std::malloc(mcap);
        }
        std::memcpy(mbuf, pbuf, mlen * sizeof(CharT));
        mbuf[plen] = 0;
    }

    inline void m_clearString() noexcept {
        mbuf[0] = 0;
        mlen = 0;
    }

    inline void m_reassign(const CharT* pbuf, std::size_t plen) {
        if (pbuf == mbuf) {
            mlen = plen;
            mbuf[mlen] = 0;
            return;
        }

        if (isSmall()) {
            // if currently in SSO
            if (!m_isLenSmall(plen)) {
                // the assignment needs heap
                mcap = m_getCapFromLen(plen);
                mbuf = (CharT*)std::malloc(mcap);
                // NOTE: THIS IN SSO, but assignment needs heap
                // => pbuf CANNOT BE IN CURRENT OBJECT'S SSO, NOR ANY SSO
                // so there's NO OVERLAP WITH THIS.SSO POSSIBLE
                // so write to mcap, mlocalbuf is garbage anyway...
            }
            // else, assignment needs SSO, no need to call malloc
            // can be overlapping
        }
        else if (plen > mlen) { // hehe!
            // if currently in heap, don't move back to SSO
            // just like gcc implementation, a reassignment doesn't move back to SSO if already in heap
            // a greater newcap matters only when plen > mlen
            // if plen <= mlen, no need to care about a newer capacity
            // totally skip the scenario when mcap not power of 2 due
            // to a shrink, and then subsequent overlapping buffer re-assign
            auto newcap = m_getCapFromLen(plen);
            if (newcap > mcap) { // can access mcap, cuz in heap
                // don't even shrink size
                mcap = newcap; // in heap, can use mcap
                std::free(mbuf); // free it now
                mbuf = (CharT*)std::malloc(newcap);
            }
        }

        mlen = plen;
        std::memmove(mbuf, pbuf, plen * sizeof(CharT));
        mbuf[mlen] = 0; // separately set the last NULL
    }

    template<bool onReassign>
    inline void m_moveToSelf(BasicString&& poth) noexcept {
        mlen = poth.mlen; // copy the other's length
        // we need to save it BEFORE we modify poth.mlen!
        if (poth.isSmall()) {
            // if other in SSO
            if constexpr (onReassign) {
                // on reassignment
                if (!isSmall()) {
                    // if this in heap
                    std::free(mbuf); // free heap
                    mbuf = mlocalbuf; // set this to SSO
                }
            }
            std::memcpy(mbuf, poth.mbuf, ssoCapacity);
        }
        else {
            // if other in heap
            if constexpr (onReassign) {
                // on reassignment
                if (!isSmall()) {
                    // if this in heap
                    std::free(mbuf);
                }
            }
            mbuf = poth.mbuf; // get the other buffer
            mcap = poth.mcap; // copy the capacity

            // put other in SSO
            poth.mbuf = poth.mlocalbuf;
        }
        // "empty" the other
        poth.mbuf[0] = 0;
        poth.mlen = 0;
    }


public:
    // Segment 6

    // init an empty string
    // C1
    BasicString() noexcept { m_initEmpty(); }

    // copy constructor
    // C2
    BasicString(const BasicString& pstr) {
        // just assign from the other string
        m_assignNew(pstr.mbuf, pstr.mlen);
    }

    // C3
    BasicString(const BasicString& pstr,
            std::size_t ppos,
            std::size_t plen = npos
    ) {
        if (ppos == pstr.mlen) {
            m_initEmpty();
        } else if (ppos > pstr.mlen) {
            throw std::out_of_range("Starting position > length of other string");
        }
        else {
            m_assignNew(
                pstr.mbuf + ppos,
                std::ranges::min(pstr.mlen - ppos, plen)
            );
        }
    }

    // C4
    BasicString(const CharT* s) {
        if (s == nullptr || s[0] == 0) {
            m_initEmpty();
            return;
        }
        // assume C string
        m_assignNew(s, chseqlen(s));
    }

    // C5
    BasicString(const CharT* s, std::size_t n) {
        if (n == 0 || s == nullptr) {
            m_initEmpty();
            return;
        }
        m_assignNew(s, n);
    }

    // C6
    BasicString(std::size_t n, CharT c) {
        if (n == 0) {
            m_initEmpty();
            return;
        }
        mlen = n;
        if (m_isLenSmall(mlen)) {
            mbuf = mlocalbuf;
        } else {
            mcap = m_getCapFromLen(mlen);
            mbuf = (CharT*)std::malloc(mcap);
        }
        std::ranges::fill_n(mbuf, mlen, c);
        mbuf[mlen] = 0;
    }

    // C7
    // STL doesn't have this overload
    BasicString(std::size_t n, const CharT* s) {
        if (n == 0 || s == nullptr || s[0] == 0) {
            m_initEmpty();
            return;
        }
        // must be non-empty string
        auto buflen = chseqlen(s);
        mlen = buflen * n;
        if (m_isLenSmall(mlen)) {
            mbuf = mlocalbuf; // in sso
        } else {
            // out of sso
            mcap = m_getCapFromLen(mlen);
            mbuf = (CharT*)std::malloc(mcap);
        }

        for (std::size_t i = 0; i < mlen; i += buflen) {
            std::ranges::copy_n(s, buflen, mbuf + i);
        }
        mbuf[mlen] = 0;
    }

    // C8
    // move constructor
    BasicString(BasicString&& poth) noexcept : mbuf(mlocalbuf) {
        m_moveToSelf<false>(std::move(poth));
    }

    // C9
    BasicString(std::initializer_list<CharT> pil) {
        if (pil.size() == 0) {
            m_initEmpty();
            return;
        }
        m_assignNew(pil.begin(), pil.size());
    }

    ~BasicString() {
        if (!isSmall()) { // important! Don't free static buffer!
            std::free(mbuf);
        }
    }

    BasicString& operator=(const BasicString& pstr) {
        m_reassign(pstr.mbuf, pstr.mlen);
        return *this;
    }

    BasicString& operator=(const CharT* s) {
        // UB: if s is non-null terminated
        if (s == nullptr) {
            m_clearString();
        } else {
            m_reassign(s, chseqlen(s));
        }
        return *this;
    }

    BasicString& operator=(CharT c) {
        const CharT buf[] = { c, 0 };
        m_reassign(buf, 1);
        return *this;
    }

    BasicString& operator=(BasicString&& poth) noexcept {
        if (this != &poth) {
            m_moveToSelf<true>(std::move(poth));
        }
        return *this;
    }

    BasicString& operator=(std::initializer_list<CharT> pil) {
        if (pil.size() == 0) {
            m_clearString();
        } else {
            m_reassign(pil.begin(), pil.size());
        }
        return *this;
    }


    // ---------- iterators -----------
    // forward, begin
    iterator begin() noexcept { return mbuf; }
    const_iterator begin() const noexcept { return mbuf; }
    const_iterator cbegin() const noexcept { return mbuf; }
    // forward, end
    iterator end() noexcept { return mbuf + mlen; }
    const_iterator end() const noexcept { return mbuf + mlen; }
    const_iterator cend() const noexcept { return mbuf + mlen; }

    // backward, rbegin
    reverse_iterator rbegin() noexcept
        { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const noexcept
        { return const_reverse_iterator(end()); }
    const_reverse_iterator crbegin() const noexcept
        { return const_reverse_iterator(cend()); }
    // backward, rend
    reverse_iterator rend() noexcept
        { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const noexcept
        { return const_reverse_iterator(begin()); }
    const_reverse_iterator crend() const noexcept
        { return const_reverse_iterator(cbegin()); }


    // ----------- capacity -----------

    inline constexpr std::size_t max_size() const noexcept {
        return maxlength();
    }

    void clear() noexcept {
        m_clearString();
        // preserves capacity
    }

    bool empty() const noexcept { return mlen == 0; }

    void shrink_to_fit() {
        // if in SSO, just skip it...
        if (isSmall()) return;

        if (m_isLenSmall(mlen)) {
            // if length fits in SSO
            std::ranges::copy_n(mbuf, mlen + 1, mlocalbuf);
            // also copy the NULL terminator
            std::free(mbuf); // free the heap
            mbuf = mlocalbuf; // put as SSO
        }
        else {
            auto newcap = (mlen + 1) * sizeof(CharT);
            auto newbuf = (CharT*)std::realloc(mbuf, newcap);
            if (newbuf != nullptr) {
                mbuf = newbuf;
                mcap = newcap;
            }
            // meh, if failure, just skip it...
            // honestly, if it fails, there's bigger
            // fish to catch...
        }
    }

    // --------- element access ---------
    CharT& operator[](std::size_t ppos) noexcept { return mbuf[ppos]; }
    const CharT& operator[](std::size_t ppos) const noexcept { return mbuf[ppos]; }

    CharT& at(std::size_t ppos) {
        if (ppos >= mlen) {
            throw std::out_of_range("Out of range index access!");
        }
        return mbuf[ppos];
    }
    const CharT& at(std::size_t ppos) const
        { return const_cast<BasicString*>(this)->at(ppos); }

    CharT& front() { return mbuf[0]; }
    const CharT& front() const
        { return const_cast<BasicString*>(this)->front(); }

    CharT& back() { return mbuf[mlen - 1]; }
    const CharT& back() const
        { return const_cast<BasicString*>(this)->back(); }

    // ------------ operations ---------
    CharT* data() noexcept { return mbuf; }
    const CharT* data() const noexcept { return mbuf; }

    const CharT* c_str() const noexcept { return mbuf; }
};

Lies and Pitfalls

There is a lie. Unions in C++ technically aren't blobs of memory. Technically this whole thing is UB. In C++ unions are unlike those of C. In C++, accessing a union member which is not active is UB, but we routinely do that. But by our compiler assumptions, of having gcc or clang, they still treat C++ unions as C unions, therefore, the class stands! And I am NOT going to sit here and reason about where the UB would lie. Here, C++ would require a tagged union, which in such a critical class is impossible to construct without inflating the object to the point of being useless, even libstdc++ doesn't check for union member lifetimes. Yes, it does imply that some very significant and important things which make C++ very fast is the fact that compilers may ignore some things at times via extensions.

And I've assumed that std::malloc always returns a valid pointer. Technically, it can fail and return a nullptr but that's a good enough assumption. Since, when std::malloc returns nullptr, you're already in a no-recovery zone. On Linux, OOM would have already killed your program before std::malloc gets the chance to throw nullptr.

Also, I have skipped a huge portion of the stdlib functions. Particularly because they're very tedious, very long, and algorithmically complex. Especially the functions for finding substrings within strings and others. The class header file is already 400+ lines long and the article is already ~8000 words big.

So that's it, that's your BasicString class from scratch with all the explanations. Bye!