【C++】STL之String模拟实现

🔺参数

private:
		char* _str;
		size_t _size;
		size_t _capacity;
		const static size_t npos = -1;
1
2
3
4
5

---

_str

用来存储string对象中字符串，是一个char*的指针； 同时，有一个函数可以用来返回该字符串：

const char* My_string::string::c_str()const
{
	return _str;
}
1
2
3
4

由于返回的字符串不能被改动，应在返回值中加入const修饰，同时为了避免函数在调用过程中可能通过其他方式对函数内的this指针进行改动应对this进行const修饰；

---

_size

用来存储字符串中的有效个数，该有效个数不包括'\0' 返回该参数的函数：

 size_t My_string::string::size()const
{
	 return _size;
}
1
2
3
4

同理，该函数在函数内并不对数据进行改动，应给this指针加上const修饰；
且由于该参数不可能出现负数情况，所以该参数的类型为size_t;

---

_capacity

该参数用来计算该string对象中还有几个有效位置，该有效位置并不包括'\0'的位置 返回该参数的函数：

 size_t My_string::string::capacity()const 
{
	return _capacity;
}
1
2
3
4

同理；

---

npos

该参数作为string对象中比较特殊的对象，该参数的类型为const static size_t 类型，值为-1；

故该值的大小为整形的最大值；

---

---

🔺构造函数

构造函数作为对象中一个比较重要的成员函数，其中构造函数包括拷贝构造函数；
构造函数是用来对对象进行初始化的函数，同时构造函数也是一个默认成员函数（若是没有显式声明编译器会自动生成一个无参的该成员函数称之为默认成员函数）；

在C++ 98中，构造函数共有7个重载，其中两个为：

• string (const char* s); 以字符串s来构造一个string对象>
• string(); 构造一个空对象

而在实现当中，可以利用缺省值来完成两个重载的整合；

string(const char* s = "");
1

若是传入了字符串则以字符串 s 进行构造，若是没有则传入缺省值"" 空字符串；
实现的思路为，使用初始化列表对_size与_capacity进行初始化，这里的初始化值为有效值，即不包括’\0’；
同时使用 new 来申请一块相应的空间，该空间的大小为有效值+1(多出来的一位用来存放无效数据’\0’)；

My_string::string::string(const char*s)//"123456789"
	:_size(strlen(s))
	,_capacity(_size)
{
	_str = new char[_size + 1];//多开一个空间用于存放'\0'
	strcpy(_str, s);
}
1
2
3
4
5
6
7

这里若是不传参的话则会传入一个缺省值(空字符串)，若是这样的话_capacity参数也一样为0，应该在后期的插入函数的扩容进行处理；

在这里引申一个概念叫做默认构造函数，无参或者全缺省的构造函数被称为默认构造函数；

---

拷贝构造

拷贝构造函数在某些意义上属于构造函数，但唯独不同的是拷贝构造函数是将该string对象拷贝为传入的string对象参数；
同时拷贝对象函数也是一个默认成员函数，若是其不显式声明则会生成一个拷贝构造函数；
这个默认生成的拷贝构造函数特点是，对内置类型进行浅拷贝（值拷贝），对内置类型则会去调用它的拷贝构造函数；

string(const string& str);//拷贝
1

在某种意义上来说，拷贝构造函数实际上是构造函数的一个重载形式；
该拷贝构造函数的思路为，因为对于内置类型将会去进行值拷贝，而再该对象中的参数都为内置类型；
_size参数与_capacity参数可以不看，但是对于_str参数而言，是一个指针，若是拷贝构造函数只进行值拷贝的话将会出现两个string对象的_str共用同一块空间；

共用同一块空间的危害若是处理好其实问题不大，但是唯一的问题在于析构部分，在一个对象的生命周期结束时将会去调用它的析构函数，而两个对象的_str指针都指向同一块空间，则会造成对一块空间的重复释放；
点击跳转至析构函数(由于析构函数内需要对开辟的空间进行释放，所以可能会出现重复释放同一块空间)

//拷贝
My_string::string::string(const string& str)
	:_str(new char[str._size+1])
	,_size(str._size)
	,_capacity(str._size)
{
	memcpy(_str, str._str,str._size);
	_str[_size] = '\0';
}
1
2
3
4
5
6
7
8
9

