盒子
盒子
文章目录
  1. Nim编程早茶
    1. 创建动态字符串
    2. 初始化
    3. 释放字符串对象
    4. 拷贝对象
    5. 清空字符串
    6. 字符串扩容
    7. 字符串连接
    8. 字符串拷贝
    9. 字符串填充指定字符
    10. 字符串去除指定字符
    11. 字符串比较
    12. 余下函数
    13. 测试

Nim 语言使用指针实现动态字符串

Nim编程早茶

这一节,我们介绍如何使用指针实现动态字符串,我们需要手动管理内存。当然这样做,是不推荐的,仅为学习的目的。与之相对的,我们应该使用 移动语义 实现动态字符串或者动态数组。

创建动态字符串

len 表示字符串的长度,avail 表示字符串的可用空间。而 buf 用存储字符串。

1
2
3
4
5
type
SDS* = object
len: int
avail: int
buf*: ptr UncheckedArray[char]

初始化

提供两种初始化方法。

1
2
3
4
5
6
7
8
9
10
proc newSDS*(initSize: int = 8): SDS = 
SDS(len: 0, avail: initSize, buf: cast[ptr UncheckedArray[char]](alloc(sizeof(char) * initSize)))

proc newSDS*(s: string, initSize: int = 8): SDS =
if s.len == 0:
return newSDS(initSize)
result.len = s.len
result.avail = s.len
result.buf = cast[ptr UncheckedArray[char]](alloc(sizeof(char) * result.len * 2))
moveMem(result.buf, s[0].unsafeAddr, s.len)

释放字符串对象

释放对象

1
2
3
proc free*(s:var SDS) = 
dealloc(s.buf)
s.buf = nil

拷贝对象

深拷贝。

1
2
3
4
5
proc clone*(s: SDS): SDS = 
result.len = s.len
result.avail = s.avail
result.buf = cast[ptr UncheckedArray[char]](alloc(result.len + result.avail))
moveMem(result.buf, s.buf, s.len)

清空字符串

惰性清空,不释放内存。

1
2
proc clear*(s: var SDS) {.inline.}= 
s.len = 0

字符串扩容

小于 1MB,空间翻倍,大于 1MB,只增长 1MB。

1
2
3
4
5
6
7
8
9
10
proc resize*(s: SDS, size: int): SDS =
if size < 1048576:
result.len = size
result.avail = size
result.buf = cast[ptr UncheckedArray[char]](alloc(size * 2))
else:
result.len = size
result.avail = 1048576
result.buf = cast[ptr UncheckedArray[char]](alloc(s.len + s.avail))
moveMem(result.buf, s.buf, s.len)

字符串连接

拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
proc cat*(s1: var SDS, s2: string) {.inline.} = 
let
total = s1.len + s2.len
tmp = s1.len
if s2.len > s1.avail:
s1 = resize(s1, total)
else:
s1.len = total
s1.avail -= s2.len
for i in 0 ..< s2.len:
s1.buf[tmp + i] = s2[i]

proc cat*(s1: var SDS, s2: SDS) {.inline.} =
let
total = s1.len + s2.len
tmp = s1.len
if s2.len > s1.avail:
s1 = resize(s1, total)
else:
s1.len = total
s1.avail -= s2.len
for i in 0 ..< s2.len:
s1.buf[tmp + i] = s2.buf[i]

字符串拷贝

浅拷贝。

1
2
3
4
5
6
7
8
9
proc copy*(s1: var SDS, s2: SDS) {.inline.} = 
if s1.len + s1.avail < s2.len:
s1 = resize(s1, s2.len)
else:
s1.len = s2.len
s1.avail -= s2.len
if s1.len == 0:
return
s1.buf = s2.buf

字符串填充指定字符

填充指定字符。

1
2
3
4
5
6
7
8
9
proc fill*(s: var SDS, c: char = '\0', size: int = 1) {.inline.} = 
let tmp = s.len
if s.avail < size:
s = resize(s, s.len + s.avail + size)
else:
s.len += size
s.avail -= size
for i in 0 ..< size:
s.buf[tmp+i] = c

字符串去除指定字符

保留原有顺序。

1
2
3
4
5
6
7
8
9
10
proc strim*(s: SDS, dict: set[char]): SDS {.inline.} = 
let total = s.len * 2
result.buf = cast[ptr UncheckedArray[char]](alloc(total))
var counter: int = 0
for c in 0 ..< s.len:
if s.buf[c] notin dict:
result.buf[counter] = s.buf[c]
inc(counter)
result.len = counter
result.avail = total - counter

字符串比较

按位比较。

1
2
3
4
5
6
7
8
9
10
proc cmp*(s1: SDS, s2: SDS): bool =
if s1.len != s2.len:
return false
for i in 0 ..< s1.len:
if s1.buf[i] != s2.buf[i]:
return false
return true

proc `==`*(s1, s2: SDS): bool =
cmp(s1, s2)

余下函数

切片,打印。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
proc `[]`*(s: SDS, idx: int): char = 
s.buf[idx]

proc `[]=`*(s: var SDS, idx: int, v: char) =
s.buf[idx] = v

proc `&`*(s1: var SDS, s2: string): SDS {.inline.} =
cat(s1, s2)
result = s1

proc `&`*(s1: var SDS, s2: SDS): SDS {.inline.} =
cat(s1, s2)
result = s1

proc `&=`*(s1: var SDS, s2: string) {.inline.} =
cat(s1, s2)

proc `&=`*(s1: var SDS, s2: SDS) {.inline.} =
cat(s1, s2)

proc `$`*(s: SDS): string =
result = newString(s.len)
for i in 0 ..< s.len:
result[i] = s.buf[i]

测试

浅拷贝与深拷贝

1
2
3
4
5
6
7
8
9
10
11
when isMainModule:
var s1 = newSDS("76test")
var s2 = newSDS("qwuyetrgu")
copy(s1, s2)
var s3 = s2.strim({'t'})
var s4 = clone(s2)
assert s1 == newSDS("qwuyetrgu")
assert s3 == newSDS("qwuyergu")
s2[3] = 'a'
assert s1 == s2
assert not (s4 == s2)