类似于vector，具备自动扩容的能力，可返回迭代器，可返回size，可返回capacity，也可以返回函数内部指针。

SSO（Small String Optimization)

string内部关于短字符串的优化 , 当字符串的长度较短时，在栈上开辟内存空间；当字符串的长度超过了一定值，再在堆上分配内存空间。

引用SSO背景

因为传统的字符串采用动态内存分配策略，即使存储的字符串数量很少时依然需要在堆上开辟内存空间，那么这种设计存在以下问题：

1. 高频次的小对象内存分配与释放的开销，短字符串会频繁触发new/delete关键对内存进行构造和释放
2. 缓存不友好，堆内存的离散化分布导致CPU缓存命中率不高，堆内存中连续的字符数组具有更好的空间局部性
3. 内存碎片化，大量的小块内存不利于系统合理管理

SSO的核心思想

针对小字符串：（小于等于N字节），保存在类内部的字符数组中（分配在栈空间）

针对大字符串：动态分配堆上的空间并且维护堆指针

通过通过Union+标志位判断当前是短字符还是长字符串。

不同的编译器对std::string的短字符串优化的字节数

• GCC：通常为15个字符（含结尾的空字符\0，实际可存储 15 个有效字符）
• Clang：与 GCC 类似，也采用 15 个字符的 SSO 缓冲区
• MSVC（Visual Studio）：早期版本为 15 个字符，部分版本可能调整为 14 个字符

SSO 的缓冲区大小通常与std::string内部存储指针和长度信息的成员变量总大小一致，这样可以避免额外的内存开销。

SSO的简单实现

1、成员结构

shortString结构体适用于存储短字符串的，它包含一个固定大小的字符数组 data[kShortCap]和两个位字段size和is_long;size字段用于存储字符串的长度（最多63字符），is_long是一个标志位，用于指定字符串是否应该被视为长字符（0表示短字符串、1表示长字符串）

struct ShortString {
            value_type data[kShortCap];
            unsigned char size: 7;
            unsigned char is_long: 1;
        };

 

LongString结构体用于存储长字符串，包含了一个指向动态分配内存的指针data、字符串的长度size、字符串的容量cap（-1，因为最高位被is_long占用），一个is_long标志位

struct LongString {
            pointer data;                                      /// 8
            size_type size;                                    /// 8
            size_type cap: sizeof(size_type) * CHAR_BIT - 1;  /// 64 - 1 = 63
            size_type is_long: 1;                             /// 1  标志位
        };

 

kShortCap：表示短字符串能够存储的最大字符数（不包括“\0"，这个值根据LongString的大小和value_type的大小计算得出

static constexpr int32_t kShortCap = sizeof(LongString) / sizeof(value_type) - 1;

 

Req：一个union联合体，用于存储字符串的数据，根据字符串的长度，它可以是LongString或 ShortString类型，只会被赋值为一个类型，当字符串的长度超过kShortCap时，字符串就是LongString类型。

struct Rep {
            union {
                LongString lstr;
                ShortString sstr;
            };
        };

2、SSOString实现

首先实现基于SSO的string，会根据SSO模式来进行构造

2.1 成员变量

	// 最大的字符串数组的大小
    static constexpr size_t SSO_BUFFER_SIZE = 15;
    // 联合体
    union{
        // 存放短字符串大小的数组
        char sso_data_[SSO_BUFFER_SIZE + 1];
        // 堆区结构体
        struct {
            char* heap_data_;  // 动态分配的指针
            size_t capacity_;   // 数组容量
        };
    };

    // 字符串长度
    size_t size_;
    bool is_sso_;   // 是否启动sso

2.2 构造与析构

构造与析构都需要判断是否是SSO模式，不同的模式下的构造结果不同

SSOString(const char* str = "")
        : size_(strlen(str))
        , is_sso_(size_ <= SSO_BUFFER_SIZE + 1)
    {
        // 还需要根据是否是SSO模式来进行构造
        if (is_sso_) {
            // 短字符模式，存储在字符数组中
            std::memcpy(sso_data_, str, size_);
        } else {
            // 堆区动态开辟
            capacity_ = size_ + 1;          // 容量需要+1  "\0"
            heap_data_ = new char[capacity_];
            std::memcpy(heap_data_, str, capacity_);
        }
    }

