在C++中,stirng 类是标准库提供的一个非常强大的字符串处理工具。相比于C语言中的字符
数组(char[ ]) , string 类提供了更多方便且安全的操作。同时也更符合我们面向对象语言的特
点。
string类的模拟实现我们就模拟实现一些高频使用的容器操作,在逐步的实现过程中了解其底
层的实现方式。需要注意地是,我们需要将直接实现的string类与系统中自带的string类分开,
使用,我将其包在一个自定义的命名空间里面
同时由于定义声明分离,我们在定义函数时需要指定类域
string类型的成员变量其实跟我们之前数据结构定义的顺序表十分相似,同时一些操作的实现
也与顺序表类似,因此实现方式也基本类似,无非就是多了类和对象的相关只是,在实现
string类的过程中也可以帮助我们对c++的一些相关知识有更好的掌握
既然和顺序表类似类似,那么其自然是三个成员变量,一个是大小size,一个是存储空间大小
capacity,一个是char*类型的指针
string(const char* str = "")
构造函数我们实现一个带缺省值的构造函数,使得我们实例化一个对象时,若没有传参则会
调缺省值生成一个空串,若传参了则按吗传的参数进行初始化。
所以首先我们的参数类型应该是接受字符串的首元素地址所以是char*类型,同时保证传递参
数不被修改加上const
对_str的初始化,自然是使用new 去申请一块空间,需要注意的是申请空间的大小应比字符串
的大小大一位,因为还需要存储 “ \0 ”。size和capacity自然是初始化为0。
同时,要调用strcpy函数将传入的字符串拷贝到string类当中
- string::string(const char* str)
- :_str(new char[strlen(str) + 1])
- , _size(strlen(str))
- , _capacity(strlen(str))
- {
- strcpy(_str, str);
- }
有了构造函数,我们自然可以实现对应的析构函数。只需要使用delete[ ]释放掉new[ ]申请的
空间,并将str=nullptr,size,capacity=0即可
- string::~string()
- {
- delete[] _str;
- _str = nullptr;
- _size = _capacity = 0;
- }
在实现pushback之前,我们要实现一个函数reserve,实现空间的扩容,避免空间不足。
首先我们函数的参数是一个size_t类型的参数n,即表示我们需要扩容的大小。我们使用if条件
判断一下当前扩容的空间n是否是否小于当前的有空间capacity,避免产生缩容
扩容的第一步自然是申请一片空间,大小为n+1,随后使用strcpy将原对象中的数据拷贝到新
开辟的空间,随后释放掉原空间申请的内存,再使_str指向新开辟的空间,最后更新capacity
- void string::reserve(size_t n)
- {
- if (n > _capacity)//判断,因为reserve功能不是缩容
- {
- char* tmp = new char[n + 1];
- strcpy(tmp, _str);
- delete[] _str;
- _str = tmp;
- _capacity = n;
- }
- }
string类的迭代器相对比较简单,一位他的数据无论是逻辑顺序还是逻辑顺序都是连续的,因
此我们简单的用指针的遍历来模拟迭代器。
- typedef char* iterator;
- typedef const char* const_iterator;
普通迭代器
- iterator begin()
- {
- return _str;
- }
-
- iterator end()
- {
- return _str + _size;
- }
const 迭代器
- const_iterator begin() const
- {
- return _str;
- }
-
- const_iterator end() const
- {
- return _str + _size;
- }
有了reserve函数之后,我们便可以实现尾插函数,而尾插函数又分为尾插一个字符和一个字
符串。插入函数的逻辑与顺序表的插入大致类似。熟悉了顺序表的插入这自然也得心应手。
尾插一个字符逻辑非常简单,只需要先判断一下空间是否需要扩容,之后再尾部加上要插入
的字符,随后更新size即可
- void string::push_back(char ch)
- {
- if (_size == _capacity)
- {
- reserve(_capacity == 0 ? 4 : 2 * _capacity);
- }
- _str[_size++]=ch;
- }
由于我们扩大逻辑一般为二倍扩容,因此若插入的字符串有可能出现及时扩容后空间依然不
足的情况,所以我们需要一个if条件判断扩容后的空间只否足够插入字符串。若扩容后的空间
依然不足插入字符串,则直接扩容至size+len的大小。扩容完毕后只需要使用strcpy将需要插
入的字符串拷贝到str的末尾即可
- void string::append(const char* str)
- {
- size_t len = strlen(str);
- if (_size + len >= _capacity)
- {
- size_t newcapacity = 2 * _capacity;
- if (newcapacity < _size + len)
- newcapacity = _size + len;
-
- reserve(newcapacity);
- }
- strcpy(_str + _size, str);
- _size += len;
- }
首先自然是扩容,其逻辑与append一致,不再过多赘述。
在扩容完成之后,需要定义一个指针end,将pos位置以后的数据依次往后挪动一位,再将
字符插入到pos位置即可
- void string::insert(size_t pos, char ch)
- {
- if (_size == _capacity)
- {
- reserve(_capacity == 0 ? 4 : 2 * _capacity);
- }
- size_t end = _size + 1;
-
- while (end != pos)
- {
- _str[end] = _str[end - 1];
- end--;
- }
- _str[pos] = ch;
- _size++;
- }
插入字符串则是再扩容之后,需要将一段区间的数据往后挪,这时候我们就需要定义指针end
end指向末尾之后的len个长度(len为插入字符串的大小),在将依次将原数据的末尾字符从
头往前挪动,最后使用strcpy将要插入的字符串拷贝到pos位置。
在有了指定位置插入insert函数之后,我们便可以复用我们的insert来实现pushback和
apped。
- void string::push_back(char ch)
- {
-
- insert(_size, ch);
- }
-
- void string::append(const char* str)
- {
-
- insert(_size, str);
- }
指定位置删除我们要实现的是删除从pos位置开始的n个字符
因此我们首先要计算出我们需要前移几个数据,,再定义一个end指针指向要移除的元素区间
的下一元素,将其赋值给(end-n)位置的元素,再让end++,直到将剩余元素移完
- void string::erase(size_t pos, size_t len)
- {
- assert(pos < _size);
- if (len >= _size - pos)
- {
- _str[pos] = '\0';
- _size = pos;
- }
- else
- {
- size_t end = pos;
- while (end + len <= _size)
- {
- _str[end] = _str[end + len];
- end++;
- }
- _size -= len;
- }
- }
库中虽然有交换函数,但是其行为对于类来说要进行多次深拷贝,代价非常的大,因此我们
自己实现一个函数,进行拷贝构造,提高其效率。
swap(string& s)
在一开始的时候我们就定义了类的成员变量,那么其实我们只要交换两个类的成员变量就可
以实现两个类的交换,这时候就可以调用库中的swap来进行成员变量的交换,因为其只涉及
浅拷贝,代价较小
- void string::swap(string& s)
- {
- std::swap(_str, s._str);
- std::swap(_size, s._size);
- std::swap(_capacity, s._capacity);
- }
由于我们的stirng在构造时候申请了资源,因此编译器自动生成的拷贝构造浅拷贝行为无法完
成我们的需要,这回导致两个对象指向同一片空间从而析构两次而报错。因此我们就需要自
己写拷贝构造。
string(const string& s)
有了类的交换函数之后我,就可以轻松的实现拷贝构造,我们只需用被拷贝的对象创建一个
临时变量tmp,再调用我们自己实现的swap函数将其与我们要创建的对象交换即可,并且tmp
这个临时对象也会在出函数的时候自动销毁不需要我们去手动销毁,一举两得
- string::string(const string& s)
- {
- string tmp(s._str);
- swap(tmp);
- }
同理于拷贝构造,我们自然也要自己实现那赋值重载。
string& operator=(string s)
由于这里的函数参数并不是对象的引用,因此是传递的参数锁构造出来的一个临时对象,我
们只需调用我们实现的swap函数进行交换最后返回*this即可,临时对象s也会在出函数之后自
己销毁。
-
- string& string::operator=(string s)
- {
- swap(s);
- return *this;
- }
运算符的重载可以复用,这意味着我们只需要实现一两个运算符的重载即可复用从而实现
其他的。
由于运算符重载的函数其第一个参数并不是累的this指针,因此我们将其实现在类的外部
又因为我们的string类是实现在自己的命名空间中,因此不需要将其再重载为友元函数,编译
器会自己在命名空间中寻找。
+=的逻辑与插入函数一致,我们只需要复用我的的两个插入函数即可
- string& string::operator+=(char ch)
- {
- push_back(ch);
- return *this;
- }
-
- string& string::operator+=(const char* str)
- {
- append(str);
- return *this;
- }
==运算符的逻辑是字符串的比较,因此我们只需要调用哭函数中的strcmp即可
- bool bit::operator==(const string& lhs, const string& rhs)
- {
- return strcmp(lhs.c_str(), rhs.c_str()) == 0;
- }
>的重载本质也是比较字符串,调用strcmp即可实现
- bool bit::operator>(const string& lhs, const string& rhs)
- {
- return strcmp(lhs.c_str(), rhs.c_str()) > 0;
- }
- bool bit::operator<(const string& lhs, const string& rhs)
- {
- return !(lhs >= rhs);
- }
- bool bit::operator>=(const string& lhs, const string& rhs)
- {
- return lhs == rhs || lhs > rhs;
- }
- bool bit::operator<=(const string& lhs, const string& rhs)
- {
- return !(lhs > rhs);
- }
- bool bit::operator!=(const string& lhs, const string& rhs)
- {
- return !(lhs == rhs);
- }
- ostream& operator<<(ostream& os, const string& str)
- {
- for (size_t i = 0; i < str.size(); i++)
- {
- os << str[i];
- }
- return os;
- }
-
- istream& operator>>(istream& is, string& str)
- {
- str.clear();
-
- int i = 0;
- char buff[256];//建立临时数组,避免频繁开空间,并且栈上开空间比堆上开空间效率高
-
- char ch;
- ch = is.get();
- while (ch != ' ' && ch != '\n')
- {
- buff[i++] = ch;
- if (i == 255)
- {
- buff[255] = '\0';
- str += buff;
- i = 0;
- }
- ch = is.get();
- }
-
- if (i > 0)
- {
- buff[i] = '\0';
- str += buff;
- }
- return is;
- }
- #pragma once
- #include<iostream>
- #include<assert.h>
- using namespace std;
-
- namespace bit
- {
-
- class string
- {
- public:
- typedef char* iterator;
- typedef const char* const_iterator;
- string(const char* str = "");
- ~string();
- string(const string& s);
-
- void reserve(size_t n);
- void push_back(char ch);
- void append(const char* str);
- string& operator+=(char ch);
- string& operator+=(const char* str);
- string& operator=(string s);
-
- void insert(size_t pos, char ch);
- void insert(size_t pos, const char* str);
- void erase(size_t pos, size_t len = npos);
- size_t find(char ch, size_t pos = 0);
- size_t find(const char* str, size_t pos = 0);
-
- string substr(size_t pos, size_t len = npos);
- void swap(string& s);
-
- const char* c_str() const
- {
- return _str;
- }
-
- size_t size() const
- {
- return _size;
- }
-
- char& operator[](size_t i)
- {
- assert(i < _size);
- return _str[i];
- }
-
- char& operator[](size_t i) const
- {
- assert(i < _size);
- return _str[i];
- }
-
- iterator begin()
- {
- return _str;
- }
-
- iterator end()
- {
- return _str + _size;
- }
-
- const_iterator begin() const
- {
- return _str;
- }
-
- const_iterator end() const
- {
- return _str + _size;
- }
-
- void clear()
- {
- _str[0] = '\0';
- _size = _capacity = 0;
- }
-
- private:
- size_t _size;
- size_t _capacity;
- char* _str;
- public:
- //static const size_t npos = -1;
- //静态成员变量不能给缺省值必须类内定义类外声明
- // 但const 整形静态成员可以直接给缺省值,算是特殊处理
- static const size_t npos;
- };
-
- void swap(string& s1, string& s2);
-
- bool operator==(const string& lhs, const string& rhs);
- bool operator!=(const string& lhs, const string& rhs);
- bool operator>(const string& lhs, const string& rhs);
- bool operator<(const string& lhs, const string& rhs);
- bool operator>=(const string& lhs, const string& rhs);
- bool operator<=(const string& lhs, const string& rhs);
-
- ostream& operator<<(ostream& os, const string& str);
- istream& operator>>(istream& is, string& str);
- istream& getline(istream& is, string& str, char delim = '\n');
- }
- #define _CRT_SECURE_NO_WARNINGS 1
- #include"string.h"
-
- namespace bit
- {
- const size_t string::npos = -1;
-
- string::string(const char* str)
- :_str(new char[strlen(str) + 1])
- , _size(strlen(str))
- , _capacity(strlen(str))
- {
- strcpy(_str, str);
- }
-
- string::~string()
- {
- delete[] _str;
- _str = nullptr;
- _size = _capacity = 0;
- }
-
- //b2(b1)
- string::string(const string& s)
- {
- string tmp(s._str);
- swap(tmp);
- }
-
- void string::reserve(size_t n)
- {
- if (n > _capacity)//判断,因为reserve功能不是缩容
- {
- char* tmp = new char[n + 1];
- strcpy(tmp, _str);
- delete[] _str;
- _str = tmp;
- _capacity = n;
- }
- }
-
- void string::push_back(char ch)
- {
- /*if (_size == _capacity)
- {
- reserve(_capacity == 0 ? 4 : 2 * _capacity);
- }
- _str[_size++] = ch;*/
- insert(_size, ch);
- }
-
- void string::append(const char* str)
- {
- //size_t len = strlen(str);
- //if (_size + len >= _capacity)
- //{
- // size_t newcapacity = 2 * _capacity;
- // if (newcapacity < _size + len)
- // newcapacity = _size + len;
- //
- // reserve(newcapacity);
- //}
- //strcpy(_str + _size, str);
- //_size += len;
- insert(_size, str);
- }
-
-
- string& string::operator+=(char ch)
- {
- push_back(ch);
- return *this;
- }
-
- string& string::operator+=(const char* str)
- {
- append(str);
- return *this;
- }
-
- void string::insert(size_t pos, char ch)
- {
- if (_size == _capacity)
- {
- reserve(_capacity == 0 ? 4 : 2 * _capacity);
- }
- size_t end = _size + 1;
-
- while (end != pos)
- {
- _str[end] = _str[end - 1];
- end--;
- }
- _str[pos] = ch;
- _size++;
- }
- void string::insert(size_t pos, const char* str)
- {
- size_t len = strlen(str);
- if (_size + len >= _capacity)
- {
- size_t newcapacity = 2 * _capacity;
- if (newcapacity < _size + len)
- newcapacity = _size + len;
-
- reserve(newcapacity);
- }
-
- len = strlen(str);
- size_t end = _size + len;
- while (end != pos + len - 1)
- {
- _str[end] = _str[end - len];
- end--;
- }
- for (size_t i = 0; i < len; i++)
- {
- _str[pos + i] = str[i];
- }
- _size += len;
- }
-
- void string::erase(size_t pos, size_t len)
- {
- assert(pos < _size);
- if (len >= _size - pos)
- {
- _str[pos] = '\0';
- _size = pos;
- }
- else
- {
- size_t end = pos;
- while (end + len <= _size)
- {
- _str[end] = _str[end + len];
- end++;
- }
- _size -= len;
- }
- }
-
- size_t string::find(char ch, size_t pos)
- {
- assert(pos < _size);
- for (size_t i = pos; i < _size; i++)
- {
- if (_str[i] == ch)
- return i;
- }
- return npos;
- }
-
- size_t string::find(const char* str, size_t pos)
- {
- assert(pos < _size);
- const char* ptr = strstr(_str + pos, str);
- if (ptr == nullptr)
- return npos;
- else
- return ptr - _str;
- }
-
- string string::substr(size_t pos, size_t len)
- {
- if (len > (_size - pos))
- {
- len = _size - pos;
- }
-
- bit::string sub;
- sub.reserve(len);
- for (size_t i = 0; i < len; i++)
- {
- sub += _str[pos + i];
- }
-
- return sub;
- }
-
- string& string::operator=(string s)
- {
- swap(s);
- return *this;
- }
-
- void string::swap(string& s)
- {
- std::swap(_str, s._str);
- std::swap(_size, s._size);
- std::swap(_capacity, s._capacity);
- }
-
- void swap(string& s1, string& s2)
- {
- s1.swap(s2);
- }
-
-
- bool bit::operator==(const string& lhs, const string& rhs)
- {
- return strcmp(lhs.c_str(), rhs.c_str()) == 0;
- }
- bool bit::operator!=(const string& lhs, const string& rhs)
- {
- return !(lhs == rhs);
- }
- bool bit::operator>(const string& lhs, const string& rhs)
- {
- return strcmp(lhs.c_str(), rhs.c_str()) > 0;
- }
- bool bit::operator<(const string& lhs, const string& rhs)
- {
- return !(lhs >= rhs);
- }
- bool bit::operator>=(const string& lhs, const string& rhs)
- {
- return lhs == rhs || lhs > rhs;
- }
- bool bit::operator<=(const string& lhs, const string& rhs)
- {
- return !(lhs > rhs);
- }
-
- ostream& operator<<(ostream& os, const string& str)
- {
- for (size_t i = 0; i < str.size(); i++)
- {
- os << str[i];
- }
- return os;
- }
-
- istream& operator>>(istream& is, string& str)
- {
- str.clear();
-
- int i = 0;
- char buff[256];//建立临时数组,避免频繁开空间,并且栈上开空间比堆上开空间效率高
-
- char ch;
- ch = is.get();
- while (ch != ' ' && ch != '\n')
- {
- buff[i++] = ch;
- if (i == 255)
- {
- buff[255] = '\0';
- str += buff;
- i = 0;
- }
- ch = is.get();
- }
-
- if (i > 0)
- {
- buff[i] = '\0';
- str += buff;
- }
- return is;
- }
-
- istream& getline(istream& is, string& str, char delim)
- {
- str.clear();
-
- int i = 0;
- char buff[256];
-
- char ch;
- ch = is.get();
- while (ch != delim)
- {
- buff[i++] = ch;
- if (i == 255)
- {
- buff[255] = '\0';
- str += buff;
- i = 0;
- }
- ch = is.get();
- }
-
- if (i > 0)
- {
- buff[i] = '\0';
- str += buff;
- }
- return is;
- }
- }