STL之序列式容器

2023-11-12

STL之序列式容器

STL容器即是将运用最广的一些数据结构实现出来，根据其在容器的排列特性，将其分为序列式容器和关联是容器。本文主要记录序列式容器，以及其常用的功能函数。

1、vector

vector和数组一样维护了一个连续的线性空间，vector空间运用较灵活，数组是静态空间一旦配置了就无法修改，而vector是动态空间，随着元素的加入其内部机制会动态扩充空间以容纳新元素。

vector常用功能函数：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*Menu
01-0-输出vector
01-1-vector 相关函数
01-2-vector 容量大小相关
01-3-vector相关算法
*/

void VecPrint(const vector<int> &v);//01-0
void VecCreate(); //01-1
void VecCapacity(); //01-2
void VecAlgorithm(); //01-3
void VecTraverse(); //01-4

//01-0
void VecPrint(const vector<int> &v)
{
	cout<<"Print Vector!"<<endl;
	cout<<'[';
	for(int i=0;i<v.size();i++)
	{
		if(i==v.size()-1)
		{
			cout<<v[i]<<']'<<endl;
		}else
		{
			cout<<v[i]<<',';
		}
	}
}
//01-1
void VecCreate()
{
	//case 1
	//vector 内存空间一般按照2倍方式增长，但是有的编译器可能按照其它算法增长
	vector<int> v1;
	for(int i=0;i<10;i++)
	{
		v1.push_back(i+1);
		cout<<v1[i]<<'\t'<<v1.capacity()<<endl;
	}
	//case 2
	int arr[] = {1,2,3,4,5,6,7,8,9,10};
	vector<int> v2(arr,arr+sizeof(arr)/sizeof(int));
	VecPrint(v2);
	//case 3
	vector<int> v3(10,6);
	VecPrint(v3);
	for(int i=0;i<3;i++)
	{
		v3.pop_back();
		cout<<v3.capacity()<<endl; //空间分配后就不会自动回收
	}
}
void  TestVecCreate()
{
	VecCreate();
}
//01-2
void VecCapacity()
{
	//case 1
	vector<int> v1;
	for(int i=0;i<10;i++)
	{
		v1.push_back(i+1);
	}
	VecPrint(v1);
	cout<<"Size:"<<v1.size()<<'\t'<<"Capacity:"<<v1.capacity()<<endl;
	//case 2
	v1.resize(5);
	cout<<"Size:"<<v1.size()<<'\t'<<"Capacity:"<<v1.capacity()<<endl;
	//case 3 使用swap回收空间
	vector<int>(v1).swap(v1);//通过匿名对象方式回收空间
	cout<<"Size:"<<v1.size()<<'\t'<<"Capacity:"<<v1.capacity()<<endl;
	VecPrint(v1);
}
void TestVecCapacity()
{
	VecCapacity();
}
//01-3
void VecAlgorithm()
{
	//case 1 开辟10万次数据用了多少空间
	std::vector<int> v;
	int *p = NULL;
	int num = 0;
	for (int i = 0; i < 10000; ++i)
	{
		v.push_back(i);
		if(p!=&v[0])
		{
			p = &v[0];
			num++;
		}
	}
	cout<<num<<endl; //重新分配了num次空间
	//case 2 reserve 预留空间,如果知道空间大致数量的话直接通过reserve预留空间，防止多次重新分配空间，从而提高效率
	std::vector<int> v2;
	v2.reserve(10000);
	int *p2 = NULL;
	int num2 = 0;
	for (int i = 0; i < 10000; ++i)
	{
		v2.push_back(i);
		if(p2!=&v2[0])
		{
			p2 = &v2[0];
			num2++;
		}
	}
	cout<<"reserve:"<<num2<<endl; //重新分配了num次空间
	//case 3 数据存存取
	std::vector<int> v3;
	for(int i=0;i<5;++i)
	{
		v3.push_back(i+1);
	}
	cout<<v3.front()<<endl; //去第一个元素
	cout<<v3.back()<<endl; //取最后一个元素
	//case 4 插入删除
	std::vector<int> v4;
	v4.insert(v4.begin(),10);
	VecPrint(v4);
	v4.insert(v4.begin(),5,6);
	VecPrint(v4);
	v4.pop_back();
	VecPrint(v4);
	v4.insert(v4.end(),5,8);
	VecPrint(v4);
	v4.erase(v4.begin());
	VecPrint(v4);
	v4.erase(v4.begin(),v4.end());
	if(v4.empty())
	{
		cout<<"Is empty!\n";
	}
}
void TestVecAlgorithm()
{
	VecAlgorithm();
}
//01-4
void VecTraverse()
{
	std::vector<int> v;
	for(int i=0;i<10;i++)
		v.push_back(i+1);
	VecPrint(v);
	//case 1 逆序遍历
	//逆序输出需要使用revers_iterator迭代器，否则会出错
	for(vector<int>::reverse_iterator it=v.rbegin();it!=v.rend();it++)
	{
		cout<<*it<<'\t';
	}
	cout<<endl;
	//case 2 vector 迭代器是随机访问迭代器 支持跳跃式访问
	vector<int>::iterator itBegin = v.begin();
	itBegin = itBegin +3;
	cout<<*itBegin<<endl;
}
void TestVecTraverse()
{
	VecTraverse();
}