拷贝构造与赋值运算也同样需要考虑是否为SSO的情况,短字符则使用memcpy，长字符串则使用new动态分配

 	SSOString(const SSOString& other)
        : size_(other.size_)
        , is_sso_(other.is_sso_)
    {
        // 还需要根据是否是SSO模式来进行构造
        if (is_sso_) {
            std::memcpy(sso_data_, other.sso_data_, size_);
        } else {
            capacity_ = other.capacity_;          // 容量需要+1  "\0"
            heap_data_ = new char[capacity_];
            std::memcpy(heap_data_, other.heap_data_, capacity_);
        }
    }

    // 拷贝赋值
    SSOString& operator=(const SSOString& other)
    {
        if (this != &other) {
           // 先析构现有对象
            this->~SSOString();
            // placement new
            new(this) SSOString(other);
        }
        return *this;
    }

移动构造与移动赋值运算，在赋值运算时，在自赋值检查通过之后需要首先析构现有的对象，然后在这块空间上构造other对象

// 移动构造
    SSOString(SSOString&& other) noexcept
        : size_(other.size_)
        , is_sso_(other.is_sso_)
    {
        // 还需要根据是否是SSO模式来进行构造
        if (is_sso_) {
            // 启用了SSO模式，说明是栈区存储元素
            std::memcpy(sso_data_, other.sso_data_, size_);
        } else {
            capacity_ = other.capacity_;          // 容量需要+1  "\0"
            heap_data_ = other.heap_data_;

            other.capacity_ = 0;
            other.heap_data_ = nullptr;
        }
        other.size_ = 0;        // 不管是哪一种方式，最后的大小都= 0
    }

    SSOString& operator=(SSOString& other) noexcept
    {
        if (this != &other) {
            // 先析构现有对象
            this->~SSOString();
            // placement new
            new(this) SSOString(std::move(other));
        }
        return *this;
    }

析构函数，由于短字符串时，存储在栈区不需要我们手动释放空间，我们只需要释放堆区的空间就行

 ~SSOString()
    {
        if (!is_sso_) {
            delete[] heap_data_;
        }
    }

2.3 常见接口

这里仅仅简单给出几个接口，后序会给出更完备的string接口。

size_t size() const
    {
        return size_;
    }

    const char* c_str() const
    {
        return is_sso_ ? sso_data_ : heap_data_;
    }

    // 重载[]
    char& operator[](size_t idx)
    {
        return is_sso_ ? sso_data_[idx] : heap_data_[idx];
    }

2.4 测试

#include "sso.h"

int main()
{
    SSOString s1("short");
    s1.debug();  // 应使用SSO
    // size_ = 5, content = short, SSO = true

    SSOString s2("this is a long string that will not use SSO");
    s2.debug();
    // size_ = 43, content = this is a long string that will not use SSO, SSO = false
}

String

下面的内容我主要给出部分函数的实现，整体的源码可以在我的仓库上（TMac-wei/mystl: MySTL 标准库实现）

模板类定义

分配器可以自定义，也可以选择标准库的内存分配器，这里直接给出模板类定义常用的类型定义

template<typename charT, typename Allocator = MyAlloc<charT>>
    class basic_string {
     public:
        using self = basic_string;
        using value_type = charT;
        using allocator_type = Allocator;
        using size_type = typename allocator_type::size_type;
        using reference = typename allocator_type::reference;
        using const_reference = typename allocator_type::const_reference;
        using pointer = typename allocator_type::pointer;
        using const_pointer = typename allocator_type::const_pointer;
        using iterator = pointer;
        using const_iterator = const_pointer;

        static constexpr size_type npos = -1;
        
     private:
        /// 实现SSO的basic_string
        struct LongString {
            pointer data;                                      /// 8
            size_type size;                                    /// 8
            size_type cap: sizeof(size_type) * CHAR_BIT - 1;  /// 64 - 1 = 63
            size_type is_long: 1;                             /// 1  标志位
        };

        static constexpr int32_t kShortCap = sizeof(LongString) / sizeof(value_type) - 1;

        struct ShortString {
            value_type data[kShortCap];
            unsigned char size: 7;
            unsigned char is_long: 1;
        };

        struct Rep {
            union {
                LongString lstr;
                ShortString sstr;
            };
        };

        Rep rep_;
        allocator_type alloc_;
    }

