STL—vector容器的用法以及算法知识

STL（Stadnard  Template  Library），也就是常说的标准模板库。

STL从意义上来讲，可以分为容器（container）、算法（algorithm）、迭代器（iterator） 

  STL容器中最重要的也就是vector

相信学过C++的同学对vector容器都不陌生，跟数组有很多相似之处，它可以称为一个升级版的数组

与数组的异同：

  vector和数组都可以存放数据，数组也相当于一个容器

  但是数组长度是编程者在之前固定好的数据，而容器可长可短

  ps：在leetcode中，需要返回一部分数据时，return 数组是报错的，这时候就需要容器（vector、deque等）

（一）vector容器的基础用法

  1.和数组一样，使用vector前也需要编程者自己定义

#include
#include     //头文件vector必须加上
using namespace std;
int main()
{
vector<数据类型>容器名；
例如：
vectorv1；
}

2.定义完成后存放数据

#include
#include
using namespace std;
int main()
{
vectorv1;
v1.push_back(0);   //将整数类型的0存放在int类型的v1中
for（int i=1；i<=10;i++）
{
v1.push_back(i);   //通过for循环将1~10添入int类型的v1中
}
}

3.存放数据后将数据输出

#include
#include
using namespace std;
int main()
{
vectorv1;
v1.push_back(0);   //将整数类型的0存放在int类型的v1中
for（int i=1；i<=10;i++）
{
v1.push_back(i);
}
for (vector::iterator it = v1.begin();it != v1.end();it++)   //此处的iterator为迭代器，容器数据输出的工具
	{
		cout << (*it) << "  " ;
	}
	cout << endl;
}

（二）vector容器的初级用法

   1.容器的复制

假如：数据类型为int，复制后为v2，复制前为v1

最常用的方法就是vectorv2(v1)

也可以v2.assign（v1.begin(),v1.end()）

vecotrv2(v1.begin(),v1.end())

vecotrv2(100,10),如果通过迭代器iterator输出，结果为100个数据10

#include
#include
using namespace std;
void PrintVector(vector &v)
{
	for (vector::iterator it = v.begin();it != v.end();it++)
	{
		cout << (*it) << "  " ;
	}
	cout << endl;
}
int main()
{
    vectorv1;
	for (int i = 0;i < 10;i++)
	{
		v1.push_back(i);
	}
	PrintVector(v1);  //通过迭代器来输出结果检验是否赋值完成
	vectorv2(v1.begin(),v1.end());  //将v1赋值给v2
	PrintVector(v2);
	vectorv3(v2);  //将v2赋值给v3
	PrintVector(v3);
	vectorv4(10, 100);  //表示10个100存在vector容器中
	PrintVector(v4);
	vectorv5;
	v5.assign(v4.begin(),v4.end());
	PrintVector(v5);  //将v4赋值给v5
}

  2.容器vector的容量、大小

前面我们提到过，数组的大小是编程者自己定义的，而容器vector大小是计算机内定的，那该如何精确查看呢？

假如：vectorv1

v1.empty()是检测v1中是否有数据

v1.capacity（）是检测v1中有多少数据

resize（）是改变容器vector的大小，如果原来vector数据少于改变后的，则补数据0

如果vector数据多于改变后的，则舍后面数据

#include
#include
using namespace std;
void PrintVector(vectorv)
{
for(vector::iterator it=v.begin();it!=v.end();it++)
 {
   cout<<(*it)<<" ";
 }
   cout<v1;
	for (int i = 0;i < 10;i++)
	{
		v1.push_back(i);
	}
	if(v1.empty())
	{
		cout << "vector为空！" << endl;
	}
	else
	{
		cout << "vector不为空！" << endl;
	}
	int num1 = v1.capacity();
	cout << "v1.capacity = " << num1 << endl;  //vector容器v1的容量
	int num2 = v1.size();
	cout << "v2.size = " << num2 << endl;  //vector容器v1的大小
	//一般情况下容量capacity要比大小size稍微大一些
	v1.resize(15);  //改变容器的size，多余的默认值为0
	PrintVector(v1);
	v1.resize(5);  //改变容器的size，只取vector中前5
	PrintVector(v1);
}

   3.容器vector的插入、删除

