STL

STL

The Standard Template Library (STL) is a set of C++ template classes to provide common programming data structures and functions such as lists, stacks, arrays, etc. It is a library of container classes, algorithms, and iterators. It is a generalized library and so, its components are parameterized. A working knowledge of template classes is a prerequisite for working with STL.

STL has four components

• Algorithms
• Containers
• Functions
• Iterators

标准模板库

标准模板库（standard template library,简写为STL）是用模板定义的一组类和函数。
STL定义了一组常用的数据结构，如向量，链表，集合，映射等，这些数据结构都被称为容器（container），为什么叫做容器呢？在我们的生活中，容器就是用来装一堆东西的。在这里，它们都用来管理一组元素，所以称之为容器。
STL定义了一组常用的算法，如排序，查找，集合计算（交集，并集）等。

容器

容器是什么？一个数组其实就是一个容器，管理某种类型的一个元素序列，每个元素都可按下标随机访问。数组作为容器的特点就是连续空间，固定大小，随机访问。缺点就是不容易在数组中间插入或者删除一个元素，因为会导致后面的元素逐个后移或前移。

STL容器是一组类模板，用来管理元素的序列。一个容器中的多个元素都具有相同类型，可以是基本类型，也可以是自定义类型。
容器可分为三大类：
序列容器（sequence container）、关联容器（associative container）和容器适配器（container adapter）
一、序列容器能维护插入元素的顺序，包括vector，deque,list等
二、关联容器按预定义顺序管理所插入元素，包括set,multiset,map,multimap
三、容器适配器是基于头等容器而建立的简单容器，包括stack，queue,priority_queue等。
序列容器与关联容器统称为头等容器（first-class container），意思是编程首选容器。

各类容器特点

容器名	中文名	头文件	特点	备注
vector <T>	向量	<vector>	适合在序列尾端加入或删除元素：适合随机访问元素	随机访问按下标，下标范围为[0,size()-1];不合适中间插入或删除
deque <T>	双端队列	<deque>	适合在序列两端加入或删除元素；适合随机访问元素	全称为double-ended queue 不合适中间插入或者删除
list<T>	链表	<list>	适合在序列中间插入或删除元素；适合双向遍历元素	双向链表实现，不适合随机访问
set<T>	集合	<set>	各元素不重复；适合双向遍历	元素按值升序排序；各元素值唯一，称为键key;不适合随机访问
multiset<T>	多集	<set>	可重复元素；可双向遍历元素	元素按值升序排序，各元素值不唯一，称为键key;不适合随机访问
map<T>	映射单射	<map>	元素是对偶pair<key,value>一对一，多对一；键不重复；适合双向遍历	各元素按键升序排序；各元素的键是一个集合
multimap	多射多值映射	<map>	元素是对偶pair<key,value>一对多，多对多；键可重复；适合双向遍历	各元素按键生按升序排序；各元素的键是一个多集
stack<T>	栈	<stack>	先进后出LIFO；不支持迭代器	用成员函数来操作元素，基于deque实现
queue<T>	队列	<queue>	先进先出FIFO；不支持迭代器	用成员函数来操作元素；基于deque 实现
priority_queue<T>	优先队列	<queue>	最高优先级先出；不支持迭代器	用成员函数来操作元素；基于vector实现；

STL还提供几种仿容器（near container）:
一、数组array和可变长数组valarray:任何一个数组都可以看作是一个容器，下标看作迭代器。
二、String字符串类型
三、bitset位集

迭代器

迭代器是什么？以数组为例，访问一个数组元素要使用下标，如a[i],则下标就是数组元素的迭代器。下标本质上是一个指针，指向要访问的那个元素。迭代器是用来访问容器中的元素的一种数据结构，是指针的抽象，但更安全，功能更强。
不论是范性思维或者STL的实际运用，迭代器（iterators）都扮演者重要角色。STL的中心思想在于：将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以一贴胶着剂将它们撮合在一起。

算法

STL算法包括<algorithm>与<numeric>

vector

vector的数据安排以及操作方式，与array非常相似。两者的唯一差别在于空间的运用的灵活性。array是静态空间，一旦配置了就不能改变。要换个大或小一点的房子，可以一切琐细得由客户端自己来：首先配置一块新空间，然后将元素从旧址一一搬到新址，再把原来的空间释放还给系统。vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必担心空间不足而一开始就要求一个大块头的array了，我们可以安心使用vector，吃多少用多少。
注意：所谓扩充空间，不论多大，是配置新空间->数据移动->释放旧空间的过程，工程浩大。所谓动态增加大小，并不是在原空间之后连续新空间，因为无法保证原空间之后尚有可配置的空间，而是以原大小两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之一构造新元素，并释放原空间。因此对vector的任何操作，一旦引起空间空间重新配置，指向原vector的所有迭代器就都失效了。

vector::vector()函数 功能 构造函数

#include<iostream>
#include<vector>
using namespace std;
int main(){
    //vector::vector()函数 功能 构造函数
   //constructors used in the same order as described above:
   vector<int>first;//empty vector of ints
   vector<int>second(4,11);//four ints with value 100
   vector<int>third(second.begin(),second.end());
   //iterating through second
   vector<int>fourth(third);//copy of third
   //the iterator constructor can also be used to construct from arrays
   int myints[]={1998,11,3,5,2,0,13,14};
   vector<int>fifth(myints,myints+sizeof(myints)/sizeof(int));
   
   cout<<"The contents of first are:";
   for(int i=0;i<first.size();i++){
   	    cout<<" "<<first[i];
   }
   cout<<endl;
   cout<<"The contents of second are:";
   for(int i=0;i<second.size();i++){
   	     cout<<" "<<second[i];
   }
   cout<<endl;
  
   cout<<"The contents of third are:";
   for(int i=0;i<third.size();i++){
   	     cout<<" "<<third[i];
   }
   cout<<endl;
 
   cout<<"The contents of fourth are:";
   for(int i=0;i<fourth.size();i++){
   	     cout<<" "<<fourth[i];
   }
   cout<<endl;
   cout<<"The contents of fifth are:";  
   for(int i=0;i<fifth.size();i++){
    	cout<<" "<<fifth[i];
   }
   cout<<endl;
}

运行结果：

The contents of first are:
The contents of second are: 11 11 11 11
The contents of third are: 11 11 11 11
The contents of fourth are: 11 11 11 11
The contents of fifth are: 1998 11 3 5 2 0 13 14

vector::operator=()函数 功能：对vector进行赋值

#include<iostream>
#include<vector>
using namespace std;
int main(){
	 //vector::operator=()函数 功能：对vector进行赋值
	vector<int>first(3,1);
	vector<int>second(5,0);
	cout<<"first contains:";
	for(int i=0;i<first.size();i++){
		cout<<" "<<first[i];
	}
	cout<<endl;
	
    first=vector<int>(6,2);
    cout<<"first contains:";
	for(int i=0;i<first.size();i++){
		cout<<" "<<first[i];
	}
	cout<<endl;
	cout<<"Size of first:"<<int(first.size())<<endl;
	second=first;
	first=vector<int>();
	cout<<"Size of first:"<<int(first.size())<<endl;
	cout<<"Size of second:"<<int(second.size())<<endl;
}

运行结果：

first contains: 1 1 1
first contains: 2 2 2 2 2 2
Size of first:6
Size of first:0
Size of second:6

vector::operator 函数 功能：获取指定位置

#include<iostream>
#include<vector>
using namespace std;
int main(){
	 //vector::operator[]()函数 功能：获取指定位置
	vector<int>myvector(10);//10 zero-initialized elements
	unsigned int i;
	vector<int>::size_type sz=myvector.size();
	//assign some values:
	for(i=0;i<sz;i++)myvector[i]=i;
	cout<<"myvector contains:";
	for(int i=0;i<myvector.size();i++){
		cout<<" "<<myvector[i];
	}
	cout<<endl;
	for(int i=0;i<sz/2;i++){
		int temp;
		temp=myvector[sz-1-i];
		myvector[sz-1-i]=myvector[i];
		myvector[i]=temp;
	}
		cout<<"myvector contains:";
	for(int i=0;i<myvector.size();i++){
		cout<<" "<<myvector[i];
	}
	cout<<endl;
}

运行结果

myvector contains: 0 1 2 3 4 5 6 7 8 9
myvector contains: 9 8 7 6 5 4 3 2 1 0

vector::assign()函数 功能：对vector中的元素赋值

//vector::assign()函数
//功能：对vector容器中的元素赋值
//定义：template<class InputIterator>
//void assign(InpputIterator first ,InputIterator last);
//void assign(size_type n,const T&u);
//头文件<vector>
//vector assign
#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::assign()功能：对vector中的元素赋值 
	vector<int>first;
	vector<int>second;
	vector<int>third;
	first.assign(7,100);//a repetition 7 times of value 100
	vector<int>::iterator it;
	it=first.begin()+1;
	second.assign(it,first.end()-1);//the 5 central values of first
	int myints[]={1949,10,1};
	third.assign(myints,myints+3);//assigning from array
	cout<<"Size of first:"<<int(first.size())<<endl;
	cout<<"Size of second:"<<int(second.size())<<endl;
	cout<<"Size of thied:"<<int(third.size()) <<endl;
}

运行结果

Size of first:7
Size of second:5
Size of thied:3

vector::begin()函数 功能：返回第一个元素的迭代器

vector::end()函数 功能：返回最末元素的迭代器(注：实指向最末元素的下一个位置）

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::begin()函数 功能：返回第一个元素的迭代器
	//vector::end()函数 功能：返回最末元素的迭代器(注：实指向最末元素的下一个位置）
	vector<int>myvector;
	for(int i=1;i<=5;i++){
		myvector.push_back(i);
	}
	vector<int>::iterator it;
	cout<<"myvector contains:";
	for(it=myvector.begin();it<myvector.end();it++){
		cout<<" "<<*it; 
	}
	cout<<endl; 	 
}

运行结果

myvector contains: 1 2 3 4 5

vector::rbegin()函数 功能：返回vector尾部的逆迭代器

vector::rend()函数 功能：返回vector起始的逆迭代器

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::rbegin()函数 功能：返回vector尾部的逆迭代器
    //vector::rend()函数 功能：返回vector起始的逆迭代器 
	vector<int>myvector;
	for(int i=1;i<9;i++){
		myvector.push_back(i);
	}
	cout<<"myvector contains:";
	vector<int>::reverse_iterator rit;
	for(rit=myvector.rbegin();rit<myvector.rend();rit++){
		cout<<" "<<*rit;
	}
	cout<<endl;
	
	cout<<"myvector contains:";
	vector<int>::iterator it;
	for(it=myvector.begin();it<myvector.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;	 
}

运行结果

myvector contains: 8 7 6 5 4 3 2 1
myvector contains: 1 2 3 4 5 6 7 8

vector::back()函数 功能：返回末一个元素

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::back()函数 功能：返回最末一个元素 
	vector<int>myvector;
	myvector.push_back(10);
	while(myvector.back()!=0){
		myvector.push_back(myvector.back()-1); 
	}
	cout<<"myvector contains:";
	for(unsigned i=0;i<myvector.size();i++)
	  cout<<" "<<myvector[i];
	cout<<endl;
}

运行结果

myvector contains: 10 9 8 7 6 5 4 3 2 1 0

vector::front()函数 功能：返回第一个元素

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::front()函数 功能：返回第一个元素
	vector<int>myvector;
	myvector.push_back(11);
	myvector.push_back(3);
	//now front equals 11,and back 3
	myvector.front()-=myvector.back();
	cout<<"myvector.front() is now:"<<myvector.front()<<endl; 
}

运行结果

myvector.front() is now:8

vector::push_back()函数 功能：在vector最后添加一个元素

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::push_back()函数 功能：在vector最后添加一个元素
	vector<int>myvector;
	int myint;
	cout<<"please enter some integers(enter 0 to end):\n";
	do{
		cin>>myint;
		myvector.push_back(myint);
	}while(myint);
	cout<<"myvector contains:";
	for(int i=0;i<myvector.size();i++){
	cout<<" "<<myvector[i]; 
	}
	cout<<endl;
	cout<<"myvector stores "<<(int)myvector.size()<<" numbers\n";
}

运行结果

please enter some integers(enter 0 to end):
1
2
3
4
5
9
0
myvector contains: 1 2 3 4 5 9 0
myvector stores 7 numbers

vector::pop_back()函数 功能：移除最后一个元素

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::pop_back()函数 功能：移除最后一个元素
	vector<int>myvector;
	int sum(0);
	myvector.push_back(1);
	myvector.push_back(2);
	myvector.push_back(3);
	while(!myvector.empty()){
		sum+=myvector.back() ;
		myvector.pop_back(); 
	}
	cout<<"The elements of myvector summed: "<<sum<<endl;
}

运行结果

The elements of myvector summed: 6

vector:insert()函数 功能：插入元素到vector中

#include<iostream>
#include<vector>
using namespace std;
int main(){
    //vector:insert()函数 功能：插入元素到vector中
	vector<int>myvector(3,11);
	vector<int>::iterator it;
	it=myvector.begin();
	it=myvector.insert(it,1998);
	myvector.insert(it,2,16);
	//it no longer valid ,get a new one
	it=myvector.begin();
	vector<int>anothervector(3,15);
	myvector.insert(it+2,anothervector.begin(),anothervector.end());
	int myarray[]={1999,2,13};
	myvector.insert(myvector.begin(),myarray,myarray+3);
	cout<<"myvector contains:  ";
	for(it=myvector.begin();it!=myvector.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
}

运行结果

myvector contains:   1999 2 13 16 16 15 15 15 1998 11 11 11

vector::erase()函数 功能：删除指定元素

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::erase()函数 功能：删除指定元素
	vector<int>myvector;
	//set some values(from1 to 10)
	for(int i=0;i<10;i++){
	myvector.push_back(i);}
	//erase the 6th element
	myvector.erase(myvector.begin()+5);
	cout<<"myvector contains:";
	vector<int>::iterator it;
	
	for(it=myvector.begin();it<myvector.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	myvector.erase(myvector.begin(),myvector.begin()+3);
	cout<<"myvector contains:";
	for(int i=0;i<myvector.size();i++){
		cout<<" "<<myvector[i];
	}
	cout<<endl;	 
}

运行结果

myvector contains: 0 1 2 3 4 6 7 8 9
myvector contains: 3 4 6 7 8 9

vector::clear()函数 功能：清空所有元素

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::clear()函数 功能：清空所有元素
    unsigned int i;
    vector<int>myvector;
    myvector.push_back(1);
    myvector.push_back(2);
    myvector.push_back(3);
    cout<<"myvector contains:";
    for(i=0;i<myvector.size();i++){
    	cout<<" "<<myvector[i];
	}
	cout<<endl;
	myvector.clear();
	myvector.push_back(2000);
	myvector.push_back(3000);
	vector<int>::iterator it;
	cout<<"myvector contains:";
	for(it=myvector.begin();it<myvector.end();it++){
		cout<<" "<<*it;
	}
}

