關(guān)于寫時(shí)復(fù)制(COW)

yuxh

大部份的STL在實(shí)現(xiàn)string時(shí)，都采用COW來保證其高效性。即多個(gè)類會(huì)共用一個(gè)數(shù)據(jù)緩沖區(qū)(buffer)，在拷貝構(gòu)造、賦值等操作時(shí)，并不會(huì)對(duì)buffer進(jìn)行復(fù)制。僅在需要對(duì)buffer進(jìn)行修改，而且此buffer已與別的類共享了，才會(huì)開辟空間，將buffer復(fù)制一份進(jìn)行修改。同樣在析構(gòu)時(shí)，如果buffer與與別的類共享，也不會(huì)釋放空間。
舉個(gè)例子：

1. #include <stdio.h>
   
2. #include <string>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.     string test1 = "hello";
   
8.     string test2(test1);
   
9. 
   
10.     printf("test1:%p test2:%p\n", test1.c_str(), test2.c_str());
    
11. }
    

復(fù)制代碼

運(yùn)行結(jié)果：

test1:0x90a9014 test2:0x90a9014

可見兩個(gè)地址是相等的，它們共用了同一個(gè)緩沖區(qū)。
什么時(shí)候會(huì)引起數(shù)據(jù)區(qū)的復(fù)制？當(dāng)然是要修改string的值的時(shí)候

1. #include <stdio.h>
   
2. #include <string>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.     string test1 = "hello";
   
8.     string test2(test1);
   
9. 
   
10.     printf("test1:%p test2:%p\n", test1.c_str(), test2.c_str());
    
11.     test2[0] = 'w';
    
12.     printf("test1:%p test2:%p\n", test1.c_str(), test2.c_str());
    
13. }

復(fù)制代碼

運(yùn)行結(jié)果：

test1:0x9e85014 test2:0x9e85014
test1:0x9e85014 test2:0x9e8502c

可以看到test2發(fā)生了變化。
再進(jìn)一步，編譯如何確定程序要對(duì)buffer進(jìn)行修改，從而去開辟新的空間呢？
程序一般是通過[]運(yùn)算符、iterator去訪問并修改數(shù)據(jù)。很自然地認(rèn)為，對(duì)于左值會(huì)引起數(shù)據(jù)復(fù)制，而右值不會(huì)。但實(shí)際上，編譯沒這么做�？赡苁亲笾祷蛴抑档呐卸ú�沒有那么簡(jiǎn)單吧？

1. #include <stdio.h>
   
2. #include <string>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.     string test1 = "hello";
   
8.     string test2(test1);
   
9. 
   
10.     printf("test1:%p   test2:%p\n", test1.c_str(), test2.c_str());
    
11.      printf("test1:%p   test2:%p\n", &test1[0], &test2[0]);
    
12. }

復(fù)制代碼

運(yùn)行結(jié)果：

test1:0x8a4a014   test2:0x8a4a014
test1:0x8a4a014   test2:0x8a4a02c

test2發(fā)生了變化。
看一下源碼：

1.       const_reference
   
2.       operator[] (size_type __pos) const
   
3.       {
   
4.         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
   
5.         return _M_data()[__pos];
   
6.       }
   
7. 
   
8.       reference
   
9.       operator[](size_type __pos)
   
10.       {
    
11.         _GLIBCXX_DEBUG_ASSERT(__pos < size());
    
12.         _M_leak();
    
13.         return _M_data()[__pos];
    
14.       }
    

復(fù)制代碼

也就是說判定是否可能有寫操作是與類的類型相關(guān)的，如果是const string，則不復(fù)制，如果是string，則一定復(fù)制
再看看這個(gè)：

1. #include <stdio.h>
   
2. #include <string>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.     string test1 = "hello";
   
8.     string test2(test1);
   
9. 
   
10.     printf("test1:%p test2:%p\n", test1.c_str(), test2.c_str());
    
11.     const string &test3 = test1;
    
12.     const string &test4 = test2;
    
13.     printf("test1:%p test2:%p\n", &test3[0], &test4[0]);
    
14. }
    

復(fù)制代碼

結(jié)果就是：

test1:0x8c62014  test2:0x8c62014
test1:0x8c62014  test2:0x8c62014

當(dāng)然這樣寫很難受，憑什么要搞兩個(gè)const的引用出來�。�
這樣就比較自然：

1. #include <stdio.h>
   
2. #include <string>
   
3. using namespace std;
   
4. 
   
5. void proc(const string& test1, const string& test2)
   
6. {
   
7.     printf("test1:%p test2:%p\n", &test1[0], &test2[0]);
   
8. }
   
9. 
   
10. int main()
    
11. {
    
12.     string test1 = "hello";
    
13.     string test2(test1);
    
14. 
    
15.     printf("test1:%p test2:%p\n", test1.c_str(), test2.c_str());
    
16.     proc(test1, test2);
    
17. }
    

復(fù)制代碼

也是說一定要嚴(yán)格地確定數(shù)據(jù)類型是否是const的，如果函數(shù)里不修改修，則傳const，良好的習(xí)慣有利于代碼質(zhì)量的提高。
string和char *是無法共享數(shù)據(jù)區(qū)的，所以用c++就盡量少用指針，兩種風(fēng)格合在一起，效率是最低的。

[ 本帖最后由 yuxh 于 2006-9-26 15:45 編輯 ]

yuxh

年紀(jì)越來越老，是不是越來越啰嗦了呢？
但一般對(duì)于vector或者list是沒有COW的，要拷貝就全拷。
但可以自己封裝，隨便寫了一個(gè)，還不是很完善：

1. #ifndef _COW_CONTAINER_
   
2. #define _COW_CONTAINER_ 1
   
3. 
   
4. #include <vector>
   
