积累沉淀

待山花烂漫，化茧成蝶

hstring测试报告

Posted on

hstring字符串操作类设计与实现

一、项目概要说明

目标：设计并实现字符串操作类hstring，实现自定义字符串的增、删、改、查等核心功能，通过缓冲区机制减少内存频繁分配／释放的开销，
全面考察类设计、运算符重载及算法实现能力。

核心特性：

  • 不依赖C++标准库string类，完全自主实现底层逻辑；
  • SSO优化，简化内存结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private:
    // SSO 缓冲区大小（包括结尾的 '\0'），可存储 small_capacity 个字符（不含 null）
    static constexpr size_type small_capacity = 15;          // 例如 15 + 1 = 16 字节

    // 存储联合体：大字符串用 dynamic，小字符串用 local
    union Storage {
        struct {
            value_type * data;         // 指向动态分配的字符数组（包含结尾 '\0'）
            size_type capacity; // 分配的容量（包含结尾 '\0' 的空间）
        } dynamic;
        value_type  local[small_capacity + 1];   // 本地缓冲区，始终以 '\0' 结尾
    } m_storage;

    // 大小与标志位的编码：
    // 最高位为 1 表示小字符串，其余位存储实际长度；
    // 最高位为 0 表示大字符串，其余位存储实际长度。
    size_type m_size;   // 编码后的大小

  • 强异常的安全保证（copy-and-swap技术）
  • 迭代器与标准库std::string的兼容
  • 支持运算符重载
  • 常用增删改查的api，增加算法find_kmp结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
namespace my {
class string {
public:
    // 常用类型定义
    using value_type             = char;
    using size_type              = std::size_t;
    using difference_type        = std::ptrdiff_t;
    using reference              = value_type&;
    using const_reference        = const value_type&;
    using pointer                = value_type*;
    using const_pointer          = const value_type*;
    using iterator               = pointer;
    using const_iterator         = const_pointer;

    static constexpr size_type npos = static_cast<size_type>(-1);

    // ---------- 构造 / 析构 ----------

    // 默认构造：空字符串（小字符串）
    string() noexcept ;

    // 从 std::string 构造
    string(const std::string &s) ;

    // 从 C 字符串构造（允许 nullptr 视为空）
    string(const value_type * s) ;

    // 从 C 字符串 + 长度构造
    string(const char* s, size_type count) ;

    // 拷贝构造
    string(const string& other) ;

    // 移动构造
    string(string&& other) noexcept ;j

    // ---------- 赋值运算符 ----------

    // 拷贝赋值（使用 copy-and-swap，强异常安全）
    string& operator=(const string& other) ;

    // 移动赋值（简单交换资源，noexcept）
    string& operator=(string&& other) noexcept ;

    // 从 C 字符串赋值
    string& operator=(const char* s) ;

    // ---------- 元素访问 ----------

    reference operator[](size_type pos) noexcept ;

    const_reference operator[](size_type pos) const noexcept ;

    reference at(size_type pos) ;

    const_reference at(size_type pos) const ;

    reference front() noexcept ;

    const_reference front() const noexcept ;

    reference back() noexcept ;

    const_reference back() const noexcept ;

    const_pointer c_str() const noexcept ;

    const_pointer data() const noexcept ;

    // ---------- 迭代器 ----------

    iterator begin() noexcept ;

    const_iterator begin() const noexcept ;

    const_iterator cbegin() const noexcept ;

    iterator end() noexcept ;

    const_iterator end() const noexcept ;

    const_iterator cend() const noexcept ;

    // ---------- 容量 ----------

    size_type size() const noexcept ;

    size_type length() const noexcept ;

    size_type capacity() const noexcept ;

    bool empty() const noexcept ;

    void reserve(size_type new_cap) ;

    void shrink_to_fit() ;

    // ---------- 修改操作 ----------

    void clear() noexcept ;

    void push_back(char ch) ;

    void pop_back() ;

    string& append(const string& str) ;

    string& append(const char* s, size_type count) ;

    string& operator+=(const string& str) ;

    string& operator+=(char ch) ;

    // 插入、擦除、替换等可类似实现，此处仅给出简单 erase 示例
    string& erase(size_type pos = 0, size_type count = npos) ;
    string &insert(size_type pos, const string &str) ;

