COW和SSO

GCC 4.x.x string的实现是 COW (写时复制)
GCC 5.x.x string的实现是 SSO (短字符串优先)

验证COW的存在

在g++ 4.

	std::string s1 = "hello,world";std::string s2(s1);printf("s1'addr = %p, str = %s, s2'addr = %p,str = %s\n", s1.c_str(), s1.c_str(), s2.c_str(), s2.c_str());s2[0] = 'H';printf("s1'addr = %p, str = %s, s2'addr = %p,str = %s\n", s1.c_str(), s1.c_str(), s2.c_str(), s2.c_str());

该例子可以看到，s2复制s1的时候进行的是浅拷贝，两者指向同一块空间，当s2发生修改时，s2会重新申请空间。

验证SSO的存在

在g++ 5.4.0

	std::string s1 = "hello,world";printf("s1'size = %d\n", sizeof(s1)); // 可以看到string不再是一个指针std::string s3 = "1234567891111111"; // 可以看到超过15个字符s3就在堆上了printf("s1'size = %p\n", s3.c_str());std::string s2(s1);printf("s1'addr = %p, str = %s, s2'addr = %p,str = %s\n", s1.c_str(), s1.c_str(), s2.c_str(), s2.c_str());std::string s4(s3); // 可以看到SSO没用引用计数，每次都是重新申请空间printf("s3'addr = %p, str = %s, s4'addr = %p,str = %s\n", s3.c_str(), s3.c_str(), s4.c_str(), s4.c_str());

如果想让SSO提升，在大于15字符后采用引用计数，可以看看FaceBook开源库中string的实现 https://github.com/facebook/folly.git

一个简单的写时复制实现

实现思路:
上图来自《Effective STL》条款15，本例只实现RefCnt和Value，Size Capactity暂时不管。
①class COWString中定义一个char的成员，char的前四个字节存放引用计数，后面存放实际的字符串。
②当发生复制构造和赋值操作时，执行浅拷贝，引用计数加1，有对象析构时引用计数减1，只有当引用计数为0时才释放空间
③当对象发生修改时，重载operator[]，进行深拷贝

