什么是STL？标准模板库的特点及应用场景解析

输出结果为：

直接利用数组：0 1 2 3 4 5 6 7 8 9 
利用迭代器：0 1 2 3 4 5 6 7 8 9

3.1.4.5二维链表两种定义方式（结果一样）

方式一

方式二

输出结果为：

0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

3.2deque

所谓的deque是”doubleendedqueue”的简写，双端队列不论在尾部或腹部插入元素，都非常迅速。而在中间插入元素则会比较费时，由于必须联通中间其他的元素。双端队列是一种随机访问的数据类型，提供了在序列两端快速插入和删掉操作的功能，它可以在须要的时侯改变自身大小，完成了标准的C++数据结构支队列的所有功能。

Vector是双向开口的连续线性空间，deque则是一种单向开口的连续线性空间。deque对象在队列的两端放置元素和删掉元素是高效的，而向量vector只是在插入序列的末尾时操作才是高效的。deque和vector的最大差别，一在于deque准许于常数时间内对头端进行元素的插入或移除操作，二在于deque没有所谓的capacity观念，由于它是动态地以分段连续空间组合而成，随时可以降低一段新的空间并链接上去。换句话说，像vector那样“因旧空间不足而重新配置一块更大空间，之后复制元素，再释放旧空间”这样的事情在deque中是不会发生的。也为此，deque没有必要提供所谓的空间预留（reserved）功能。

尽管deque也提供RandomAccessIterator，但它的迭代器并不是普通表针，其复杂度和vector不可同日而语，这其实涉及到各个运算层面。为此，除非必要，我们应尽可能选择使用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector脸上，将vector排序后（借助STL的sort算法），再复制回deque。

deque是一种优化了的对序列两端元素进行添加和删掉操作的基本序列容器。一般由一些独立的区块组成，第一区块朝某方向扩充，最后一个区块朝另一方向扩充。它容许较为快速地随机访问但它不像vector一样把所有对象保存在一个连续的显存块，而是多个连续的显存块。而且在一个映射结构中保存对那些块以及次序的跟踪。

3.2.1申明deque容器

#include  // 头文件
deque deq;  // 声明一个元素类型为type的双端队列que
deque deq(size);  // 声明一个类型为type、含有size个默认值初始化元素的的双端队列que
deque deq(size, value);  // 声明一个元素类型为type、含有size个value元素的双端队列que
deque deq(mydeque);  // deq是mydeque的一个副本
deque deq(first, last);  // 使用迭代器first、last范围内的元素初始化deq

3.2.2deque的常用成员函数

deque deq;

deq：拿来访问单向队列中单个的元素。deq.front()：返回第一个元素的引用。deq.back()：返回最后一个元素的引用。deq.push_front(x)：把元素x插入到单向队列的脸部。deq.pop_front()：弹出单向队列的第一个元素。deq.push_back(x)：把元素x插入到单向队列的尾部。deq.pop_back()：弹出单向队列的最后一个元素。

3.2.3deque的一些特征

支持随机访问，即支持以及at()，而且性能没有vector好。可以在内部进行插入和删掉操作，但性能不及list。deque两端都还能快速插入和删掉元素，而vector只能在尾端进行。deque的元素存取和迭代器操作会稍稍慢一些，由于deque的内部结构会多一个间接过程。deque迭代器是特殊的智能表针，而不是通常表针，它须要在不同的区块之间跳转。deque可以包含更多的元素，其max_size可能更大，由于不止使用一块显存。deque不支持对容量和显存分配时机的控制。在不仅首尾两端的其他地方插入和删掉元素，都将会引起指向deque元素的任何pointers、references、iterators失效。不过，deque的显存重分配优于vector，由于其内部结构显示不须要复制所有元素。deque的显存区块不再被使用时，会被释放，deque的显存大小是可削减的。不过，是不是那么做以及如何做由实际操作版本定义。deque不提供容量操作：capacity()和reverse()，然而vector可以。

3.2.4实例

#include
#include
#include
using namespace std;
int main(void)
{
	int i;
	int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
	deque q;
	for (i = 0; i <= 9; i++)
	{
		if (i % 2 == 0)
			q.push_front(a[i]);
		else
			q.push_back(a[i]);
	}                                  /*此时队列里的内容是: {8,6,4,2,0,1,3,5,7,9}*/
	q.pop_front();
	printf("%dn", q.front());    /*清除第一个元素后输出第一个(6)*/
	q.pop_back();
	printf("%dn", q.back());     /*清除最后一个元素后输出最后一个(7)*/
	deque::iterator it;
	for (it = q.begin(); it != q.end(); it++) {
		cout << *it << 't';
	}
	cout << endl;
	system("pause");
	return 0;
}

输出结果：

3.3list3.3.1list定义

