STL容器之string&vector

六大组件

1 string类

1.1 auto和范围for

auto关键字 在这里补充2个C++11的小语法，方便我们后面的学习。 在早期C/C++中auto的含义是：使用auto修饰的变量，是具有自动存储器的局部变量，后来这个不重要了。C++11中，标准委员会变废为宝赋予了auto全新的含义即：auto不再是一个存储类型指示符，而是作为一个新的类型指示符来指示编译器，auto声明的变量必须由编译器在编译时期推导而得。*用auto声明指针类型时，用auto和auto没有任何区别，但用auto声明引用类型时则必须加&，当在同一行声明多个变量时，这些变量必须是相同的类型，否则编译器将会报错，因为编译器实际只对第一个类型进行推导，然后用推导出来的类型定义其他变量。auto不能作为函数的参数，可以做返回值，但是建议谨慎使用auto不能直接用来声明数组**

//auto fun()//可以做函数的返回类型，根据返回值的类型推导返回类型
//{
//	return 10;//auto 不能做函数的返回值和参数
//}
//int main()
//{
//	//int a = 0;
//	//auto b = 0;//编译器根据右值推导左值的类型
//	//const auto& a1 = 10;
//
//	// A aa;
//	// auto a2 = aa;//可以推导类类型
//	// auto& a3 = aa;//可以推导引用类类型
//	// auto ptr = &a;//两种取地址推导没有区别
//	// auto* ptr1 = &a;
//     //不能推导数组
//	 //auto array[3] = { 1,2,3 };
//
//	//范围for
//	int arr[4] = { 1,2,3,4 };
//	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
//	{
//		arr[i] = i+1;
//	}
//	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
//	{
//		arr[i] = arr[i]*2;
//		cout << arr[i] << " ";
//	}
//	cout << endl;
//	//范围for,语法糖，从数组arr中依次取出元素赋值给e
//	for (auto e : arr)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	//修改数组中的内容,用引用
//	for (auto& e : arr)
//	{
//		e = 2 * e;
//		cout << e << " ";
//	}
//}

1.2 string 类的扩容机制

15个字符从30开始，后面的容量等于前面的容量加上前面容量的一半

void test4()
{
	string s;
	cout << s.capacity() << endl;
	cout << "make a grow" << endl;
	size_t old = s.capacity();

	s.reserve(10);//提前开好n个字节空间，
				  //如果开的空间比原来的小则不会去动原来的空间和内容
				//反正不会去修改内容
	for (int i=0;i<100;i++)//观察每次扩容的倍数
	{
		s += 'c';
		if (old != s.capacity())
		{
			old = s.capacity();
			cout << "capacity changed:" << old << endl;
		}
	}
}

15
make a grow
capacity changed:31
capacity changed:47
capacity changed:70
capacity changed:105

1.3string的模拟实现注意点

底层维护的三个成员变量为

size_t _size;//有效字符的个数不包括\0
char* _str;//当前申请的堆区空间的起始地址
size_t _capacity;//当前申请的空间的有效容量。不不包括\0
const static size_t npos;//静态成员变量为全局变量，需要在类外丁一初始化
						//类外初始化不能const static一起使用，之用const

申请空间及实现构造函数时的注意点

永远要多开一个char空间给\0,因为字符串就是以\0结尾的

string::string(const char* str="")//声明定义分离只能声明给缺省值
		:_size(strlen(str))//不统计'\0'的长度
	{
		_str = new char[_size + 1];//多开一个空间给斜杆0,
		_capacity = _size;
		strcpy(_str, str);//常量字符串拷贝给自己,斜杆0也拷贝
	}
	//拷贝构造函数
	string::string(const string& str)
	{
		_str = new char[str.capacity()+1];
		strcpy(_str, str.c_str());
		_size = str.size();
		_capacity= str.capacity();
	}

1.4 string类的简单模拟实现

实现源码gitee链接：