#include 
#include class COWString {
public:COWString();COWString(const char* pstr);COWString(const COWString& rhs);COWString& operator=(const COWString& rhs);~COWString();const char& operator[](size_t idx) const { return _pstr[idx]; }char& operator[](size_t idx);size_t size() { return strlen(_pstr); }const char* c_str() const { return _pstr; }size_t refcount() const { return *(int*)(_pstr - 4); }private:void initRefcount() { *(int*)_pstr = 1; }void increaseRefcount() { (*(int*)(_pstr - 4))++; }void decreaseRefcount(){ if (_pstr == NULL) {return;}(*(int*)(_pstr - 4))--; }void release(){decreaseRefcount();if (refcount() == 0) {std::cout << "delete _pstr" << std::endl;delete [](_pstr - 4);   // 注意这里一定要减4,不然内存泄露}}
private:char* _pstr;
};COWString::COWString()
{this->_pstr = new char[5]();  // 前四个字节用来存放引用计数，再加上一个'\0'，申请5个字节  注意这里的()要加上，不然申请的数组没有初始化，可能会有脏数据 重载了operator+后几个字符串相加会触发这个buginitRefcount();this->_pstr += 4;
}COWString::COWString(const char* pstr)
{this->_pstr = new char[strlen(pstr) + 5]();initRefcount();this->_pstr += 4;strcpy_s(this->_pstr, strlen(pstr) + 1, pstr);
}COWString::COWString(const COWString& rhs)
{this->_pstr = rhs._pstr;increaseRefcount();
}COWString& COWString::operator=(const COWString& rhs)
{if (this != &rhs) {release();this->_pstr = rhs._pstr;increaseRefcount();}return *this;
}// 下标访问运算符无法区分出是读操作还是写操作
char& COWString::operator[](size_t idx)
{if (refcount() > 1) {char* tmp = new char[strlen(_pstr) + 5]();tmp += 4;strcpy_s(tmp, size() + 1, this->_pstr);decreaseRefcount();this->_pstr = tmp;increaseRefcount();}return _pstr[idx];
}COWString::~COWString()
{std::cout << "COWString::~COWString " << _pstr << std::endl;release();
}int main()
{COWString s1("hello");COWString s2(s1);COWString s3 = s1;printf("s1' addr = %p, s1' c_str() = %s, refcount = %d\n", s1.c_str(), s1.c_str(), (int)s1.refcount());printf("s2' addr = %p, s2' c_str() = %s, refcount = %d\n", s2.c_str(), s2.c_str(), (int)s2.refcount());printf("s3' addr = %p, s3' c_str() = %s, refcount = %d\n", s3.c_str(), s3.c_str(), (int)s3.refcount());std::cout << "执行修改操作后" << std::endl;s3[1] = 'E';printf("s1' addr = %p, s1' c_str() = %s, refcount = %d\n", s1.c_str(), s1.c_str(), (int)s1.refcount());printf("s2' addr = %p, s2' c_str() = %s, refcount = %d\n", s2.c_str(), s2.c_str(), (int)s2.refcount());printf("s3' addr = %p, s3' c_str() = %s, refcount = %d\n", s3.c_str(), s3.c_str(), (int)s3.refcount());return 0;
}

执行结果如图：

思考：
引用计数为什么要与char*放一起，不能单独定义一个成员变量存储？
①引用计数作为成员变量如：

class COWString{char* _pstr;int _refCnt;
}

这样不行，每个对象的引用计数相互独立了，无法同步增减。
②引用计数作为静态成员变量如：

class COWString{char* _pstr;static int _refCnt;
}

这样不行，静态成员变量为整个类共有，会造成不是指向同一个字符串的对象的引用计数也一致了。
③通过保存引用计数的指针：

class COWString{char* _pstr;int* _refCnt;
}

这样可行，不过要申请两次内存，因此将两个成员合并就是本例的实现。
④通过对象成员：

class String{friend class COWString;char* _pstr;int _refCnt;
}
class COWString{String* _string;;
}

可行。

区分读写操作的写时复制实现

上面的例子有个问题，就是只访问下标的元素，没有发生修改时，也会去重新开辟空间，如：const char c = s1[0];
实现思路：
①写操作：s1[0] = ‘H’; 先调用COWString::operator[idx]返回char，然后调用char的operator=修改变量
读操作：const char c = s1[0]; 仅仅调用COWString::operator[idx]返回char
因此区分读还是写操作就在于是否调用了char类型对象的operator=对operator[idx]重新赋值，COWString::operator[idx]返回的是一个char，由于char是内置类型，不能重载，因此我们考虑将COWString::operator[idx]返回一个自定义对象，然后重载自定义对象的operator=，这样写操作就实现了
②由于COWString::operator[idx]返回一个自定义对象，例const char c = s1[0]返回的自定义对象不能直接赋值给char类型变量，因此需要类型转换函数来解决。

#include 
#include class COWString {class CharProxy {public:CharProxy(size_t idx, COWString& self): _idx(idx), _self(self){}operator char() { // 类型转换函数std::cout << "CharProxy::operator char()" << std::endl;return _self._pstr[_idx];}char& operator=(const char& ch){if (_self.refcount() > 1) {char* tmp = new char[strlen(_self._pstr) + 5]();tmp += 4;strcpy_s(tmp, _self.size() + 1, _self._pstr);_self.decreaseRefcount();_self._pstr = tmp;_self.increaseRefcount();}return _self._pstr[_idx];}private:size_t _idx;COWString& _self;};
public:COWString();COWString(const char* pstr);COWString(const COWString& rhs);COWString& operator=(const COWString& rhs);~COWString();const char& operator[](size_t idx) const{ return _pstr[idx]; }CharProxy operator[](size_t idx);size_t size() { return strlen(_pstr); }const char* c_str() const { return _pstr; }size_t refcount() const { return *(int*)(_pstr - 4); }private:void initRefcount() { *(int*)_pstr = 1; }void increaseRefcount() { (*(int*)(_pstr - 4))++; }void decreaseRefcount(){ if (_pstr == NULL) {return;}(*(int*)(_pstr - 4))--; }void release(){decreaseRefcount();if (refcount() == 0) {std::cout << "delete _pstr" << std::endl;delete [](_pstr - 4);   // 注意这里一定要减4,不然内存泄露}}
private:char* _pstr;
};COWString::COWString()
{this->_pstr = new char[5]();  // 前四个字节用来存放引用计数，再加上一个'\0'，申请5个字节  注意这里的()要加上，不然申请的数组没有初始化，可能会有脏数据 重载了operator+后几个字符串相加会触发这个buginitRefcount();this->_pstr += 4;
}COWString::COWString(const char* pstr)
{this->_pstr = new char[strlen(pstr) + 5]();initRefcount();this->_pstr += 4;strcpy_s(this->_pstr, strlen(pstr) + 1, pstr);
}COWString::COWString(const COWString& rhs)
{this->_pstr = rhs._pstr;increaseRefcount();
}COWString& COWString::operator=(const COWString& rhs)
{if (this != &rhs) {release();this->_pstr = rhs._pstr;increaseRefcount();}return *this;
}// 注意这里是返回的对象，return的是个临时对象，返回引用，临时对象销毁，会异常
COWString::CharProxy COWString::operator[](size_t idx)
{return CharProxy(idx, *this);
}COWString::~COWString()
{std::cout << "COWString::~COWString " << _pstr << std::endl;release();
}int main()
{COWString s1("hello");COWString s2(s1);COWString s3 = s1;printf("s1' addr = %p, s1' c_str() = %s, refcount = %d\n", s1.c_str(), s1.c_str(), (int)s1.refcount());printf("s2' addr = %p, s2' c_str() = %s, refcount = %d\n", s2.c_str(), s2.c_str(), (int)s2.refcount());printf("s3' addr = %p, s3' c_str() = %s, refcount = %d\n", s3.c_str(), s3.c_str(), (int)s3.refcount());std::cout << "执行写操作后 s3[1] = 'E' " << std::endl;s3[1] = 'E';printf("s1' addr = %p, s1' c_str() = %s, refcount = %d\n", s1.c_str(), s1.c_str(), (int)s1.refcount());printf("s2' addr = %p, s2' c_str() = %s, refcount = %d\n", s2.c_str(), s2.c_str(), (int)s2.refcount());printf("s3' addr = %p, s3' c_str() = %s, refcount = %d\n", s3.c_str(), s3.c_str(), (int)s3.refcount());std::cout << "执行读操作后 s2[1] " << s2[1] << std::endl;s3[1] = 'E';printf("s1' addr = %p, s1' c_str() = %s, refcount = %d\n", s1.c_str(), s1.c_str(), (int)s1.refcount());printf("s2' addr = %p, s2' c_str() = %s, refcount = %d\n", s2.c_str(), s2.c_str(), (int)s2.refcount());printf("s3' addr = %p, s3' c_str() = %s, refcount = %d\n", s3.c_str(), s3.c_str(), (int)s3.refcount());const char c = s2[1]; // 隐式调用类型转换成员函数std::cout << "执行读操作后 s2[1] " << c << std::endl;printf("s1' addr = %p, s1' c_str() = %s, refcount = %d\n", s1.c_str(), s1.c_str(), (int)s1.refcount());printf("s2' addr = %p, s2' c_str() = %s, refcount = %d\n", s2.c_str(), s2.c_str(), (int)s2.refcount());printf("s3' addr = %p, s3' c_str() = %s, refcount = %d\n", s3.c_str(), s3.c_str(), (int)s3.refcount());return 0;
}

执行结果如图：

参考资料：https://www.cnblogs.com/cthon/p/9181979.html
http://www.kohn.com.cn/wordpress/?p=245
《Effective STL》

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！