List是stl实现的单向数组，与向量(vectors)相比,它容许快速的插入和删掉，并且随机访问却比较慢。使用时须要添加头文件

#include

3.3.2list定义和初始化

listlst1;//创建空list

listlst2(5);//创建富含5个元素的list

listlst3(3,2);//创建富含3个元素的list

listlst4(lst2);//使用lst2初始化lst4

listlst5(lst2.begin(),lst2.end());//同lst4

3.3.3list常用操作函数

Lst1.assign()给list形参

Lst1.back()返回最后一个元素

Lst1.begin()返回指向第一个元素的迭代器

Lst1.clear()删掉所有元素

Lst1.empty()假如list是空的则返回true

Lst1.end()返回末尾的迭代器

Lst1.erase()删掉一个元素

Lst1.front()返回第一个元素

Lst1.get_allocator()返回list的配置器

Lst1.insert()插入一个元素到list中

Lst1.max_size()返回list能容纳的最大元素数目

Lst1.merge()合并两个list

Lst1.pop_back()删掉最后一个元素

Lst1.pop_front()删掉第一个元素

Lst1.push_back()在list的末尾添加一个元素

Lst1.push_front()在list的腹部添加一个元素

Lst1.rbegin()返回指向第一个元素的逆向迭代器

Lst1.remove()从list删掉元素

Lst1.remove_if()按指定条件删掉元素

Lst1.rend()指向list末尾的逆向迭代器

Lst1.resize()改变list的大小

Lst1.reverse()把list的元素倒转

Lst1.size()返回list中的元素个数

Lst1.sort()给list排序

Lst1.splice()合并两个list

Lst1.swap()交换两个list

Lst1.unique()删掉list中相邻重复的元素

3.3.4List使用实例

3.3.4.1迭代器遍历list

  for(list::const_iteratoriter = lst1.begin();iter != lst1.end();iter++)
    {
      cout<<*iter;
    }
    cout<<endl;

3.3.4.2综合实例1

输出结果

3.3.4.3综合实例2

#include  
#include  
 
using namespace std;
typedef list INTLIST;
 
//从前向后显示list队列的全部元素 
void put_list(INTLIST list, char *name)
{
	INTLIST::iterator plist;
 
	cout << "The contents of " << name << " : ";
	for (plist = list.begin(); plist != list.end(); plist++)
		cout << *plist << " ";
	cout << endl;
}
 
//测试list容器的功能 
void main(void)
{
	//list1对象初始为空 
	INTLIST list1;
	INTLIST list2(5, 1);
	INTLIST list3(list2.begin(), --list2.end());
 
	//声明一个名为i的双向迭代器 
	INTLIST::iterator i;
 
	put_list(list1, "list1");
	put_list(list2, "list2");
	put_list(list3, "list3");
 
	list1.push_back(7);
	list1.push_back(8);
	cout << "list1.push_back(7) and list1.push_back(8):" << endl;
	put_list(list1, "list1");
 
	list1.push_front(6);
	list1.push_front(5);
	cout << "list1.push_front(6) and list1.push_front(5):" << endl;
	put_list(list1, "list1");
 
	list1.insert(++list1.begin(), 3, 9);
	cout << "list1.insert(list1.begin()+1,3,9):" << endl;
	put_list(list1, "list1");
 
	//测试引用类函数 
	cout << "list1.front()=" << list1.front() << endl;
	cout << "list1.back()=" << list1.back() << endl;
 
	list1.pop_front();
	list1.pop_back();
	cout << "list1.pop_front() and list1.pop_back():" << endl;
	put_list(list1, "list1");
 
	list1.erase(++list1.begin());
	cout << "list1.erase(++list1.begin()):" << endl;
	put_list(list1, "list1");
 
	list2.assign(8, 1);
	cout << "list2.assign(8,1):" << endl;
	put_list(list2, "list2");
 
	cout << "list1.max_size(): " << list1.max_size() << endl;
	cout << "list1.size(): " << list1.size() << endl;
	cout << "list1.empty(): " << list1.empty() << endl;
 
	put_list(list1, "list1");
	put_list(list3, "list3");
	cout <list3: " < list3) << endl;
	cout << "list1<list3: " << (list1 < list3) << endl;
 
	list1.sort();
	put_list(list1, "list1");
 
	list1.splice(++list1.begin(), list3);
	put_list(list1, "list1");
	put_list(list3, "list3");
	system("pause");
}

输出结果：

3.4map/multimap

map和multimap都须要#include，惟一的不同是，map的通配符key不可重复，而multimap可以，也正是因为这些区别，map支持运算符，multimap不支持运算符。在用法上没哪些区别。

