Shulou(Shulou.com)06/02 Report--

The editor will share with you an example analysis of the underlying framework of C++string. I hope you will gain something after reading this article. Let's discuss it together.

I. Preface

This paper mainly explains the advantages and disadvantages of shallow copy and deep copy, as well as the logic of imitating string class and analyzing the implementation process.

2. Advantages and disadvantages of shallow copy and deep copy. Shallow copy

Let's start with the last set of codes.

Class string {public: string (char* str= "): _ size (strlen (str)), _ capacity (_ size) {_ str= new char [_ capacity+1]; strcpy (_ str, str);} char& operator [] (const char& pos) const {return _ strpos] } ~ string () {delete [] _ str; _ str = nullptr; _ size = _ capacity = 0;} private: char* _ str; size_t _ size; size_t _ capacity;}; void Test1 () {string S1 ("never gonna give you up"); string S2 = S1; S2 [0] = 'Yothers;}

When we copy S1 to S2, is it a deep copy or a shallow copy? Leaving aside the answer, let's debug take a look at it.

At a glance, S1 and S2 here are the same address.

So when we change the value of S2 [0], S1 [0] also changes, so it still gives people the feeling that there is no complete independent copy. This is the shallow copy. I believe we have also seen the disadvantages of the shallow copy.

Second, there will be problems when we call the destructor. Since they point to the same space, S2 will first destruct the array delete and empty it.

Then S1 will report an error when it calls the destructor, so it cannot point to the same space.

Summarize the shallow copy problem:

This space will affect the other object when the destructor of two objects is modified by delete twice.

two。 Deep copy

How to achieve deep copy?

String (const string& s) / / function overload: _ str (new char [strlen (s._str) + 1]) {strcpy (this- > _ str, s._str);}

We re-new a space for S2. The following figure shows that S1 and S2 are no longer the same space on the heap.

The first parameter here is that this is anonymous. For the sake of aspect, I added this.

The difference between the shallow copy and the shallow copy is that it indicates that the current string needs to be reassigned and reassigned to the newly opened set of new space, so the deep copy here will not have the above problem. When we change the value of S2 [0], S1 [0] will not change accordingly.

The way of assignment overloading to solve the problem of shallow copy

String& operator= (string& s) {if (this! = & s) {char* tmp = new char [strlen (s._str) + 1]; delete [] _ str; / / Delete the original content of this _ str = tmp; / / assign new space to _ str strcpy (_ str, s._str); _ size = _ capacity = strlen (s._str); _ str [_ size] ='\ 0' } return * this;} 3. Deep copy modern version

The above are all traditional writing methods, opening up a new set of heap space through new, which is different from the modern writing method.

Here is to reconstruct a temporary string tmp variable to open a new set of spaces, and then swap to exchange the two, equal to this- > _ str to get the new space, and finally automatically destruct the unneeded space.

String (const string& str): _ str (nullptr) {string tmp (str); swap (_ str, tmp._str);} / / this group does not use references, because the parameter automatically invokes the copy construction string& operator= (string t) {swap (_ string t) {return * this;} 4. Copy while writing

So does a deep copy have to be the best?

The answer is not necessarily. The copy when writing adds a reference counting method to the shallow copy, in other words, how many objects point to this space, the count will be + +, then only when an object writes data, that object will be deeply copied, and then count-

This is essentially a delayed deep copy when writing, but if no one modifies it after copying the object and does not make a deep copy to reopen a piece of space, it will naturally improve efficiency. But in the practical application scenario, it is not ideal.

Third, string framework building 1. Frame definition

Here, the private member structure is like a sequence table. When we add or delete data, we need to record the current information and whether we need to expand the capacity. Npos is used to find out whether there is this character. Default returns-1.

Class string {public: private: char* _ str; size_t _ size; size_t _ capacity; static const size_t npos;}; const size_t string::npos =-1 position 2. Constructor void Test2 () {string S1 ("helloworld"); string S2 (5,'g'); string ();}

The above function names all constitute function overloading, and currently implement three common

String (const char* str= "): _ size (strlen (str)), _ capacity (_ size) {_ str= new char [_ capacity+1]; strcpy (_ str, str);}

The first is the most common, which simply assigns the string to S1

String (size_t n, char c): _ size (n), _ capacity (_ size) {_ str = new char [_ size + 1]; for (size_t iS2? / / "abc", "abc" false// "abc", "ab" true// "ab", "abc" falsebool operator > (const string& S1, const string& S2) {size_t i1 = 0, i2 = 0; while (i1)

< s1.size() && i2 < s2.size()){ if(s1[i1] >

S2 [i2]) {return true;} else if (S1 [i1]

< s2[i2]){ return false; }else{ ++i1; ++i2; } } if(i1 == s1.size()){ return false; }else{ return true; } return true;}bool operator==(const string& s1, const string& s2){ size_t i1 = 0, i2 =0; while(i1 < s1.size() && i2 < s2.size()){ if(s1[i1] >

S2 [i2]) {return true;} else if (S1 [i1]

< s2[i2]){ return false; }else{ ++i1; ++i2; } } if(i1 == s1.size() && i2 == s2.size()){ return true; }else{ return false; }}bool operator!=(const string& s1, const string& s2){ return !(s1==s2);}bool operator>

= (const string& S1, const string& S2) {return (S1 > S2 | | s1==s2);} bool operator= S2);} bool operators2);} String operator+ (const string& S1, const string& str) {String ret = S1; ret + = str; return ret;} 5. Achieve capacity expansion

