C++标准库中的6种顺序容器

时间：2018-11-29 09:30:01

关键字： c++ 标准库顺序容器

[导读]---- C++标准库定义了6种顺序容器（Sequential Container）类型： vector，deque，list，forward_list，array，string---- 顺

---- C++标准库定义了6种顺序容器（Sequential Container）类型：

vector，deque，list，forward_list，array，string

---- 顺序容器为程序员提供了控制元素存储和访问顺序的能力，这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

对顺序容器内的元素按其位置存储和访问。

---- 标准库中的所有容器都提供了快速顺序访问元素的能力，在以下方面有不同的性能折中：

--1）向容器添加或从容器删除元素的代价。

--2）非顺序访问容器中元素的代价。

vector 可变大小数组，支持快速随机访问。
在尾部之外的位置插入或删除元素可能较慢。 deque 双端队列，支持快速随机访问，在头尾位置插入/删除速度很快。 list 双向链表，只支持双向顺序访问。
在list中的任何位置进行插入/删除操作速度快。 forward_list 单向链表，支持单向顺序访问。插入/删除速度快。 array 固定大小数组 string 与vector相似的容器。

---- deque：双端队列，double-ended queue的简写，发音为“deck”。其实现类似于vector容器，支持随机访问。

主要区别在于：从deque对象的起始位置插入和删除元素的时间是固定的，而不像vector中那样是线性时间的。

所以如果多数操作发生在序列的起始和结尾处，则应考虑使用deque数据结构。

-- 为实现在deque两端执行插入和删除操作的时间为固定的这一目的，deque对象的设计比vector对象更为复杂。

因此，尽管两者都提供对元素的随机访问和在序列中部执行线性时间的插入和删除操作，但vector容器执行这些操作时速度要快些。

---- 标准库还提供了三种顺序容器适配器（adaptors）：stack，queue，priority_queue

---- stack：后进先出（LIFO）堆栈。

---- queue：先进先出（FIFO）队列。

---- priority_queue：有优先级管理的队列。

适配器是根据原始的容器类型所提供的操作，通过定义新的操作接口，来适应基础的容器类型。

1、push_back()

---- 所有顺序容器都支持push_back()操作，提供在容器尾部插入一个元素的功能。

---- 调用push_back函数会在容器尾部创建一个新元素，并使容器的长度加1.

---- 除了push_back之外，list和deque容器类型还提供了push_front()实现在容器首部插入新元素的功能。

2、在顺序容器中添加元素的操作

c.push_back(t) 在容器c的尾部添加值为t的元素。返回void类型 c.push_front(t) 在容器c的首部添加值为t的元素。返回void类型
只适用于list和deque容器类型 c.insert(p,t) 在迭代器p所指向的元素前面插入1个值为t的新元素。
返回指向新添加元素的迭代器。 c.insert(p,n,t) 在迭代器p所指向的元素前面插入n个值为t的新元素。
返回void类型
c.insert(p,b,e) 在迭代器p所指向的元素前面插入由迭代器b和e标记的
范围内的元素。返回void类型

举例说明：

#include#include#include#includeusing namespace std;
int main()
{
	vectorivec;
	ivec.push_back(10);
	vector::iterator itor = ivec.end();
	ivec.insert(itor,5,20);//尾部插入5个20
	for(itor=ivec.begin();itor!=ivec.end();itor++)
	{
		cout<<*itor<<" ";
	}
	cout<<endl<<"ivec.size() = "<<ivec.size()<<endl;
	
	vectorsvec;
	svec.insert(svec.begin(),"china");
	svec.insert(svec.begin(),3,"yan");
	string sarray[4]={"dog","cat","pig","bird"};
	svec.insert(svec.end(),sarray,sarray+4);
	vector::iterator stor;
	for(stor=svec.begin();stor!=svec.end();++stor)
	{
		cout<<*stor<<" ";
	}
	cout<<endl<<"svec.size() = "<<svec.size()<<endl;
	
	listilist;
	ilist.push_back(15);
	ilist.push_front(20);//list and deque can use
	ilist.insert(ilist.begin(),3,8);
	list::iterator iltor;
	for(iltor=ilist.begin();iltor!=ilist.end();++iltor)
	{
		cout<<*iltor<<" ";
	}
	cout<<endl<<"ilist.size() = "<<ilist.size()<<endl;
	system("pause");
	return 0;
}

输出：

3、容器的比较（关系操作符）

---- 相比较的容器必须具有相同的容器类型，而且其元素类型也必须相同。

例如：vector

---- 容器的比较是基于容器内元素的比较。

--1）如果两个容器具有相同的长度而且所有元素都相等，那么这两个容器就相等；否则，它们就不相等。

--2）如果两个容器的长度不相等，但较短的容器中的所有元素都等于较长容器中对应的元素，则称较短的容器小于另一个容器。

--3）如果两个容器都不是对文的初始子序列，则它们的比较结果取决于所比较的第一个不相等的元素。

例如：

ivec1: 1 3 5 7 9 12

ivec2: 0 2 4 6 8 10

ivec3: 1 3 9