这里的拷贝构造函数传参应该传引用而不应该传值；
若是传值的话则会发生这种情况：
自定义类型在作为参数的时将会生成一个临时对象，而生成这个临时对象将会去调用它的拷贝构造函数；
这里调用拷贝构造函数又会将刚刚的临时对象作为参数进行调用，参数被调用又会调用拷贝构造函数；
周而复始，最终会因为无穷递归而导致栈溢出；

---

🔺析构函数

在string对象中的析构函数应该处理好，因为析构函数也属于一个默认成员函数，这个默认生成的析构函数的特点为，对内置类型不作处理，对自定义类型将会去调用它的析构函数；

~string();//析构
1

//析构
My_string::string::~string() 
{
	delete[]_str;//重点是将这块空间释放
	_size = _capacity = 0;
}
1
2
3
4
5
6

---

---

🔺迭代器

迭代器作为容器中重要的一个部件，经常用于遍历容器中的元素，而迭代器的本质是模拟指针进行访问；

模拟迭代器我们可以直接以指针的形式进行模拟；

而迭代器的类型也有几种，以string为例，迭代器的类型分别为：

1. 正向迭代器：

• iterator (正向迭代器)
• const_iterator (const修饰的正向迭代器)

2. 反向迭代器：

• reverse_iterator (反向迭代器)
• const_reverse_iterator (const修饰的反向迭代器)

实际上这个迭代器类型在某种意义上来说是一个“ char* ”的指针，根据char*的指针可以将容器进行遍历；
所以迭代器的类型可以用typedef进行设置；

	typedef char* iterator;

	typedef const char* const_iterator;
1
2
3

正向迭代器的区间一般为左闭右开区间[ )，即begin()的位置为字符串的首字符，而end()的位置为末尾字符的后一个字符；
反向迭代器则相反，rbegin()的位置为最后一个字符，而rend()所在的位置为第一个字符的前一个字符；

---

begin() && end()

根据上述可知在模拟时只需要返回相应的指针即可；

