STL常用容器归纳————序列容器

Posted on | In | Visitors:

目录：

  • vector
    动态连续数组.
    大小可变
    使用的内存是连续的.
    所以支持随机存取
    在末端的增删操作性能好,但是中间的插入删除性能差.
  • deque
    双头队列;
    可在头部和尾部插入删除;
    使用的内存是不连续的, 但是一段一段的;
    随机存取时间复杂度为o(1);
    头尾插入删除基本也是o(1);
    插入删除任意元素是o(n);
  • list
    双向链表
    插入删除元素常量时间;
    增加, 删除, 移动元素, 不会使得其他元素的迭代器失效;

vector

头文件

#include<vector>
using namespace std;

创建

1
2
3
4
vector <type_name> c 		//创建一个空vector
vector <type_name> c1(c2)	//把vector（c2）复制给vector（c1）
vector <type_name> c(n)		//创建一个vector，含有n个数据，数据均已缺省构造产生
vector <type_name> c(n,elem)	//创建一个含有n个elem拷贝的vector

常用成员函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
c.front()		//取第一个元素
c.back()		//取最后一个元素
c.begin()		//取首元素的地址
c.end()			//取尾元素的地址
c.empty()		//判断是否为空
c.clear()		//清空容器中所有数据
c.erase(pos)	//删除迭代器pos位置的元素，返回下一个数据的位置
c.erase(beg,end)//删除[beg,end)区间内的元素，返回下一个数据的位置
c.insert(pos,elem)	//在pos位置插入一个elem拷贝，返回新数据位置
c.insert(pos,n,elem)	//在pos位置插入n个elem数据。无返回值
c.push_back(elem)		//在尾部插入一个元素
c.pop_back()			//从尾部弹出一个元素
c.size()				//返回容器中实际数据的个数
c.capacity()			//返回容器的容量
c.max_size() 			//返回当前vector所能容纳元素数量的最大值
c1.swap(c2);		//将c1和c2的元素互换
swap(c1,c2);
find(beg,end,elem)		//在指定区域内查找指定元素，找不到则返回位置end()

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int i;
	vector<int> iv(2,9);
	cout<<iv.size()<<endl;		//size = 2;
	cout<<iv.capacity()<<endl;	//capacity = 2;

	iv.push_back(1);
	cout<<iv.size()<<endl;		//size = 3;
	cout<<iv.capacity()<<endl;	//capacity = 4;

	iv.push_back(2);
	cout<<iv.size()<<endl;		//size = 4;
	cout<<iv.capacity()<<endl;	//capacity = 4;

	iv.push_back(3);
	cout<<iv.size()<<endl;		//size = 5;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	iv.push_back(4);
	cout<<iv.size()<<endl;		//size = 6;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	
	for(int i = 0;i<iv.size();i++)
		cout<<iv[i]<<' ';		//9 9 1 2 3 4
	cout<<endl;

	iv.push_back(5);
	cout<<iv.size()<<endl;		//size = 7;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	iv.pop_back();
	iv.pop_back();
	cout<<iv.size()<<endl;		//size = 5;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	vector<int>::iterator ivite = find(iv.begin(),iv.end(),1);
	if(ivite != iv.end())	
		iv.erase(ivite);
	cout<<iv.size()<<endl;		//size = 4;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	for(int i = 0;i<iv.size();i++)
		cout<<iv[i]<<' ';		//9 9 2 3 
	cout<<endl;	
	ivite = find(iv.begin(),iv.end(),2);
	if(ivite != iv.end())	
		iv.insert(ivite,3,7);

	cout<<iv.size()<<endl;		//size = 7;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	
	for(int i = 0;i<iv.size();i++)
		cout<<iv[i]<<' ';		//9 9 7 7 7 2 3
	cout<<endl;

	iv.clear();
	cout<<iv.size()<<endl;		//size = 0;
	cout<<iv.capacity()<<endl;	//capacity = 8;	
}

deque

头文件

#include<deque>
using namespace std;

创建

1
2
3
4
5
deque<type> c;			//创建空的deque
deque<type> c1(c);		//把c复制给c1
deque<type> c(n);		//创建n个元素的deque，数据均由缺省构造函数产生
deque<type> c(n,elem)	//有n个元素数值均为elem的deque
						//等价于c.assign(n,elem)

常用成员函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c.at(index);	//返回索引index所指的数据，如果越界抛出错误
c.front();		//返回第一个数据
c.back();		//返回最后一个数据
c.begin();		//返回第一个数据的迭代器
c.end();		//返回最后一个数据的下一个位置的迭代器
c.push_back(elem);	//尾插
c.push_front(elem);	//头插
c.pop_back();		//尾删
c.pop_front();		//头删
c.insert(pos,elem);	//pos位置插入elem元素，返回新数据位置
c.insert(pos,n,elem);//pos位置插入n个elem元素，无返回值
c.erase(pos);		//删除pos位置的数据，返回下一个元素位置
c.erase(begin,end)	//删除[begin,end)区间内的数据，返回下一个数据的位置
c.empty();			//判空
c.size();			//返回容器中实际数据的数量
c.max_size();		//返回容器中最大数据的数量