C++中map提供的是一种通配符对容器，上面的数据都是成对出现的,如右图：每一对中的第一个值称之为关键字(key)，每位关键字只能在map中出现一次；第二个称之为该关键字的对应值。

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每位关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，因为这个特点，它完成有可能在我们处理一对一数据的时侯，在编程上提供快速通道。这儿说下map内部数据的组织，map内部自建一颗黑红树(一种非严格意义上的平衡二叉树)，这颗树具有对数据手动排序的功能，所以在map内部所有的数据都是有序的。

3.4.1基本操作函数

begin()返回指向map背部的迭代器

clear(）删掉所有元素

count()返回指定元素出现的次数

empty()假如map为空则返回true

end()返回指向map末尾的迭代器

equal_range()返回特殊条目的迭代器对

erase()删掉一个元素

find()查找一个元素

get_allocator()返回map的配置器

insert()插入元素

key_comp()返回比较元素key的函数

lower_bound()返回通配符>=给定元素的第一个位置

max_size()返回可以容纳的最大元素个数

rbegin()返回一个指向map尾部的逆向迭代器

rend()返回一个指向map背部的逆向迭代器

size()返回map中元素的个数

swap()交换两个map

upper_bound()返回通配符>给定元素的第一个位置

value_comp()返回比较元素value的函数

3.4.2申明

//头文件
#include

3.4.3迭代器

共有八个获取迭代器的函数：*begin,end,rbegin,rend*以及对应的*cbegin,cend,crbegin,crend*。

两者的区别在于，前者一定返回const_iterator，而后者则依照map的类型返回iterator或则const_iterator。const情况下，不容许对值进行更改。如下边代码所示：

map::iterator it;
map mmap;
const map const_mmap;
 
it = mmap.begin(); //iterator
mmap.cbegin(); //const_iterator
 
const_mmap.begin(); //const_iterator
const_mmap.cbegin(); //const_iterator

返回的迭代器可以进行加减操作，再者，假如map为空，则begin=end。

3.4.4插入操作

3.4.4.1用insert插入pair数据

//数据的插入--第一种：用insert函数插入pair数据  
#include 

3.4.4.2用insert函数插入value_type数据

//第二种：用insert函数插入value_type数据，下面举例说明  
  
#include 

3.4.4.3用insert函数进行多个插入

insert共有4个重载函数：

// 插入单个键值对，并返回插入位置和成功标志，插入位置已经存在值时，插入失败
pair insert (const value_type& val);
 
//在指定位置插入，在不同位置插入效率是不一样的，因为涉及到重排
iterator insert (const_iterator position, const value_type& val);
 
// 插入多个
void insert (InputIterator first, InputIterator last);
 
//c++11开始支持，使用列表插入多个   
void insert (initializer_list il);

下边是具体使用示例：

#include 
#include 

3.4.4.4用链表形式插入数据

//第三种：用数组方式插入数据，下面举例说明  
  
#include 

以上三种用法，尽管都可以实现数据的插入，并且它们是有区别的，其实了第一种和第二种在疗效上是完成一样的，用insert函数插入数据，在数据的插入上涉及到集合的惟一性这个概念，即当map中有这个关键字时，insert操作是插入数据不了的linux c++定时器，并且用链表形式就不同了，它可以覆盖先前该关键字对应的值，用程序说明

mapStudent.insert(map::value_type(1,”student_one”));

mapStudent.insert(map::value_type(1,”student_two”));

里面这两条句子执行后，map中1这个关键字对应的值是“student_one”，第二条句子并没有生效，这么这就涉及到我们如何晓得insert句子是否插入成功的问题了，可以用pair来获得是否插入成功，程序如下

pair::iterator,bool>Insert_Pair;

Insert_Pair=mapStudent.insert(map::value_type(1,”student_one”));

我们通过pair的第二个变量来晓得是否插入成功，它的第一个变量返回的是一个map的迭代器，假如插入成功的话Insert_Pair.second应当是true的，否则为false。

下边给出完成代码，演示插入成功与否问题

//验证插入函数的作用效果  
#include 

你们可以用如下程序，看下用链表插入在数据覆盖上的疗效

//验证数组形式插入数据的效果   
#include 

3.4.5查找、删除、交换

查找

// 关键字查询，找到则返回指向该关键字的迭代器，否则返回指向end的迭代器
// 根据map的类型，返回的迭代器为 iterator 或者 const_iterator
iterator find (const key_type& k);
const_iterator find (const key_type& k) const;

删掉

// 删除迭代器指向位置的键值对，并返回一个指向下一元素的迭代器
iterator erase( iterator pos )
 
// 删除一定范围内的元素，并返回一个指向下一元素的迭代器
iterator erase( const_iterator first, const_iterator last );
 
// 根据Key来进行删除， 返回删除的元素数量，在map里结果非0即1
size_t erase( const key_type& key );
 
// 清空map，清空后的size为0
void clear();

交换

// 就是两个map的内容互换
void swap( map& other );

3.4.6容量