int main(int argc, char const *argv[])
{
//01-1
	//TestVecCreate();
//-01-2
	//TestVecCapacity();
//-01-3
	//TestVecAlgorithm();
//-01-4
	TestVecTraverse();
	return 0;
}

2、deque

deque是一个双向开口的连续线性空间，可在头尾两端分别做元素的删除和插入操作。相对于vector其允许于常数时间内在头部进行插入删除；其没有所谓的容量空间观念，它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来；其没有vector中的重新分配空间-拷贝-释放等过程。

deque常用功能函数如下：

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

/*Menu
02-0-输出deque
02-1- deque创建方法
02-2- deque常用方法
02-3- deque排序方法
*/

void DeqPrint(const deque<int> &d); //02-0
void DeqCreate(); //02-1
void DeqMethod(); //02-2
void DeqAlgorithm(); //02-3

//02-0
void DeqPrint(const deque<int> &d)
{
	cout<<'[';
	for(deque<int>::const_iterator it=d.begin();it!=d.end();it++)
	{
		if(it==d.end()-1)
		{
			cout<<*it<<']'<<endl;	
		}else
		{
			cout<<*it<<',';
		}
	}
}
//02-1
//deque 和vector区别在于其用常数时间在头部插入删除数据
void DeqCreate()
{
	//create method 1
	deque<int> d;
	d.push_back(1);
	d.push_back(2);
	d.push_back(3);
	d.push_back(4);
	DeqPrint(d);
	//create method 2
	deque<int> d2(d.begin(),d.end());
	d2.push_back(100);
	DeqPrint(d2);
	//交换
	cout<<"swap:\n";
	d.swap(d2);
	DeqPrint(d2);
	DeqPrint(d);
}
void TestDeqCreate()
{
	DeqCreate();
}
//02-2
void DeqMethod()
{
	//case 1 
	deque<int> d;
	d.push_back(1);
	d.push_back(2);
	d.push_front(11);
	d.push_front(21);
	DeqPrint(d);
	d.pop_back();
	d.pop_front();
	DeqPrint(d);
	cout<<"Front:"<<d.front()<<'\t'<<"Back:"<<d.back()<<endl;
	//case 2 insert
	deque<int>d2;
	d2.push_back(10);
	d2.push_back(20);
	d2.insert(d2.begin(),d.begin(),d.end());
	DeqPrint(d2);
	//case3 除了头部操作外，其它和vector类似
}
void TestDeqMethod()
{
	DeqMethod();
}
//02-3
bool DeqCompare(int val1,int val2)
{
	return val1>val2;
}
void DeqAlgorithm()
{
	deque<int> d;
	d.push_back(15);
	d.push_back(2);
	d.push_front(11);
	d.push_front(21);
	DeqPrint(d);
	//sort() 正常从小到大
	sort(d.begin(),d.end());
	DeqPrint(d);
	//使用仿函数 设置sort的排序规则
	sort(d.begin(),d.end(),DeqCompare);
	DeqPrint(d);
}
void TestDeqAlgorithm()
{
	DeqAlgorithm();
}

int main(int argc, char const *argv[])
{
//02-1
	//TestDeqCreate();
//02-2
	//TestDeqMethod();
//02-3
	TestDeqAlgorithm();
	return 0;
}

3、stack

stack是一种后进先出的容器，其不允许遍历操作，运行新增、移除、取得顶部元素等操作。

stack常用功能函数如下：

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

/*Menu
03-0- stack输出
03-1- stack 创建
*/

void StaPrint(stack<int> &s); //03-0
void StaCreate(); //03-1

//03-0
void StaPrint(stack<int> &s)
{
	cout<<'[';
	while(s.size()!=0)
	{
		if(s.size()==1)
		{
			cout<<s.top()<<']';
			s.pop();
		}else
		{
			cout<<s.top()<<',';
			s.pop();
		}
	}
	cout<<endl;
}
//03-1
void StaCreate()
{
	stack<int> s;
	s.push(1);
	s.push(2);
	s.push(3);
	StaPrint(s);
	cout<<s.size()<<endl;
}
void TestStaCreate()
{
	StaCreate();
}

int main(int argc, char const *argv[])
{
//03-1
	TestStaCreate();
	return 0;
}

4、queue

queue使用一种先进先出的容器，其不允许遍历操作，其有两个出口，queue允许新增元素、移除元素、从最底端加入、最顶端取出元素。

