首页 > 代码库 > 数据结构《19》----String容器的三种实现

数据结构《19》----String容器的三种实现

一、序言

一个简单的string 容器到底是如何实现的?

本文给出了 String 的三种从易到难的实现,涉及了 reference counting, copy on write 的技术。


二、第一个实现

我们设计的string类里面包含一个char* 的指针, 通过指针的管理,来实现string的基本功能。

废话不多说了,直接上代码:


<script src="https://code.csdn.net/snippets/336885.js" type="text/javascript"></script>

几点注意的:类包含指针,因此需要 copy control, 也就是自行实现拷贝构造函数,赋值构造函数,析构函数,
而不能依赖于编译器生成的默认版本,默认版本拷贝仅仅是 bitwise 拷贝,会导致悬挂指针等等问题。

二、改进版本

第一个版本过于简单,相比聪明的读者早已看 strlen 不顺眼,因此,下一个版本加入表示当前字符串长度的变量。
代码如下:


<script src="https://code.csdn.net/snippets/336897.js" type="text/javascript"></script>

三、写时拷贝的 String
Copy-on-write(以下简称COW)是一种很重要的优化手段。它的核心思想是懒惰处理多个实体的资源请求,在多个实体之间共享某些资源,直到有实体需要对资源进行修改时,才真正为该实体分配私有的资源。

COW技术的一个经典应用在于Linux内核在进程fork时对进程地址空间的处理。由于fork产生的子进程需要一份和父进程内容相同但完全独立的地址空间,一种做法是将父进程的地址空间完全复制一份,另一种做法是将父进程地址空间中的页面标记为”共享的“(引用计数+1),使子进程与父进程共享地址空间,但当有一方需要对内存中某个页面进行修改时,重新分配一个新的页面(拷贝原内容),并使修改进程的虚拟地址重定向到新的页面上。



<script src="https://code.csdn.net/snippets/336912.js" type="text/javascript"></script>

四、参考
1. http://www.cnblogs.com/promise6522/archive/2012/03/22/2412686.html
2. More Effective C++