5. #include <list>
   
6. using namespace std;
   
7. 
   
8. template<typename _Tp>
   
9. class cow_container
   
10. {
    
11. public:
    
12.   typedef typename _Tp::value_type value_type;
    
13.   typedef typename _Tp::reference reference;
    
14.   typedef typename _Tp::const_reference const_reference;
    
15.   typedef typename _Tp::iterator iterator;
    
16.   typedef typename _Tp::const_iterator const_iterator;
    
17.   cow_container()
    
18.   {
    
19.     m_pCowNode = new cow_node;
    
20.     m_pCowNode->m_refCount = 0;
    
21.   }
    
22.   cow_container(const cow_container& __cc)
    
23.   {
    
24.     m_pCowNode = __cc.m_pCowNode;
    
25.     m_pCowNode->m_refCount++;
    
26.   }
    
27.   cow_container(const_iterator _begin, const_iterator _end)
    
28.   {
    
29.     m_pCowNode = new cow_node;
    
30.     m_pCowNode->m_refCount = 0;
    
31.     const_iterator itr;
    
32.     for(itr = _begin(); itr != _end; ++itr) {
    
33.       m_pCowNode->m_data.push_back(*itr);
    
34.     }
    
35.   }
    
36.   cow_container(const_iterator _begin, size_t _n)
    
37.   {
    
38.     m_pCowNode = new cow_node;
    
39.     m_pCowNode->m_refCount = 0;
    
40.     const_iterator itr;
    
41.     for(itr = _begin(); itr < _begin + _n; ++itr) {
    
42.       m_pCowNode->m_data.push_back(*itr);
    
43.     }
    
44.   }
    
45.   cow_container(const _Tp& __cc)
    
46.   {
    
47.     m_pCowNode = new cow_node;
    
48.     m_pCowNode->m_refCount = 0;
    
49.     m_pCowNode->m_data = __cc;
    
50.   }
    
51.   ~cow_container()
    
52.   {
    
53.     if(m_pCowNode->m_refCount == 0)
    
54.       delete m_pCowNode;
    
55.     else
    
56.       m_pCowNode->m_refCount--;
    
57.   }
    
58.   cow_container &operator=(const cow_container& __cc)
    
59.   {
    
60.     if(m_pCowNode != __cc.m_pCowNode) {
    
61.       if(m_pCowNode->m_refCount == 0)
    
62.         delete m_pCowNode;
    
63.       else
    
64.         m_pCowNode->m_refCount--;
    
65.       m_pCowNode = __cc.m_pCowNode;
    
66.       m_pCowNode->m_refCount++;
    
67.     }
    
68.     return *this;
    
69.   }
    
70.   cow_container &operator=(const _Tp& __cc)
    
71.   {
    
72.     if(m_pCowNode != __cc.m_pCowNode) {
    
73.       if(m_pCowNode->m_refCount == 0)
    
74.         delete m_pCowNode;
    
75.       else
    
76.         m_pCowNode->m_refCount--;
    
77.       m_pCowNode = new cow_node;
    
78.       m_pCowNode->m_refCount = 0;
    
79.       m_pCowNode->m_data = __cc;
    
80.     }
    
81.     return *this;
    
82.   }
    
83.   const_iterator begin() const
    
84.   {
    
85.     return m_pCowNode->m_data.begin();
    
86.   }
    
87.   const_iterator end() const
    
88.   {
    
89.     return m_pCowNode->m_data.end();
    
90.   }
    
91.   iterator begin()
    
92.   {
    
93.     do_copy();
    
94.     return m_pCowNode->m_data.begin();
    
95.   }
    
96.   iterator end()
    
97.   {
    
98.     do_copy();
    
99.     return m_pCowNode->m_data.end();
    
100.   }
     
101.   const_reference operator[](int _n) const
     
102.   {
     
103.     return m_pCowNode->m_data[_n];
     
104.   }
     
105.   reference operator[](int _n)
     
106.   {
     
107.     do_copy();
     
108.     return m_pCowNode->m_data[_n];
     
109.   }
     
110.   void push_back(const value_type& _val)
     
111.   {
     
112.     do_copy();
     
113.     m_pCowNode->m_data.push_back(_val);
     
114.   }
     
115.   iterator insert(iterator __position, const value_type& __x)
     
116.   {
     
117.     do_copy();
     
118.     m_pCowNode->m_data.insert(__position, __x);
     
119.   }
     
120. 
     
121.   const _Tp& container() const
     
122.   {
     
123.     return m_pCowNode->m_data;
     
124.   }
     
125. private:
     
126.   struct cow_node
     
127.   {
     
128.     int          m_refCount;
     
129.     _Tp          m_data;
     
130.   };
     
131.   cow_node     *m_pCowNode;
     
132. 
     
133.   void do_copy()
     
134.   {
     
135.     if(m_pCowNode->m_refCount > 0) {
     
136.       const _Tp &bak = m_pCowNode->m_data;
     
137.       m_pCowNode->m_refCount--;
     
138.       m_pCowNode = new cow_node;
     
139.       m_pCowNode->m_refCount = 0;
     
140.       m_pCowNode->m_data = bak;
     
141.     }
     
142.   }
     
143. };
     
144. 
     
145. template<class _Tp>
     
146. class VECTOR:public cow_container< vector<_Tp> > { };
     
147. 
     
148. template<class _Tp>
     
149. class LIST:public cow_container< list<_Tp> > { };
     
150. 
     
151. #endif
     

復(fù)制代碼

[ 本帖最后由 yuxh 于 2006-9-26 15:48 編輯 ]

Alligator27

我的直覺string是靠RefCount來判斷是否COW, 看來得在查查.

醉臥水云間

樓主總能給我們帶來驚喜，感謝。