string·模拟实现

自学网站

推荐给老铁们两款学习网站：
面试利器&算法学习：牛客网
风趣幽默的学人工智能：人工智能学习
首个付费专栏：《C++入门核心技术》

下面我们模拟实现 string

string 面试题

面试官: 给你十分钟, 在只考虑资源管理深浅拷贝, 不考虑增删查改的情况下, 模拟实现string.
乍一听, 好像很难的样子, 其实非也, 简直就是送分题, 不信你看:

#include
#include
#include

class string
{
public:
    //构造函数
    string(const char* str = " ")
    {
        if(str == nullptr)
        {
            assert(str);
            return;
        }
        _str = new char[strlen(str) + 1];
        strcpy(_str, str);
    }

    //析构函数
    ~string()
    {
        if(_str)
        {
            delete[] _str;
            _str = nullptr;
        }
    }

    //拷贝构造
    //过时写法
    // string(const string& s)
    //     :_str(new char[strlen(s._str) + 1])
    // {
    //     strcpy(_str, s._str);
    // }

    //现代写法
    void swap(string& s)
    {
        std::swap(_str, s._str);
    }
	//string s2(s1);
    string(const string& s)
        :_str(nullptr)
    {
        string tmp(s._str);
        swap(tmp);
    }

    //赋值重载
    //过时写法
    // string& operator=(const string& s)
    // {
    //     if(this != &s)
    //     {
    //         char* tmp = new char[strlen(s._str) + 1];
    //         strcpy(tmp, _str);
    //         delete[] _str;
    //         _str = tmp;
    //     }
    //     return *this;
    // }

    //现代写法
    //s1 = s2;
    string& operator=(string s/*传值过来就是拷贝构造*/)
    {
        swap(s);
        return *this;
    }

private:
    char* _str;
};
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

深浅拷贝问题

我们看到, 上面我们是自己实现拷贝构造和赋值重载函数的, 因为涉及到资源管理, 所以需要我们显示实现成深拷贝, 如果我们没有显示实现成深拷贝, 而是采用编译器默认生成的拷贝构造和赋值重载函数, 那么执行下面代码时会有问题:

string s1("hello string");
string s2(s1);//用s2拷贝构造s1
1
2

当编译器采用默认生成的拷贝构造时会导致s1和s2共用同一块空间, 在释放时同一块空间会被释放两次,导致程序崩溃, 这种拷贝方式称为浅拷贝.
浅拷贝的问题:

• 同一块空间会析构两次;
• 其中一个修改数据也会影响另外一个(共用同一块空间)

浅拷贝

浅拷贝, 也称值拷贝, 编译器只是将对象中的值拷贝过来. 如果对象中管理资源, 最后就会导致多个对象共用同一份资源, 当其中一个对象销毁时该资源就被释放掉了, 而此时另一些对象不知道该资源已经被释放, 以为还有效, 当继续对该资源进行操作时, 就会发生违规访问. 所以要解决浅拷贝问题, C++特意引入了深拷贝.

深拷贝

如果一个类中涉及资源的管理, 其拷贝构造函数, 赋值运算符重载以及析构函数必须要显示给出, 一般都是按照深拷贝方式实现.

模拟实现

好的, 那下面我们快来看看C++官方库中是怎么来实现string的, 我们自己来模拟实现一下:
首先实现string的构造, 析构, 拷贝构造, 赋值重载:

namespace sl
{
    class string
    {
    public:

        //构造函数
        string(const char* str = " ")
            :_size(strlen(str))
            ,_capacity(_size)
        {
            _str = new char[_capacity + 1];//+1是因为始终要为'\0'多开一个空间
            strcpy(_str, str);
        }

        //析构函数
        ~string()
        {
            if(_str)
            {
                delete[] _str;
                _str = nullptr;
                _size = _capacity = 0;
            }
        }

        void swap(string& s)
        {
            std::swap(_str, s._str);
            std::swap(_size, s._size);
            std::swap(_capacity, s._capacity);
        }

        //拷贝构造
        string(const string& s)
            :_str(nullptr)
            ,_size(0)
            ,_capacity(0)
        {
            string tmp(s._str);
            swap(tmp);
        }

        //赋值重载
        string& operator=(string s)
        {
            swap(s);
            return *this;
        }

    private:
        char* _str;
        size_t _size;//有效字符的个数
        size_t _capacity;//实际存储有效字符的空间
    };
}
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

下面再看对空间的管理:

namespace sl
{
    class string
    {
    public:
 				......
 				
        size_t size()const
        {
            return _size;
        }

        size_t capacity()const
        {
            return _capacity;
        }

        void reserve(size_t n)
        {
            if(n > capacity())
            {
                char* tmp = new char[n + 1];
                strcpy(tmp, _str);
                delete[] _str;
                _str = tmp;

                _capacity = n;
            }
        }
		
		//分三种情况考虑
        void resize(size_t n, char ch = '\0')
        {
            if(n < _size)
            {
                _size = n;
                _str[_size] = ch;
            }
            else
            {
                if(n > _capacity)
                {
                    reserve(n);
                }
                for(size_t i = _size; i < n; i++)
                {
                    _str[i] = ch;
                }
                _size = n;
                _str[_size] = '\0';
            }
        }

