C++——STL之vector详解-创新互联

• 🏐1.什么是vector
• 🏐2.vector的使用
• • 🏀2.1vector的实例化
  • 🏀2.2访问遍历vector
  • • ⚽2.2.1**下标+[]**
    • ⚽2.2.2**迭代器**
    • ⚽2.2.3**范围for**
  • 🏀2.3.vector容量问题
  • • ⚽2.3.1size和capacity
    • ⚽2.3.2reserve和resize
  • 🏀3.4.vector中插入/查找/删除
  • • ⚽3.4.1insert
    • ⚽3.4.2erase
    • ⚽3.4.3find
  • 🏀排序（体验泛型排序
  • 🏀push_back
• 🏐vector的实现（含迭代器失效问题）
• • 🏀insert
  • 🏀erase
• 💬一些小点

👀先看这里👈
😀作者：江不平
📖博客：江不平的博客
📕学如逆水行舟，不进则退
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
❀本人水平有限，如果发现有错误的地方希望可以告诉我，共同进步👍

学习了string之后，学习其他模板将会更容易上手，一起来看一下vector吧！

vector是表示大小可以变化的数组的序列容器。

• 就像数组一样，vector对其元素使用连续的存储位置，这意味着也可以使用指向其元素的常规指针上的偏移量来访问其元素，并且与数组中的元素一样有效。但与数组不同的是，它们的大小可以动态变化，它们的存储由容器自动处理。
• 在内部，vector使用动态分配的数组来存储其元素。当插入新元素时，可能需要重新分配此数组以增加大小，这意味着分配新数组并将所有元素移动到该数组。就处理时间而言，这是一项相对昂贵的任务，因此，vector不会在每次将元素添加到容器时重新分配。
• 因此，与数组相比，vector消耗更多的内存，以换取管理存储和以有效方式动态增长的能力。

作为类模板来说，vector只能显式实例化

void test_vector1()
	{vectorv1;
		vectorv2(10, 1);
		vectorv3(v2);//类模板必须显示实例化，要说明类型为int
	}

访问遍历有大概三种方式

相比于string来说，[]返回的不仅仅是char类型，返回的是reference，也就是pos位置数据的引用

void test_vector2()
	{vectorv1;
		v1.push_back(0);
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);

		// 下标+[]
		for (size_t i = 0; i< v1.size(); ++i)
		{	v1[i]++;
		}
		for (size_t i = 0; i< v1.size(); ++i)//相比于string来说，[]返回的不只是char，返回的是pos位置数据元素的引用
		{	cout<< v1[i]<< " ";
		}
		cout<< endl;
}

void test_vector2()
	{vectorv1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		// 迭代器
		vector::iterator it = v1.begin();
		while (it != v1.end())
		{	(*it)--;

			cout<< *it<< " ";
			++it;
		}
		cout<< endl;
	}

void test_vector2()
	{vectorv1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		for (auto e : v1)
		{	cout<< e<< " ";
		}
		cout<< endl;
	}

范围for的底层也是迭代器，可以迭代器就可以用范围for

通过size函数获取当前容器中的有效元素个数，通过capacity函数获取当前容器的大容量。

#include#includeusing namespace std;

int main()
{vectorv(10, 2);
	cout<< v.size()<< endl; //获取当前容器中的有效元素个数
	cout<< v.capacity()<< endl; //获取当前容器的大容量
	return 0;
}

通过reserse函数改变容器的大容量，resize函数改变容器中的有效元素个数。

reserve规则：
 1、当所给值大于容器当前的capacity时，将capacity扩大到该值。
2、当所给值小于容器当前的capacity时，什么也不做。

resize规则：
 1、当所给值大于容器当前的size时，将size扩大到该值，扩大的元素为第二个所给值，若未给出，则默认为0。（也就是将扩容的空间进行了初始化
 2、当所给值小于容器当前的size时，将size缩小到该值。

void TestVectorExpand()
	{size_t sz;
		vectorv;
		//v.resize(100);//resize是不止开辟了空间，还插入了100个数据，这地方不能用
		//v.reserve(100);//空间提前开好，提高效率

		sz = v.capacity();
		cout<< "making v grow:\n";
		for (int i = 0; i< 100; ++i)
		{	v.push_back(i);
			if (sz != v.capacity())
			{		sz = v.capacity();
				cout<< "capacity changed: "<< sz<< '\n';
			}
		}
	}

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

