220
C++麵試中string類的一種正確寫法
C++ 的一個常見麵試題是讓你實現一個 String 類，限於時間，不可能要求具備 std::string 的功能，但至少要求能正確管理資源。具體來說：
- 能像 int 類型那樣定義變量，並且支持賦值、複製。
- 能用作函數的參數類型及返回類型。
- 能用作標準庫容器的元素類型，即 vector/list/deque 的 value_type。（用作 std::map 的 key_type 是更進一步的要求，本文從略）。
換言之，你的 String 能讓以下代碼編譯運行通過，並且沒有內存方麵的錯誤。
|
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
|
void
foo(String x)
{}void
bar(const
String& x)
{}String baz(){ String ret("world");
return
ret;
}int
main()
{ String s0;
String s1("hello");
String s2(s0);
String s3 = s1;
s2 = s1;
foo(s1);
bar(s1);
foo("temporary");
bar("temporary");
String s4 = baz();
std::vector<String> svec;
svec.push_back(s0);
svec.push_back(s1);
svec.push_back(baz());
svec.push_back("good job");
} |
本文給出我認為適合麵試的答案，強調正確性及易實現（白板上寫也不會錯），不強調效率。某種意義上可以說是以時間（運行快慢）換空間（代碼簡潔）。
首先選擇數據成員，最簡單的 String 隻有一個 char* 成員變量。好處是容易實現，壞處是某些操作的複雜度較高（例如 size() 會是線性時間）。為了麵試時寫代碼不出錯，本文設計的 String 隻有一個 char* data_成員。而且規定 invariant 如下：一個 valid 的 string 對象的 data_ 保證不為 NULL，data_ 以 '\0' 結尾，以方便配合 C 語言的 str*() 係列函數。
其次決定支持哪些操作，構造、析構、拷貝構造、賦值這幾樣是肯定要有的（以前合稱 big three，現在叫 copy control）。如果鑽得深一點，C++11的移動構造和移動賦值也可以有。為了突出重點，本文就不考慮 operator[] 之類的重載了。
這樣代碼基本上就定型了：
|
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#include <utility>#include <string.h>class
String
{ public:
String()
: data_(new
char[1])
{
*data_ =
'\0';
}
String(const
char* str)
: data_(new
char[strlen(str) + 1])
{
strcpy(data_, str);
}
String(const
String& rhs)
: data_(new
char[rhs.size() + 1])
{
strcpy(data_, rhs.c_str());
}
/* Delegate constructor in C++11
String(const String& rhs)
: String(rhs.data_)
{
}
*/
~String()
{
delete[] data_;
}
/* Traditional:
String& operator=(const String& rhs)
{
String tmp(rhs);
swap(tmp);
return *this;
}
*/
String& operator=(String rhs)
// yes, pass-by-value
{
swap(rhs);
return
*this;
}
// C++ 11
String(String&& rhs)
: data_(rhs.data_)
{
rhs.data_ =
nullptr;
}
String& operator=(String&& rhs)
{
swap(rhs);
return
*this;
}
// Accessors
size_t
size() const
{
return
strlen(data_);
}
const
char* c_str()
const
{
return
data_;
}
void
swap(String& rhs)
{
std::swap(data_, rhs.data_);
}
private:
char* data_;
}; |
注意代碼的幾個要點：
- 隻在構造函數裏調用 new char[]，隻在析構函數裏調用 delete[]。
- 賦值操作符采用了《C++編程規範》推薦的現代寫法。
- 每個函數都隻有一兩行代碼，沒有條件判斷。
- 析構函數不必檢查 data_ 是否為 NULL。
- 構造函數
String(const char* str)沒有檢查 str 的合法性，這是一個永無止境的爭論話題。這裏在初始化列表裏就用到了 str，因此在函數體內用 assert() 是無意義的。
這恐怕是最簡潔的 String 實現了。
練習1：增加 operator==、operator<、operator[] 等操作符重載。
練習2：實現一個帶 int size_; 成員的版本，以空間換時間。
練習3：受益於右值引用及移動語意，在 C++11 中對 String 實施直接插入排序的性能比C++98/03要高，試編程驗證之。（g++的標準庫也用到了此技術。）
最後更新：2017-04-03 12:56:30