我们在前面说到vector增加元素是v.push_back( )是在尾端添加一个元素

    而在尾端删除一个元素就是v.pop_back()

     可以用insert（）在首端插入数据       例：v.insert（v1.begin(),1），首端插入数据1

vector容器的清除

v.erase（v.begin(),v.end()）      //就是从begin（）到end（）全部删除数据

v.clear()                                     //数据直接全部清除

#include
#include
using namespace std;
void PrintVector(vector v)
{
for(vector::iteator it=v.begin();it!=v.end();it++)
  {
    cout<<" "<<(*it)<<;
  }
    cout<v1;
	for (int i = 0;i < 10;i++)
	{
		v1.push_back(i);
	}
	v1.push_back(11);  //尾端插入11
	PrintVector(v1);
	v1.pop_back();  //尾端删除一个元素
	PrintVector(v1);
	v1.insert(v1.begin(), -1);  //在起始位插入-1
	v1.insert(v1.begin(), 2, 1); //在起始位插入2个1
	PrintVector(v1);
	v1.erase(v1.end());
	v1.erase(v1.begin(), v1.end());  //删除vector所有元素
	v1.clear();  //清空vector
	PrintVector(v1);
}

ps:其他容器中，有可以在首端直接添加和删除元素（push_front、pop_front），vector容器不兼容

4.vector容器元素的存储、获取

   在前面已经学到关于存放、获取元素的几种方法，这里讨论一下跟数组一样的获取元素

	vectorv1;
	for (int i = 0;i < 10;i++)
	{
		v1.push_back(i);
	}
	v1.at(5);    //获取下端为5的元素
	cout << "v1第一个元素 ：" << v1.front() << endl;
	cout << "v1最后一个元素 ：" << v1.back() << endl;

5.vector的互换容器

通过swap（）函数交换两个vector容器中的元素，前提定义两个容器的数据类型相同

#include
#include
using namespace std;
void PrintVector(vector v)
{
for(vector::iteator it=v.begin();it!=v.end();it++)
  {
    cout<<" "<<(*it)<<;
  }
    cout<v1, v2;
	for (int i = 0;i < 10;i++)
	{
		v1.push_back(i);
		v2.push_back(9 - i);
	}
	    PrintVector(v1);
		PrintVector(v2);
		cout << "互换后" << endl;
		v1.swap(v2);
		PrintVector(v1);
		PrintVector(v2);
		//通过与匿名对象交换来改变容量大小
		v1.resize(5);
		cout << "v1容量为：" << v1.capacity() << endl;
		cout << "v1大小为：" << v1.size() << endl;
		vector(v1).swap(v1);  //收缩内存
		cout << "v1容量为：" << v1.capacity() << endl;
		cout << "v1大小为：" << v1.size() << endl;
}

ps：这里的收缩内存是为了让容量（capacity）和大小（size）保持一致，避免了内存浪费

  为减少vector在动态扩展容量时的扩展次数，所以reserve（）预留空间。

（三） vector容器的高级用法

  1.vector容器的自定义类型用法，通过用户自定义类型来增添删改一些元素

#include
#include
#include
using namespace std;
class person
{
public:
	person(int n, string na)
	{
		num = n;
		name = na;
	}
	int num;
	string name;
};
int main()
{

	//vector容器的自定义类型用法
	vectorvet;
	person p1(90, "小田");
	person p2(95, "小刘");
	person p3(99, "小明");
	vet.push_back(p1);
	vet.push_back(p2);
	vet.push_back(p3);
	for (vector::iterator it=vet.begin();it != vet.end();it++)
	{
		cout << "  " << (*it).num << (*it).name << endl;
	}
	
}

2.vector容器的嵌套用法（二阶）