如果在某一特定值位置进行插入或删除，需要用到find函数。不然直接指定位置插入

void test_vector4()
	{vectorv1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		vector::iterator pos = find(v1.begin(), v1.end(), 3);//嫌长也可以用auto
		if (pos != v1.end())//为什么说！=而不是<，因为不一定像string那样是连续的存储空间，比如树
		{	v1.insert(pos, 567);
		}
	}

注意：insert如果插入位置>capacity，那么将会在最后一个位置的下一个位置进行插入，并不会报错（不要有侥幸心理），erase就不一样了，如果删除位置>capacity就会报错。

void test_vector4()
	{vectorv1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

        vector::iterator pos = find(v1.begin(), v1.end(), 3);//嫌长也可以用auto
        pos = find(v1.begin(), v1.end(), 300);//进行erase的时候会报错，没有300这个数的位置（虽然这个时候返回的end位置，但是仍不在capacity内，end表示的是最后一个位置的下一个位置
		if (pos != v1.end())
		{	v1.erase(pos);
		}
	}

vector不提供find，像vector，list等容器，find是通用的，都是在一段迭代器区间去找，所以直接写在了algorithm中，就是个函数模板

• find函数共三个参数，前两个参数确定一个迭代器区间（左闭右开），第三个参数确定所要寻找的值。
• find函数在所给迭代器区间寻找第一个匹配的元素，并返回它的迭代器，若未找到，则返回所给的第二个参数last。

void test_vector4()
	{vectorv1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

        vector::iterator pos = find(v1.begin(), v1.end(), 3);//嫌长也可以用auto
        if (pos != v1.end())
		{v1.insert(pos, 567); //在3的位置插入567
		}
       
        pos = find(v.begin(), v.end(), 3); //获取值为3的元素的迭代器

		if (pos != v1.end())
		{   v1.erase(pos); //删除3
		}
	}

注意：

1. find函数是在算法模块（algorithm）当中实现的，不是vector的成员函数。vector不提供find
2. find的实现只能用!=，不能用<，因为对于string，vector，空间连续，还可以这样干，但是list这些，空间不连续，<根本不能用

以前我们常用qsort函数来实现排序，这次我们看一下

我们来充分理解一下这里的参数**（为什么要有const和&）**，一般来说我们插入数据我们有这么几种方式：

vectorstr;
第一种
string str1;
str1="小彭";
str.push_back(str1);
第二种
str.push_back(string("老彭");
第三种
str.push_back("彭彭");

引用&是有必要的，第一种如果没有引用，那就会进行拷贝构造，开辟空间是个深拷贝，过程代价大，所以避免多次开空间，加&。
我们可以看到const的使用也是有必要的，比如第二种我们使用了匿名对象，像匿名对象，临时对象这种不能改变的量我们都需要加上const，为了避免出现权限放大的问题。
为什么支持第三种写法呢，也是因为有const，我们看到string的构造函数string（const charstr）{}*，这里面有隐式类型的转换,会产生临时变量。（这里涉及到右值引用）
如下

double d=1.1;
int i=d;//这样赋值完全没问题，隐式类型转换
看下面
double d=1.1;
int& i=d;//这样就是错误的，引用的不是d，而是中间的临时变量，而临时变量具有常性，但我们加个const就没有问题了，
再看下面
double d=1.1;
const int& i=d;

看完这里，你估计就明白了
关于范围for加const &也是一样，假如我们要把上面插入的数据输出

for(auto e:str)
{cout<

在这个过程中，底层会发生的是迭代器将每个数据拷贝给范围变量e，又是拷贝！！！所以我们直接写成下面这种

for(const auto& e:str)
{cout<

void insert(iterator pos, const T& x)
		{	assert(pos >= _start);
			assert(pos<= _finish);

			if (_finish == _end_of_storage)
			{		size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len;
			}
			// 挪动数据
			iterator end = _finish - 1;
			while (end >= pos)
			{		*(end + 1) = *end;
				--end;
			}
			*pos = x;

			++_finish;
		}

stl 规定erase返回删除位置下一个位置迭代器
		iterator erase(iterator pos)
		{	assert(pos >= _start);
			assert(pos< _finish);

			iterator begin = pos + 1;
			while (begin< _finish)
			{		*(begin - 1) = *begin;
				++begin;
			}

			--_finish;
			//if (size()< capacity()/2)
			//{	//	// 缩容 -- 以时间换空间
			//}

			return pos;
		}