运行结果

myvector contains: 1 2 3
myvector contains: 2000 3000

vector::empty()函数 功能判断vector是否为空,(返回true时为空）

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::empty()函数 功能判断vector是否为空,(返回true时为空）
	vector<int>myvector;
	int sum(0);
	for(int i=1;i<=10;i++){
		myvector.push_back(i);
	} 
	while(!myvector.empty()){
		sum+=myvector.back();
		myvector.pop_back();
	}
	cout<<"total:"<<sum<<endl;
}

运行结果

total:55

vector::size()函数 功能：返回vector元素数量大小

#include<iostream>
#include<vector>
using namespace std;
int main(){
	 //vector::size()函数 功能：返回vector元素数量大小
	vector<int>myints;
	cout<<"0.size: "<<int(myints.size())<<endl;
	for(int i=0;i<11;i++){
		myints.push_back(i);
	}
	cout<<"1.size: "<<int(myints.size())<<endl;
	
	myints.insert(myints.end(),11,3);
	cout<<"2.size: "<<int(myints.size())<<endl;
	for(int i=0;i<myints.size();i++){
		cout<<" "<<myints[i];
	}
	cout<<endl;
	myints.pop_back();
	cout<<"3.size: "<<int(myints.size())<<endl;
}

运行结果

0.size: 0
1.size: 11
2.size: 22
 0 1 2 3 4 5 6 7 8 9 10 3 3 3 3 3 3 3 3 3 3 3
3.size: 21

vector::resize()函数 功能：改变vector元素数量的大小

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::resize()函数 功能：改变vector元素数量的大小
	vector<int>myvector;
	for(int i=0;i<10;i++){
		myvector.push_back(i);
	} 
	cout<<"myvector contains:";
	for(int i=0;i<myvector.size();i++){
		cout<<" "<<myvector[i];
	}
	cout<<endl;
	myvector.resize(5);
	cout<<"myvector contains:";
	for(int i=0;i<myvector.size();i++){
		cout<<" "<<myvector[i];
	}
	cout<<endl;
	myvector.resize(11,3);
	cout<<"myvector contains:";
	for(int i=0;i<myvector.size();i++){
		cout<<" "<<myvector[i];
	}
	cout<<endl;
	myvector.resize(16);
	cout<<"myvector contains:";
	for(int i=0;i<myvector.size();i++){
		cout<<" "<<myvector[i];
	}
	cout<<endl;
}

运行结果

myvector contains: 0 1 2 3 4 5 6 7 8 9
myvector contains: 0 1 2 3 4
myvector contains: 0 1 2 3 4 3 3 3 3 3 3
myvector contains: 0 1 2 3 4 3 3 3 3 3 3 0 0 0 0 0

vector::swap()函数 功能：交换两个vector

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::swap()函数 功能：交换两个vector
	vector<int>first(3,10);//three ints with a value of 10
	vector<int>second(5,20);//five ints with a value of 20
	cout<<"first contains:";
	for(int i=0;i<first.size();i++){
		cout<<" "<<first[i];
	}
	cout<<endl;
	cout<<"second contains:";
	for(int i=0;i<second.size();i++){
		cout<<" "<<second[i];
	}
	cout<<endl;
	 
    
	first.swap(second);
	cout<<"first contains:";
	for(int i=0;i<first.size();i++){
		cout<<" "<<first[i];
	}
	cout<<endl;
	cout<<"second contains:";
	for(int i=0;i<second.size();i++){
		cout<<" "<<second[i];
	}
	cout<<endl;
}

运行结果

first contains: 10 10 10
second contains: 20 20 20 20 20
first contains: 20 20 20 20 20
second contains: 10 10 10

vector::get_allocator()函数 功能：返回vector的内存分配器

#include<iostream>
#include<vector>
using namespace std;
int main(){
	//vector::get_allocator()函数 功能：返回vector的内存分配器
	vector<int>myvector0;
	int *p;
	//allocate an array of 10 elements using vector's allocator
	p=myvector0.get_allocator().allocate(5);
	
	//assign some values to array
	for(int i=0;i<5;i++){
		p[i]=i; 
	} 
	cout<<"The allocated array contains:";
	for(int i=0;i<5;i++){
		cout<<" "<<p[i];
	}
	cout<<endl;
    vector<int>myvector(3,1);
    vector<int>::iterator it;
    
    it=myvector.begin();
    it=myvector.insert(it,2);
    myvector.insert(it,3);
    //"it" no longer valid,get a new one;
    it=myvector.begin();
    vector<int>anthervector(2,4);
    
    myvector.insert(it+2,anthervector.begin(),anthervector.end());
    
    int myarray[]={5,2,0};
    
    myvector.insert(myvector.begin(),myarray,myarray+3);
    cout<<"myvector contains:";
    for(it=myvector.begin();it<myvector.end();it++){
    	cout<<" "<<*it;
	} 
}

运行结果

The allocated array contains: 0 1 2 3 4
myvector contains: 5 2 0 3 2 4 4 1 1 1

vector::at()函数 功能：返回指定位置的元素

#include<iostream>
#include<vector>
using namespace std;
int main(){
    //vector::at()函数 功能：返回指定位置的元素 
	vector<int>myvector(10);//10 zero-initialized ints
	unsigned int i;
	//assign some values;
	for(i=0;i<myvector.size();i++){
		myvector.at(i)=i;
	} 
	cout<<"myvector contains:";
	for(i=0;i<myvector.size();i++){
		cout<<" "<<myvector.at(i);
	}
	cout<<endl;
} 

运行结果

myvector contains: 0 1 2 3 4 5 6 7 8 9

vector::max_size()函数 功能：返回vector所能容纳元素的最大数量上

vector::capacity()函数 功能：返回vector所能容纳的元素数量，在不重新分配内存的情况下

#include<iostream>
#include<vector>
using namespace std;
    
int main(){
	//vector::max_size()函数 功能：返回vector所能容纳元素的最大数量上限
	//vector::capacity()函数 功能：返回vector所能容纳的元素数量，在不重新分配内存的情况下 
	vector<int>myvector;
	//set some content in the vector:
	for(int i=1;i<98;i++){
		myvector.push_back(i);
	}
	cout<<"size: "<<(int)myvector.size()<<endl;
	cout<<"capacity: "<<(int)myvector.capacity()<<endl;
	cout<<"max_size: "<<(int)myvector.max_size()<<endl;
}

运行结果

size: 97
capacity: 128
max_size: -1

priority_queue

顾名思义，priority_queque是一个拥有权值观念的queque,它允许加入新元素，移除旧元素，审视新元素值等功能。由于这是一个queque,所以只允许在底端键入元素，并从顶端取出元素，除此之外别无其他存取元素途径。priority_queque带有权值观念，其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列（通常权值以实值表示）。权值最高者，排在最前。缺省情况下priority_queque系利用一个max_heap完成，后者是一个vector表现得complete binary tree.max_heap 可以满足priority_queque所需要的“依照权值高低自动递减排序”的特性。由于priority_queque完全以底部容器为根据，再加上heap处理规则，所以实现非常简单。缺省情况下是以vector为底部容器。由于priority_queque系以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，成为（配接器，适配器）adapter,因此SLT priority_queque 往往不被归类为container（容器），而被归类为container adapter。priority_queque的所有元素，进出都有一定规则，只有queqeu顶端的元素（权值最高者），才有机会被外界取用。priority_queque不提供遍历功能，也不提供迭代器。

priority_queue::empty()函数 功能：如果优先队列为空，则返回真

priority_queue::pop()函数 功能：删除第一个元素

priority_queue::push()函数 功能：加入一个元素

priority_queue::size()函数 功能：返回优先队列中拥有的元素的个数

priority_queue::top()函数 功能：返回优先队列中有最高优先级的元素

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

int main(){
    //priority_queue::empty()函数 功能：如果优先队列为空，则返回真
    //priority_queue::pop()函数 功能：删除第一个元素
	//priority_queue::push()函数 功能：加入一个元素 
	//priority_queue::size()函数 功能：返回优先队列中拥有的元素的个数
	//priority_queue::top()函数 功能：返回优先队列中有最高优先级的元素
	 
    priority_queue<int>mypq;
    int sum(0);
    for(int i=0;i<=11;i++){
    	mypq.push(i);
	}
	cout<<mypq.top()<<endl; 
	while(!mypq.empty()){
		sum+=mypq.top();
		mypq.pop();
	}
	cout<<"total:"<<sum<<endl;
	
    priority_queue<int>mypq1;
	
	mypq1.push(1999);
	mypq1.push(2000);
	mypq1.push(1998);
	mypq1.push(2020);
	cout<<"size of mypq1 :"<<mypq1.size()<<endl;
	cout<<"popping out elements:";
	while(!mypq1.empty()){
		cout<<" "<<mypq1.top();
		mypq1.pop();
	}
	cout<<endl;
	cout<<"size of mypq1 :"<<mypq1.size()<<endl;
	 
	  
	
} 

运行结果

size of mypq :4
popping out elements: 2020 2000 1999 1998
size of mypq :0

pari的比较，先比较第一个元素，第一个相等比较第二

#include<iostream>
#include<queue> 
#include<utility>//pair
using namespace std;

int main(){
   
   int profits[] = {1,2,3};
   int capitals[] = {0,1,1};
   priority_queue<pair<int, int>,vector<pair<int, int>>, greater<pair<int, int>>> capitalProfits;
    
   for (int i = 0; i < 3; i++) 
        capitalProfits.emplace(make_pair(capitals[i], profits[i]));
    
   while (!capitalProfits.empty()) 
    {
        cout << capitalProfits.top().first << ' ' << capitalProfits.top().second << '\n';
        capitalProfits.pop();
    }

} 

运行结果

0 1
1 2
1 3

#include<iostream>
#include<queue> 
#include<utility>//pair
using namespace std;

int main(){
   
   int profits[] = {1,2,3};
   int capitals[]  = {0,1,1};
//   priority_queue<pair<int, int>,vector<pair<int, int>>, greater<pair<int, int>>> capitalProfits;
   priority_queue<pair<int,int>> capitalProfits; 
   for (int i = 0; i < 3; i++) 
        capitalProfits.emplace(make_pair(capitals[i], profits[i]));
    
   while (!capitalProfits.empty()) 
    {
        cout << capitalProfits.top().first << ' ' << capitalProfits.top().second << '\n';
        capitalProfits.pop();
    }

} 

运行结果

1 3
1 2
0 1

String

string::string() 功能：构造函数，用于字符串初始化

#include<iostream>
#include<string>

using namespace std;

int main(){
   //string::string() 功能：构造函数，用于字符串初始化 
   string s1;
   string s2("mozhenhai string");
   string s3(s2);
   string s4(s2,8);
   string s5(10,'m');
   string s6a(10,42);
   string s6b(s2.c_str(),s2.c_str()+4);
   cout<<s1<<endl;
   cout<<s2<<endl;
   cout<<s3<<endl;
   cout<<s4<<endl;
   cout<<s5<<endl;
   cout<<s6a<<endl;
   cout<<s6b<<endl;
} 

运行结果

mozhenhai string
mozhenhai string
i string
mmmmmmmmmm
**********
mozh

string::operator+=()函数 功能：连接两个字符串

#include<iostream>
#include<string>

using namespace std;

int main(){
    //string::operator+=()函数 功能：连接两个字符串
	string first("tomy");
	string second("may");
	first+=" is a boy ";
	second+=" is a girl";
	cout<<first<<endl;
	cout<<first<<endl;
	first+=second;
	cout<<first<<endl;

} 

运行结果

tomy is a boy
tomy is a boy
tomy is a boy may is a girl

string::operator=()函数 功能：字符串赋值

#include<iostream>
#include<string>

using namespace std;

int main(){
    //string::operator=()函数 功能：字符串赋值
	string str1="Test string " ;
	string str2("code");
	string str3("mo");
	
	str1+=str2;
	cout<<str1<<endl;
	str1+=str3;
	cout<<str1<<endl;
    //string::operator[]()函数 功能：获取特定的字符
	string str("test string");
	for(int i=0;i<str.size();i++){
		cout<<str[i]<<" ";
	}

} 

运行结果

Test string code
Test string codemo
t e s t   s t r i n g

string::operator[] () 功能：获取特定的字符

#include<iostream>
#include<string>

using namespace std;

int main(){
   //string::operator[]() 功能：获取特定的字符
   string str("mozhenhai");
   for(int i=0;i<str.length();i++){
   	cout<<str[i]<<" ";
   } 
   
} 

运行结果

m o z h e n h a i

string::assign()函数 功能：为字符串赋新值

#include<iostream>
#include<string>

using namespace std;

int main(){
	//string::assign()函数 功能：为字符串赋新值
	string str;
	string base="mozhenhai is wrinting#code";
	//used in the smae order as described above
	str.assign(base);
	    cout<<str<<endl;
	str.assign(base,9,12);
    	cout<<str<<endl;	
	str.assign("program is the tool",7);
		cout<<str<<endl;
	str.assign("I like coding");
		cout<<str<<endl;
	str.assign(3,'?');
		cout<<str<<endl;
	str.assign<int>(3,0x2F);
		cout<<str<<endl; 
	str.assign(base.begin()+2,base.end()-4);
	    cout<<str<<endl;
} 