My_string::iterator My_string::string::begin()
 {
	 return _str;
 }

 My_string::iterator  My_string::string::end()
 {
	 return _str + _size ;
 }

 My_string::const_iterator My_string::string::begin()const
 {
	 return _str;
 }

 My_string::const_iterator My_string::string::end()const
 {
	 return _str + _size ;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

同时，由于begin()与end()函数中都有一个重载，这个重载的意义在于在调用时可以根据所需的情况自动调用；

---

---

🔺扩容函数 reserve

该函数为string中比较核心的一个函数，函数的作用为将当前容量扩到所需要的范围；
同时，该函数也将成为对象扩容的函数；

//扩容
		void reserve(size_t n = 0);
1
2

该函数的作用为，传入一个size_t类型的值，若是这个值比当前的容量大，则进行扩容；
同时这个函数也是一个缺省参数，确保可以无参调用；

该函数的模拟实现的思路即为，判断所给形参是否大于当前的_capacity，若是大于则扩容，若是小于或等于则不做出调整；
根据条件可知只需要用if条件判断是否大于_capacity即可；

 //扩容
 void My_string::string::reserve(size_t n)
 {
	 if (n > _capacity) {
		 char* temp = new char[n+1];//多开1的空间确保n为有效数据的空间而+1为给'\0'的无效空间
		 strcpy(temp, _str);
		 _capacity = n;
		 delete[]_str;
		 _str = temp;
	 }
 }
1
2
3
4
5
6
7
8
9
10
11

若是满足条件则new一块空间，并使用memcpy函数或者strcpy函数将原字符串的内容拷贝至新空间；
拷贝完后释放原空间并将新空间的位置赋值给_str；

---

---

🔺交换函数swap()

在string容器中有一个作为成员函数的swap函数，它的作用为交换两个string对象的内容；
作为成员函数的swap函数与标准库中的swap函数中最本质的区别是，string内的成员函数swap可以直接将两个string对象互换，实际上换的是两个string对象中的指针；
而标准库的swap函数若是要交换两个自定义类型时，则会调用拷贝构造从而导致没必要的开销；

//交换
void swap (string& str);
1
2

void My_string::string::swap(string& str)
 {
	 ::swap(str._str, _str);
	 ::swap(str._size, _size);
	 ::swap(str._capacity, _capacity);
 }
 //这里是调用标准库中的swap函数来交换每个成员变量的数据或者指针；
 //由于调用的是标准库中的swap函数所以需要加上::
 //否则在调用过程中将会先找域中的swap函数而导致调用失败
1
2
3
4
5
6
7
8
9

---

---

🔺判空函数 empty()

该函数的作用为判断该string对象是否为空；
则返回_size参数是否为0即可；

bool empty() const;
1

这里不做实现；

---

---

🔺清除当前字符串内容 clear()

该函数的作用为清空当前string对象中的内容；

		//clear清除函数
		void clear();
1
2

思路为将第一个字符改为’\0’;
同时修改_size参数；

void My_string::string::clear()
 {
	 _size = 0;
	 _str[_size] = '\0';
 }
1
2
3
4
5

---

---

🔺查找函数 find()

该函数的作用为从一个string对象中找到所需的数据，这个数据可能是一个字符，也可能是一个字串；
在C++98中，该函数共有四个重载：

size_t find (const string& str, size_t pos = 0) const;
//从一个string对象的pos位置开始，向后寻找带有string对象str中的字符串子串
//找到则返回该位置的下标，否则返回string::npos
	
size_t find (const char* s, size_t pos = 0) const;
//从一个string对象的pos位置开始，向后找s子串，若是找到则返回下标
//否则返回string::npos

size_t find (const char* s, size_t pos, size_t n) const;
//从一个string对象的pos位置开始向后找s子串的前n个字符，若是找到返回下标
//否则返回string::npos
	
size_t find (char c, size_t pos = 0) const;
//从一个string对象的pos位置开始向后找字符c，若是找到返回下标
//若是没找到则返回npos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

该函数实现两个重载，分别为:

• size_t find (char c, size_t pos = 0) const;

该重载的实现思路为，从pos位置开始遍历至结尾，若是找到则返回下标，否则返回npos;

 size_t My_string::string::find(const char ch, size_t pos)
 {
	 assert(pos < _size);
	 for (; pos < _size; pos++) {
		 if (_str[pos] == ch) {
			 return pos;
		 }
	 }
	 return npos;
 }
1
2
3
4
5
6
7
8
9
10

• size_t find (const char* s, size_t pos = 0) const;

该重载的思路为利用strstr函数，从pos位置开始找，找到返回两个地址之间的偏移量(下标)；
若是调用strstr函数返回为nullptr则代表未找到，返回npos；

 size_t My_string::string::find(const char* sub, size_t pos)
 {
	 char* s = strstr(_str + pos, sub);
	 if (s == nullptr) {
		 return npos;
	 }
	 return s - _str;
 }
1
2
3
4
5
6
7
8

---

---

🔺插入函数

插入函数中的insert函数在我看来是一个比较重要的函数，即使在中间插入或者头插时需要挪动数据使得开销变大，但是不影响push_back函数与append函数对该函数的复用；

---

insert()

该函数的作用为插入；
在C++98中，该函数的重载共有7个；
在此处主要实现其中三个：

1. string& insert(size_t pos, const char*s);

• 在pos位置后插入一个常量字符串；

该重载在实现过程中应该首先注意string 的扩容，若是盲目扩容2倍的话可能会出现，该字符串长度仍比2倍的_capacity要大，还有一种可能为，该字符串的长度只有1，若是已有的_capacity容量已经很大的话仍扩2倍则可能出现内存利用率不高等情况；
在扩容时，应该优先直接扩容该常量字符串的长度+1次(1留给’\0’)；
在扩容成功后控制字符串的下标以达到挪动数据的效果；
最后再使用memcpy函数或者是strncpy函数将这个常量字符串的数据拷贝至_str中（这里使用memcpy与strncpy的原因为，可能存在中间插入，故拷贝时不能+‘\0’）；

My_string::string& My_string::string::insert(size_t pos, const char* s)
 {
	 assert(pos <= _capacity);
	 size_t len = strlen(s);
	 if (_size + len > _capacity) 
	 {
		 reserve(_capacity + len);
	 }

	 size_t _end = _size + len;

	 while (_end > pos+len-1) {
		 _str[_end] = _str[_end - len];
		 _end--;
	 }
	 memcpy(_str + pos, s, len);
	 _size += len;
	 return *this;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2. string& insert(size_t pos, const string& str);

• 在pos位置后插入一个string对象(该函数可以直接复用第一个insert重载)

该函数可以直接复用第一个重载，参数的话则给该string对象str的_str即可；

 My_string::string& My_string::string::insert(size_t pos, const string& str)
 {
	 insert(pos, str.c_str());
	 return *this;
 }
1
2
3
4
5

3. iterator insert(iterator p,char c);

• 在迭代器p的位置插入一个字符c；

该重载的实现较上面两个重载的实现较难，原本的思路应该是一样的使用迭代器，在扩容后遍历；
但是这里出现了一个问题，这个问题就是，在该实现中所有的扩容都为异地扩容，而异地扩容后原来定义的迭代器所给的地址就相当于一个野指针，再次访问时则会出现非法访问等问题；
要解决这个问题只能钻个小空子，由于string的模型就是一个数组，所以它的物理空间是连续的；
所以应该在设置迭代器后使用计数器count变量来记录位置p的偏移量；
在扩容之后根据偏移量将所给的p进行更新；
最后再进行插入；

My_string::iterator My_string::string::insert(iterator p, char c)//begin() 6
 {

	//断言位置p是否在迭代器范围以内；
	 assert(p>=begin()&&p<=end());
	 size_t count = 0;
	 while (*p != _str[count])
	 {
		 count++;
	 }

	 if (_size == _capacity) 
	 {
		 size_t Newcapacity = _capacity < 4 ? 15 : 2 * _capacity;
		 reserve(Newcapacity);
	 }
	 //问题 这里是扩容之后由于是异地扩容，所以p会被释放 不存在，导致的报错
	 p = begin() + count;
	 iterator pos = end();
	 while (pos!=p)
	 {
		 *(pos + 1) = *pos;
		 pos--;
	 }
	 *(pos + 1) = *pos;
	 *p = c;
	 _size++;
	 return begin();
 }
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

---

push_back()

该函数的作用为尾插，即在string对象的末尾添加一个字符；

void push_back (char c);
1

该函数可以直接复用insert函数中的迭代器版本的重载；

void My_string::string::push_back(char c)
 {
	 insert(end(), c);
 }
1
2
3
4

---

append()

该函数的作用也一样为尾插，只不过与push_back函数不同的是，该函数尾插的一半为一个字符串；
同时该函数在C++98中共有6个重载；
在这里主要实现其中两个重载；

		string& append(const string& str);

		string& append(const char* s);
1
2
3

这两个重载也与push_back函数一样可以复用insert函数中的函数重载；

 My_string::string& My_string::string::append(const string& str)
 {
	 insert(_size, str);
	 return *this;
 }

 My_string::string& My_string::string::append(const char* s)
 {
	 insert(_size, s);
	 return *this;
 }
1
2
3
4
5
6
7
8
9
10
11

---

---

🔺操作符重载（运算符重载）

在string对象中除了成员函数以外还有许多运算符(操作符)重载，这些重载都方便了很多的string使用；

operator[]

		char& operator[](size_t pos);
		const char& operator[](size_t pos)const;
1
2

通过[]直接对string中的字符串内容进行访问，设置为两个版本分别为：
const版本 使得在使用[]访问时只给读的权限不给写的权限；
非const版本 使得在使用[]进行访问时既可以读也可以写；
这两个重载将会根据string对象的属性灵活的进行调用；

 char& My_string::string::operator[](size_t pos)
 {
	 assert(pos <= _size);
	 return _str[pos];
 }

 const char& My_string::string::operator[](size_t pos)const
 {
	 assert(pos <= _size);
	 return _str[pos];
 }
1
2
3
4
5
6
7
8
9
10
11

同时该重载应该注意，标准库中的string对象对于访问越界的判定是十分严格的，所以在进行访问时应该断言是否越界；

---

operator+=

该重载实现了string对象可以进行追加，追加的数据可以是string对象，常量字符串或者字符等；

		string& operator+=(const string& str);

		string& operator+=(const char* s);
		
		string& operator+=(const char c);
1
2
3
4
5

通过该重载，使得string对象可以直接进行尾插，同时返回的string&也使得string对象在尾插的过程中更加具有连续性；
同时在实现时直接调用append即可；

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

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

 My_string::string& My_string::string::operator+=(const char c)
 {
	 push_back(c);
	 return *this;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

赋值运算符重载operator=()

赋值运算符重载也是一个十分重要的重载，在一个自定义类型中，赋值运算符重载也为一个默认成员函数，即若是不显式声明时，编译器将会自动生成一个无参的赋值运算符重载；
该函数在C++98中共有3个重载，这次主要实现其中一个：

string& operator=(/*const string& str*/string str);
1

该重载可以使得string对象可以随意的进行赋值。
而该重载的一般思路首先为，不能自己对自己赋值；
同时，重载将会像拷贝构造函数那样一个个进行赋值；

My_string::string& My_string::string::operator=(const string& str)//赋值操作符重载
 {
	if (this != &str) {
		 char* temp = new char[str._capacity+1];
		 strcpy(temp, str._str);
		 delete[]_str;
		 _str = temp;
		 _size = str._size;
		 _capacity = str._capacity;
	 }
	 return *this;
 }
1
2
3
4
5
6
7
8
9
10
11
12

除了这种方法以外，还有一种方法可以利用自定义类型作为参数生成的临时拷贝从而赋值成功；

 My_string::string& My_string::string::operator=(string str)//赋值操作符重载
 {
	 swap(str);
	 return *this;
 }
1
2
3
4
5

这里的str作为参数将会去调用它的拷贝构造函数从而生成临时对象；
而这里可以在与该临时对象进行交换的前提，即不影响实参的情况下；
成功进行赋值；

---

流插入 operator<<()重载

作为一个合格的string对象，应当支持流插入与流提取，流插入则为可以直接将string对象进行打印；
这里的打印与打印函数c_str不同，打印c_str函数时将会以字符串的形式进行打印，即遇到’\0’时会终止，而流插入的打印则会完全的将string对象进行打印，该打印是以_size参数为前提；

	ostream& operator<<(ostream& out, const string& str);
1

同时该函数的返回值为 ostream& 确保了该运算符可以进行连续调用；
同时，流插入流提取重载并不都为友元函数；
定义成友元函数一般考虑是否需要访问私有类对象；
而在这里并不需要访问私有类对象 对于string中的字符串只需要调用operator[]以及下标来访问每个元素即可
所以在面试中若是问到所有流插入都需要定义成友元时明显是错误的，
且该函数不能定义为成员函数 应该定义为公共函数，
原因是若是定义成成员函数的话 函数参数中自带一个隐含的this指针
这个隐含的this指针将会影响流插入<<符号的使用顺序 将会变成" str< 故不可取；

 ostream& My_string::operator<<(ostream& out, const string& str)
{


    for (size_t i = 0; i < str.size(); i++) {
   	 out << str[i];
    }

    return out;
}

1
2
3
4
5
6
7
8
9
10
11

流提取 operator>>()重载

流插入的思路为，利用getchar()接收字符，接收字符后判断该字符是否为’\n’或空格，若是’\n’或空格则停止输入；
同时将字符一个个利用 +=的重载加入至string对象中，在此之前应首先将原字符串内的数据进行清空；

 istream& My_string::operator>>(istream& in, string& str) 
 {
	 str.clear();//清除原字符串内的数据
	 char ch;
	 ch = getchar();//读取第一个字符以便进行循环

	 while (ch != ' ' && ch != '\n') {

		 str+=ch;
		 ch = getchar();
	 }

	 return in;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

但是该种思路有一种缺陷，在使用+=字符时，将会不停的扩容，从而导致开销太大，但若是直接开过大的空间的话则可能出现内存浪费的现象；

思路2：
开辟一个静态数组，这个静态数组的空间可以自定但不要过大，静态数组内用来存放getchar()输入的字符，若是数组满了则将这个数组内的数据+=至string对象中；

 istream& My_string::operator>>(istream& in, string& str) 
 {
	 str.clear();//清除原字符串内的数据
	 char ch;
	 ch = getchar();//读取第一个字符以便进行循环

	 const size_t N = 32;
	 char buff[N];
	 int i = 0;
	 while (ch != ' ' && ch != '\n') {

		 buff[i++] = ch;
		 if (i  == N-1) {//判满
			 buff[i] = '\0';
			 str += buff;
			 i = 0;
		 }
		 
		 ch = getchar();
	 }

	 /*
	  * 最后一段字符串也需要在末尾处加上'\0'
	  */
	 buff[i] = '\0';
	 str += 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