c1.swap(c2);		//将c1和c2的元素互换
swap(c1,c2);
find(beg,end,elem)		//在指定区域内查找指定元素，找不到则返回位置end()

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<deque>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	deque<int> ideq(20,9);
	cout<<"size = "<<ideq.size()<<endl;		//size = 20
	//现在该deque有20个元素，且初值均为9，缓冲区大小为32bytes

	for(int i = 0;i<ideq.size();i++)
		ideq[i] = i;
	for(int i = 0;i<ideq.size();i++)
		cout<<ideq[i]<<" ";		//0 1 2 ... 19
	cout<<endl;
	for(int i = 0;i<3;i++)
		ideq.push_back(i);
	for(int i = 0;i<ideq.size();i++)
		cout<<ideq[i]<<" ";		//0 1 2 ... 19 0 1 2
	cout<<endl;
	cout<<"size = "<<ideq.size()<<endl;		//size = 23

	ideq.push_back(3);		//先配置新的缓冲区，再设妥新元素内容，更改finish状态
	for(int i = 0;i<ideq.size();i++)
		cout<<ideq[i]<<" ";		//0 1 2 ... 19 0 1 2 3
	cout<<endl;
	cout<<"size = "<<ideq.size()<<endl;		//size = 24

	ideq.push_front(99);
	ideq.push_front(98);
	ideq.push_front(97);
	for(int i = 0;i<ideq.size();i++)
		cout<<ideq[i]<<" ";		//97 98 99 0 1 2 ... 19 0 1 2 3
	cout<<endl;
	cout<<"size = "<<ideq.size()<<endl;		//size = 27

	deque<int>::iterator itr;
	itr = find(ideq.begin(),ideq.end(),99);
	if(itr!=ideq.end()){
		cout<<*itr<<endl;		//99
	}
	ideq.erase(find(ideq.begin(),ideq.end(),97));
		cout<<ideq.front()<<endl;		//98
	ideq.pop_back();
	ideq.pop_front();
	cout<<"size = "<<ideq.size()<<endl;		//size = 25
	for(int i = 0;i<ideq.size();i++)
		cout<<ideq[i]<<" ";		// 98 99 0 1 2 ... 19 0 1 2 
	
	return 0;
}

list

头文件

#include<list>
using namespace std;

创建

1
2
3
4
list<type> c;			//创建空的list
list<type> c1(c);		//把c复制给c1
list<type> c(n);		//创建n个元素的list，数据均由缺省构造函数产生
list<type> c(n,elem)	//有n个元素数值均为elem的list

常用成员函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
c.front();			//返回第一个数据
c.back();			//返回最后一个数据
c.begin();			//返回第一个数据的迭代器
c.end();			//返回最后一个数据的下一个位置的迭代器
c.push_back(elem);	//尾插
c.push_front(elem);	//头插
c.pop_back();		//尾删
c.pop_front();		//头删
c.empty();			//判空
c.size();			//返回容器中实际数据的数量
c.max_size();		//返回容器中最大数据的数量
c.erase(pos);		//删除pos位置的数据，返回下一个元素位置
c.insert(pos,elem);	//pos位置插入elem元素，返回新数据位置
c.insert(pos,n,elem);//pos位置插入n个elem元素，无返回值
c.erase(begin,end)	//删除[begin,end)区间内的数据，返回下一个数据的位置
c.remove(elem) 		//删除链表中指定的元素( 匹配元素全部删除)
c.reverse() 		//反转链表
c.sort() 			//对链表排序，默认升序( 可自定义回调函数 )
					//L1.sort( );  L1(1,3,4,4,5)
					//L1.sort( greater <int >() );  L1(5,4,4,3,1)
c.unique() 			//删除相邻重复元素,使之只剩一个
c.swap(c2) 			//交换两个链表	
find(beg,end,elem)		//在指定区域内查找指定元素，找不到则返回位置end()

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<list>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int i;
	list<int> ilist;
	cout<<"size:"<<ilist.size()<<endl;		//size = 0
	for(i = 0;i<5;i++)
		ilist.push_back(i);
	cout<<"size:"<<ilist.size()<<endl;		//size = 5
	list<int>::iterator ite;
	for(ite = ilist.begin();ite!=ilist.end();++ite)
		cout<<*ite<<' ';					//0 1 2 3 4
	cout<<endl;
	
	ite = find(ilist.begin(),ilist.end(),3);
	if(ite!=ilist.end())
		ilist.insert(ite,99);
	cout<<"size:"<<ilist.size()<<endl;		//size = 6
	cout<<*ite<<endl;						//3
	for(ite = ilist.begin();ite!=ilist.end();++ite)
		cout<<*ite<<' ';					//0 1 2 99 3 4
	cout<<endl;
	ite = find(ilist.begin(),ilist.end(),1);
	if(ite!=ilist.end())
		cout<< *(ilist.erase(ite))<<endl;	//2
	
	for(ite = ilist.begin();ite!=ilist.end();++ite)
		cout<<*ite<<' ';					//0 2 99 3 4
	cout<<endl;
	
	int iv[5] = {5,6,7,8,9};
	list<int> ilist2(iv,iv+5);
	ite = find(ilist.begin(),ilist.end(),99);
	ilist.splice(ite,ilist2);				//0 2 5 6 7 8 9 99 3 4
	ilist.reverse();						//4 3 99 9 8 7 6 5 2 0
	ilist.sort();							//0 2 3 4 5 6 7 8 9 99
	return 0;
}