运行结果

mozhenhai is wrinting#code
 is wrinting
program
I like coding
???
///
zhenhai is wrinting#

string::append()函数 功能：在字符串的末尾添加文本

#include<iostream>
#include<string>

using namespace std;

int main(){
	//string::append()函数 功能：在字符串的末尾添加文本 
	string str;
	string str2="mozhenhai";
	string str3="you#are#a#bad#boy";
	//used in the same order as described above
	str.append(str2);
	cout<<str<<endl;
	str.append(str3,3,6);//第四个个字符后面六个字符包括第四个 
	cout<<str<<endl;
	str.append("boy",2);
	cout<<str<<endl;
	str.append("good:");
	cout<<str<<endl;
	str.append(6,'!');
	cout<<str<<endl;
	str.append(str3.begin()+4,str3.end());
	cout<<str<<endl;
	str.append<int>(6,0x2E);//"......"
	cout<<str<<endl;
} 

运行结果

mozhenhai
mozhenhai#are#a
mozhenhai#are#abo
mozhenhai#are#abogood:
mozhenhai#are#abogood:!!!!!!
mozhenhai#are#abogood:!!!!!!are#a#bad#boy
mozhenhai#are#abogood:!!!!!!are#a#bad#boy......

string::begin()函数 功能：返回一个迭代器；指向第一个字符

string::end()函数 功能：返回一个迭代器；指向字符串的末尾。(最后一个字符的下一个位置)

#include<iostream>
#include<string>

using namespace std;

int main(){
	 //string::begin()函数 功能：返回一个迭代器；指向第一个字符
    //string::end()函数  功能：返回一个迭代器；指向字符串的末尾。(最后一个字符的下一个位置)
	 
	string str("program");
	string::iterator it;
	for(it=str.begin();it<str.end();it++){
		cout<<" "<<*it;
		
	} 
} 

运行结果

p r o g r a m

string::rbegin()函数 功能：返回一个逆向迭代器，指向最后一个字符

string::rend()函数 功能：返回一个逆向迭代器，指向第一个元素的前一个位置

#include<iostream>
#include<string>
#include<fstream>

using namespace std;

int main(){
   //string::rbegin()函数 功能：返回一个逆向迭代器，指向最后一个字符
   //string::rend()函数 功能：返回一个逆向迭代器，指向第一个元素的前一个位置
   string str("mozhenhai is coding");
   string::reverse_iterator rit;
   for(rit=str.rbegin();rit!=str.rend();rit++){
   	cout<<*rit;
   } 
   cout<<endl;
   
} 

运行结果

gnidoc si iahnehzom

string::push_back() 功能：Append character to string待完善

#include<iostream>
#include<string>
#include<fstream>

using namespace std;

int main(){
   //string::push_back() 功能：Append character to string
   string str;
   ifstream file("test.txt",ios::in);
   while(!file.eof()){
   	str.push_back(file.get());
   }
   cout<<str;

   
} 

test.txt 的内容

You are coder.The code is art.
Coding is cool.

运行结果

You are coder.The code is art.
Coding is cool.

string::insert()函数 功能：插入字符

#include<iostream>
#include<string>

using namespace std;

int main(){
    //string::insert()函数 功能：插入字符
	string str1="you are a lovely boy";
	string str2="not ";
	string str3("is intelligent girl");
	
	string::iterator it;
	
//	used in the same order as described above
    str1.insert(8,str2);
    cout<<str1<<endl;
    str1.insert(14,str3,3,11);
    cout<<str1<<endl;
    str1.insert(14,"code is intersting ",5);
    cout<<str1<<endl;
    str1.insert(14,"code is intersting ");
    cout<<str1<<endl;
    str1.insert(14,2,',');
    cout<<str1<<endl;
    str1.insert(str1.begin()+3,'#');
    cout<<str1<<endl;
	str1.insert(str1.end(),4,'!');
	cout<<str1<<endl;
	it=str1.insert(str1.begin()+3,'$');
	cout<<str1<<endl;
	str1.insert(it+2,str3.begin(),str3.begin()+2);
	cout<<str1<<endl;

} 

运行结果

you are not a lovely boy
you are not a intelligentlovely boy
you are not a code intelligentlovely boy
you are not a code is intersting code intelligentlovely boy
you are not a ,,code is intersting code intelligentlovely boy
you# are not a ,,code is intersting code intelligentlovely boy
you# are not a ,,code is intersting code intelligentlovely boy!!!!
you$# are not a ,,code is intersting code intelligentlovely boy!!!!
you$#is are not a ,,code is intersting code intelligentlovely boy!!!!

string::erase()函数 功能：删除字符

#include<iostream>
#include<string>

using namespace std;

int main(){
    //string::erase()函数 功能：删除字符
	string str("you are a lovely boy");
	string::iterator it;
	//erase used in the same order as described above:
	str.erase(14);//删除下标为14（第十五个字符）及以后的字符 
	cout<<str<<endl;
	str.erase(5,2);//删除下标为5及后面一个字符。就是连同下标为5的两个字符 
	cout<<str<<endl;

} 

运行结果

you are a love
you a a love

string::clear()函数 功能：Clear string

#include<iostream>
#include<string>

using namespace std;

int main(){
    //string::clear()函数 功能：Clear string
    string str("tomy");
    cout<<str<<endl;
	str.clear();
	cout<<"after str.clear:"<<str<<endl;
	char c;
	cout<<"please type some lines of text.Enter a period to finsh:\n"<<endl;
	do{
		c=cin.get();
		str+=c;
		if(c=='\n'){
			cout<<str<<endl;
			str.clear();
			
		}
	}while(c!='.');
	cout<<"after str.clear:"<<str;//str 为 . 
} 

运行结果

tomy
after str.clear:
please type some lines of text.Enter a period to finsh:

hello world.
after str.clear:hello world.

string::empty()函数 功能：如果字符串为空，返回真

#include<iostream>
#include<string>

using namespace std;

int main(){
    //string::empty()函数 功能：如果字符串为空，返回真
	string str1;
	string str2;
	cout<<"please introduce a text,Enter an empty line to finsh:\n"<<endl;
	do{
		getline(cin,str2);
		str1+=str2+'\n';
		 
	}while(!str2.empty());
	cout<<"The text you intorduced was:\n";
	cout<<str1;

} 

运行结果

please introduce a text,Enter an empty line to finsh:

hello world

The text you intorduced was:
hello world

string::c_str()函数 功能：将字符串以C字符数组的形式返回

#include<iostream>
#include<string>
#include<cstring>
#include<fstream>

using namespace std;

int main(){
   //string::c_str()函数 功能：将字符串以C字符数组的形式返回
   char *cstr,*p;
   string str("mo zhen hai is coding program is intersting");
   cstr=new char [str.size()+1];
   strcpy(cstr,str.c_str());
   //cstr now contains a c-string copy of str
   p=strtok(cstr," ");
   while(p!=NULL){
   	cout<<p<<endl;
   	p=strtok(NULL," ");
   }
    delete[] cstr;
} 

运行结果

mo
zhen
hai
is
coding
program
is
intersting

/* strtok example */
#include <stdio.h>
#include <string.h>

int main ()
{
  char str[] ="- This, a sample string.";
  char * pch;
  printf ("Splitting string \"%s\" into tokens:\n",str);
  pch = strtok (str," ,.-");
  while (pch != NULL)
  {
    printf ("%s\n",pch);
    pch = strtok (NULL, " ,.-");
  }
  return 0;
}

运行结果

Splitting string "- This, a sample string." into tokens:
This
a
sample
string

string::copy()函数 功能：将内容复制为一个字符数组

#include<iostream>
#include<string>

using namespace std;

int main(){
    //string::copy()函数 功能：将内容复制为一个字符数组
	
	string str("program codecode");
	int length;
	char buffer[20];
	length=str.copy(buffer,6,5);//6,5:5为字符的下标，6为字符串长度 
	buffer[length]='\0';
	
	cout<<"buffer contains: "<<buffer<<endl;
	
	char *array=new char [20];
	array[str.copy(array,4,6)];
	cout<<array<<endl;
	array[str.copy(array,5)];
	cout<<array<<endl;
	delete []array; 

} 

运行结果

buffer contains: am cod
m co
progr

string::length()函数 功能：返回字符串的长度

#include<iostream>
#include<string>

using namespace std;

int main(){
    //string::length()函数 功能：返回字符串的长度
	string str("I like program");
	cout<<"The length of str is :"<<str.length()<<"characters"<<endl;

} 

运行结果

The length of str is :14characters

string::size()函数 功能：返回字符串中字符的数量

#include<iostream>
#include<string>

using namespace std;

int main(){
    //string::size()函数 功能：返回字符串中字符的数量
	//string::length()函数 功能：返回字符串的长度
	string str("program code");
	cout<<"The size of str is : "<<str.size()<<endl;
	cout<<"The length of str is : "<<str.length()<<endl;
    //string::substr()函数 功能：返回某个子字符串
	string str1("you are program boy");
	string str2=str1.substr(3,4);//3,4 3是下标位置 ，4是长度 
	cout<<str2<<endl; 
} 

运行结果

The size of str is : 12
The length of str is : 12
 are

string::capacity()函数 功能：返回重新分配空间前的字符容量

#include<iostream>
#include<string>

using namespace std;

int main(){
	//string::capacity()函数 功能：返回重新分配空间前的字符容量
	string str("program is");
	cout<<"size "<<str.size()<<endl;
	cout<<"length: "<<str.length()<<endl;
	cout<<"capacity "<<str.capacity()<<endl;
	cout<<"max_size "<<str.max_size()<<endl;
} 

运行结果

size 10
length: 10
capacity 10
max_size 4611686018427387897

string::max_size()函数 功能：返回字符的最大可能个数

#include<iostream>
#include<string>
#include<cstring>
#include<fstream>

using namespace std;

int main(){
   //string::max_size()函数 功能：返回字符的最大可能个数
   string str("mozhenhai");
   cout<<"size: "<<str.size()<<endl;
   cout<<"length: "<<str.length()<<endl;
   cout<<"capacity: "<<str.capacity()<<endl;
   cout<<"max_size: "<<str.max_size()<<endl; 
  
}
   

运行结果

size: 9
length: 9
capacity: 9
max_size: 4611686018427387897

string::swap()函数 功能：交换两个字符串的内容

#include<iostream>
#include<string>

using namespace std;

int main(){
   //string::swap()函数 功能：交换两个字符串的内容
	string buyer("money");
	string seller("goods");
	
	cout<<"before swap buyer:"<<buyer<<endl;
	cout<<"before swap seller:"<<seller<<endl;
	
	seller.swap(buyer);
	 
    cout<<"after swap buyer:"<<buyer<<endl;
	cout<<"after swap seller:"<<seller<<endl;
} 

运行结果

before swap buyer:money
before swap seller:goods
after swap buyer:goods
after swap seller:money

string::find()函数 功能：在字符串中查找字符

#include<iostream>
#include<string>

using namespace std;

int main(){
   //string::find()函数 功能：在字符串中查找字符
    string str("The boy is writing code");
    string strf1("by");
    string strf2("is");
    cout<<string::npos<<endl; 
    cout<<str.find(strf1)<<endl; //返回子字符串在字符串中的起始位置下标 
    size_t found;
    found-str.find(strf2);
    if(found!=string::npos){
    	cout<<strf2<<" at: "<<found<<endl;
	}
} 

运行结果

18446744073709551615
18446744073709551615
is at: 24

string::substr()函数 功能：返回某个子字符串

#include<iostream>
#include<string>
#include<cstring>
#include<fstream>

using namespace std;

int main(){
   //string::substr()函数 功能：返回某个子字符串
   string str="i am coding,what are you doing";
   string str1,str2;
   size_t pos;
   str1=str.substr(5,6);//"coding"
   pos=str.find("you");//get from "you" to the end
   str2=str.substr(pos);
   cout<<str1<<endl;
   cout<<str2<<endl; 
} 

运行结果

coding
you doing

string::at()函数 功能：按给定索引值返回字符

#include<iostream>
#include<string>

using namespace std;

int main(){
		//string::at()函数 功能：按给定索引值返回字符
	string str("mozhenhai");
	for(int i=0;i<str.length();i++){
		cout<<str.at(i)<<endl;
	}
} 

运行结果

m
o
z
h
e
n
h
a
i

#include<iostream>
#include<string>
#include<cstring>
#include<fstream>

using namespace std;

int main(){
   //string::data()函数 功能：返回内容的字符数组形式
   int length;
   string str="mozhenhai";
   char *cstr="mozhenhai";
   if(str.length()==strlen(cstr)){
   	cout<<"str and cstr hava the same length"<<endl;
   	length=str.length();
   	//C 库函数 int memcmp(const void *str1, const void *str2, size_t n))
	// 把存储区 str1 和存储区 str2 的前 n 个字节进行比较。
	/*参数
    str1 -- 指向内存块的指针。
    str2 -- 指向内存块的指针。
    n -- 要被比较的字节数。
    返回值
    如果返回值 < 0，则表示 str1 小于 str2。
    如果返回值 > 0，则表示 str1 大于 str2。
    如果返回值 = 0，则表示 str1 等于 str2。*/
    /*s1,s2为字符串时候memcmp(s1,s2,1)就是比较s1和s2的第一个字节的ascII码值；
    memcmp(s1,s2,n)就是比较s1和s2的前n个字节的ascII码值；

    如:char *s1="abc";
       char *s2="acd";
       int r=memcmp(s1,s2,3);
   就是比较s1和s2的前3个字节，
   第一个字节相等，第二个字节比较中大小已经确定，
   不必继续比较第三字节了所以r=-1.*/
   	if(memcmp(cstr,str.data(),length)==0){
   		cout<<"str and cstr have the same content"<<endl;
	   }
   }
}
   

运行结果

str and cstr hava the same length
str and cstr have the same content

