String容器的底层实现

String

String是STl中的六大组件之一,里面可以存放字符串,在c语言中同样可以用数组来存放字符串,但是c语言中无法直接使用函数对字符串进行操作,所以使用String类可以避免这些,而这里也符合了c++封装的思想。
在String类中增加了许多接口,专门对字符串进行操作

类成员

String类主要的成员有三个,一个指针,一个有效字符长度,一个容量大小
指针指向的空间用来存放字符串

private:
		char* _str;
		size_t _size;
		size_t _capacity;

构造函数和拷贝构造函数

string(char* str = "")//在无参传入时候,以空字符传入,使用半缺省构造
	:_size(strlen(str))//这里的初始化列表的顺序只和声明类成员顺序有关
	, _capacity(_size)
{
	_str = new char[_capacity + 1];
	strcpy(_str, str);
}

~string() {//析构函数
	delete[] _str;//因为是进行new char[_capacity + 1];所以在释放空间时,
	_capacity = 0;//delete后面需要加[]
	_str = nullptr;
}

void swap(string& s) {
	::swap(_str, s._str);//使用的是库函数的swap函数
	::swap(_size, s._size);
	::swap(_capacity, s._capacity);
}

// s2(s1)现代构造函数方法
string(const string& s)//传入一个string对象
	:_str(nullptr)
{
	string tmp(s._str);//创建一个tmp变量,将s的字符串传入
	//this->swap(tmp);
	swap(tmp);//这里进行交换
}

// s2 = s1;现代拷贝构造函数方法
string& operator = (string str) {//这里进行了传值,会进行一次构造函数来开空间,
	swap(str);					 //所以可以直接使用swap函数来进行交换
	return *this;
}

我们需要注意的是,在string类中,在创建,拷贝,传返回值等都是会深拷贝,所以这时候引用(&)就显得尤为重要,它可以避免我们进行深拷贝,去创建空间,而是直接使用

迭代器

typedef char* iterator;            //由于我们有时候可能会出现我可以进行读写操作,或
typedef const char* const_iterator;//者只能进行读操作,所以会有const的出现

iterator begin() {//返回头节点
	return _str;
}

iterator end() {//返回尾节点
	return _str + _size;
}

const_iterator begin() const{
	return _str;
}

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

在string类中,迭代器本身其实是指针,但是,在别的容器里迭代器本不是指针,至于是什么,在list容器中我会进行解释,迭代器其实还有很多操作,比如+,+=,>>,<<等等,他将我们大多的运算符全都重载一遍,使我们用起来和数组类似,但在这里我没有展示

函数功能

基本功能有尾插,扩容,插入字符串,插入字符,删除字符,开空间

void reserve(size_t n) {//扩容
	if (n > _capacity) {//判断容量是否超过
		char* tmp = new char[n + 1];
		strcpy(tmp, _str);//如果超过了话,则重新创建一个更大的空间,在把之前空间的内容
		delete[] _str;//复制到新的空间中去
		_str = tmp;
		_capacity = n;
	}
};

void push_back(char c) {//尾插,这里和append都可以使用insert函数进行复写
	if (_size >= _capacity) {
		reserve(_capacity * 2);
	}
	_str[_size] = c;
	_size++;
	_str[_size] = '';
}

void append(const char* c) {//插字符串
	size_t len = strlen(c);
	if (_size + len >= _capacity) {
		reserve(_size + len);
	}
	strcpy(_str + _size, c);
	_size += len;
}

//const char& operator[] (size_t num)   只能读
char& operator[] (size_t num) {//同数组一样,可读可写
	return *(_str + num);
}

void resize(size_t n, char ch = ''){
	if (n <= _size) {//当需要的有效空间小于等于_size时,会直接插入
		for (size_t i = 0; i < n; i++)
			*(_str + i) = ch;
		_size = n;
		_str[_size] = '';
	}
	else {//当需要的有效空间大于_size,则要先判断是否要重新扩容,再写入ch
		if (n > _capacity) {
			reserve(n);
		}
		for (size_t i = _size; i < n; i++)//写入ch
			*(_str + i) = ch;
		_size = n;
		_str[_size] = '';
	}
}
//值得注意的是,resize函数,在写入多个''时,即使显示出来的有效字符不变,
//但实际上他并不会在第一个'位置停止读取,后面的''仍然算有效字符

size_t size() const{
	return _size;
}

size_t capacity() const {
	return _capacity;
}

