Repository navigation
Expand file tree
/
Copy pathc-stl-vector.html
More file actions
381 lines (346 loc) · 16.1 KB
/
Copy pathc-stl-vector.html
File metadata and controls
381 lines (346 loc) · 16.1 KB
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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>C语言实现STL：vector（动态数组） - CoccusQ的博客</title>
<link href="https://cdnjs.cloudflare.com/ajax/libs/prism/1.24.1/themes/prism.min.css" rel="stylesheet">
<link rel="stylesheet" href="style.css">
</head>
<body class="layout-container">
<!-- 导航栏 -->
<nav class="navbar">
<div class="navbar-container">
<a href="https://coccusq.github.io" class="navbar-logo">CoccusQ</a>
<div class="navbar-links">
<a href="https://coccusq.github.io/about">关于本站✓</a>
<a href="https://github.com/CoccusQ/coccusq.github.io">GitHub↗</a>
</div>
</div>
</nav>
<!-- 左侧边栏 -->
<aside class="sidebar-left">
<!-- 左侧导航内容 -->
</aside>
<main class="main-content">
<header class="article-header">
<h1 class="article-title" id="headline">C语言实现STL：vector（动态数组）</h1>
<div class="article-meta">
By <a href="https://github.com/CoccusQ">CoccusQ</a> · 2025.03.01 Update
</div>
</header>
<!-- 下面这个是占位符，不能去除 -->
<section class="section">
<h2 class="section-title" id="前言">前言</h2>
<p>C语言实现动态数组的原理并不复杂，只需要实现数组元素的插入和删除、随机访问以及根据当前数组内元素数量自动调整数组占用内存大小的功能即可。</p>
<p>唯一的难点在于存储不同类型的数据。C++ STL中的<code>vector</code>利用了C++的模板功能，能够存储任意类型数据，而想要在C语言中实现类似的功能，就需要利用到<code>void*</code>指针。<code>void*</code>指针只存储一个地址，而不关心这个地址内存储的数据类型，因此我们只需要按照不同数据类型的字节数来访问<code>void*</code>中的数据。</p>
<p>例如，如果我们要动态分配一块内存给一个<code>int</code>数组，常规做法就是使用<code>stdlib.h</code>中的<code>malloc</code>函数，代码如下：</p>
<pre class="language-c"><code>int num = 24;
int* array = (int*)malloc(sizeof(int) * num);</code></pre>
<p>事实上，无论<code>malloc</code>还是<code>calloc</code>、<code>realloc</code>，这些函数返回的内存地址都是以<code>void*</code>指针作为载体的，而内存的分配过程也是“简单粗暴”地将<code>int</code>的字节数乘上数组的元素个数，而程序员在访问内存的时候只要以<code>int</code>的字节数为单位进行，数据就不会出错。</p>
</section>
<section class="section">
<h2 class="section-title" id="代码分析">代码分析</h2>
<p>以下是实现代码：</p>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">初始化操作</h3>
<pre class="language-c"><code>/*vector结构体*/
struct vector {
int capacity;
int size;
void* items;
size_t sizeOfType;
};
/*构造函数，分配初始内存空间*/
void vector_init(struct vector* v, int capacity, size_t sizeOfType) {
v->capacity = capacity;
v->sizeOfType = sizeOfType;
v->size = 0;
v->items = calloc(v->capacity, v->sizeOfType);
if (v->items == NULL) exit(errno);
}
/*重新调整数组大小，且原来的元素不会丢失*/
void vector_resize(struct vector* v, int capacity) {
void* temp = v->items;
int temp_cap = v->capacity;
v->capacity = capacity;
v->items = realloc(v->items, v->sizeOfType * v->capacity);
if (v->items == NULL) exit(errno);
if (v->items != temp)
memmove(v->items, temp, v->sizeOfType * temp_cap);
}</code></pre>
<p>其中，<code>vector</code>类（其实是结构体）的数据成员有容量<code>capacity</code>、元素个数<code>size</code>、指向数组首地址的指针<code>item</code>、当前数组内存放数据的字节数<code>sizeOfType</code>，<code>vector_init</code>函数和<code>vector_resize</code>函数的内存分配过程均是以<code>sizeOfType</code>为单位进行。</p>
<p>细节：</p>
<div class="note">
<strong>要点说明</strong>
<ul><li>在复制整个数组时，采用`memmove`而不是`memcpy`，因为在重新分配内存时新的内存空间可能和旧的空间有重合，这种重合的情况在`memcpy`是未定义行为，而`memmove`会在遇到重合的时候创建一个临时缓冲区进行复制，更安全。</li><li>`calloc`和`realloc`：与`malloc`不同，`calloc`在分配内存时还会把每个元素初始化为0；而`realloc`会尝试在原来的地址处调整内存空间大小，如果空间足够，原来的数据就不会丢失，只有空间不够的情况下才会重新找一块内存，这时候原来的数据就不能一起迁移过来，需要重新复制一遍，`vector_resize`函数的最后两行就是在做这个判断（如果新分配的指针地址和原来不一样，说明起始地址变了，需要 复制原来的数据到新的内存空间里）。</li></ul>
</div>
</div>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">插入元素</h3>
<pre class="language-c"><code>/*在尾部插入元素*/
void vector_push_back(struct vector* v, void* item) {
if (v->size >= v->capacity)
vector_resize(v, v->capacity * 2);
memcpy(v->items + (v->size * v->sizeOfType), item, v->sizeOfType);
v->size++;
}
/*在给定位置插入元素*/
void vector_insert(struct vector* v, void* item, int index) {
if (index < 0) return;
if (index >= v->size) {
vector_push_back(v, item);
}
else {
if (v->size >= v->capacity)
vector_resize(v, v->capacity * 2);
memmove(v->items + (index + 1) * v->sizeOfType, v->items + index * v->sizeOfType, v->sizeOfType * (v->size - index));
v->size++;
memcpy(v->items + (index * v->sizeOfType), item, v->sizeOfType);
}
}</code></pre>
</div>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">删除元素</h3>
<pre class="language-c"><code>/*删除尾部元素*/
void vector_pop_back(struct vector* v) {
if (v->size <= 0) return;
v->size--;
if (v->size < v->capacity / 3)
vector_resize(v, v->capacity / 2);
}
/*删除给定位置的元素*/
void vector_erase(struct vector* v, int index) {
if (index < 0 || index >= v->size) return;
if (index == v->size - 1) {
vector_pop_back(v);
}
else {
memmove(v->items + index * v->sizeOfType, v->items + (index + 1) * v->sizeOfType, v->sizeOfType * (v->size - index - 1));
v->size--;
if (v->size < v->capacity / 3)
vector_resize(v, v->capacity / 3);
}
}</code></pre>
</div>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">实现元素随机访问</h3>
<pre class="language-c"><code>/*访问头部元素*/
void* vector_front(struct vector* v) {
return v->items;
}
/*访问尾部元素*/
void* vector_back(struct vector* v) {
if (v->size < 1) return NULL;
return v->items + (v->size - 1) * v->sizeOfType;
}
/*随机访问元素*/
void* vector_get(struct vector* v, int index) {
if (index < 0 || index >= v->size) return NULL;
return v->items + index * v->sizeOfType;
}</code></pre>
<p>访问时的<code>v->sizeOfType</code>就是在按照元素类型的字节数访问，保证读取的数据正确。</p>
</div>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">清零和析构操作</h3>
<pre class="language-c"><code>/*清空数组*/
void vector_clear(struct vector* v) {
if (v->size == 0) return;
memset(v->items, 0, v->sizeOfType * v->capacity);
}
/*析构函数，释放动态分配的内存*/
void vector_free(struct vector* v) {
free(v->items);
}</code></pre>
</div>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">一些宏定义</h3>
<pre class="language-c"><code>/*简化构造函数的调用*/
#define VECTOR(type, name, capacity) struct vector name; vector_init(&name, capacity, sizeof(type))
#define VECTOR_GET(type, name, index) *(type*)vector_get(&name, index)
#define VECTOR_FRONT(type, name) *(type*)vector_front(&name)
#define VECTOR_BACK(type, name) *(type*)vector_back(&name)</code></pre>
<p>利用宏的替换机制，实现类似于C++模板的编译时替换操作；同时将动态数组的随机访问函数的返回值进行操作，将原来的<code>void*</code>类型依据数据类型转换成数值，便于进行赋值操作。</p>
<p>（ps：这一部分对c语言宏的使用是我感觉最有意思的地方。）</p>
</div>
</section>
<section class="section">
<h2 class="section-title" id="小结一下">小结一下</h2>
<p>这是C语言实现STL系列的第一个尝试，由于语言特点和个人技术，最终的使用效果和性能离STL这种工业级轮子有很大的差距，不过使用C语言的种种特性来完成一些巧妙的操作还是非常有意思的，尤其是利用<code>void*</code>类型实现不同类型数据的存储（其实这里的灵感也来源于标准库里的<code>malloc</code>函数申请内存的用法）</p>
<p>最后是完整的头文件代码：</p>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">完整代码</h3>
<pre class="language-c"><code>/*vector.h*/
#ifndef _VECTOR_H_
#define _VECTOR_H_
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#define VECTOR(type, name, capacity) struct vector name; vector_init(&name, capacity, sizeof(type))
#define VECTOR_GET(type, name, index) *(type*)vector_get(&name, index)
#define VECTOR_FRONT(type, name) *(type*)vector_front(&name)
#define VECTOR_BACK(type, name) *(type*)vector_back(&name)
struct vector {
int capacity;
int size;
void* items;
size_t sizeOfType;
};
void vector_init(struct vector* v, int capacity, size_t sizeOfType) {
v->capacity = capacity;
v->sizeOfType = sizeOfType;
v->size = 0;
v->items = calloc(v->capacity, v->sizeOfType);
if (v->items == NULL) exit(errno);
}
void vector_resize(struct vector* v, int capacity) {
void* temp = v->items;
int temp_cap = v->capacity;
v->capacity = capacity;
v->items = realloc(v->items, v->sizeOfType * v->capacity);
if (v->items == NULL) exit(errno);
if (v->items != temp)
memmove(v->items, temp, v->sizeOfType * temp_cap);
}
void vector_push_back(struct vector* v, void* item) {
if (v->size >= v->capacity)
vector_resize(v, v->capacity * 2);
memcpy(v->items + (v->size * v->sizeOfType), item, v->sizeOfType);
v->size++;
}
void vector_pop_back(struct vector* v) {
if (v->size <= 0) return;
v->size--;
if (v->size < v->capacity / 3)
vector_resize(v, v->capacity / 2);
}
void vector_insert(struct vector* v, void* item, int index) {
if (index < 0) return;
if (index >= v->size) {
vector_push_back(v, item);
}
else {
if (v->size >= v->capacity)
vector_resize(v, v->capacity * 2);
memmove(v->items + (index + 1) * v->sizeOfType, v->items + index * v->sizeOfType, v->sizeOfType * (v->size - index));
v->size++;
memcpy(v->items + (index * v->sizeOfType), item, v->sizeOfType);
}
}
void vector_erase(struct vector* v, int index) {
if (index < 0 || index >= v->size) return;
if (index == v->size - 1) {
vector_pop_back(v);
}
else {
memmove(v->items + index * v->sizeOfType, v->items + (index + 1) * v->sizeOfType, v->sizeOfType * (v->size - index - 1));
v->size--;
if (v->size < v->capacity / 3)
vector_resize(v, v->capacity / 3);
}
}
void* vector_front(struct vector* v) {
return v->items;
}
void* vector_back(struct vector* v) {
if (v->size < 1) return NULL;
return v->items + (v->size - 1) * v->sizeOfType;
}
void* vector_get(struct vector* v, int index) {
if (index < 0 || index >= v->size) return NULL;
return v->items + index * v->sizeOfType;
}
void vector_clear(struct vector* v) {
if (v->size == 0) return;
memset(v->items, 0, v->sizeOfType * v->capacity);
}
void vector_free(struct vector* v) {
free(v->items);
}
#endif</code></pre>
</div>
</section>
<!-- 索引部分 -->
<div class="guide-grid">
<article class="guide-card">
<div class="guide-card-left">
<span class="guide-date">Last post</span>
<a href="https://coccusq.github.io/about" class="guide-title-link">
<h2 class="guide-title">« 关于本站</h2>
</a>
</div>
</article>
<article class="guide-card">
<div class="guide-card-right">
<span class="guide-date">Next post</span>
<a href="https://coccusq.github.io/c-stl-list" class="guide-title-link">
<h2 class="guide-title">C语言实现STL：list（双向循环链表） »</h2>
</a>
</div>
</article>
</div>
</main>
<!-- 右侧边栏 -->
<aside class="sidebar-right">
<div class="sidebar-header">文档目录</div>
<nav class="sidebar-nav" id="sidebar-nav"></nav>
</aside>
<!-- 页脚内容 -->
<footer class="footer">
<div class="footer-container">
<div class="footer-column">
<h4 class="footer-title">About us</h4>
<div class="footer-links">
<a href="https://coccusq.github.io/about">✒️Learn More</a>
<a href="https://coccusq.github.io/build-tools">🛠️Build-tools</a>
</div>
</div>
<div class="footer-column">
<h4 class="footer-title">Useful Tools</h4>
<div class="footer-links">
<a href="https://chat.deepseek.com">🤖DeepSeek</a>
<a href="https://github.com/cayxc/Mdtht">📑Mdtht</a>
<a href="https://www.emojiall.com">😄EMOJIALL</a>
</div>
</div>
<div class="footer-column">
<h4 class="footer-title">Social</h4>
<div class="footer-links">
<a href="mailto:king_crab_cn@outlook.com">Email</a>
<a href="https://github.com/CoccusQ/coccusq.github.io">GitHub↗</a>
</div>
</div>
</div>
<div class="footer-divider"></div>
<div class="footer-copyright">
<p>© 2025 CoccusQ 🇨🇳. All rights reserved.</p>
</div>
</footer>
<div class="copy-feedback" id="copyFeedback"></div>
<script src="script.js"></script>
<!-- 代码高亮 -->
<script src="https://cdnjs.cloudflare.com/ajax/libs/prism/1.24.1/prism.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/prism/1.24.1/components/prism-c.min.js"></script>
</body>
</html>