queue常用功能函数如下：

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

/*Menu
04-0 queue
04-1 queue创建方法
*/

void QuePrint(queue<int> &q); //04-0
void QueCreate(); //04-1

//04-0
void QuePrint(queue<int> &q)
{
	cout<<'[';
	while(!q.empty())
	{
		if(q.size()==1)
		{
			cout<<q.front()<<']';
			q.pop();
		}else
		{
			cout<<q.front()<<',';
			q.pop();
		}
	}
	cout<<endl;
}
//04-1
void QueCreate()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	cout<<"front:"<<q.front()<<'\t'<<"back:"<<q.back()<<endl;
	QuePrint(q);
	cout<<q.size()<<endl;
}
void TestQueCreate()
{
	QueCreate();
}

int main(int argc, char const *argv[])
{
//04-1
	TestQueCreate();
	return 0;
}

5、list

list是双向开口的数据结构，其节点不保证在连续空间，相对于vector，其对资源利用更好，不浪费资源，其插入和删除都是常数时间。其不仅是一个双向链表，还是一个双向环状链表，所以它只需要一个指针便可以完整表现整个链表。其迭代器具备前移、后移的能力，其有一个重要性质：插入操作和接合操作(splice)都不会造成原有的list迭代器失效。

list常用功能函数如下：

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

/*Menu
05-0 list输出
05-1 list创建
05-2 
05-3 
*/

void ListPrint(list<int> &l);//05-0
void ListCreate();//05-1
void ListMethod();//05-2
void ListAlgorithm();//05-3

//05-0
void ListPrint(list<int> &l)
{
	list<int>::iterator it = l.begin();
	int i=0;
	for(;it!=l.end();it++,i++)
	{
		if(i==l.size()-1){
			cout<<*it;
		}else
			cout<<*it<<"->";
	}
	cout<<endl;
}
//05-1
void ListCreate()
{
	//case 1
	list<int> l;
	for(int i=0;i<10;i++)
	{
		l.push_back(i+1);
	}
	ListPrint(l);
	//case 2
	list<int> l2(10,10);
	ListPrint(l2);
	//case 3
	list<int> l3(l.begin(),l.end());
	ListPrint(l3);
}
void TestListCreate()
{
	ListCreate();
}
//05-2
void ListMethod()
{
	list<int> l;
	for(int i=0;i<10;i++)
	{
		l.push_back(i+1);
	}
	//case 1 逆序输出
	//list 不支持随机访问
	int i=0;
	for(list<int>::reverse_iterator it=l.rbegin();it!=l.rend();it++,i++)
	{
		if(i==l.size()-1){
			cout<<*it;
		}else
			cout<<*it<<"->";
	}
	cout<<endl;
	//case 2 插入节点
	list<int> l2;
	l2.push_back(11);
	l2.push_back(12);
	l2.push_back(13);
	l2.push_front(3);
	l2.push_front(2);
	l2.push_front(1);
	ListPrint(l2);
	//case 3 删除节点
	l2.pop_back();
	l2.pop_front();
	ListPrint(l2);
	//case 4 插入操作
	l2.insert(l2.begin(),1);
	l2.insert(l2.end(),13);
	ListPrint(l2);
	//case 5 remove 删除所有与elem值相匹配的元素
	// erase 参数为删除迭代器指向的位置
	l2.push_back(13);
	l2.remove(13);
	l2.erase(l2.begin());
	ListPrint(l2);
	//case 6
	if(!l2.empty())
	{
		cout<<"size:"<<l2.size()<<endl;
	}
	l2.resize(8);//比实际size大就补0
	ListPrint(l2); 
	l2.resize(3);//比实际size小就去前n个
	ListPrint(l2);
	l2.swap(l);
	cout<<"l:\t";
	ListPrint(l);
	cout<<"l2:\t";
	ListPrint(l2);
}
void TestListMethod()
{
	ListMethod();
}
//05-3
bool ListCompare(int val1,int val2)
{
	return val1>val2;
}
void ListAlgorithm()
{
	list<int> l;
	for(int i=0;i<10;i++)
	{
		l.push_back(i+1);
	}
	//case 1
	l.reverse();
	ListPrint(l);
	//case 2
	//sort() 不支持随机迭代器的无法使用系统中的sort函数，可以使用其自带sort功能
	l.sort();
	ListPrint(l);
	//case 3 从大到小
	//如果使用自定义类型，如类成员，必须使用自定义排序规则
	//同理，remove时候，也需要自定义删除规则
	l.sort(ListCompare);
	ListPrint(l);

}
void TestListAlgorithm()
{
	ListAlgorithm();
}

int main(int argc, char const *argv[])
{

//05-1
	//TestListCreate();
//05-2
	//TestListMethod();
//05-3
	TestListAlgorithm();
	return 0;
}

6、说明

当前已在mingw32(gcc 4.9.2)上测试通过。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)