    string &insert(size_type pos, const char *s) ;

    string &insert(size_type pos, const char *s, size_type count) ;
    // 4. 在迭代器位置 p 之前插入一个字符 ch，返回指向插入字符的迭代器
    iterator insert(const_iterator p, value_type ch) ;

    // 在迭代器位置 p 之前插入 count 个相同字符 ch，返回指向第一个插入字符的迭代器
    iterator insert(const_iterator p, size_type count, value_type ch) ;

    // 交换
    void swap(string& other) noexcept ;

    // ---------- 查找 ----------
    size_type find(const string& str, size_type pos = 0) const noexcept ;


    // 使用 KMP 算法查找子串 str，从位置 pos 开始
    size_type find_kmp(const string& str, size_type pos = 0) const ;

    // 使用 KMP 算法查找子串 s（长度为 count），从位置 pos 开始
    size_type find_kmp(const_pointer s, size_type pos, size_type count) const ;

    size_type find(const char* s, size_type pos, size_type count) const noexcept ;

    // ---------- 比较 ----------
    int compare(const string& other) const noexcept ;

    // ---------- 子串 ----------
    string substr(size_type pos = 0, size_type count = npos) const ;
    // ---------- 分隔 ----------
    std::vector<string> split(char delimiter, bool skip_empty = true) ;

    std::vector<string> split(const string &delimiter, bool skip_empty = true);
    

};

// ---------- 非成员运算符重载 ----------

inline bool operator==(const string& lhs, const string& rhs) noexcept ;

inline bool operator!=(const string& lhs, const string& rhs) noexcept ;

inline bool operator<(const string& lhs, const string& rhs) noexcept ;

inline bool operator<=(const string& lhs, const string& rhs) noexcept ;

inline bool operator>(const string& lhs, const string& rhs) noexcept ;

inline bool operator>=(const string& lhs, const string& rhs) noexcept ;

// 与 C 字符串的比较
inline bool operator==(const string& lhs, const char* rhs) ;
inline bool operator==(const char* lhs, const string& rhs) ;
// ... 其他比较运算符可类似定义

inline string operator+(const string& lhs, const string& rhs) ;
inline string operator+(const string& lhs, const char* rhs) ;
inline string operator+(const char* lhs, const string& rhs) ;
inline string operator+(const string& lhs, char rhs) ;
inline string operator+(char lhs, const string& rhs) ;

// 输出流支持
inline std::ostream& operator<<(std::ostream& os, const string& str) ;
} // namespace my

using hstring = my::string;

二、性能测试与标准库std::string的比较（windows 10, 64bit, Ubuntu22.04）

  • benchmark 输出数据格式（release mode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
Running D:\dev\workspace\clion\cppbase\cmake-build-release\test\test_hstring_benchmark.exe
Run on (4 X 2904 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x2)
  L1 Instruction 32 KiB (x2)
  L2 Unified 256 KiB (x2)
  L3 Unified 4096 KiB (x1)