vector中再嵌一个vector容器，相当于数组中二维数组

#include
#include
#include
using namespace std;
int main()
{
	
	                 //vetctor容器的嵌套用法
	vector>v;
	vectorvet1;
	vectorvet2;
	vectorvet3;
	vectorvet4;
	for (int i = 0;i < 4;i++)
	{
		vet1.push_back(i + 1);
		vet2.push_back(i + 2);
		vet3.push_back(i + 3);
		vet4.push_back(i + 4);
	}
	v.push_back(vet1);
	v.push_back(vet2);
	v.push_back(vet3);
	v.push_back(vet4);
	for (vector>::iterator it = v.begin();it != v.end();it++)
	{
		for (vector::iterator itr = (*it).begin();itr != (*it).end();itr++)
		{
			cout << " " << (*itr) ;
		}
		cout << endl;
	}
}

（四） vector容器的终极用法

终极用法则是通过算法（algorithm）包含的库函数进行元素的编排

find（）类查找元素

count（）类统计元素个数

sort（）排序算法

random_shuffle() 在指定范围内重新洗牌

merge（）容器元素合并储存在另一容器中

reverse（）反转容器的元素 

copy （）容器内指定范围的元素拷贝到另一容器中

replace （）将容器内指定范围的旧元素修改为新元素

replace_if （）容器内指定范围满足条件的元素替换为新元素

set_intersection （） 求两个容器的交集   

set_union （） 求两个容器的并集

set_difference （）求两个容器的差集

     将几个比较重要的用法用代码块表示出来

1.count类用法

#include
#include
#include
#include
using namespace std;
class person
{
public:
	person(string s,int a)
	{
		name = s;
		age = a;
	}
	string name;
	int age;
};
class compare
{
public:
	bool operator()(int p)
	{
		return p > 5;
	}
};
class compare1
{
public:
	bool operator()(person& p)
	{
		return p.age > 18;
	}
};
void printvector(int val)
{
	cout << val << " ";
}
void printvectorP(person p)
{
	cout << p.name << p.age << endl;
}
int main()
{
	vectorv;
	for (int i = 0;i < 10;i++)
	{
		v.push_back(i + 1);
	}
	//迭代器遍历
	for (vector::iterator it = v.begin();it != v.end();it++)
	{
		cout << " " << *it;
	}
	cout << endl;
	//利用algorithm中for_each
	for_each(v.begin(), v.end(), printvector);
	int num = count(v.begin(), v.end(), 5);
	cout << "元素5出现的个数:" << num << endl;
	cout << "比元素5大的个数:" << count_if(v.begin(), v.end(), compare());
	person p1("iii", 19);
	person p2("kkk", 20);
	person p3("aaa", 15);
	vectorp;
	p.push_back(p1);
	p.push_back(p2);
	p.push_back(p3);
	for_each(p.begin(), p.end(), printvectorP);
	cout << "年龄大于18个数：" << count_if(p.begin(), p.end(), compare1());
}

2.find（）用法

