在CppPractice中，作者归类了 std::string的三种实现方式
- 无特殊处理(eager copy)，采用类似
std::vector的数据结构 copy-on-write(COW)。g++的std::string一直采用这种方式实现。- 短字符串优化(SSO)，利用
string对象本身的空间来存储短字符串。VC使用这种方式实现。
这三种实现方式都有各自的优势，下面将通过三个时下比较流行的库来讨论这三种实现。
标准库中的string
string的构造函数以及大小
在libstdc++中包含 string的文件有， basic_string.h和 basic_string.tcc，前者是string的定义，后者则为实现。在 basic_string.h中，我们看到如下注释，
1
2
3
4
5
6
7
8
9
* A string looks like this:
*
* @code
* [_Rep]
* _M_length
* [basic_string<char_type>] _M_capacity
* _M_dataplus _M_refcount
* _M_p ----------------> unnamed array of char_type
* @endcode
由上述定义可以看出，string其实是一个结构体，含有4个变量。 其中_M_p指向 string的第一个字符，这样设计的好处在于一个string对象只有一次内存分配。另外，当参数 _M_refcount == 0时，意味着这个对象有一个引用，这也就说，我们不应该试图去销毁一个空字符串。对于上面的注释还有如下需要注意的地方，
- 字符串应该包含
_M_length + 1个字符，因为\0 _M_capacity >= _M_length_M_refcount有三种state- -1:
leaked - 0: 一个引用，
non-const - >0 :
n+1个引用，操作需要加锁
- -1:
- 空字符串时，结构体中所有的值都为0
上面注释在代码中的实现为
1
2
3
4
5
6
struct _Rep_base
{
size_type _M_length;
size_type _M_capacity;
_Atomic_word _M_refcount;
};
可以看出在这个名为 _Rep_base的结构体中并不含有数据部分，所以在标准库中还有另外一个结构体
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct _Rep : _Rep_base
{
// Types:
typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
// (Public) Data members:
static const size_type _S_max_size;
static const _CharT _S_terminal;
static size_type _S_empty_rep_storage[];
static _Rep& _S_empty_rep()
{
void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);
return *reinterpret_cast<_Rep*>(__p);
}
....
struct _Alloc_hider : _Alloc
{
_Alloc_hider(_CharT* __dat, const _Alloc& __a)
: _Alloc(__a), _M_p(__dat) { }
_CharT* _M_p; // The actual data.
};
private：
mutable _Alloc_hider _M_dataplus;
}
通过上面的代码可以看到，string类型的成员类型是_Alloc_hider，而该类型实质上是个指向_CharT的指针。这说明，在 GUN g++的实现中，将string类型转换成了一个只需要占据 _CharT*大小的指针，同时，其他信息存储在 heap中。
string的拷贝构造
拷贝构造代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<typename _CharT, typename _Traits, typename _Alloc basic_string<_CharT, _Traits, _Alloc>::basic_string(const basic_string& __str)
: _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
__str.get_allocator()),
__str.get_allocator())
{ }
_CharT* _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
{
return (!_M_is_leaked() && __alloc1 == __alloc2)
? _M_refcopy() : _M_clone(__alloc1);
}
_CharT* _M_refcopy() throw()
{
#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
if (__builtin_expect(this != &_S_empty_rep(), false))
#endif
__gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
return _M_refdata();
}
_CharT* _M_clone(const _Alloc&, size_type __res = 0);
string的拷贝构造函数先后调用了，basic_string(const basic_string& __str),_M_grab()和 _M_refcopy。在 _M_refcopy中又调用了 __atomic_add_dispatch()确保线程安全将引用计数增加1。
string的copy-on-write
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
reference operator[](size_type __pos)
{
// allow pos == size() as v3 extension:
_GLIBCXX_DEBUG_ASSERT(__pos <= size());
// but be strict in pedantic mode:
_GLIBCXX_DEBUG_PEDASSERT(__pos < size());
_M_leak();
return _M_data()[__pos];
}
void _M_leak() // for use in begin() & non-const op[]
{
if (!_M_rep()->_M_is_leaked())
_M_leak_hard();
}
template<typename _CharT, typename _Traits, typename _Alloc>
void basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
{
#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
if (_M_rep() == &_S_empty_rep())
return;
#endif
if (_M_rep()->_M_is_shared())
_M_mutate(0, 0, 0);
_M_rep()->_M_set_leaked();
}
template<typename _CharT, typename _Traits, typename _Alloc> void basic_string<_CharT, _Traits, _Alloc>::_M_mutate(size_type __pos, size_type __len1, size_type __len2)
{
const size_type __old_size = this->size();
const size_type __new_size = __old_size + __len2 - __len1;
const size_type __how_much = __old_size - __pos - __len1;
if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
{
// Must reallocate.
const allocator_type __a = get_allocator();
_Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
if (__pos)
_M_copy(__r->_M_refdata(), _M_data(), __pos);
if (__how_much)
_M_copy(__r->_M_refdata() + __pos + __len2,
_M_data() + __pos + __len1, __how_much);
_M_rep()->_M_dispose(__a);
_M_data(__r->_M_refdata());
}
else if (__how_much && __len1 != __len2)
{
// Work in-place.
_M_move(_M_data() + __pos + __len2,
_M_data() + __pos + __len1, __how_much);
}
_M_rep()->_M_set_length_and_sharable(__new_size);
}
当我们想要修改一个string对象的值时，我们通常会使用 []，在 []的重载函数中，现调用了 _M_leak()来判断这个对象是否 leak(定义请参照第一部分)。当我们想修改指向同一内存的string对象时，会调用 _M_leak_hard()，在这个函数中又调用了 _M_mutate(0,0,0)。通过该函数的源代码，可以看出当调用这个函数之后，会重新申请一块内存给我们需要修改的对象，这样就能安全的修改string了。但是当我们不使用，string提供的标准接口时，会导致直接修改共享内存的值。
leveldb中的Slice
leveldb中的 Slice本质上是个可读视图，构造函数代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Create an empty slice.
Slice() : data_(""), size_(0) { }
// Create a slice that refers to d[0,n-1].
Slice(const char* d, size_t n) : data_(d), size_(n) { }
// Create a slice that refers to the contents of "s"
Slice(const std::string& s) : data_(s.data()), size_(s.size()) { }
// Create a slice that refers to s[0,strlen(s)-1]
Slice(const char* s) : data_(s), size_(strlen(s)) { }
....
private:
const char* data_;
size_t size_;
这个数据结构中包含两个变量，第一个是常量指针 data_，第二个是数据的大小size_。这种设计就相当于是个移动窗口，我知道窗口的开始地方和窗口的大小，那么就能知道整个窗口的内容。接下来就看看其中的成员函数，
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
// Return a pointer to the beginning of the referenced data
const char* data() const { return data_; }
// Return the length (in bytes) of the referenced data
size_t size() const { return size_; }
// Return true iff the length of the referenced data is zero
bool empty() const { return size_ == 0; }
// Return the ith byte in the referenced data.
// REQUIRES: n < size()
char operator[](size_t n) const {
assert(n < size());
return data_[n];
}
// Change this slice to refer to an empty array
void clear() { data_ = ""; size_ = 0; }
// Drop the first "n" bytes from this slice.
void remove_prefix(size_t n) {
assert(n <= size());
data_ += n;
size_ -= n;
}
// Return a string that contains the copy of the referenced data.
std::string ToString() const { return std::string(data_, size_); }
// Three-way comparison. Returns value:
// < 0 iff "*this" < "b",
// == 0 iff "*this" == "b",
// > 0 iff "*this" > "b"
int compare(const Slice& b) const;
// Return true iff "x" is a prefix of "*this"
bool starts_with(const Slice& x) const {
return ((size_ >= x.size_) &&
(memcmp(data_, x.data_, x.size_) == 0));
}
inline bool operator==(const Slice& x, const Slice& y) {
return ((x.size() == y.size()) &&
(memcmp(x.data(), y.data(), x.size()) == 0));
}
//这里需要注意，为什么 != 进行操作符重载的时候，使用的是 return !(x == y),
//因为在上面已经写过 == 操作符重载了
inline bool operator!=(const Slice& x, const Slice& y) {
return !(x == y);
}
inline int Slice::compare(const Slice& b) const {
const size_t min_len = (size_ < b.size_) ? size_ : b.size_;
int r = memcmp(data_, b.data_, min_len);
if (r == 0) {
if (size_ < b.size_) r = -1;
else if (size_ > b.size_) r = +1;
}
return r;
}
通过分析成员函数的签名可以看出，其中有返回值的函数返回值类型都是constant。这就表明我们并不能修改 Slice数据结构的值，我们只能读而不能写。 如果我们想进行写操作的话，可以使用 ToString()构建一个临时的string对象，然后再转换为 Slice对象。但是我觉得这种过于繁琐，一定会有更简单的方式。