c++基础/c++String类模拟实现/pro1/pro1/String.h · 坤坤/c++入门代码及笔记 - 码云 - 开源中国

2vector类

2.1 扩容注意点

//capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2
//倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是
//根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
//reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代
//价缺陷问题。
//resize在开空间的同时还会进行初始化，影响size

2.2模拟实现注意点

底层维护的三个指针变量

typedef T* iterator;
iterator _start=nullptr;//指向数组有效数据开始的指针
iterator _finish = nullptr;//指向数组有效数据结束的位置的下一个位置的指针
iterator _end_of_storage = nullptr;//指向数组空间结束的下一个位置的指针

迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对 指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器 底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即 如果继续使用已经失效的迭代器，程序可能会崩溃)。

对于vector可能会导致其迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、 assign、push_back等。申请空间扩容时，会释放原来的空间地址原来的迭代器失效

#include <iostream>
using namespace std;
#include <vector>
int main()
{
  vector<int> v{1,2,3,4,5,6};
 
  auto it = v.begin();
 
  // 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
  // v.resize(100, 8);
 
  // reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
  // v.reserve(100);
 
  // 插入元素期间，可能会引起扩容，而导致原空间被释放
  // v.insert(v.begin(), 0);
  // v.push_back(8);
 
  // 给vector重新赋值，可能会引起底层容量改变
  v.assign(100, 8);
 
  /*
  出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释
放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块
已经被释放的空间，而引起代码运行时崩溃。
  解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给
it重新赋值即可。
  */
  while(it != v.end())
 {
    cout<< *it << " " ;
    ++it;
 }
  cout<<endl;
  return 0;
}

指定位置元素的删除操作--erase：

#include <iostream>
using namespace std;
#include <vector>
int main()
{
int a[] = { 1, 2, 3, 4 };
vector<int> v(a, a + sizeof(a) / sizeof(int));
// 使用find查找3所在位置的iterator
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
// 删除pos位置的数据，导致pos迭代器失效。
v.erase(pos);
cout << *pos << endl; // 此处会导致非法访问
return 0;
}

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。 以下代码的功能是删除vector中所有的偶数，请问那个代码是正确的，为什么？

#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
	if (*it % 2 == 0)
		v.erase(it);
	++it;//不对，此时迭代器指向的不是被删除的元素的位置的下一个位置了，要更新一下
}
 
return 0;
}
int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
while (it != v.end())
{
	if (*it % 2 == 0)
		it = v.erase(it);
	else
		++it;
}
return 0;
}

深拷贝和浅拷贝问题

使用memcpy拷贝问题假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？

问题分析：

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存 空间中

2. 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

3. 结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为 memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

解决方法:利用自定义对象实现的赋值重载实现深拷贝，如果自定义对象没有实现深拷贝那就会出错。

void reserve(size_t n)
		{
			if (n > capacity()) {
				T* tem = new T[n];
				size_t Old_size = size();
				//从地址2按字节拷贝到地址1,为浅拷贝，被拷贝的对象与拷贝对象所指向的资源是
				// 共用的，delete[]以后会释放指向的资源空间，被拷贝的自定义类型对象
				// 的指针就变成了野指针
				//如果地址2为空，且拷贝字节数为0，也不会报错，如果不为0则报错
				//因为对空指针解引用了
				//memcpy(tem,_start,sizeof(T)*size());	
				for (int i = 0; i < Old_size; i++)
				{
					tem[i] = _start[i];//利用赋值运算符，如果是自定义类型如对象
									   //则调用赋值拷贝实现深拷贝，如果是内置类型
										//则就是简单的赋值
				}

				delete[] _start;
				_finish = tem + Old_size;
				_start = tem;
				_end_of_storage = _start +n;
			}

		}

2.3 vector类的简单模拟实现链接

c++基础/c++Vector(顺序表)/Project1/Project1/vector.h · 坤坤/c++入门代码及笔记 - 码云 - 开源中国

如果对你学习C++有帮助的话，动动小手点个赞吧。