string::compare()函数 功能：比较两个字符串,相等返回0，不相等返回-1

#include<iostream>
#include<string>

using namespace std;

int main(){
    //string::compare()函数 功能：比较两个字符串,相等返回0，不相等返回-1 
	
	string str1("code");
	string str2("programcode");
	string str3("code");
	cout<<str1.compare(str3)<<endl;
	if(str1.compare(str2)){
		cout<<"str1:"<<str1<<endl<<"str2:"<<str2; 
	}
	cout<<str2.compare(7,10,"code")<<endl;
	//7,10表示第八个字符到第十一个字符 
	cout<<str2.size()<<endl;
	
	cout<<str2.compare(str2.size()-4,4,"code")<<endl;
	cout<<str2.compare(7,4,"code")<<endl;
	
	//7,4表示第八个字符后面四个字符包括第八个
	//简单概括就是如果后面数字前面大按照下标截取
	//如果后面数字比前面小或等按照下标加长度
	cout<<str1.compare(2,2,str2,9,10)<<endl;//str1:de str2:de
	cout<<str1.compare(2,2,str2,9,12)<<endl;//str1:de str2:de
	//第二种截取字符串的方法
	//表明超出字符串长度的下标和字符串最大下标效果一样 
} 

运行结果

0
str1:code
str2:programcode0
11
0
0
0
0

stack

stack是一种先进后出（First In Last Out,FILO）的数据结构。它只有一个出口，stack允许新增元素，移除元素，取得最顶端元素，但是除了最顶端外，没有任何其他方法可以存取stack的其他元素，换而言之，stack不允许有遍历行为。
将元素推入stack的操作称为push,将元素推出stack的操作称为pop.
以某种既有容器作为底部结构，将其接口改变，使之符合“先进后出”的特性，形成一个stack，是很容易做到的。deque是双向开口的数据结构，若以deque为底部结构并封闭其头端开口，便轻而易举地形成了一个stack.以deque作为缺省情况下的stack底部结构，stack的实现很简单。
由于stack系以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，成为（配接器，适配器）adapter,因此SLT stack 往往不被归类为container（容器），而被归类为container adapter。
stack所有元素的进出都必须符合“先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。stack不提供走访功能，也不提供迭代器。
除了deque之外，list也是双向开口的数据结构。因为若以list底部结构并封闭其头端开口，一样能够轻易形成一个stack。

stack::empty()函数 功能：栈为空则返回真

stack::pop()函数 功能：移除栈顶元素

stack::push()函数 功能：在栈顶添加元素

stack::size()函数 功能：返回栈中元素数目

stack::top()函数 功能：返回栈顶元素

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

int main(){
     //stack::empty()函数 功能：栈为空则返回真
     //stack::pop()函数 功能：移除栈顶元素
	 //stack::push()函数 功能：在栈顶添加元素
	 //stack::size()函数 功能：返回栈中元素数目 
	 //stack::top()函数 功能：返回栈顶元素 
	 stack<int>mystack;
	 int sum(0);
	 for(int i=0;i<11;i++){
	 	mystack.push(i);
	 }
	 cout<<"mystack size:"<<mystack.size()<<endl;
	 cout<<"mystack.top() is now :"<<mystack.top()<<endl;
	 while(!mystack.empty()){
	 	sum+=mystack.top();
	 	mystack.pop();
	 }
	 cout<<"total:"<<sum<<endl; 
     // stack::stack()函数 功能: 构造stack
}     

运行结果

mystack size:11
mystack.top() is now :10
total:55

queue

queue::queue()函数 创建queue

queue::size()函数 功能：返回队列中元素的个数

queue::push()函数 功能：在队列末尾加入一个元素

queue::pop()函数 功能：删除队列第一个元素

queue::front()函数 功能:返回第一个元素

queue::back()函数 功能：返回最后一个元素

queue::empty()函数 功能：如果队列为空则返回真

#include<iostream>
#include<queue>
#include<list>
#include<deque> 
using namespace std;

int main(){
	//queue::queue()函数 创建queue
	deque<int>mydeck(3,1999);//deque with 3 elements
	list<int>mylist(2,1998);//list with 2 elements
	queue<int>first;//empty queue
	queue<int>second(mydeck);//queue initialized to copy of deque
	queue<int,list<int>>third;
	//empty queue with lish as underlying container
	
	queue<int,list<int>>fourth(mylist);
	
	cout<<"size of first:"<<(int)first.size()<<endl;
	cout<<"size of second:"<<(int)second.size()<<endl;
	cout<<"size of third:"<<(int)third.size()<<endl;
	cout<<"size of fourth:"<<(int)fourth.size()<<endl;
} 

运行结果

size of first:0
size of second:3
size of third:0
size of fourth:2

#include<iostream>
#include<queue>
#include<list>
#include<deque> 
using namespace std;

int main(){
    //queue::size()函数 功能：返回队列中元素的个数
	//queue::push()函数 功能：在队列末尾加入一个元素
	//queue::pop()函数 功能：删除队列第一个元素
	//queue::front()函数 功能:返回第一个元素 
	//queue::back()函数 功能：返回最后一个元素
	//queue::empty()函数 功能：如果队列为空则返回真
	 
	queue<int>myints;
	cout<<"0.size:"<<(int)myints.size()<<endl;
	for(int i=0;i<10;i++)
	{
		myints.push(i); 
	}
	cout<<"1.size:"<<(int)myints.size()<<endl;
	cout<<myints.front()<<endl;
	myints.pop();
	
	cout<<myints.front()<<endl;
	cout<<myints.back()<<endl; 
	int sum(0);
	while(!myints.empty()){
		sum+=myints.front();
		myints.pop();
	} 
	cout<<sum<<endl;
	}

运行结果

0.size:0
1.size:10
0
1
9
45

deuque

deque是连续空间（至少逻辑上看来如此），连续线性空间总是令我们联想到array或vector。array无法成长，vector虽然可以成长，却只能向尾端成长，而且其所谓的成长是个假象，事实上是：一另觅更大空间，二将原有数据复制过去，三释放原空间三部曲。如果不是vector每次配置新空间是都有留下一个余裕，其成长假象所带来的带起将是相当高昂。deque系由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在deqeu的头部或尾部。便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置，复制，释放”的轮回，代价则是复杂的迭代器架构。受到分段连续线性空间的字面影响，我们可能以为deque的实现复杂程度和vector相比较虽不中亦不远矣，其实不然。主要因为，既曰分段连续线性空间，就必须有中央控制，而为了维持整体连续的假象，数据结构的设计及迭代器前进后退等操作都颇为繁琐。deque的实现代码分量远比vector或list都多得多。deque采用一块所谓的map（注意：不是STL的map容器），作为主控，这里所谓map是一小块连续空间，其中每个元素（此处成为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，成为缓冲区。缓冲区才是deque的存储空间主体。

deque::deque()函数 功能：创建一个新双向队列

#include<iostream>
#include<deque>
using namespace std;
int main(){
	//deque::deque()函数 功能：创建一个新双向队列
	deque<int>first;//empty deque if ints
	deque<int>second(5,20);//five ints with values 20
	deque<int>third(second.begin(),second.end());//iterating through second
	deque<int>fourth(third);//a copy of third
	//the iterator constructor can also be used to construct from arrays
	int myints[]={1998,11,3,520,13,14};
	
	deque<int>fifth(myints,myints+sizeof(myints)/sizeof(int));
	cout<<"the contents of first are:";
	for(int i=0;i<first.size();i++){
		cout<<" "<<first[i];
	}
	cout<<endl;
	cout<<"the contents of second are:";
	for(int i=0;i<second.size();i++){
		cout<<" "<<second[i];
	}
	cout<<endl;
	cout<<"the contents of third are:";
	for(int i=0;i<third.size();i++){
		cout<<" "<<third[i];
	}
	cout<<endl;
	cout<<"the contents of fourth are:";
	for(int i=0;i<fourth.size();i++){
		cout<<" "<<fourth[i];
	}

	cout<<endl;
	cout<<"the contents of fifth are:";
	for(int i=0;i<fifth.size();i++){
		cout<<" "<<fifth[i];
	}
	cout<<endl;   
}

运行结果

the contents of first are:
the contents of second are: 20 20 20 20 20
the contents of third are: 20 20 20 20 20
the contents of fourth are: 20 20 20 20 20
the contents of fifth are: 1998 11 3 520 13 14

deque::operator=()函数 功能赋值双向队列

#include<iostream>
#include<deque>
using namespace std;
int main(){
	///deque::operator=()函数 功能赋值双向队列 
	deque<int>first(3);//deque with 3 zero-initialized ints
	deque<int>second(5);//deque with 5 zero-initialized ints
	second=first;
	first=deque<int>(6);
	cout<<"size of fist "<<int(first.size())<<endl;
	cout<<"size of second "<<int(second.size())<<endl;
}

运行结果

size of fist 6
size of second 3

deque::operator函数 功能：Access element

#include<iostream>
#include<deque>
using namespace std;
int main(){
	// deque::operator[]()函数 功能：Access element
    deque<int>mydeque(10);//10 zero-initialized elements
	deque<int>::size_type sz=mydeque.size();
	for(int i=0;i<sz;i++)mydeque[i]=2*i;
	//reverse order of elements using operator[]:
	for(int i=0;i<sz/2;i++){
		int temp;
		temp=mydeque[sz-1-i];
		mydeque[sz-1-i]=mydeque[i];
		mydeque[i]=temp;
	}
	cout<<"mydeque contains:"<<endl;
	for(int i=0;i<sz;i++){
		cout<<" "<<mydeque[i];
	}
	cout<<endl;
}

运行结果

mydeque contains:
 18 16 14 12 10 8 6 4 2 0

deque::assign函数 功能：设置双向队列的值

#include<iostream>
#include<deque>
using namespace std;
int main(){
    //deque::assign函数 功能：设置双向队列的值
	deque<int>first;
	deque<int>second;
	deque<int>third;
	first.assign(6,11);//a repetition 6 times of value 11
	deque<int>::iterator it;
	it=first.begin()+1;
	second.assign(it,first.end());//the 5 values of first
	int myints[]={1998,11,3};
	third.assign(myints,myints+3);//assigning from array
	cout<<"size of first: "<<int(first.size())<<endl;
	cout<<"size of second: "<<int(second.size())<<endl;
	cout<<"size of third: "<<int(third.size())<<endl;
}

运行结果

size of first: 6
size of second: 5
size of third: 3

deque::begin()函数 功能：返回指向第一个元素的迭代器

deque::end()函数 功能：返回指向尾部的迭代器

deque::rbegin()函数 功能：返回指向尾部的逆向迭代器

deque::rend()函数 功能：返回指向头部的逆向迭代器

#include<iostream>
#include<deque>
using namespace std;
int main(){
     //deque::begin()函数 功能：返回指向第一个元素的迭代器
	 //deque::end()函数 功能：返回指向尾部的迭代器
	 //deque::rbegin()函数 功能：返回指向尾部的逆向迭代器
	 //deque::rend()函数 功能：返回指向头部的逆向迭代器
	  
	deque<int>mydeque;
	deque<int>::iterator it;
	deque<int>::reverse_iterator rit;
	for(int i=0;i<9;i++){
	 	mydeque.push_back(i);
	 }
	cout<<"mydeque contains:";
	 
	for(it=mydeque.begin();it!=mydeque.end();it++){
	 	cout<<" "<<*it;
	 } 
	cout<<endl;
    it=mydeque.begin();
    cout<<"begin to end";
    while(it!=mydeque.end()){
    	cout<<" "<<*it++;
	}
	
	rit=mydeque.rbegin();
	cout<<endl;
	cout<<"mydeque contains:";
	cout<<"rbegin to rend";
	while(rit!=mydeque.rend()){
		cout<<" "<<*rit++; 
	}
}

运行结果

mydeque contains: 0 1 2 3 4 5 6 7 8
begin to end 0 1 2 3 4 5 6 7 8
mydeque contains:rbegin to rend 8 7 6 5 4 3 2 1 0

deque::back()函数 功能：返回最后一个元素

#include<iostream>
#include<deque>
using namespace std;
int main(){
    //deque::back()函数 功能：返回最后一个元素
	deque<int>mydeque;
	mydeque.push_back(10);
	while(mydeque.back()!=0){
	mydeque.push_back(mydeque.back()-1);
	}
	cout<<"mydeque contains: ";
	for(int i=0;i<mydeque.size();i++){
	cout<<" "<<mydeque[i]; 
	}
	cout<<endl;
}

运行结果

mydeque contains:  10 9 8 7 6 5 4 3 2 1 0

deque::front()函数 功能：返回第一个元素

#include<iostream>
#include<deque>
using namespace std;
int main(){
    //deque::front()函数 功能：返回第一个元素 
	deque<int>mydeque;
	mydeque.push_back(11);
	mydeque.push_back(3);
	mydeque.push_front(1998);
	mydeque.front()+=mydeque.back();
	cout<<"mydeque contains:";
	for(int i=0;i<mydeque.size();i++){
		cout<<" "<<mydeque[i];
	} 
}

运行结果

mydeque contains: 2001 11 3

deque::push_back()函数 功能：在尾部加入一个元素

deque::pop_back()函数 功能: 删除尾部的元素

deque::push_front()函数 功能：在头部加入一个元素

deque::pop_front()函数 功能：删除头部的元素

#include<iostream>
#include<deque>
using namespace std;
int main(){
	//deque::pop_back()函数 功能: 删除尾部的元素
    //deque::push_back()函数 功能：在尾部加入一个元素
    
    //deque::pop_front()函数 功能：删除头部的元素 
	//deque::push_front()函数 功能：在头部加入一个元素
	
    //deque::back()函数 功能：返回最后一个元素
	//deque::front()函数 功能：返回第一个元素
	deque<int>mydeque;
	int sumback(0);
	int sumfront(0);
	mydeque.push_back(1998);
	mydeque.push_back(11);
	mydeque.push_back(3);
	while(!mydeque.empty()){
		sumback+=mydeque.back();
		mydeque.pop_back();
	}
	mydeque.push_front(1998);
	mydeque.push_front(11);
	mydeque.push_front(3);
	while(!mydeque.empty()){
		sumfront+=mydeque.front();
		mydeque.pop_front();
	}
	cout<<"the elements of mydeque summed "<<sumback<<" or "<<sumfront<<endl; 
}