Resize is divided into three situations.

When n is less than or equal to size, then size is equal to n

Data cannot be added when n is greater than size but less than capacity

When n is greater than capacity, increase the capacity first, and then fill in the data from size to n

Void reserve (size_t n) {if (n > _ capacity) {char* tmp = new char [nyst1]; / / Open a larger space strcpy (tmp, _ str); / / copy, and then release the space delete [] _ str; _ str = tmp; / / and point to the newly opened space} _ capacity = n } void resize (size_t n, char ch='\ 0') {/ / greater than, less than, or equal to if (n _ capacity) {/ / is not enough space, first increase the capacity of reserve (n); for (size_t I = _ size) (I = _ capacity) {/ / if both size and capacity are 0, then the calculated twice w is also 0, and an error / / reserve (_ capacity*2) is reported when destructing is called at last; size_t newCapacity = _ capacity = = 0? 4: _ capacity*2; reserve (newCapacity);} _ str [_ size] = c; + _ size; _ str [_ size] ='\ 0values;}

Add a string of characters at the end of the string. Here you need to judge whether the original capacity is smaller than the newly added string capacity. If so, you need a new reserve with more space.

Void append (const char* s) {size_t len = strlen (s); if (_ size + len > = _ capacity) {reserve (_ size + len);} strcpy (_ str + _ size, s); / / copy this string to the past _ size + = len;}

In the pos position, insert characters or strings, which are not recommended in our practical applications, because when the array data is too large, the data behind the pos needs to be moved backward after the middle insertion.

String& insert (size_t pos, char ch) {assert (pos _ size) {_ strend-1] = _ strend];-- end;} _ str [_ size] = ch; + + _ size; return * this;} string& insert (size_t pos, const char* str) {assert (pos _ capacity) {reserve (len + _ size);} size_t end = _ size + len While (end > = pos + len) {_ stre [end] = _ stre [end-len];-- end;} for (size_t I = 0; I = _ size) {_ stro [pos] ='\ 0size; _ size = pos;} else {/ / delete part of strcpy (_ str + pos, _ str + pos + len); _ size-= len } return * this;} 8. Data search

Find the first character that matches and return its subscript

/ / search, and directly return the character's subscript position size_t find (char ch, size_t pos=0) {for (size_t I = pos; I > S1; / / cout)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.