构造与析构

提供了默认构造、拷贝构造、移动构造以及利用边长字符串数组进行构造的方式。

我这里主要给出部分函数实现。

		basic_string(size_type size) {
            if (size > max_size()) {
                throw std::length_error("basic_string");
            }
            if (fits_in_sso_(size)) {  /// 短字符串
                set_short_size_(size);
            } else {  /// 长字符串
                auto capacity = recommend_(size);
                auto p = alloc_.allocate(capacity);
                set_long_size_(size);
                set_long_capacity_(capacity);
                set_long_pointer_(p);
            }
        }

        /// 拷贝构造
        basic_string(const basic_string &str) {
            init_(str.data(), str.size());
        }

总的来说，在实现的过程中，就是需要去设置对应的短字符串与长字符串的相关变量，其中set_short_size_、set_long_size_(size)、set_long_capacity_(capacity)、set_long_pointer_(p)都是相应的辅助函数。

init_()函数与上一章节SSO的初始化一样，都是需要去根据字符串的长度判断启用哪种模式，然后进行对应的初始化，如下：

 		void init_( const value_type *str, size_type n) {
            rep_.sstr.is_long = 0;
            pointer p;
            /// 首先判断是否为短字符
            if (fits_in_sso_(n)) {
                p = get_short_pointer_();
                set_short_size_(n);
            } else {
                auto cap = recommend_(n);
                p = alloc_.allocate(cap);
                set_long_capacity_(cap);
                set_long_pointer_(p);
                set_long_size_(n);
            }
            /// 将str的内容拷贝到p上
            memcpy(p, str, n);
            p[n] = value_type();
        }

如果传入的参数变长的字符数组指针，那么就先计算出这个数组的长度，然后再初始化就行，整体思路都是一致的。

析构函数，主要负责清理堆区 的数据，栈区的数据会自动清理

	~basic_string() {
            if (is_long_()) {
                alloc_.deallocate(get_long_pointer_(), get_long_capacity_());
            }
        }

常见的数据接口

这里展示常见的接口，例如size(),data(),empty()等，直接给出实现

		value_type *data() { return get_pointer_(); }

        const value_type *data() const { return get_pointer_(); }

        size_type size() const { return is_long_() ? get_long_size_() : get_short_size_(); }

        size_type length() const { return size(); }

        size_type capacity() const { return is_long_() ? get_long_capacity_() : kShortCap - 1; }

        bool empty() const { return size() == 0; }

        value_type *c_str() { return data(); }

        const value_type *c_str() const { return data(); }

        basic_string substr(size_type pos = 0, size_type n = npos) const { return basic_string(*this, pos, n); }

        reference operator[](size_type pos) { return data()[pos]; }

        const_reference operator[](size_type pos) const { return data()[pos]; }

        size_type max_size() const { return alloc_.max_size(); }

迭代器操作

		iterator begin() { return data(); }

        const_iterator cbegin() const { return data(); }

        iterator end() { return data() + size(); }

        const_iterator cend() const { return data() + size(); }

        iterator rbegin() { return data() + size() - 1; }

        const_iterator crbegin() const { return data() + size() - 1; }

        iterator rend() { return data() - 1; }

        const_iterator crend() const { return data() - 1; }

内存操作

assign 给字符串对象赋新值