string& insert(size_t pos, char ch) {//插入字符
	assert(pos <= _size);
	if (_size >= _capacity) {//可能会存在_capacity是0的情况,
		size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;//为了避免_capacity是0而产生的报错
		reserve(_size);
	}
	size_t newnode = _size + 1;
	while (newnode > pos) {//移动位置
		_str[newnode] = _str[newnode - 1];
		--newnode;
	}
	_str[pos] = ch;
	_size++;
	return *this;//因为在主函数内变量仍然存在,所以需要*this,同样,返回类型得是string&
}

string& insert(size_t pos, const char* str) {//插入字符串
	assert(pos <= _size);
	size_t len = strlen(str);
	if (_size+len >= _capacity) {
		reserve(_size+len);
	}
	size_t newnode = _size + len;
	while (newnode >= pos+len) {
		_str[newnode] = _str[newnode-len];
		newnode--;
	}
	for (size_t i = 0; i < len; ++i)//把str的字符串写入_str中
	{
		_str[pos + i] = str[i];
	}
	_size += len;
	return *this;
}

string& erase(size_t pos, size_t len = npos) {//删除字符串
	assert(pos < _size);
	if (pos + len >= _size || len == pos) {
		_str[0] = 'n';
		_size = npos;
	}
	else {
		strcpy(_str + pos, _str + pos + len);
		_size -= len;
	}
	return *this;
}
//这里的nops,其实在类的private中定义的全局变量
//static const size_t npos;,
//其次他的初始化是在类的外部定义的,	const size_t string::npos = -1;

在VS19里面,空间的扩容基本上是以1.5倍的方式进行的,但在别的环境中又不一样,比如在linux下是以2倍的方式进行扩容

完整代码

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;
		}

		string(const char* str = "")
			:_size(strlen(str))
			, _capacity(_size)
		{
			_str = new char[_capacity + 1];
			strcpy(_str, str);
		}

		~string() {
			delete[] _str;
			_capacity = 0;
			_str = nullptr;
		}

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

		// s2(s1)
		string(const string& s)
			:_str(nullptr)
		{
			string tmp(s._str);
			//this->swap(tmp);
			swap(tmp);
		}

		// s2 = s1;
		string& operator = (string str) {
			swap(str);
			return *this;
		}

		void reserve(size_t n) {//扩容
			if (n > _capacity) {
				char* tmp = new char[n + 1];
				strcpy(tmp, _str);
				delete[] _str;
				_str = tmp;
				_capacity = n;
			}
		};

		void push_back(char c) {//尾插
			if (_size >= _capacity) {
				reserve(_capacity * 2);
			}
			_str[_size] = c;
			_size++;
			_str[_size] = '';

		}

		void append(const char* c) {//插字符串
			size_t len = strlen(c);
			if (_size + len >= _capacity) {
				reserve(_size + len);
			}
			strcpy(_str + _size, c);
			_size += len;
		}

		char& operator[] (size_t num) {//同数组一样
			return *(_str + num);
		}

		void resize(size_t n, char ch = '')
		{
			if (n <= _size) {
				for (size_t i = 0; i < n; i++)
					*(_str + i) = ch;
				_size = n;
				_str[_size] = '';
			}
			else {
				if (n > _capacity) {
					reserve(n);
				}
				for (size_t i = _size; i < n; i++)
					*(_str + i) = ch;
				_size = n;
				_str[_size] = '';
			}
		}

		//string& operator+=(char ch)

		size_t size() const{
			return _size;
		}

		size_t capacity() const {
			return _capacity;
		}

		string& insert(size_t pos, char ch) {
			assert(pos <= _size);
			if (_size >= _capacity) {
				size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;
				reserve(_size);
			}
			size_t newnode = _size + 1;
			while (newnode > pos) {
				_str[newnode] = _str[newnode - 1];
				--newnode;
			}
			_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);
			}
			size_t newnode = _size + len;
			while (newnode >= pos+len) {
				_str[newnode] = _str[newnode-len];
				newnode--;
			}
			for (size_t i = 0; i < len; ++i)
			{
				_str[pos + i] = str[i];
			}
			_size += len;
			return *this;
		}

		string& erase(size_t pos, size_t len = npos) {
			assert(pos < _size);
			if (pos + len >= _size || len == pos) {
				_str[0] = 'n';
				_size = npos;
			}
			else {
				strcpy(_str + pos, _str + pos + len);
				_size -= len;
			}
			return *this;
		}

		void clear() {
			_str[0] = '';
			_size = 0;
		}
		

	private:
		char* _str;
		size_t _size;
		size_t _capacity;

		static const size_t npos;
	};

	const size_t string::npos = -1;

总结

string容器的底层逻辑其实非常简单,他利用数组存储字符串,但外加各种接口来方便使用,并且重载运算符,将重载后的运算符功能和本身功能一样,由于string对象都是进行深拷贝,所以我们有时候可以利用引用,来减少开空间的负担

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>