#include
#include
#include
#include
using namespace std;
class person
{
public:
	bool operator==(const person& p1)
	{
		if (name==p1.name && age == p1.age)
		{
			return true;
		}
		else {
			return false;
		}
	}
	person(string nam, int a)
	{
		name = nam;
		age = a;
	}
	string name;
	int age;
}; 
class compare
{
public:
	bool operator()(person& p)
	{
		if (p.age > 18)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
};
int main()
{
	vectorv;
	for (int i = 0;i < 10;i++)
	{
		v.push_back(i + 1);
	}
	vector::iterator it = find(v.begin(), v.end(), 5);
	if (it == v.end())
	{
		cout << "没找到！" << endl;
	}
	else
	{
		cout << "找到！" << *it << endl;
	}
	person p1("田", 19);
	person p2("王", 20);
	person p3("梁", 18);
	person p5("广", 15);
	person p4("gu", 16);
	person p6("ii", 21);
	vectorv1;
	v1.push_back(p1);
	v1.push_back(p2);
	v1.push_back(p3);
	v1.push_back(p4);
	v1.push_back(p5);
	v1.push_back(p6);
	vector::iterator its = find(v1.begin(), v1.end(), p1);
	if (its == v1.end())
	{
		cout << "未找到！" << endl;
	}
	else
	{
		cout << "找到！" << its->name << "  " << its->age << endl;
	}

	//根据所要找寻条件搜索
	vector::iterator iter = find_if(v1.begin(), v1.end(), compare());
	if (iter == v1.end())
	{
		cout << "未找到！" << endl;
	}
	else
	{
		cout << "找到！(单个)" << iter->name << "  " << iter->age << endl;
	}
	
}

3.sort（）用法

#include
#include
#include
#include
using namespace std;
class compare
{
public:
	bool operator()(int a, int b)
	{
		return a > b;
	}
};
void print_(int val)
{
	cout << val << " " ;
}
int main()
{
	vectorv;
	for (int i = 0;i < 10;i++)
	{
		v.push_back(i + 1);
		v.push_back(20 - i);
	}
	//按照从小到大顺序
	cout << "排序前：" << endl;
	for_each(v.begin(), v.end(), print_);
	cout << "排序后：" << endl;
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), print_);
	//按照从大到小的顺序
	cout << "改变大——小顺序后：" << endl;
	sort(v.begin(), v.end(), compare());
	for_each(v.begin(), v.end(), print_);
	//种下随机数种子
	srand((unsigned int)time(NULL));
	random_shuffle(v.begin(), v.end());
	cout << "随机排列之后" << endl;
	for_each(v.begin(), v.end(), print_);
	vectorv1, v2;
	for (int i = 0;i < 5;i++)
	{
		v1.push_back(i);
		v2.push_back(i + 1);
	}
	vectorv3;
	v3.resize(v1.size() + v2.size());
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	cout << " 合并后  " << endl;
	for_each(v3.begin(), v3.end(), print_);
	cout << "反转前：" << endl;
	for_each(v.begin(), v.end(), print_);
	reverse(v.begin(), v.end());
	cout << "反转后" << endl;
	for_each(v.begin(), v.end(), print_);
	return 0;
}

4.其他类算法

#include
#include
#include
#include
using namespace std;
void print_(int val)
{
	cout << val << " " << endl;
}
int main()
{
	vectorv1;
	for (int i = 0;i < 100;i++)
	{
		v1.push_back(i);
	}
	cout << "调用算法累加后：" << endl;
	cout << accumulate(v1.begin(), v1.end(), 0) << endl;
	fill(v1.begin(), v1.end(), 100);
	cout << " 添加元素后：" << endl;
	for_each(v1.begin(), v1.end(), print_);
	vectorv2, v3,v4,v5,v6;
	for (int i = 0;i < 10;i++)
	{
		v2.push_back(i + 1);
		v3.push_back(i + 5);
	}
	//必须给目标容器开辟空间
	v4.resize(v3.size() + v2.size());
	v5.resize(v3.size() + v2.size());
	v6.resize(v3.size() + v2.size());
	cout << "求v2、v3交集：" << endl;
	set_intersection(v2.begin(), v2.end(), v3.begin(), v3.end(), v4.begin());
	for_each(v4.begin(), v4.end(), print_);
	cout << endl;
	cout << "求v2、v3的并集：" << endl;
	set_union(v2.begin(), v2.end(), v3.begin(), v3.end(), v5.begin());
	for_each(v5.begin(), v5.end(), print_);
	cout << endl;
	cout << "求v2、v3的差集：" << endl;
	set_difference(v2.begin(), v2.end(), v3.begin(), v3.end(), v6.begin());
	for_each(v6.begin(), v6.end(),print_);
	cout << endl;
}

    到这里，vector的全部用法已经结束了

跟其他容器相比，vector的用法包括一些库函数较多，用起来比较方便，也是编程者最喜欢的容器

     欢迎大家进行补充！