首先都要判断传入的字符数量与SSO模式，然后再对不同的模式进行对应的操作，这里以将字符串内容设置为 count 个 _c 字符为例

	basic_string& assign(size_type count, value_type _c) {
            size_type cap = capacity(); 	/// 获取现有的容量
            if (cap < count) {
                if (is_long_()) {
                    /// 释放现有的空间，然后分配新的
                    alloc_.deallocate(get_long_pointer_(), cap);
                }
                /// init_(count, _c) 是构造新数据
                init_(count, _c);
            } else {
                pointer p = get_pointer_();
                for (size_type i = 0; i < count; ++i) {
                    p[i] = _c;
                }
                p[count] = value_type();
                set_size_(count);
            }
            return *this;
        }

append 追加字符串

将新元素追加到字符串的末尾，首先需要判断当前的大小和总空间是否足够，如果足够则写入到末尾，如果不足够需要构建新的空间并且添加数据

		basic_string& append(const value_type* s, size_type n) {
            /// 获取当前的大小和总空间
            size_type cap = capacity();
            size_type size_ = size();
            if (cap - size_ - 1 >= n) {  /// 剩下的空间足够
                memcpy(data() + size_, s, n);
                set_size_(size_ + n);
                data()[size()] = value_type();  /// 这里必须写到新的size末尾，而不能是data()[size_] = value_type()，这样会导致截断
            } else {
                /// 剩下的空间不足够就会构建新的空间并且添加数据
                grow_by_and_add_(cap, size_ + n - cap, size_, n, s);
            }
            return *this;
        }

如果在剩下的空间不足够的情况下，需要构建新的空间并且添加数据，也就是这里grow_by_and_add_，那么这里涉及到了扩容策略

内存扩容策略

扩容并且添加数据

在旧数据基础上扩容，并在末尾追加新的数据段。

完整的扩容流程如下：

1. 首先获取需要扩容的新容量大小，先取原容量的2倍和旧容量+需要添加元素数量的最大值，将其结果作为参数传入recommend_计算内存的对齐的最合适的当前大小

推荐一个“合理的”扩容大小，满足至少为 size，并向上按 8 字节对齐;类比 STL vector 的_M_get_new_capacity()可以限制最大容量，防止内存爆炸式增长

		static size_type recommend_(size_type size) {
            if (size < kShortCap) {
                return static_cast<size_type>(kShortCap);
            }
            /// (size + 1) 向上对齐到 8 的倍数
            const size_type guess = align_it_<8>(size + 1);
            return guess;
        }

		/// 将数字 n 向上对齐到 N 的整数倍
        /// 对齐到 8 字节，能使结构体、内存块等满足 SIMD/CPU cache 的需求
        template<size_type N>
        static size_type align_it_(size_type n) {
            return (n + N - 1) & ~(N - 1);
        }

2. 根据推荐的容量大小开辟新的空间，然后将原始数据先拷贝到新的空间
3. 拷贝需要追加的元素到新的地址空间
4. 如果是长字符串模式的话，需要释放原始的地址空间
5. 更新相应的参数，包括指针地址、容量、大小等

 void grow_by_and_add_(size_type old_cap,size_type extra_cap,size_type old_sz,
                              size_type n_add,const value_type *new_buffer) {
            /// 首先调用 recommend_() 函数计算新容量（2倍扩容或满足新增需求）
            auto new_cap = recommend_(my::max(old_cap + extra_cap, 2 * old_cap));
            auto new_data = alloc_.allocate(new_cap);
            if (old_sz > 0) {
                /// 分配成功之后拷贝原数据（可能是 small 模式或 heap 模式）到新分配区
                memcpy(new_data, get_pointer_(), old_sz);
            }
            if (n_add > 0) {
                memcpy(new_data + old_sz, new_buffer, n_add);
            }
            if (is_long_()) {
                alloc_.deallocate(get_long_pointer_(), old_cap);
            }
            /// 更新参数
            set_long_pointer_(new_data);
            set_long_capacity_(new_cap);
            set_long_size_(old_sz + n_add);
            new_data[get_long_size_()] = value_type();
        }

只扩容不添加新元素

只扩容不添加元素的情况，一般适用于准备插入或者reserve预分配的情况

流程是：

1. 首先获取合适的大小（即recommand_的结果）
2. 分配新的空间，并且拷贝原来的旧数据到新空间
3. 释放原始的堆区空间
4. 更新对应参数