运行结果

the elements of mydeque summed 2012 or 2012

deque::insert()函数 功能：插入 一个元素到双向队列中

#include<iostream>
#include<deque>
#include<vector>
using namespace std;
int main(){
    //deque::insert()函数 功能：插入 一个元素到双向队列中
	deque<int>mydeque;
	deque<int>::iterator it;
	//set some initial values
	for(int i=1;i<6;i++){
		mydeque.push_back(i);//1 2 3 4 5
	} 
	it=mydeque.begin();
	it=mydeque.insert(it,1998);
	//it now points to the newly inserted 10
	mydeque.insert(it,3,11);
	//it no longer valid!!!!
	it=mydeque.end()-3;
	vector<int>myvector(2,23);
	mydeque.insert(it,myvector.begin(),myvector.end());
	cout<<"mydeque contains: ";
	for(it=mydeque.begin();it!=mydeque.end();it++){
		cout<<" "<<*it; 
	}
}

运行结果

mydeque contains:  11 11 11 1998 1 2 23 23 3 4 5

deque::erase()函数 功能：删除一个元素

#include<iostream>
#include<deque>
using namespace std;
int main(){
    //deque::erase()函数 功能：删除一个元素
	deque<int>mydeque;
	//set some values (from 1 to 10)
	for(int i=1;i<11;i++){
		mydeque.push_back(i);
	}
	//erase the 6th element
	mydeque.erase(mydeque.begin()+5);
	cout<<"mydeque contains: ";
	for(int i=0;i<mydeque.size();i++){
		cout<<" "<<mydeque[i]; 
	}
	cout<<endl;
	//erase the first 3 elements
	mydeque.erase(mydeque.begin(),mydeque.begin()+3);
	cout<<"mydeque contains: ";
	for(int i=0;i<mydeque.size();i++){
		cout<<" "<<mydeque[i]; 
	}
	cout<<endl;
}

运行结果

mydeque contains:  1 2 3 4 5 7 8 9 10
mydeque contains:  4 5 7 8 9 10

deque::clear()函数 功能：删除所有元素

#include<iostream>
#include<deque>
using namespace std;
int main(){
    //deque::clear()函数 功能：删除所有元素 
    deque<int>mydeque;
    mydeque.push_back(1998);
    mydeque.push_back(11);
    mydeque.push_back(3);
    cout<<"mydeque contains: ";
    for(int i=0;i<mydeque.size();i++){
    	cout<<" "<<mydeque[i]; 
	}
	cout<<endl;
	mydeque.clear();
	
	cout<<"size of mydeque: "<<mydeque.size()<<endl;
	
	mydeque.push_back(2000);
	mydeque.push_back(2);
	cout<<"mydeque contains: ";
    for(int i=0;i<mydeque.size();i++){
    	cout<<" "<<mydeque[i]; 
	}
	cout<<endl;
}

运行结果

mydeque contains:  1998 11 3
size of mydeque: 0
mydeque contains:  2000 2

deque::empty()函数 功能：返回真如果双向队列为空

#include<iostream>
#include<deque>
using namespace std;
int main(){
    //deque::empty()函数 功能：返回真如果双向队列为空
	deque<int>mydeque;
	int sum(0);
	for(int i=0;i<=10;i++){
		mydeque.push_back(i);
	}
	while(!mydeque.empty()){
		sum+=mydeque.back();
		mydeque.pop_back();
	}
	cout<<"total:"<<sum;
}

运行结果

total:55

deque::size()函数 功能：返回双向队列中元素的个数

deque::resize()函数 功能：改变双向队列的大小

#include<iostream>
#include<deque>
using namespace std;
int main(){
    //deque::resize()函数 功能：改变双向队列的大小
    //deque::size()函数 功能：返回双向队列中元素的个数 
	deque<int>mydeque;
	deque<int>::iterator it;
	//set some initial content
	for(int i=1;i<11;i++){
		mydeque.push_back(i);
	}
	mydeque.resize(5);
	cout<<"mydeque contains:";
	for(it=mydeque.begin();it!=mydeque.end();it++){
		cout<<" "<<*it;
	} 
	cout<<" size of mydeque： "<<mydeque.size();
	cout<<endl;
	mydeque.resize(8,23);
	cout<<"mydeque contains:";
	for(it=mydeque.begin();it!=mydeque.end();it++){
		cout<<" "<<*it;
	} 
	cout<<" size of mydeque： "<<mydeque.size();
	cout<<endl;
	mydeque.resize(11);
	cout<<"mydeque contains:";
	for(it=mydeque.begin();it!=mydeque.end();it++){
		cout<<" "<<*it;
	} 
	cout<<" size of mydeque： "<<mydeque.size(); 
	cout<<endl;
}

运行结果

mydeque contains: 1 2 3 4 5 size of mydeque： 5
mydeque contains: 1 2 3 4 5 23 23 23 size of mydeque： 8
mydeque contains: 1 2 3 4 5 23 23 23 0 0 0 size of mydeque： 11

deque::swap()函数 功能：和另一个双向队列交换元素

#include<iostream>
#include<deque>
using namespace std;
int main(){
    //deque::swap()函数 功能：和另一个双向队列交换元素
	deque<int>first(3,1998);//three ints with a value of 1998
	deque<int>second(5,20);//five ints with value of 20
	cout<<"before first contains: ";
	for(int i=0;i<first.size();i++){
		cout<<" "<<first[i];
	}
	cout<<endl;
	cout<<"before second contains: ";
	for(int i=0;i<second.size();i++){
		cout<<" "<<second[i];
	}
	cout<<endl;
	first.swap(second);
	cout<<"after first contains: ";
	for(int i=0;i<first.size();i++){
		cout<<" "<<first[i];
	}
	cout<<endl;
	cout<<"after second contains: ";
	for(int i=0;i<second.size();i++){
		cout<<" "<<second[i];
	}
	cout<<endl;
	 
}

运行结果

before first contains:  1998 1998 1998
before second contains:  20 20 20 20 20
after first contains:  20 20 20 20 20
after second contains:  1998 1998 1998

deque::get_allocator()函数 功能：返回双向队列的配置器

#include<iostream>
#include<deque>
using namespace std;
int main(){
    //deque::get_allocator()函数 功能：返回双向队列的配置器
	deque<int>mydeque;
	int *p;
	unsigned int i;
	//allocate an array of 5 elements using deque's allocator
	p=mydeque.get_allocator().allocate(5);
	//assign some values to array
	for(i=0;i<5;i++){
		p[i]=i;
	}
	cout<<"the allocated array contains:";
	for(i=0;i<5;i++){
		cout<<" "<<p[i]; 
	}
    cout<<endl;
    mydeque.get_allocator().deallocate(p,5);
}

运行结果

the allocated array contains: 0 1 2 3 4

deque()::at()函数 功能：返回指定元素

#include<iostream>
#include<deque>
using namespace std;
int main(){
     //deque()::at()函数 功能：返回指定元素
	deque<int>mydeque(10);
	//10 zero-initialized ints
	//assign some values
	for(int i=0;i<mydeque.size();i++){
		mydeque.at(i)=i;}
		
		cout<<"mydeque contains: ";
		for(int i=0;i<mydeque.size();i++){
			cout<<" "<<mydeque.at(i);
		} 
		cout<<endl;	 
}

运行结果

mydeque contains:  0 1 2 3 4 5 6 7 8 9

deque::max_size()函数 功能：返回双向队列能容纳的最大元素个数

#include<iostream>
#include<deque>
using namespace std;
int main(){
    //deque::max_size()函数 功能：返回双向队列能容纳的最大元素个数
	deque<int>mydeque;
	int i;
	cout<<"enter number of elements:";
	cin>>i;
	if(i<mydeque.max_size())mydeque.resize(i);
	else cout<<"that size exceeds the limit \n"; 
}

list

相较于vector的连续线性空间，list就显得复杂许多，它的好处就是每次插入或删除一个元素，就配置或释放一个元素空间。因此对于空间的运用有绝对的精准，一点也不浪费。而且对于任何位置的元素的插入或元素移除，list永远是常数时间。list和vector是两个最常被使用的容器。什么时机在最适合使用哪一种容器，必须视元素的多寡，元素的构造复杂度（有无 non-traivial copy constructor ,non-trivial copy assugnmen operator），元素的存取行为的特性而定。list不在能够像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在。所谓的list迭代器正确的递增，递减，取值，成员取用的操作是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取用的是节点的成员。
STL list 是一个双向链表（double linked-list），迭代器必须具备前移，后移的能力，所以list提供的是Bidirectional iterators.
list 有一个重要性质：插入操作（insert）和接合操作（splice）都不会造成原有的list迭代器失效。这在vector是不成立的，因为vector的插入操作造成记忆体（内存空间）重新配置，导致原有的跌大气全部失效。list的元素删除操作（erase），也只有指向被删除元素的那个迭代器失效，其他迭代器不受任何影响。

list::list()函数 功能：构造list

#include<iostream>
#include<list> 
using namespace std;
int main(){
	//list::list()函数 功能：构造list
    //constructors used in the same order as described above:
    list<int>::iterator it;
	list<int>first;//empty list of ints
	list<int>second(5,20);//five ints with value 20;
	list<int>third(second.begin(),second.end());
	cout<<"the contents of third are:";
	for(it=third.begin();it!=third.end();it++){
		cout<<" "<<*it;
	} 
	cout<<endl;
	//iterating through second
	list<int>fourth(third);
	cout<<"the contents of fourth are:";
	for(it=fourth.begin();it!=fourth.end();it++){
		cout<<" "<<*it;
	} 
	cout<<endl;
	//a copy of third 
	//the iterator constructor can also be used to construct from arrays
	int myints[]={1998,11,3,520};
	list<int>fifth(myints,myints+sizeof(myints)/sizeof(int));
	
	cout<<"the contents of fifth are:";
	for(it=fifth.begin();it!=fifth.end();it++){
		cout<<" "<<*it;
	} 
	cout<<endl;
} 
 

list::operator=()函数 功能：赋值list

#include<iostream>
#include<list> 
using namespace std;
int main(){
	//list::operator=()函数 功能：赋值list
	list<int>first(3);//list of 3 zero-initialized ints
	list<int>second(11);//list of 11 zero-initialized ints
	second=first;
	first=list<int>();
	cout<<"size of first :"<<int(first.size())<<endl;
	cout<<"size of second :"<<int(second.size())<<endl;
}

list::assign()函数 功能：给list赋值