    private:
        char* _str;
        size_t _size;
        size_t _capacity;
    };
}
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

上面的接口都挺简单的,我们在这里就不做过多阐述了, 关于resize() 需要画图去理解哦, 一共有三种情况.

OK, 下面我们来看看插入删除的接口:

void push_back(char ch)
{
    if (_size == _capacity)
    {
        reserve(_capacity == 0 ? 4 : _capacity * 2);
    }

    _str[_size] = ch;
    _size++;
    _str[_size] = '\0'; // string与顺序表不同, 要单独处理末尾的'\0'
}

string &operator+=(char ch)
{
    push_back(ch);
    return *this;
}

//注意追加一个字符串不同于追加一个字符, 需要小心处理
void append(const char *str)
{
    size_t len = _size + strlen(str);
    if (len > _capacity)
    {
        reserve(len);
    }
    strcpy(_str + _size, str);
    _size = len;
}

string &operator+=(const char *str)
{
    append(str);
    return *this;
}

const char *c_str() const
{
    return _str;
}

//随机插入
string &insert(size_t pos, char ch)
{
    assert(pos <= _size);

    if (_size == _capacity)
        reserve(_capacity == 0 ? 4 : _capacity * 2);

    size_t end = _size + 1; //注意, 遇到size_t时处理起来要格外小心
    while (end > pos)
    {
        _str[end] = _str[end - 1];
        end--;
    }
    _str[pos] = ch;
    _size++;

    return *this;
}

//随机插入
string &insert(size_t pos, const char *str)
{
    assert(pos <= _size);

    size_t len = strlen(str);
    if (_size + len > _capacity)
    {
        reserve(_size + len);
    }

    //往后挪 len 个位置
    //注意这个过程较复杂需要画图理解
    size_t end = _size + len;
    while (end > pos + len - 1) //注意这个循环条件
    {
        _str[end] = _str[end - len];
        end--;
    }
    strncpy(_str + pos, str, len); // strcpy()会拷贝'\0'
    _size += len;

    return *this;
}

//随机删除
string &erase(size_t pos, size_t len = std::string::npos) //注意哦
{
    assert(pos < _size);

    if (len == std::string::npos || len + pos >= _size)
    {
        _str[pos] = '\0';
        _size = pos;
    }
    else
    {
        size_t begin = pos + len;
        while (begin <= _size) //注意判断循环条件
        {
            _str[begin - len] = _str[begin];
            begin++;
        }
        _size -= len;
    }
    return *this;
}
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

其实我们之前有认真实现常见的数据结构会发现这个真的不难, 对于insert() 和 erase() 接口如果不理解需要自己动手画图哦.

迭代器

下面我们谈谈迭代器部分:
迭代器可以认为就是指针或者是像指针一样的东西, 具体看容器底层的实现.

namespace sl
{
    class string
    {
    public:
				.......
				
        typedef char *iterator;
        typedef const char *const_iterator;

        iterator begin()
        {
            return _str;
        }

        iterator end()
        {
            return _str + _size;
        }

        const_iterator begin() const
        {
            return _str;
        }

        const_iterator end() const
        {
            return _str + _size;
        }

    private:
        char *_str;
        size_t _size;
        size_t _capacity;
    };
}
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

流插入和流提取接口:

//流插入
//不需要设计成友元函数, 因为没有访问私有成员
ostream &operator<<(ostream &out, const string &s)
{
    for (auto& e : s)
    {
        out << e;
    }
    return out;
}

//流提取
// istream& operator>>(istream& in, string& s)
// {
//     char ch;
//     //in >> ch;//注意cin不能读取到空格和换行
//     ch = in.get();//get()便是从流中提取字符
//     while(ch != ' ' && ch != '\n')
//     {
//         s += ch;
//         ch = in.get();
//     }

//     return in;
// }

//上面实现的流提取不够高效, 原因在于会频繁插入数据导致经常扩容影响效率
//优化
//流提取
istream &operator>>(istream &in, string &s)
{
    s.clear(); //将数据全部清理掉

    char ch;
    ch = in.get();
    char buff[128] = {'\0'};
    size_t i = 0;
    while(ch != '\n')
    {
        buff[i++] = ch;
        if(i == 127)
        {
            s += buff;
            memset(buff, '\0', 128);
            i = 0;
        }
        ch = in.get();
    }
    s += buff;
    
    return in;
}
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

其他一些接口:

namespace sl
{
    class string
    {
    public:
        	......

        void clear()
        {
            _str[0] = '\0';
            _size = 0;//不必释放空间
        }

        const char* c_str()const
        {
            return _str;
        }

        size_t find(const char* str, size_t pos = 0)const
        {
            const char* p = strstr(_str + pos, str);
            if(p == nullptr)
                return std::string::npos;
            else
                return p - _str;
        }

    private:
        char *_str;
        size_t _size;
        size_t _capacity;
    };
}
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