void grow_by_(size_type old_cap, size_type extra_cap, size_type old_sz) {
            auto new_cap = recommend_(my::max(old_cap + extra_cap, 2 * old_cap));
            auto new_data = alloc_.allocate(new_cap);
            if (old_sz > 0) {
                memcpy(new_data, get_long_pointer_(), old_sz);
            }
            alloc_.deallocate(get_long_pointer_(), old_cap);
            set_long_pointer_(new_data);
            set_long_capacity_(new_cap);
        }

reverse 预分配空间

提前预分配足够的空间，可以减少内存重分配的次数，提升性能。

如果预分配的大小小于当前容量大小，则直接退出；否则根据预分配的大小调用recommend_获取应该分配的合理大小，然后根据结果判断是缩容还是扩容

void reserve(size_type request_capacity) {
            if (request_capacity <= capacity()) {
                return;
            }
            size_type target_capacity = std::max(request_capacity, size());
            target_capacity = recommend_(target_capacity);
            if (target_capacity == capacity()) {
                return;
            }
            shrink_or_extend_(target_capacity);
        }

resize

原理就是判断所要求的大小与当前大小的关系，然后执行对应的操作

void resize(size_type request_size) {
            size_type size_ = size();

            if (request_size < size_) {
            /// 如果需求大小 ＞ 当前的大小，则将对于的空间用默认的方式设置
                data()[request_size] = value_type();
                set_size_(request_size);
            } else if (request_size > size_) {
                /// 如果不够，需要分配新的空间
                size_type cap = capacity();
                if (cap < request_size) {
                    grow_by_(cap, request_size - size_, size_);
                }
                pointer p = get_pointer_();
                for (size_type i = size_; i <= request_size; ++i) {
                    p[i] = value_type();
                }
                set_size_(request_size);
            }
        }

shrink_or_extend_

根据目标容量 target_capacity，在 short buffer（SSO）和 long buffer（堆分配）之间切换，并复制旧数据到新空间中，确保字符串有效

void shrink_or_extend_(size_type target_capacity) {
            size_type cap = capacity();
            size_type sz = size();

            bool was_long = is_long_();
            bool now_long = true;
            pointer new_data = nullptr;
            pointer old_data = nullptr;
            if (was_long) {
                old_data = get_long_pointer_();
            } else {
                old_data = get_short_pointer_();
            }
            if (fits_in_sso_(target_capacity)) {
                now_long = false;
                new_data = get_short_pointer_();
            } else {
                new_data = alloc_.allocate(target_capacity);
            }
            memcpy(new_data, old_data, sz);
            new_data[sz] = '\0';
            if (was_long) {
                alloc_.deallocate(old_data, cap);
            }
            if (now_long) {
                set_long_pointer_(new_data);
                set_long_capacity_(target_capacity);
                set_long_size_(sz);
            } else {
                set_short_size_(sz);
            }
        }

 

string类型定义

以上为基础的字符串类型 basic_string，我们需要使用string，则传入具体的类型即可

using string = basic_string<char>;

重载 == ！=

提供string类型与其他字符串的对比（包括同类类型和C风格字符串），主要是为了解决字符串的相等性判断。

比较的逻辑就是：

1. 若是两个string类型，长度相同且内容需要完全一致（strcmp判断）
2. string与C风格字符串，内容必须完全一致才能相等（strcmp判断）

 	bool operator==(const my::string& lhs, const my::string& rhs) {
        return lhs.size() == rhs.size() && strcmp(lhs.data(), rhs.data()) == 0;
    }

    bool operator==(const my::string& lhs, const char* rhs) {
        return strcmp(lhs.data(), rhs) == 0;
    }

    bool operator==(const char* lhs, const my::string& rhs) {
        return rhs == lhs;
    }

    bool operator!=(const my::string& lhs, const my::string& rhs) {
        return !(lhs == rhs);
    }

    bool operator!=(const my::string& lhs, const char* rhs) {
        return !(lhs == rhs);
    }

    bool operator!=(const char* lhs, const my::string& rhs) {
        return !(lhs == rhs);
    }