C++STL容器——string和模拟实现
1 为什么学习string类
C语言中，字符串是以'\0'结尾的一些字符的集合，为了操作方便，C标准库中提供了一些str系列的库函数，但是这些库函数与字符串是分离开的，不太符合OOP的思想，而且底层空间需要用户自己管理，稍不留神可能还会越界访问。所以为了使得字符串和操作字符串的方法封装在一起所以C++STL容器才产生string类，所以它的学习是很有必要的
2 标准库中的string类以及语法补充
1 string类
2 auto 和 范围for
auto关键字
在这里补充2个C++11的小语法，方便我们后面的学习：
1 在早期C/C++中auto的含义是： 使用auto修饰的变量，是具有自动存储器的局部变量在每个局部变量前都会显示或者隐式包含，后来这个不重要了。
2 C++11中，标准委员会变废为宝赋予了auto全新的含义即：它成为了一个"万能类型"它可以通过上下文你对于auto修饰变量的赋值等来通过编译器编译将auto关键字转变为对应类型推导类型auto声明的变量必须由编译器在编译时期推导而得
3 用auto声明指针类型时，用auto和auto*没有任何区别，但用auto声明引用类型时则必须加&
4 当在同一行声明多个变量时，这些变量必须是相同的类型，否则编译器将会报错，因为编译器实际只对第一个类型进行推导，然后用推导出来的类型定义其他变量。
5 auto不能用来做函数参数但是可以用来做函数返回值(因为函数参数是声明不是初始化/赋值，所以编译器编译函数声明时不知道参数类型是什么无法编译)
6 auto 不能直接用来声明数组(因为auto定义要根据初始化/赋值的值来推到auto,但是数组定义确实要先明确左边的值也就是数组大小，所以导致发生了逻辑冲突)
#include <iostream>
using namespace std;
auto add(int a,int b)//auto可以做返回值
{
return a+b;
}
int main()
{
int a = 10;
auto b = a;
auto c = 'a';
auto d = add();
return 0;
}范围for
对于一个有范围的集合而言，由程序员来说明循环的范围是多余的，有时候还会容易犯错误。因此C++11中引入了基于范围的for循环。for循环后的括号由冒号“ ：”分为两部分：第一部分是范围内用于迭代的变量，第二部分则表示被迭代的范围，自动迭代，自动取数据，自动判断结束。
范围for可以作用到数组和容器对象上进行遍历
范围for的底层很简单，容器遍历实际就是替换为迭代器，这个从汇编层也可以看到。
#include<iostream>
#include <string>
using namespace std;
int main()
{
string s="hello world";
for(auto e : s)
{
cout<<e<<" ";
}
cout<<endl;
return 0;
}3 string的常用接口说明
1. string类对象的常见构造
| (constructor) 函数名称 | 功能说明 |
|---|---|
| string ()（重点） | 构造空的 string 类对象，即空字符串 |
| string (const char* s)（重点） | 用 C-string 来构造 string 类对象 |
| string(size_t n, char c) | string 类对象中包含 n 个字符 c |
| string (const string&s)（重点） | 拷贝构造函数 |
2 string类对象的容量操作
| 函数名称 | 功能说明 |
|---|---|
| size(重点) | 返回字符串有效字符长度 |
| length | 返回字符串有效字符长度 |
| capacity | 返回空间总大小 |
| empty | 检测字符串是否为空串，是返回 true，否则返回 false |
| clear(重点) | 清空有效字符 |
| reserve(重点) | 为字符串预留空间 **,如果输入的个数n<字符串大小则实现看编译器 |
| resize(重点) | 将有效字符的个数改成 n 个，多出的空间用字符 c 填充，多出的字符则去除 |
注意：
1. size()与length()方法底层实现原理完全相同，引入size()的原因是为了与其他容器的接
口保持一致，一般情况下基本都是用size()。
2. clear()只是将string中有效字符清空，不改变底层空间大小。
3. resize(size_t n) 与 resize(size_t n, char c)都是将字符串中有效字符个数改变到n个，不
同的是当字符个数增多时：resize(n)用0来填充多出的元素空间，resize(size_t n, char
c)用字符c来填充多出的元素空间。注意：resize在改变元素个数时，如果是将元素个数
增多，可能会改变底层容量的大小，如果是将元素个数减少，底层空间总大小不变。
4. reserve(size_t res_arg=0)：为string预留空间，不改变有效元素个数，当reserve的参
数小于string的底层空间总大小时，reserver不会改变容量大小。
5 注意string的capacity和size没有包括\0的大小但是实际上开辟的空间是有\0的
3. string类对象的访问及遍历操作
| 函数名称 | 功能说明 |
|---|---|
| operator[](重点) | 返回 pos 位置的字符，const string 类对象调用 |
| begin+end | begin 获取一个字符的迭代器 + end 获取最后一个字符下一个位置的迭代器 |
| rbegin+rend | rbegin 获取反向起始迭代器 + rend 获取反向结束迭代器 |
| 范围for | C++11 支持更简洁的范围 for 的新遍历方式 |
4 string类对象的修改
| 函数名称 | 功能说明 |
|---|---|
| push_back | 在字符串后尾插字符 c |
| append | 在字符串后追加一个字符串 |
| operator+=(重点) | 在字符串后追加字符串 str |
| c_str | 返回 C 格式字符串 |
| find+npos | 从字符串 pos 位置开始往后找字符 c，返回该字符在字符串中的位置 |
| rfind | 从字符串 pos 位置开始往前找字符 c，返回该字符在字符串中的位置 |
| substr | 在 str 中从 pos 位置开始，截取 n 个字符，然后将其返回 |
注意：
1. 在string尾部追加字符时，s.push_back(c) / s.append(1, c) / s += 'c'三种的实现方式差
不多，一般情况下string类的+=操作用的比较多，+=操作不仅可以连接单个字符，还可
以连接字符串。
2. 对string操作时，如果能够大概预估到放多少字符，可以先通过reserve把空间预留
好。
5 string类非成员函数
| 函数 | 功能说明 |
|---|---|
| operator+ | 尽量少用，因为传值返回，导致深拷贝效率低 |
| operator>>(重点) | 输入运算符重载 |
| operator<<(重点) | 输出运算符重载 |
| getline(重点) | 获取一行字符串 |
| relational_operators(重点) | 大小比较 |
6. vs和g++下string结构的说明
注意：下述结构是在32位平台下进行验证，32位平台下指针占4个字节。
vs下string的结构
string总共占28个字节，内部结构稍微复杂一点，先是有一个联合体，联合体用来定义string中字符串的存储空间：
1 当字符串长度小于16时，使用内部固定的字符数组来存放
2 当字符串长度大于等于16时，从堆上开辟空间
union _Bxty
{
// storage for small buffer or pointer to larger one
value_type _Buf[_BUF_SIZE];
pointer _Ptr;
char _Alias[_BUF_SIZE]; // to permit aliasing
} _Bx;这种设计也是有一定道理的，大多数情况下字符串的长度都小于16，那string对象创建
好之后，内部已经有了16个字符数组的固定空间，不需要通过堆创建，效率高。
其次：还有一个size_t字段保存字符串长度，一个size_t字段保存从堆上开辟空间总的
容量
g++下string的结构
g++下，string是通过写时拷贝实现的，string对象总共占4个字节，内部只包含了一个
指针，该指针将来指向一块堆空间，内部包含了如下字段：
1 空间总大小
2 字符串有效长度
3 引用计数
struct _Rep_base
{
size_type _M_length;
size_type _M_capacity;
_Atomic_word _M_refcount;
};4 指向堆空间的指针，用来存储字符串
4 string的模拟实现
#include <iostream>
using namespace std;
namespace yjs
{
class string
{
friend ostream& operator<<(ostream& _cout, const yjs::string& s);
friend istream& operator>>(istream& _cin, yjs::string& s);
public:
typedef char* iterator;
string(const char* str = "")
{
int i;
int len = strlen(str);
_str = new char[len + 1];
for ( i= 0;i<len; i++)
{
_str[i] = str[i];
_size++;
}
_str[i] = '\0';
_capacity = _size;
}
string(const string& s)
{
_size = s._size;
_capacity = s._capacity;
char* temp = new char[_capacity + 1];
int i;
for (i = 0; i < _size; i++)
{
temp[i] = s._str[i];
}
temp[i] = '\0';
delete[] _str;
_str = temp;
}
string& operator=(const string& s)
{
_size = s._size;
_capacity = s._capacity;
char* temp = new char[_capacity + 1];
int i;
for (i = 0; i < _size; i++)
{
temp[i] = s._str[i];
}
temp[i] = '\0';
_str = temp;
delete[] temp;
return *this;
}
~string()
{
_size = _capacity = 0;
delete[] _str;
}
iterator begin()
{
return _str;
}
iterator end()
{
return nullptr;
}
size_t size()
{
return _size;
}
size_t capacity()
{
return _capacity;
}
void reserve(int n)
{
if (n > _capacity)
{
char* temp = new char[n + 1] {0};
int i;
for (i = 0; i < _size; i++)
{
temp[i] = _str[i];
}
temp[i] = '\0';
delete[] _str;
_str = temp;
_capacity = n;
}
}
void resize(size_t n, char c = '\0')
{
if (n > _size)
{
reserve(n);
int i = 0;
for (i = _size; i < n; i++)
{
_str[i] = c;
_size++;
}
_str[i] = '\0';
}
else
{
_str[n] = '\0';
}
}
bool empty()
{
return _size == 0;
}
void push_back(char c)
{
if (_size == _capacity)
{
reserve(_capacity * 2);
}
_str[_size++] = c;
_str[_size] = '\0';
}
string& operator+=(char c)
{
if (_size == _capacity)
{
reserve(_capacity * 2);
}
_str[_size++] = c;
_str[_size] = '\0';
return *this;
}
void append(const char* str)
{
int i;
int len = strlen(str);
int n = _size + len;
if (n >=_capacity)
{
reserve(n);
}
else
{
reserve(2 * _capacity);
}
for (i = 0; i < len; i++)
{
_str[_size++] = str[i];
}
_str[_size] = '\0';
}
string& operator+=(const char* str);
void clear()
{
_size = _capacity = 0;
}
void swap(string& s)
{
char* temp_str = s._str;
int temp_size=s._size, tem_capacity = s._capacity;
s._str = _str;
s._size = _size;
s._capacity = _capacity;
_str = temp_str;
_size = temp_size;
_capacity = tem_capacity;
}
const char* c_str()const
{
return _str;
}
char& operator[](size_t index)
{
return _str[index];
}
const char& operator[](size_t index)const
{
return (const char)_str[index];
}
bool operator<(const string& s)
{
for (int i = 0; i < _size; i++)
{
if (_str[i] >= s._str[i])
return false;
}
if (_size > s._size)
return false;
return true;
}
bool operator<=(const string& s)
{
return ((*this) < s || (*this) == s);
}
bool operator>(const string& s)
{
return !((*this) <= s);
}
bool operator>=(const string& s)
{
return ((*this) > s || (*this) == s);
}
bool operator==(const string& s)
{
if (_size == s._size)
{
for (int i = 0; i < _size; i++)
{
if (_str[i] != s._str[i])
return false;
}
return true;
}
return false;
}
bool operator!=(const string& s)
{
return !((*this) == s);
}
// 返回c在string中第一次出现的位置
size_t find(char c, size_t pos = 0) const
{
for (int i = pos; i < _size; i++)
{
if (_str[i] == c)
{
return i;
}
}
return -1;
}
// 返回子串s在string中第一次出现的位置
size_t find(const char* s, size_t pos = 0) const;
// 在pos位置上插入字符c/字符串str，并返回该字符的位置
string& insert(size_t pos, char c)
{
if (_size == _capacity)
{
reserve(_capacity * 2);
}
for (int i = _size; i > pos;i--)
{
_str[i] = _str[i - 1];
}
_str[pos] = c;
_size++;
return *this;
}
string& insert(size_t pos, const char* str)
{
int len = strlen(str);
if (_size == _capacity)
{
if (_size + len >= 2 * _capacity)
reserve(_size + len);
else
reserve(2 * _capacity);
}
for (int i = _size + len; i > pos ;i--)
{
_str[i] = _str[i - len];
}
for (int i = 0; str[i] != '\0'; i++)
{
_str[pos++] = str[i];
}
_size += len;
return *this;
}
// 删除pos位置上的元素，并返回该元素的下一个位置
string& erase(size_t pos)
{
for (int i = pos;i<=_size;i++)
{
_str[i] = _str[i + 1];
}
_size--;
}
private:
char* _str;
int _size=0;
int _capacity=0;
};
ostream& operator<<(ostream& _cout, const yjs::string& s)
{
_cout << s._str;
return _cout;
}
istream& operator>>(istream& _cin, yjs::string& s)
{
_cin >> s._str;
return _cin;
}
}
5 现代版写法的string类
class String
{
public:
String(const char* str = "")
{
if (nullptr == str)
{
assert(false);
return;
}
str = new char[strlen(str) + 1];
strcpy(_str, str);
}
String(const String& s)
: _str(nullptr)
{
String strTmp(s._str);
swap(_str, strTmp._str);
}
// 对比下和上面的赋值那个实现比较好？
String& operator=(String s)
{
swap(_str, s._str);
return *this;
}
/*
String& operator=(const String& s)
{
if(this != &s)
{
String strTmp(s);
swap(_str, strTmp._str);
}
return *this;
}
*/
~String()
{
if (_str)
{
delete[] _str;
_str = nullptr;
}
}
private:
char* _str;
};现代写法本质是复用。在之前的写法中拷贝构造/拷贝赋值需要在函数里实现空间的开辟和资源的复制，但是在现代写法中通过传参(不传引用)会构造临时对象调用构造的时候后复用构造里的空间开辟而且开辟的临时对象的参数可以和拷贝对象直接交换参数，这样原来拷贝对象开辟空间可以由出函数是对象调用析构函数的时候释放完成了对析构函数的复用
更多推荐
8
0- 0
已为社区贡献4条内容
所有评论(0)