#include<iostream>
#include<list>
using namespace std;
int main(){
	//list::assign()函数 功能：给list赋值
	list<int>first;
	list<int>second;
	first. assign(5,20);//5 ints with value 20
	second.assign(first.begin(),first.end());//a copy of first
	list<int>::iterator it;
	cout<<"first contains:";
	for(it=first.begin();it!=first.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	int myints[]={1998,11,3};
	first.assign(myints,myints+3);//assigning from array
	cout<<"size of first:"<<(int)first.size()<<endl;
	cout<<"size of second:"<<(int)second.size()<<endl; 
   
}

list::begin()函数 功能：返回指向第一个元素的迭代器

list::end()函数 功能：返回末尾的迭代器

list::rbegin()函数 功能：返回指向list尾部的逆向迭代器

list::rend()函数 功能：返回指向第一个元素的逆向迭代器

#include<iostream>
#include<list> 
using namespace std;
int main(){
	//list::begin()函数 功能：返回指向第一个元素的迭代器
	//list::end()函数 功能：返回末尾的迭代器 
	//list::rbegin()函数 功能：返回指向list尾部的逆向迭代器
	//list::rend()函数 功能：返回指向第一个元素的逆向迭代器 
    int myints[]={1998,11,3,5,20};
    list<int>mylist(myints,myints+5);
    list<int>::iterator it;
    cout<<"mylist contains:";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	list<int>::reverse_iterator rit;
	cout<<"mylist contains:";
	for(rit=mylist.rbegin();rit!=mylist.rend();rit++){
		cout<<" "<<*rit;
	}
	cout<<endl;
	
}
 

list::back()函数 功能：返回最后一个元素

#include<iostream>
#include<list> 
using namespace std;
int main(){ 
    //list::back()函数 功能：返回最后一个元素
	list<int>mylist;
	list<int>::iterator it;
	mylist.push_back(11);
	while(mylist.back()!=1){
		mylist.push_back(mylist.back()-1);
	}
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
    
} 
 

list::front()函数 功能：返回第一个元素

#include<iostream>
#include<list> 
using namespace std;
int main(){ 
    //list::front()函数 功能：返回第一个元素
	list<int>mylist;
	mylist.push_back(1998);
	mylist.push_back(11);
	mylist.push_back(3);
	//now front equals 1998,and back 3
	mylist.front()-=mylist.back();
	cout<<"mylist.front()is now:  "<<mylist.front()<<endl; 
} 
 

list::push_back()函数 功能：在list的末尾添加一个元素

#include<iostream>
#include<list> 
using namespace std;
int main(){
	//list::push_back()函数 功能：在list的末尾添加一个元素
	list<int>mylist;
	int myint;
	cout<<"please enter some integers(enter 0 to end):\n";
	do{
		cin>>myint;
		mylist.push_back(myint);
	} while(myint);
	cout<<"mylist stores:  "<<(int)mylist.size()<<endl;
} 
 

list::pop_back()函数 功能： 删除最后一个元素

#include<iostream>
#include<list> 
using namespace std;
int main(){ 
    //list::pop_back()函数 功能： 删除最后一个元素
    list<int>mylist;
    int sum(0);
    mylist.push_back(1998);
    mylist.push_back(11);
    mylist.push_back(3);
    while(!mylist.empty()){
    	sum+=mylist.back();
    	mylist.pop_back();
	}
	cout<<"the elements of mylist summed "<<sum<<endl;
} 
 

list::push_front()函数 功能：在list的头部添加一个元素

#include<iostream>
#include<list> 
using namespace std;
int main(){
    //list::push_front()函数 功能：在list的头部添加一个元素 
    list<int>mylist(5,20);//five ints with a value of 20
    mylist.push_front(1998);
	mylist.push_front(11);
	mylist.push_front(3);
	cout<<"mylist contains:  ";
	list<int>::iterator it;
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	 
} 
 

list::pop_front()函数 功能：删除第一个元素

#include<iostream>
#include<list> 
using namespace std;
int main(){
	//list::push_back()函数 功能：在list的末尾添加一个元素
    //list::push_front()函数 功能：在list的头部添加一个元素 
    //list::pop_back()函数 功能： 删除最后一个元素
    //list::pop_front()函数 功能：删除第一个元素 
    list<int>mylist(5,20);//five ints with a value of 20
    list<int>::iterator it;
    
    mylist.push_back(13);
	mylist.push_back(14);
	cout<<"mylist contains:  ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	
    mylist.push_front(1998);
	mylist.push_front(11);
	mylist.push_front(3);
	cout<<"mylist contains:  ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	
	mylist.pop_back();
	cout<<"mylist contains:  ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	
	mylist.pop_front();
	cout<<"mylist contains:  ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	
	
	
	
	 
} 
 

list::insert()函数 功能：插入一个元素到list中(插入下标的前面）

#include<iostream>
#include<list> 
#include<vector>
using namespace std;
int main(){ 
     //list::insert()函数 功能：插入一个元素到list中(插入下标的前面）	
    list<int>mylist;
    list<int>::iterator it;
    //set some initial values
    for(int i=1;i<11;i++){
    	mylist.push_back(i);//1 2 3 4 5 6 7 8 9 10
	}
	cout<<"mylist contains:";
	for(list<int>::iterator it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	 
	it=mylist.begin();
	++it;//it points now to number 2
	mylist.insert(it,1314);//1 1314 2 3 4 5 6 7 8 9 10
	cout<<"mylist contains:";
	for(list<int>::iterator it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	 
	mylist.insert(it,3,5);//1 1314 5 5 5 2 3 4 5 6 7 8 9 10
	//注意 此时 it 还是指向2 
	cout<<"mylist contains:";
	for(list<int>::iterator it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	 
	vector<int>myvector(5,100);
	mylist.insert(it,myvector.begin(),myvector.end());
	cout<<"mylist contains:";
	for(list<int>::iterator it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	//注意 此时 it 还是指向2
	mylist.erase(it);//删掉了2  
	cout<<"mylist contains:";
	for(list<int>::iterator it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	//如果此时还删掉it，则没有效果 
	++it; //删掉了3
	 
	mylist.erase(it);  
	cout<<"mylist contains:";
	for(list<int>::iterator it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	
	mylist.erase(--it,++it);//注意此时it的位置不变--++，如果两次++++ 
	cout<<"mylist contains:";
	for(list<int>::iterator it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;

} 
 

list:erase()函数 功能：删除一个元素或者一组连续元素

#include<iostream>
#include<list> 
using namespace std;
int main(){
	//list:erase()函数 功能：删除一个元素或者一组连续元素 
	list<int>mylist;
	list<int>::iterator it,it1,it2;
	//set some values:
	for(int i=1;i<10;i++)mylist.push_back(i);
	//1 2 3 4 5 6 7 8 9
	cout<<"mylist contains: ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	} 
	cout<<endl;
	
	it1=it2=mylist.begin();
	advance(it2,6);
	++it1;
	it1=mylist.erase(it1);//1 3 4 5 6 7 8 9
	cout<<"mylist contains: ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	} 
	cout<<endl;
	it2=mylist.erase(it2);//1 3 4 5 6 8 9
	cout<<"mylist contains: ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	} 
	cout<<endl;
	++it1;
	--it2;
	mylist.erase(it1,it2);//1 3 6 8 9
	cout<<"mylist contains: ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	} 
	cout<<endl;
}

list::clear()函数 功能：删除所有元素

#include<iostream>
#include<list> 
using namespace std;
int main(){
	//list::clear()函数 功能：删除所有元素
	list<int>mylist;
	list<int>::iterator it;
	mylist.push_back(1998);
	mylist.push_back(11);
	mylist.push_back(3);
	cout<<"mylist contains:  ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl; 
	mylist.clear();
	cout<<"mylist contains:  ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	mylist.push_back(1);
	mylist.push_back(2);
	mylist.push_back(3);
	cout<<"mylist contains:  ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
}

list::empty()函数 功能：如果list是空的则返回true

#include<iostream>
#include<list> 
using namespace std;
int main(){
	//list::empty()函数 功能：如果list是空的则返回true
	list<int>mylist;
	int sum=0;
	for(int i=1;i<11;i++){
		mylist.push_back(i);
	}
	while(!mylist.empty()){
		sum+=mylist.back();
		mylist.pop_back();
	}
	cout<<"total: "<<sum<<endl;
}

list::size()函数 功能：返回list中元素的个数

#include<iostream>
#include<list> 
using namespace std;
int main(){
	//list::size()函数 功能：返回list中元素的个数
	list<int>myints;
	cout<<"0.size"<<(int)myints.size()<<endl;
	for(int i=0;i<10;i++){
		myints.push_back(i);
	} 
	cout<<"1.size"<<(int)myints.size()<<endl;
	myints.insert(myints.begin(),11,3);
	cout<<"2.size"<<(int)myints.size()<<endl;
	myints.pop_back();
	cout<<"3.size"<<(int)myints.size()<<endl;
}

list::resize()函数 功能：改变list的大小

#include<iostream>
#include<list> 
using namespace std;
int main(){
	//list::resize()函数 功能：改变list的大小
	list<int>mylist;
	list<int>::iterator it;
	//set some initial content
	for(int i=1;i<11;i++) {
		mylist.push_back(i);
	}
	mylist.resize(5);
	cout<<"mylist contains: ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	} 
	cout<<endl;
	mylist.resize(8,3);
	cout<<"mylist contains: ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	} 
	cout<<endl;
	mylist.resize(11);
	cout<<"mylist contains: ";
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	} 
	cout<<endl;
}

list::swap()函数 功能：交换两个list

#include<iostream>
#include<list>
using namespace std;
int main(){
    //list::swap()函数 功能：交换两个list
	list<int>first(3,11);
	//three ints with a value of 100
	list<int>second(5,20);
	//five ints with a value of 20

	list<int>::iterator it;
	cout<<"first contains: ";
	for(it=first.begin();it!=first.end();it++){
		cout<<" "<<*it; 
	}
	cout<<endl;
	cout<<"second contains: ";
	for(it=second.begin();it!=second.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	
	first.swap(second);
	
	cout<<"first contains: ";
	for(it=first.begin();it!=first.end();it++){
		cout<<" "<<*it; 
	}
	cout<<endl;
	cout<<"second contains: ";
	for(it=second.begin();it!=second.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	 
	
    
}

list::get_allocator()函数 功能：返回list的适配器

#include<iostream>
#include<list> 
using namespace std;
int main(){
	//list::get_allocator()函数 功能：返回list的适配器
	list<int>mylist;
	int *p;
	//allocate an array of 5 elements using mylist's allocator
	p=mylist.get_allocator().allocate(5);
	//assign some values to array
	for(int i=0;i<5;i++)p[i]=i;
	cout<<"size of mylist"<<mylist.size()<<endl;//0
	cout<<"the allocated array contains: ";
	for(int i=0;i<5;i++){
		cout<<"  "<<p[i]; 
	}
	cout<<endl;
	mylist.get_allocator().deallocate(p,5);
}

list::max_size()函数 功能：返回list能容纳的最大元素数量

#include<iostream>
#include<list>
using namespace std;
    
int main(){
	//list::max_size()函数 功能：返回list能容纳的最大元素数量
	list<int>mylist;
	int i;
	cout<<"enter number of elements:";
	cin>>i;
	if(i<mylist.max_size())mylist.resize(i);
	else cout<<"that size exceeds the limit"<<endl;
	list<int>::iterator it;
	for(it=mylist.begin();it!=mylist.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	cout<<"size: "<<mylist.size()<<endl;
	cout<<"max_size: "<<mylist.max_size()<<endl;
	
}

list::sort()函数 功能：给list排序

#include<iostream>
#include<list>
#include<vector>
#include<string>
#include<cctype>
using namespace std;
bool compare_nocase(string first,string second){
	
		unsigned  int i=0;
		while((i<first.length())&&(i<second.length())){
			if(tolower(first[i])<tolower(second[i]))//转换为小写 
			 return true;
			++i;
		}
		if(first.length()<second.length())return true;
		else return false;
	}
	//先按长度由小到大，在按开头字符a-z 
int main(){
    list<string>mylist;
	list<string>::iterator it;
	mylist.push_back("one");
	mylist.push_back("two");
	mylist.push_back("Three");
	mylist.push_back("four");
		
    mylist.sort();
    cout<<"mylist contians:";
    for(it=mylist.begin();it!=mylist.end();it++){
    	cout<<" "<<*it;
	}
	cout<<endl;
	
	mylist.sort(compare_nocase);
	

    cout<<"mylist contians:";
    for(it=mylist.begin();it!=mylist.end();it++){
    	cout<<" "<<*it;
	}
	cout<<endl;
	string str = "THIS IS A STRING";
    for (int i=0; i <str.size(); i++)
       str[i] = tolower(str[i]);//把大写全部转为小写
    cout<<str<<endl;	
 
}

set

标准的STL关联式容器分为set(集合）和map（映射表）两大类。以及这两大类的衍生体multiset（多建集合）和multimap（多键映射表）。这些容器的底层机制均是以RB-tree（红黑树）完成的。RB-tree也是一个独立容器，但并不对外开放使用。

set 的特性是，所有元素都会根据元素的键值自动被排序，set的元素不像map那样可以同时拥有实值（value）和键值（key）,set元素的键值就是实值，实值就是键值，set不允许两个元素有相同的键值。
我们可以通过set的迭代器改变set的元素值吗？不行，因为set的元素值就是其键值，关系到set元素的排列规则。如果任意改变set的元素值，会严重破坏set组织。set<T>::iterator 被定义为底层RB-tree的const_iterator,杜绝写入操作，换句话说，set iterators 是一种constant iterator（相对于 mutable iterator）。
set拥有和list相同的某些性质，当客户端对它进行元素新增操作（insert）或删除操作（erase）时，操作之前的所有迭代器，在操作完成之后都依然有效。当然，被删除的那个元素的迭代器必然是个例外。
由于RB-tree是一种平衡二叉搜索树，自动排序的效果很是不错，所以标准的STL set 即以RB-tree为底层机制。又由于map所开放的各种操作接口，RB-tree也都提供了，所以几乎所有的set的操作行为，都只是转调用RB-tree的操作行为而已。
multiset 的特性以及用法与set完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique()。

set::set()函数 功能：构造set

#include<iostream>
#include<set>
using namespace std;

bool fncomp(int lhs,int rhs){
	     return lhs<rhs;
	}
	struct classcomp{
		bool operator()(const int& lhs,const int& rhs){
			return lhs<rhs;
		}
	}; 
	
int main(){
    //set::set()函数 功能：构造set
    set<int>first;//empty set of ints
    int myints[]{1,2,3,4,5};
    set<int>second(myints,myints+5);
    //pointers used as iterator
    set<int>third(second);//a copy of second
    set<int>fourth(second.begin(),second.end());
    //iterator ctor
	set<int,classcomp>fifth;
	//class as compare
	bool(*fn_pt)(int,int)=fncomp;
	set<int,bool(*)(int,int)>sixth(fn_pt);//function pointer as compare
	return 0;		 
}

set::operator=()函数 功能：赋值set

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    //set::operator=()函数 功能：赋值set
	//set::size()函数 功能：集合中元素的数目
	//set::begin()函数  功能：返回指向第一个元素的迭代器
	//set::end()函数 功能：返回指向最后一个元素的迭代器 
	int myints[]={1998,11,1,2,3};
	set<int>first(myints,myints+5);//set with 5 ints
	set<int>second;//empty set
	second=first;//now second contains the 5 ints
	first=set<int>();//and first is empty
	set<int>myset;
	myset=second;
	
	cout<<"Size of first:"<<int(first.size())<<endl; 
	cout<<"Size of second:"<<int(second.size())<<endl; 
	set<int>::iterator it;
	cout<<"myset contains";
	for(it=myset.begin();it!=myset.end();it++){
		cout<<" "<<*it;
	}
}

运行结果

Size of first:0
Size of second:5
myset contains 1 2 3 11 1998

set::begin()函数 功能：返回指向第一个元素的迭代器

set::end()函数 功能：返回指向最后一个元素的迭代器

set::rbegin()函数 功能：返回指向集合中最后一个元素的反向迭代器

set::rend()函数 功能：返回指向集合中第一个元素的反向迭代器

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    //set::rbegin()函数 功能：返回指向集合中最后一个元素的反向迭代器 
    //set::rend()函数  功能：返回指向集合中第一个元素的反向迭代器
	int myints[]={1998,11,1};
	set<int>myset(myints,myints+3);
	set<int>::iterator it;
	cout<<"myset contains:";
	for(it=myset.begin();it!=myset.end();it++){
		cout<<" "<<*it;
	} 
	cout<<endl;
	set<int>::reverse_iterator rit;
	cout<<"myset contains:";
	for(rit=myset.rbegin();rit!=myset.rend();rit++){
		cout<<" "<<*rit;
	} 
	cout<<endl;
}

运行结果

myset contains: 1 11 1998
myset contains: 1998 11 1

set::insert()函数 功能： 在集合中插入元素

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    //set::insert()函数 功能： 在集合中插入元素
	set<int>myset;
	set<int>::iterator it;
	pair<set<int>::iterator,bool>ret;
	//set some initial values
	for(int i=1;i<6;i++){
		myset.insert(i*10);
	//set:10  20 30 40 50 	
	} 
	ret=myset.insert(20);//no new elements inserted
	if(ret.second==false)it=ret.first;//it now points to elements 20
	myset.insert(it,25);//max efficiency inserting
	myset.insert(it,24);//max efficiency inserting
	myset.insert(it,26);//no max efficiency inserting
	
	int myints[]={1949,10,1};
	//10 already in set,not inserted
	myset.insert(myints,myints+3);
	cout<<"myset contains:";
	for(it=myset.begin();it!=myset.end();it++){
		cout<<" "<<*it; 
	}
	cout<<endl;

}

运行结果

myset contains: 1 10 20 24 25 26 30 40 50 1949

set::erase()函数 功能：删除集合中的元素

set::find()函数 功能：返回一个指向被查找元素的迭代器

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    //set::erase()函数 功能：删除集合中的元素
    //set::find()函数 功能：返回一个指向被查找元素的迭代器 
	set<int>myset;
	set<int>::iterator it;
	//insert some values
	for(int i=1;i<11;i++){
		myset.insert(i*10);
	}
	it=myset.begin();
	it++;//it points now to 2o
	myset.erase(it);
	myset.erase(40);//找得到就删除，如果没有就删除，比如41 
	it=myset.find(60);
	
	myset.erase(it,myset.end());
	cout<<"myset contains:";
	for(it=myset.begin();it!=myset.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
}

运行结果

myset contains: 10 30 50

set::clear()函数 功能：清除所有元素

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    //set::clear()函数 功能：清除所有元素 
    set<int>myset;
	set<int>::iterator it;
	myset.insert(1998);
	myset.insert(11);
	myset.insert(3);
	cout<<"myset contains:";
	for(it=myset.begin();it!=myset.end();it++){
		cout<<" "<<*it;	
	}
	cout<<endl;
	myset.clear();
	cout<<"myset contains:";
	for(it=myset.begin();it!=myset.end();it++){
		cout<<" "<<*it;	
	}
	cout<<endl;
	myset.insert(1999);
	myset.insert(2000);
		cout<<"myset contains:";
	for(it=myset.begin();it!=myset.end();it++){
		cout<<" "<<*it;	
	}
	cout<<endl;
}

运行结果

myset contains: 3 11 1998
myset contains:
myset contains: 1999 2000

set::empty()函数 功能：如果集合为空，返回true

#include<iostream>
#include<set>
using namespace std;
    
int main(){
    //set::empty()函数 功能：如果集合为空，返回true
	set<int>myset;
	myset.insert(1998); 
	myset.insert(11); 
	myset.insert(3);
	myset.insert(1999);
	cout<<"myset contains: ";
	while(!myset.empty()){
		cout<<" "<<*myset.begin();
		myset.erase(myset.begin());
	}
	cout<<endl;
	  
	 
}

运行结果

myset contains:  3 11 1998 1999

set::count()函数 功能：返回某个值元素的个数

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    //set::count()函数 功能：返回某个值元素的个数
	set<int>myset;
	//set some intial values
	for(int i=1;i<5;i++){
		myset.insert(i*3);//set:3 6 9 12
	} 
	for(int i=0;i<10;i++){
		cout<<i;
		if(myset.count(i)>0)
		 cout<<" is an elements of myset"<<endl;
		else
		 cout<<" is not an elements of myset"<<endl;
		 	
	}
	myset.insert(9);
	myset.insert(9);
	myset.insert(9);
    cout<<myset.count(9)<<endl;//只输出一个	
}

运行结果

0 is not an elements of myset
1 is not an elements of myset
2 is not an elements of myset
3 is an elements of myset
4 is not an elements of myset
5 is not an elements of myset
6 is an elements of myset
7 is not an elements of myset
8 is not an elements of myset
9 is an elements of myset
1

set::size()函数 功能：集合中元素的数目

#include<iostream>
#include<set>
using namespace std;
    
int main(){
    //set::size()函数 功能：集合中元素的数目 
	set<int>myset;
	myset.insert(1998); 
	myset.insert(11); 
	myset.insert(3);
	cout<<"myset contains: ";
	while(!myset.empty()){
		cout<<" "<<*myset.begin();
		myset.erase(myset.begin());
	}
	cout<<endl;
	cout<<"size "<<(int)myset.size()<<endl;
	for(int i=1;i<11;i++)myset.insert(i);
	cout<<"size "<<(int)myset.size()<<endl;
	myset.insert(1998);
	myset.insert(98);//插入自动排序 
	cout<<"size "<<(int)myset.size()<<endl;
	myset.erase(6);
	cout<<"size "<<(int)myset.size()<<endl;
	cout<<"myset contains: ";
	set<int>::iterator it;
	for(it=myset.begin();it!=myset.end();it++){
	cout<<" "<<*it; 
	} 
	cout<<endl;
}

运行结果

myset contains:  3 11 1998
size 0
size 10
size 12
size 11
myset contains:  1 2 3 4 5 7 8 9 10 98 1998

set::swap()函数 功能：交换两个集合变量

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    //set::swap()函数 功能：交换两个集合变量
    int myints[]={1,2,3,4,5,6,7,8,9};
	set<int>first(myints,myints+3);
	set<int>second(myints+3,myints+6);
	set<int>::iterator it;
	
	cout<<"before swap first contains:";
	for(it=first.begin();it!=first.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	cout<<"before swap second contains:";
	for(it=second.begin();it!=second.end();it++){
		cout<<" "<<*it; 
	}
	cout<<endl;
	
	first.swap(second);
	
	cout<<"first contains:";
	for(it=first.begin();it!=first.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
	cout<<"second contains:";
	for(it=second.begin();it!=second.end();it++){
		cout<<" "<<*it; 
	}
	cout<<endl;
}

运行结果

before swap first contains: 1 2 3
before swap second contains: 4 5 6
first contains: 4 5 6
second contains: 1 2 3

set::get_allocator()函数 功能:返回集合分配器

#include<iostream>
#include<set>
using namespace std;
 
int main(){
     //set::get_allocator()函数 功能:返回集合分配器
    set<int>myset;
	int *p;
	unsigned int i;
	//allocate an array of 5 elements ysing myset's allocator
	p=myset.get_allocator().allocate(6);
	//assign some values to array
	for(int i=0;i<6;i++){
		p[i]=(i+1)*10;
	}
	cout<<"The allocated array contains:";
	for(int i=0;i<6;i++){
		cout<<" "<<p[i];
	}
	cout<<endl;
	myset.get_allocator().deallocate(p,6);

}

运行结果

The allocated array contains: 10 20 30 40 50 60

set::key_comp()函数 功能：返回一个用于元素间比较的函数

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    //set::key_comp()函数 功能：返回一个用于元素间比较的函数 
    set<int>myset;
	set<int>::key_compare mycomp;
	set<int>::iterator it;
	int highest;
	mycomp=myset.key_comp();
	for(int i=0;i<=5;i++){
		myset.insert(i);
	}
	cout<<"myset contains:";
	highest=*myset.rbegin();
	//set::rbegin()返回指向集合中最后一个元素的反向迭代器 
	 
	it=myset.begin();
	do{
		cout<<" "<<*it;
	}while(mycomp(*it++,highest));
	cout<<endl;
}

运行结果

myset contains: 0 1 2 3 4 5

set::value_comp()函数 功能：返回一个用于比较元素间的值的函数

#include<iostream>
#include<set>
using namespace std;
    
int main(){
    //set::value_comp()函数 功能：返回一个用于
	set<int>myset;
	set<int>::value_compare mycomp;
	set<int>::iterator it;
	int highest;
	mycomp=myset.value_comp();
	for(int i=0;i<=5;i++){
		myset.insert(i);
	}
	cout<<"myset contains:";
	highest=*myset.rbegin();
	//set::rbegin()返回指向集合中最后一个元素的反向迭代器 
	 
	it=myset.begin();
	do{
		cout<<" "<<*it;
	}while(mycomp(*it++,highest));
	cout<<endl; 
}

运行结果

myset contains: 0 1 2 3 4 5

set::lower_bound()函数 返回指向大于等于某值的第一个元素的迭代器

set::upper_bound()函数 返回指向大于等于某值的迭代器

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    //set::lower_bound()函数 返回指向大于等于某值的第一个元素的迭代器
    //set::upper_bound()函数 返回指向大于等于某值的迭代器 
	set<int>myset;
	set<int>::iterator it ,itlow,itup;
	for(int i=1;i<10;i++){
		myset.insert(i*10);//10 20 30 40 50 60 70 80 90
	} 
    itlow=myset.lower_bound(30);
    itup=myset.upper_bound(60);
	cout<<"itlow:"<<*itlow<<endl;
	cout<<"itup:"<<*itup<<endl; 
	myset.erase(itlow,itup);//不删除itup指向的元素 
	//10 20 70 80 90
	cout<<"myset contains:";
	for(it=myset.begin();it!=myset.end();it++){
		cout<<" "<<*it;
	}
	cout<<endl;
}

运行结果

itlow:30
itup:70
myset contains: 10 20 70 80 90

set::max_size()函数 返回集合能容纳的元素的最大限值

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    //set::max_size()函数 返回集合能容纳的元素的最大限值
	set<int>myset;
	if(myset.max_size()>1000){
		for(int i=0;i<1000;i++){
			myset.insert(i);
		}
		cout<<"the set contains 1000 elements"<<endl;
	}
	else{
		cout<<"the set could not contains 1000 elements"<<endl;	
	} 
	cout<<myset.max_size();
}

运行结果

the set contains 1000 elements
461168601842738790

set::equal_range()函数 功能：返回集合中与给定值相等的上下限的两个迭代器

#include<iostream>
#include<set>
using namespace std;
 
int main(){
    //set::equal_range()函数 功能：返回集合中与给定值相等的上下限的两个迭代器
	set<int>myset;
	pair<set<int>::iterator,set<int>::iterator>ret;
	for(int i=1;i<6;i++){
		myset.insert(i*10);//set:10 20 30 40 50
	} 
	ret=myset.equal_range(30);
	cout<<"lower bound points to:"<<*ret.first<<endl;
	cout<<"upper bound points to:"<<*ret.second<<endl;
}

运行结果

lower bound points to:30
upper bound points to:40

multiset::count()函数 与set::count()有区别

#include<iostream>
#include<set>
using namespace std;

int main(){
     //multiset::count()函数 与set::count()有区别
	int myints[]={1,2,3,3,3,3,3,4,5,6};
	multiset<int>mymultiset(myints,myints+sizeof(myints));
	cout<<"3 appears ";
	cout<<(int)mymultiset.count(3);
	cout<<" times in mymultiset"<<endl;
	//与set的区别，其他函数大都相同 
} 

运行结果

3 appears 5 times in mymultiset

map

标准的STL关联式容器分为set(集合）和map（映射表）两大类。以及这两大类的衍生体multiset（多建集合）和multimap（多键映射表）。这些容器的底层机制均是以RB-tree（红黑树）完成的。RB-tree也是一个独立容器，但并不对外开放使用。
map的特性是，所有元素都会根据元素的键值自动被排序。map的所有元素都是pair,同时拥有实值（value)和键值（key）。pair的第一元素被视为键值。第二元素被视为实值。map不允许两个元素拥有相同的键值。
我们可以通过map的迭代器改变map的元素内容吗？如果想要修正元素的键值，答案是不行，因为map元素的键值关系到map元素的排序规则。任意改变map元素键值，将会严重破坏map组织。但是如果想要修正元素的实值，答案是可以的，因为map元素的实值并不影响map的元素的排列规则。因此，map iterators 既不是一种constant iterator,也不是一种mutable iterators
。
map拥有和list相同的某些性质，当客户端对它进行元素新增操作（insert）或删除操作（erase）时，操作之前的所有迭代器，在操作完成之后都依然有效。当然，被删除的那个元素的迭代器必然是个例外。
由于RB-tree是一种平衡二叉搜索树，自动排序的效果很是不错，所以标准的STL map 即以RB-tree为底层机制。又由于map所开放的各种操作接口，RB-tree也都提供了，所以几乎所有的map的操作行为，都只是转调用RB-tree的操作行为而已。
multimap 的特性以及用法与map完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique()。

map::map()函数 功能：构造map

map::operator=()函数 功能：赋值map

#include<iostream>
#include<map>
using namespace std;
 
int main(){
    //map::operator=()函数 赋值map 
	map<char,int>first;
	map<char,int>second;
	first['x']=8;
	first['y']=18;
	first['z']=28;
	second=first;//second now contains 3 ints
	first=map<char,int>();//and first is now empty
	cout<<"size of first: "<<int(first.size())<<endl;
	cout<<"size of second: "<<int(second.size())<<endl;
}

运行结果

size of first: 0
size of second: 3

map::begin()函数 功能：返回指向map头部的迭代器

map::end()函数 功能：返回指向map末尾的迭代器

map::rbegin()函数 功能：返回一个指向map尾部的逆向迭代器

map::rend()函数 功能：返回一个指向map头部的逆向迭代

#include<iostream>
#include<map>
using namespace std;
 
int main(){
	//map::begin()函数 功能：返回指向map头部的迭代器
	//map::end()函数 功能：返回指向map末尾的迭代器
	//map::rbegin()函数 功能：返回一个指向map尾部的逆向迭代器
	//map::rend()函数 功能：返回一个指向map头部的逆向迭代器
	map<char,int>mymap;
	map<char,int>::iterator it;
	mymap['a']=100;
	mymap['b']=200;
	mymap['c']=300;
	//show content;
	for(it=mymap.begin();it!=mymap.end();it++){
		cout<<(*it).first<<"："<<(*it).second<<endl;
	}
	map<char,int>::reverse_iterator rit;
	for(rit=mymap.rbegin();rit!=mymap.rend();rit++){
		cout<<(*rit).first<<": "<<(*rit).second<<endl;
		
	} 
}

运行结果

a：100
b：200
c：300
c: 300
b: 200
a: 100

map::insert()函数 功能：插入元素

#include<iostream>
#include<map>
using namespace std;
 
int main(){
    //map::insert()函数 功能：插入元素
	map<char,int>mymap;
	map<char,int>::iterator it;
	pair<map<char,int>::iterator,bool>ret;
	//first insert function vertion(single parameter):
    mymap.insert(pair<char,int>('a',10));
	mymap.insert(pair<char,int>('z',20));
	ret=mymap.insert(pair<char,int>('z',60));
	if(ret.second==false){
		cout<<"element  'z' already existed"<<endl;
		cout<<"with a value of "<<ret.first->second<<endl;
	}
	//second insert function version(with hint position):
	it=mymap.begin();
	mymap.insert(it,pair<char,int>('b',11));//max efficiency inserting
	mymap.insert(it,pair<char,int>('c',12));//no max efficiency inserting
	//third insert function version(range insertion)
	map<char,int>anothermap;
	anothermap.insert(mymap.begin(),mymap.find('c'));
	//show contents:
	cout<<"mymap contains:"<<endl;
	for(it=mymap.begin();it!=mymap.end();it++){
		cout<<(*it).first<<":"<<(*it).second<<endl;
	}
	cout<<"anothermap contains:"<<endl;
	for(it=anothermap.begin();it!=anothermap.end();it++){
		cout<<(*it).first<<":"<<(*it).second<<endl;
	}
}

运行结果

element  'z' already existed
with a value of 20
mymap contains:
a:10
b:11
c:12
z:20
anothermap contains:
a:10
b:11

map::erase()函数 功能：删除一个元素

#include<iostream>
#include<map>
using namespace std;
 
int main(){
	//map::erase()函数 功能：删除一个元素
	map<char,int>mymap;
	map<char,int>::iterator it;
	// insert some values
	mymap['a']=1;
	mymap['b']=2;
	mymap['c']=3;
	mymap['d']=4;
	mymap['e']=5;
	mymap['f']=6;
	mymap['g']=7;
	it=mymap.find('b');
	mymap.erase(it);//erasing by iterator
	mymap.erase('c');//erasing by key
	it=mymap.find('e');
	mymap.erase(it,mymap.end());//erasing by range
	//show content
	for(it=mymap.begin();it!=mymap.end();it++){
		cout<<(*it).first<<":"<<(*it).second<<endl;
	}
}

运行结果

a:1
d:4

map::find()函数 功能：查找一个元素，如果找到返回改元素的迭代器

#include<iostream>
#include<map>
using namespace std;
 
int main(){
    //map::find()函数 功能：查找一个元素，如果找到返回改元素的迭代器
    map<char,int>mymap;
	map<char,int>::iterator it;
	// insert some values
	mymap['a']=1;
	mymap['b']=2;
	mymap['c']=3;
	mymap['d']=4;
	mymap['e']=5;
	mymap['f']=6;
	mymap['g']=7;
	it=mymap.find('b');
	mymap.erase(it);
	mymap.erase(mymap.find('d'));
	while(!mymap.empty()){
//		cout<<(*mymap.begin()).first<<":"<<(*mymap.begin()).second<<endl;
		cout<<mymap.begin()->first<<":"<<mymap.begin()->second<<endl;
		mymap.erase(mymap.begin());
	}
}

运行结果

a:1
c:3
e:5
f:6
g:7

map::clear() 函数 功能：删除所有元素

#include<iostream>
#include<map>
using namespace std;
int main(){
    //map::clear() 函数 功能：删除所有元素
	map<char,int>mymap;
	map<char,int>::iterator it;
	mymap['m']=1998;
	mymap['z']=11;
	mymap['h']=3;
	cout<<"mymap contains:\n";
	for(it=mymap.begin();it!=mymap.end();it++){
		cout<<(*it).first<<"->"<<(*it).second<<endl;
	}
	mymap.clear();
	mymap['a']=1999;
	mymap['b']=9;
	mymap['c']=15;
	cout<<"mymap contains:\n";
	for(it=mymap.begin();it!=mymap.end();it++){
		cout<<(*it).first<<"->"<<(*it).second<<endl;
	}
	 
}

运行结果

mymap contains:
h->3
m->1998
z->11
mymap contains:
a->1999
b->9
c->15

map::empty()函数 功能：如果map为空则返回true

#include<iostream>
#include<map>
using namespace std;
 
int main(){
    //map::empty()函数 功能：如果map为空则返回true
	map<char,int>mymap;
	map<char,int>::iterator it;
	// insert some values
	mymap['a']=1;
	mymap['b']=2;
	mymap['c']=3;
	mymap['d']=4;
	mymap['e']=5;
	mymap['f']=6;
	mymap['g']=7;
	while(!mymap.empty()){
		cout<<(*mymap.begin()).first<<":"<<(*mymap.begin()).second<<endl;
		cout<<mymap.begin()->first<<":"<<mymap.begin()->second<<endl;
		mymap.erase(mymap.begin());
	}
}

运行结果

a:1
a:1
b:2
b:2
c:3
c:3
d:4
d:4
e:5
e:5
f:6
f:6
g:7
g:7

map::count()函数 功能：返回指定元素出现的次数

#include<iostream>
#include<map>
using namespace std;
 
int main(){
	 //map::count()函数 功能：返回指定元素出现的次数
	map<char,int>mymap;
	char c;
	mymap['a']=1;
	mymap['b']=2;
	mymap['c']=3;
	for(c='a';c<'h';c++){
		cout<<c;
		if(mymap.count(c)>0)
		  cout<<"  is an elements of mymap"<<endl;
		else
		  cout<<"  is not an elements of mymap"<<endl;
	} 
}

运行结果

a  is an elements of mymap
b  is an elements of mymap
c  is an elements of mymap
d  is not an elements of mymap
e  is not an elements of mymap
f  is not an elements of mymap
g  is not an elements of mymap

map::size()函数 功能：返回map中元素的个数

map::swap()函数 功能：交换两个map

#include<iostream>
#include<map>
using namespace std;
 
int main(){
    //map::swap()函数 功能：交换两个map
    //map::size()函数 功能：返回map中元素的个数 
	map<char,int>foo;
	map<char,int>bar;
	map<char,int>::iterator it;
	foo['x']=1;
	foo['y']=2;
	foo['z']=3;
	bar['a']=4;
	bar['b']=5;
	cout<<"before swap foo contains:"<<endl;	
	for(it=foo.begin();it!=foo.end();it++){
		cout<<(*it).first<<"->"<<(*it).second<<endl; 
	}
	cout<<"size of foo: "<<foo.size()<<endl; 
	cout<<"before swap bar contains:"<<endl;	
	for(it=bar.begin();it!=bar.end();it++){
		cout<<(*it).first<<"->"<<(*it).second<<endl; 
	}
	cout<<"size of bar: "<<bar.size()<<endl;
	foo.swap(bar);
	cout<<"after swap foo contains:"<<endl;	
	for(it=foo.begin();it!=foo.end();it++){
		cout<<(*it).first<<"->"<<(*it).second<<endl; 
	}
	cout<<"size of foo: "<<foo.size()<<endl; 
	cout<<"after swap bar contains:"<<endl;	
	for(it=bar.begin();it!=bar.end();it++){
		cout<<(*it).first<<"->"<<(*it).second<<endl; 
	}
		cout<<"size of bar: "<<bar.size()<<endl;
}

运行结果

before swap foo contains:
x->1
y->2
z->3
size of foo: 3
before swap bar contains:
a->4
b->5
size of bar: 2
after swap foo contains:
a->4
b->5
size of foo: 2
after swap bar contains:
x->1
y->2
z->3
size of bar: 3

map::get_allocator()函数 功能：返回map的配置器

#include<iostream>
#include<map>
using namespace std;
 
int main(){
    //map::get_allocator()函数 功能：返回map的配置器
	int psize;
	map<char,int>mymap;
	pair<const char,int>* p;
	//allocate an array of 5 elements using mamap's allocate
	p=mymap.get_allocator().allocate(5);
	psize=(int)sizeof(map<char,int>::value_type)*5;
	cout<<"the allocated array has a size of  "<<psize<<"  bytes"<<endl;
	mymap.get_allocator().deallocate(p,5);
}

运行结果

the allocated array has a size of  40  bytes

may::key_comp()函数 功能：返回比较元素key的函数

#include<iostream>
#include<map>
using namespace std;
 
int main(){
    //may::key_comp()函数 功能：返回比较元素key的函数
	map<char,int>mymap;
	map<char,int>::key_compare mycomp;
	map<char,int>::iterator it;
	char highest;
	mycomp=mymap.key_comp();
	
	mymap['a']=1; 
	mymap['b']=3; 
	mymap['c']=4; 
	mymap['d']=5; 
	mymap['e']=2; 
	cout<<"mymap contains:"<<endl;
	highest=mymap.rbegin()->first;//key value of last element
	it=mymap.begin();
	do{
		cout<<(*it).first<<"->"<<(*it).second<<endl;
	}while(mycomp((*it++).first,highest));
	cout<<endl;
}

运行结果

mymap contains:
a->1
b->3
c->4
d->5
e->2

map::value_comp()函数 功能：返回比较元素value的函数

#include<iostream>
#include<map>
using namespace std;
 
int main(){
    //map::value_comp()函数 功能：返回比较元素value的函数
	map<char,int>mymap;
	map<char,int>::iterator it;
	pair<char,int>highest;
	mymap['x']=2000;
	mymap['y']=2001;
	mymap['z']=2002;
	cout<<"mymap contains:"<<endl;
	highest=*mymap.rbegin();//last element
	it=mymap.begin();
	do{
		cout<<(*it).first<<"->"<<(*it).second<<endl;
		
	}while(mymap.value_comp()(*it++,highest));
}

运行结果

mymap contains:
x->2000
y->2001
z->2002

map::lower_bound()函数 功能：返回键值大于等于(>=)给定元素的第一个位置

map::upper_bound()函数 功能：返回键值大于(>)给定元素的第一个位置

#include<iostream>
#include<map>
using namespace std;
 
int main(){
    //map::lower_bound()函数 功能：返回键值大于等于(>=)给定元素的第一个位置
    //map::upper_bound()函数 功能：返回键值大于(>)给定元素的第一个位置 
	map<char,int>mymap;
	map<char,int>::iterator it,itlow,itup;
	mymap['a']=20;
	mymap['b']=40;
	mymap['c']=60;
	mymap['d']=80;
	mymap['e']=100;
	mymap['f']=120;
	mymap['g']=140;
	itlow=mymap.lower_bound('b');//itlow points to b
	itup=mymap.upper_bound('d');//itup points to e (not d!)
	mymap.erase(itlow,itup);//erases [itlow,itup)
	//print content:
	for(it=mymap.begin();it!=mymap.end();it++){
		cout<<(*it).first<<"->"<<(*it).second<<endl;
	} 
}

运行结果

a->20
e->100
f->120
g->140

map::max_size()函数 功能：返回可以容纳的最大元素个数

#include<iostream>
#include<map>
using namespace std;
    
int main(){
	//map::max_size()函数 功能：返回可以容纳的最大元素个数 
	map<int,int>mymap;
	if(mymap.max_size()>1000){
		for(int i=0;i<10;i++)mymap[i]=1;
		cout<<"the map contains 10 elements \n";
	}
	else cout<<"the map could not hold 1000 elements\n";
	cout<<"mymap contains: ";
	map<int,int>::iterator it;
	for(it=mymap.begin();it!=mymap.end();it++){
		cout<<(*it).first<<"   "<<(*it).second<<endl; 
   }
}

运行结果

the map contains 10 elements
mymap contains: 0   1
1   1
2   1
3   1
4   1
5   1
6   1
7   1
8   1
9   1

map::equal_range()函数 功能：返回map中与给定值相等的上下限的两个迭代器

#include<iostream>
#include<map>
using namespace std;
    
int main(){
	//map::equal_range()函数 功能：返回map中与给定值相等的上下限的两个迭代器 
	//左闭右开 
	map<char,int>mymap;
	pair<map<char,int>::iterator,map<char,int>::iterator>ret;
	mymap['a']=1;
	mymap['b']=2;
	mymap['e']=4;
	mymap['c']=3;
	ret=mymap.equal_range('b');
	cout<<"lower bound points to : ";
	cout<<ret.first->first<<" ->"<<ret.first->second<<endl;
	cout<<"upper bound points to : ";
	cout<<ret.second->first<<" ->"<<ret.second->second<<endl;
}

运行结果

lower bound points to : b ->2
upper bound points to : c ->3

multimap::count()函数 与map::count()有区别

#include<iostream>
#include<map>
using namespace std;

int main(){
	//multimap::count()函数 与map::count()有区别 
	map<char,int>mymap;
	mymap['a']=1;
	mymap['a']=2;
	mymap['a']=3;
	cout<<"map count 'a'"<<mymap.count('a')<<endl;//只输出1 
	
	multimap<char,int>mymultim;
	mymultim.insert(pair<char,int>('a',1));
	mymultim.insert(pair<char,int>('a',2));
	mymultim.insert(pair<char,int>('a',3));
	cout<<"multimap count 'a'"<<mymultim.count('a')<<endl;//输出3 
	
	
	multimap<char,int>mymm;
	multimap<char,int>::iterator it;
	char c;
	mymm.insert(pair<char,int>('x',1));
	mymm.insert(pair<char,int>('y',2));
	mymm.insert(pair<char,int>('y',3));
	mymm.insert(pair<char,int>('y',4));
	mymm.insert(pair<char,int>('z',5));
	mymm.insert(pair<char,int>('z',6));
	mymm.insert(pair<char,int>('y',1));
	mymm.insert(pair<char,int>('z',1));
	for(c='x';c<='z';c++){
		cout<<"there are "<<(int)mymm.count(c);
		cout<<" elements with key  "<<c<<"  :";
		for(it=mymm.equal_range(c).first;it!=mymm.equal_range(c).second;++it)
		  cout<<" "<<(*it).second;
		cout<<endl;
	}

}

运行结果

map count 'a'1
multimap count 'a'3
there are 1 elements with key  x  : 1
there are 4 elements with key  y  : 2 3 4 1
there are 3 elements with key  z  : 5 6 1