目录
? ? ? ? STL容器的模拟实现是我们了解STL函数接口的重要部分，也是在学习C++容器时的重要环节。这里，我们模拟实现string的常规接口。
steing的框架结构：
? ? ? ? 在调试窗口上可观察到string的参数有size(大小)、capacity(大小)、串(char*)。至于迭代器，这里可先认为指针。
//框架设计模型
class string
{
public:
? ? typedef char* iterator;? ?//迭代器
private:
? ? char* _str;? ? ? ? ? ? ? ?//串
? ? size_t _capacity;? ??//容量
? ? size_t _size;? ? ? ? ?? //大小
};
? ? ? ? 构造函数在实现时首先要注意缺省值的情况。当创建string空类时，默认不会初始化，且输出时不会输出乱码，无任何数据，因此，这里需将缺省值设为""。
//String(const char* str = "\0") 错误示范，可能会出现程序崩溃
//String(const char* str = nullptr) 错误示范，可能会出现程序崩溃//普通构造
string(const char* str = "")
? ? ?: _capacity(strlen(str) + 1)
? ? ?, _size(strlen(str))
{
? ? ?// 构造String类对象时，如果传递nullptr指针，可以认为程序非
? ? ?if (nullptr == str)
? ? ?{
? ? ? ? ?assert(false);
? ? ? ? ?return;
? ? ?}
? ? ?_str = new char[_capacity];
? ? ?memcpy(_str, str, _capacity);
}
//拷贝构造
string(const string& s)
? ? : _capacity(s._capacity)
? ? , _size(s._size)
{? ??// 构造String类对象时，如果传递nullptr指针，可以认为程序非
? ? if (nullptr == s)
? ? {
? ? ? ? assert(false);
? ? ? ? return;
? ? }
? ? _str = new char[_capacity];
? ? memcpy(_str, s._str, s._size + 1);
}//析构函数
~string()
{
? ? ? delete[] _str;
? ? ? _str = nullptr;
? ? ??_capacity = _size = 0;}
? ? ? ? 赋值运算符重载跟构造函数的注意事项一样，需注意的是这里进行的是深拷贝，不是浅拷贝，即重新开辟新的空间进行拷贝。
string& operator=(const string& s)
{
? ? delete[] _str;
? ? char* str = new char[s._capacity];
? ? memcpy(str, s._str, s._size + 1);
? ? _str = str;
? ? _size = s._size;
? ? _capacity = s._capacity;
? ? return *this;
}
? ? ? ? 流的操作符中，输出流实现简单，只需根据string类的大小进行输出字符即可，但输入流需注意以下两点：
//输出流
ostream& operator<<(ostream& _cout, const bit::string& s)
{
? ? for (int i = 0; i < s._size; i++)
? ? {
? ? ? ? _cout << s._str[i];
? ? }
? ? return _cout;
}//输入流
istream& operator>>(istream& _cin, bit::string& s)
{
? ? //先清理数据string中的数据
? ? delete[] s._str;
? ? char* str = new char[s._capacity];
? ? s._str = str;
? ? memcpy(s._str, "\0", 1);
? ? s._size = 0;
? ? //下面进行开始输入操作
? ? char buff[128];
? ? char ch = _cin.get();
? ? int i = 0;
? ? while (ch != ' ' && ch != '\n')
? ? {
? ? ? ? buff[i++] = ch;
? ? ? ? if (i == 127)
? ? ? ? {
? ? ? ? ? ? buff[i] = '\0';
? ? ? ? ? ? //在进行增添之前要先判断容量是否够容载
? ? ? ? ? ? if (s._capacity < s._size + strlen(buff))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s._capacity += 2 * (s._size + strlen(buff));
? ? ? ? ? ? ? ? char* str = new char[s._capacity];
? ? ? ? ? ? ? ? memcpy(str, s._str, s._size + 1);
? ? ? ? ? ? ? ? delete[] s._str;
? ? ? ? ? ? ? ? s._str = str;
? ? ? ? ? ? }
? ? ? ? ? ? //连接操作，注意：这里不能用strcat，因为strcat本身有bug，如下? ?? ? ? ??/*char str[] = "\0";
?? ??? ??? ?strcat(str, "avbsc");
?? ??? ??? ?cout << str << endl;
?? ??? ??? ?此程序将会崩溃，strcat的第一个参数不能为空*/
? ? ? ? ? ? int k = 0;
? ? ? ? ? ? for (int j = s._size; j < s._size + strlen(buff); j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s._str[j] = buff[k++];
? ? ? ? ? ? }
? ? ? ? ? ? s._size += strlen(buff);
? ? ? ? ? ? i = 0;
? ? ? ? }
? ? ? ? ch = _cin.get();
? ? }
? ? buff[i] = '\0';
? ? //判断容量
? ? if (s._capacity < s._size + strlen(buff))
? ? {
? ? ? ? s._capacity += 2 * (s._size + strlen(buff));
? ? ? ? char* str = new char[s._capacity];
? ? ? ? memcpy(str, s._str, s._size + 1);
? ? ? ? delete[] s._str;
? ? ? ? s._str = str;
? ? }
? ? //连接操作
? ? int k = 0;
? ? for (int j = s._size; j < s._size + strlen(buff); j++)
? ? {
? ? ? ? s._str[j] = buff[k++];
? ? }
? ? s._size += strlen(buff);
? ? return _cin;
}
? ? ? ? 我们目前最常用的迭代器是begin()和end()，begin()指向首元素的地址，而end()指向尾元素的下一个地址处，实现机制如下：
iterator begin()
{
? ? return _str;
}
iterator end()
{
? ? return _str + _size;
}
? ? ? ? 至于运算符重载的实现，这里，我们对 “[]、>、>=、<、<=、==、!=” 进行重载实现。
char& operator[](size_t index)
{
? ? //防止遍历出界
? ? assert(index <= _size && index >= 0);
? ? return *(_str + index);
}
const char& operator[](size_t index)const
{
? ? //防止遍历出界
? ? assert(index <= _size && index >= 0);
? ? return (const char)(*_str + index);
}
bool operator<(const string& s)
{
? ? for (int i = 0; i < _size; i++)
? ? {
? ? ? ? if (_str[i] < s._str[i])
? ? ? ? {
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? else if (_str[i] > s._str[i])
? ? ? ? {
? ? ? ? ? ? return false;
? ? ? ? }
? ? }
? ? return false;
}
bool operator<=(const string& s)
{
? ? for (int i = 0; i < _size; i++)
? ? {
? ? ? ? if (_str[i] < s._str[i])
? ? ? ? {
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? else if (_str[i] > s._str[i])
? ? ? ? {
? ? ? ? ? ? return false;
? ? ? ? }
? ? }
? ? return true;
}
bool operator>(const string& s)
{
? ? return !(*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)
{
? ? return !(*this == s);
}
? ? ? ? 在实现增删之前，我们首先实现reserve增容接口。需注意reserve不能减小容量，只能增加容量。
void reserve(size_t n)
{
? ? if (_capacity < n)? ?//不能减小容量
? ? {
? ? ? ? _capacity = _capacity == 1 ? n : 2 * n;
? ? ? ? char* str = new char[_capacity];
? ? ? ? memcpy(str, _str, strlen(_str) + 1);
? ? ? ? delete[] _str;
? ? ? ? _str = str;
? ? }
}
? ? ? ? 这里我们对push_back、erase、+=、append操作进行接口实现。其中，push_back只能在末尾增添一个字符，erase可删除多个字符或全部字符，“+=” 和append都是在末尾连接一个串。在实现中，要注意string为空和满载的情况。当满载时，需使用reserve进行增容操作，当为空时，要根据接口的功能来进行下一步作用。
//删除操作
string& erase(size_t pos, size_t len)
{? ? //防止错误操作
? ? assert(len >= 0);
? ? assert(pos >= 0 && pos < _size);
? ? int deletelen = len;
? ? if (deletelen > _size - pos) //注意当len大于string大小的情况
? ? {
? ? ? ? deletelen = _size - pos;
? ? }
? ? int _strlen = _size + 1;
? ? memcpy(_str + pos, _str + pos + deletelen, _strlen - pos - deletelen);
? ? return *this;
}//增加操作
void push_back(char c)
{
? ? if (_size == _capacity - 1)
? ? {
? ? ? ? reserve(_capacity + 1);
? ? }
? ? _str[_size++] = c;
? ? _str[_size] = '\0';
}void append(const char* str)
{
? ? if (_capacity - 1 < _size + strlen(str))
? ? {
? ? ? ? reserve(_size + strlen(str));
? ? }
? ? for (int i = 0; i < strlen(str); i++)
? ? {
? ? ? ? push_back(str[i]);
? ? }
}string& operator+=(char c)
{
? ? push_back(c);
? ? return *this;
}
string& operator+=(const char* str)
{
? ? append(str);
? ? return *this;
}
? ? ? ? 这里我们模拟find查找和insert插入。实现find查找，若找到指定的数据，返回第一次出现的位置，若没有找到，返回无符号整型-1的数值。实现insert插入，只需注意要插入的位置在合理位置上即可。
//find查找操作
size_t find(char c, size_t pos = 0) const? ?//返回c在string中第一次出现的位置
{
? ? for (int i = pos; i < _size && pos >= 0; i++)
? ? {
? ? ? ? if (_str[i] == c)
? ? ? ? {
? ? ? ? ? ? return i;
? ? ? ? }
? ? }
? ? return -1;
}
size_t find(const char* s, size_t pos = 0) const? //返回子串s在string中第一次出现的位置
{
? ? for (int i = pos; i < _size && pos >= 0; i++)
? ? {
? ? ? ? int k = i;
? ? ? ? for (int j = 0; j < strlen(s) && i < _size; j++)
? ? ? ? {
? ? ? ? ? ? if (s[j] == _str[i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (i - k + 1 == strlen(s))
? ? ? ? ? ? ? ? ? ? return k;
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? i = k;
? ? }
? ? return -1;
}//insert插入操作
string& insert(size_t pos, char c)
{
? ? assert(pos >= 0 && pos <= _size);? ?//保证插入的位置在合理范围中
? ? if (_capacity == _size)
? ? {
? ? ? ? reserve(_capacity + 1);
? ? }
? ? for (int i = _size; i >= pos; i--)
? ? {
? ? ? ? _str[i + 1] = _str[i];
? ? }
? ? _str[pos] = c;
? ? _size++;
? ? return *this;
}
string& insert(size_t pos, const char* str)
{
? ? assert(pos >= 0 && pos <= _size);? ? //保证插入的位置在合理范围中
? ? if (_capacity < _size + strlen(str) + 1)
? ? {
? ? ? ? reserve(_size + strlen(str) + 2);
? ? }
? ? for (int i = _size; i >= pos; i--)
? ? {
? ? ? ? _str[i + strlen(str)] = _str[i];
? ? }
? ? int j = 0;
? ? for (int i = pos; i < pos + strlen(str); i++)
? ? {
? ? ? ? _str[i] = str[j++];
? ? }
? ? _size += strlen(str);
? ? return *this;
}
? ? ? ? string容器其它的常规接口有resize、swap、c_str、size、capacity、empty、clear七大函数操作。之前已经说明了这七个接口的功能，它们的实现原理也很简单，这里就不做说明，代码如下：
void swap(string& s)
{
? ? string tem = s;
? ? s = *this;
? ? *this = tem;
}
const char* c_str()const
{
? ? return _str;
}
size_t size()const
{
? ? return _size;
}
size_t capacity()const ??
{
? ? return _capacity;
}
bool empty()const
{
? ? return _size == 0 ? true : false;
}void resize(size_t n, char c = '\0')
{
? ? assert(n >= 0);
? ? for (int i = _size; i < n; i++)
? ? {
? ? ? ? push_back(c);
? ? }
? ? _size = n;
? ? _str[_size] = '\0';
}
void clear()? ? //注意：clear不会清理空间，只是将数据清理掉
{
? ? delete[] _str;
? ? char* str = new char[_capacity];
? ? _str = str;
? ? memcpy(_str, "", 1);
? ? _size = 0;
}
? ? ? ? 以上是对string容器实现的常规接口操作，实现的功能与正规的功能具有差别，这里只需保证我们实现功能用法与正规的一样并保证操作时不会出现bug即可。特别注意的是构造与析构、赋值运算符的模拟实现，这种形式在公司面试和笔试上经常会出现。