------------------------------------------------------------------------
Benchmark                              Time             CPU   Iterations
------------------------------------------------------------------------
std_string_construct_long/0         9.45 ns         9.03 ns     64000000
std_string_construct_long/1          125 ns          126 ns      5600000
std_string_construct_long/0         9.37 ns         9.42 ns     89600000
std_string_construct_long/1          126 ns          126 ns      5600000
hstring_construct_long/0            7.31 ns         7.32 ns     89600000
hstring_construct_long/1             122 ns          120 ns      6400000
hstring_construct_long/0            7.25 ns         6.98 ns    112000000
hstring_construct_long/1             126 ns          126 ns      5600000
std_string_copy_long/0              4.02 ns         3.99 ns    172307692
std_string_copy_long/1              93.8 ns         88.9 ns      8960000
std_string_copy_long/0              3.94 ns         3.77 ns    165925926
std_string_copy_long/1              75.2 ns         75.0 ns      8960000
hstring_copy_long/0                 5.49 ns         5.47 ns    100000000
hstring_copy_long/1                 72.9 ns         73.2 ns      8960000
hstring_copy_long/0                 5.55 ns         5.58 ns    112000000
hstring_copy_long/1                 73.8 ns         73.2 ns      8960000
std_string_move_long/0              8.34 ns         8.20 ns     89600000
std_string_move_long/1              79.2 ns         79.5 ns      7466667
std_string_move_long/0              8.23 ns         8.37 ns     89600000
std_string_move_long/1              80.5 ns         79.5 ns      7466667
hstring_move_long/0                 10.9 ns         10.7 ns     64000000
hstring_move_long/1                 77.1 ns         76.7 ns      8960000
hstring_move_long/0                 10.3 ns         10.3 ns     64000000
hstring_move_long/1                 76.6 ns         76.7 ns      8960000
std_string_copy_assign_long/0       6.45 ns         6.45 ns     89600000
std_string_copy_assign_long/1       9.08 ns         9.03 ns     64000000
std_string_copy_assign_long/0       6.82 ns         6.80 ns     89600000
std_string_copy_assign_long/1       8.83 ns         8.58 ns     74666667
hstring_copy_assign_long/0          7.91 ns         8.02 ns     89600000
hstring_copy_assign_long/1          75.0 ns         73.2 ns      7466667
hstring_copy_assign_long/0          7.87 ns         8.02 ns     89600000
hstring_copy_assign_long/1          77.9 ns         78.5 ns      8960000
std_string_move_assign_long/0       7.37 ns         7.50 ns     89600000
std_string_move_assign_long/1       77.3 ns         76.7 ns      8960000
std_string_move_assign_long/0       7.40 ns         7.39 ns    112000000
std_string_move_assign_long/1       81.7 ns         80.2 ns      8960000
hstring_move_assign_long/0          11.0 ns         11.0 ns     64000000
hstring_move_assign_long/1          76.7 ns         76.7 ns      8960000
hstring_move_assign_long/0          11.9 ns         12.0 ns     64000000
hstring_move_assign_long/1          77.8 ns         78.1 ns      6400000
std_string_index_long/0             9.45 ns         9.21 ns     74666667
std_string_index_long/1              188 ns          188 ns      3733333
std_string_index_long/0             10.7 ns         10.7 ns     74666667
std_string_index_long/1              190 ns          184 ns      3733333
hstring_index_long/0                8.37 ns         8.37 ns     74666667
hstring_index_long/1                 182 ns          184 ns      4072727
hstring_index_long/0                11.1 ns         11.0 ns     64000000
hstring_index_long/1                 197 ns          195 ns      3200000
std_string_shrink_long/0            2.39 ns         2.35 ns    298666667
std_string_shrink_long/1            3.97 ns         4.02 ns    186666667
std_string_shrink_long/0            2.32 ns         2.34 ns    280000000
std_string_shrink_long/1            3.53 ns         3.52 ns    186666667
hstring_shrink_long/0               1.87 ns         1.86 ns    320000000
hstring_shrink_long/1               2.37 ns         2.34 ns    320000000
hstring_shrink_long/0               1.80 ns         1.80 ns    407272727
hstring_shrink_long/1               2.39 ns         2.41 ns    298666667
std_string_push_back_long/0         12.5 ns         12.6 ns     56000000
std_string_push_back_long/1         2.86 ns         2.89 ns    248888889
std_string_push_back_long/0         12.5 ns         12.3 ns     56000000
std_string_push_back_long/1         2.84 ns         2.76 ns    248888889
hstring_push_back_long/0            18.0 ns         18.0 ns     37333333
hstring_push_back_long/1            4.18 ns         4.14 ns    165925926
hstring_push_back_long/0            18.0 ns         18.0 ns     37333333
hstring_push_back_long/1            4.19 ns         4.24 ns    165925926
std_string_append_long/0            7.70 ns         7.53 ns     74666667
std_string_append_long/1            96.4 ns         95.2 ns      6400000
std_string_append_long/0            9.59 ns         9.63 ns     74666667
std_string_append_long/1             108 ns         97.7 ns      6400000
hstring_append_long/0               16.5 ns         16.5 ns     40727273
hstring_append_long/1                148 ns          150 ns      4480000
hstring_append_long/0               16.1 ns         16.0 ns     44800000
hstring_append_long/1                147 ns          146 ns      4480000
std_string_insert_long/0            16.0 ns         15.7 ns     44800000
std_string_insert_long/1            91.8 ns         92.1 ns      7466667
std_string_insert_long/0            15.9 ns         15.7 ns     40727273
std_string_insert_long/1             277 ns          226 ns      4977778
hstring_insert_long/0               15.1 ns         15.3 ns     40727273
hstring_insert_long/1                154 ns          150 ns      4480000
hstring_insert_long/0               14.5 ns         14.4 ns     49777778
hstring_insert_long/1                153 ns          151 ns      4977778
std_string_erase_long/0             8.01 ns         7.85 ns     89600000
std_string_erase_long/1             82.9 ns         82.0 ns      8960000
std_string_erase_long/0             7.85 ns         7.95 ns    112000000
std_string_erase_long/1             81.4 ns         81.6 ns      7466667
hstring_erase_long/0                11.6 ns         11.7 ns     64000000
hstring_erase_long/1                78.2 ns         77.4 ns      7466667
hstring_erase_long/0                12.4 ns         12.3 ns     56000000
hstring_erase_long/1                78.6 ns         78.5 ns      8960000
std_string_find_long/0              5.23 ns         5.30 ns    112000000
std_string_find_long/1              53.3 ns         53.0 ns     11200000
std_string_find_long/0              5.29 ns         5.30 ns    112000000
std_string_find_long/1              53.3 ns         53.0 ns     11200000
hstring_find_long/0                 8.30 ns         8.02 ns     89600000
hstring_find_long/1                 54.0 ns         54.4 ns     11200000
hstring_find_long/0                 8.08 ns         7.95 ns     74666667
hstring_find_long/1                 54.1 ns         53.0 ns     11200000
hstring_find_kmp_long/0             86.5 ns         85.8 ns      7466667
hstring_find_kmp_long/0             86.5 ns         87.2 ns      8960000
hstring_find_kmp_long/1              279 ns          276 ns      2488889
std_string_compare_long/0           6.82 ns         6.80 ns     89600000
std_string_compare_long/1           10.2 ns         10.3 ns     64000000
std_string_compare_long/0           6.87 ns         6.84 ns    112000000
std_string_compare_long/1           10.0 ns         10.0 ns     64000000
hstring_compare_long/0              8.01 ns         8.02 ns     89600000
hstring_compare_long/1              11.5 ns         11.5 ns     64000000
hstring_compare_long/0              8.62 ns         8.54 ns     89600000
hstring_compare_long/1              11.3 ns         11.2 ns     64000000
std_string_iterate_long/0           9.61 ns         9.63 ns     74666667
std_string_iterate_long/1            168 ns          167 ns      4480000
std_string_iterate_long/0           9.68 ns         9.63 ns     74666667
std_string_iterate_long/1            160 ns          160 ns      4480000
hstring_iterate_long/0              12.5 ns         12.6 ns     56000000
hstring_iterate_long/1               220 ns          220 ns      3200000
hstring_iterate_long/0              12.8 ns         12.6 ns     56000000
hstring_iterate_long/1               228 ns          229 ns      3200000
std_string_substr_long/0            8.12 ns         8.20 ns     89600000
std_string_substr_long/1            8.56 ns         8.58 ns     74666667
std_string_substr_long/0            7.90 ns         7.74 ns     74666667
std_string_substr_long/1            7.96 ns         7.95 ns     74666667
hstring_substr_long/0               7.32 ns         7.32 ns     89600000
hstring_substr_long/1               7.58 ns         7.50 ns     89600000
hstring_substr_long/0               7.58 ns         7.67 ns    112000000
hstring_substr_long/1               7.54 ns         7.53 ns    112000000
BM_MyStringSplitChar                4936 ns         5000 ns       100000
BM_MyStringSplitString              5077 ns         5156 ns       100000
  • 性能对比图表：std::string vs hstring
    说明：短字符串和长字符串多次测试，取平均值

std::string vs hstring

  • 结论：hstring 的性能基本上和 std::string 相当（append,copy_assign,insert较std::string慢2倍作用，其他相当）
Buy me a coffee please.