C++ STL学习笔记

C++ STL学习笔记一

为何要学习STL：

数据结构与算法是编程的核心，STL中包含各种数据结构和优秀的算法，确实值得深入学习，本文中虽然着重使用，但希望有心的朋友能多看看相关数据结构的实现，对于C++语言确实会有较大帮助。

STL库有多个版本，我采用的是SGI版本，编译安装方法请参考如下链接：

http://blog.csdn.net/hong201/archive/2009/07/06/4322975.aspx

PS：按照网上孟岩老师的安装方法，我出现了一些问题，后来按照上面文章所说的安装成功。

关于为何采用SGI版本STL库，目前我并没有较深感触，网上的说法是：

1.开源

2.可读性强

3.自设了一些容器，如slist、hash_set等

谈点我的感觉：运用VC自带库使用set容器时，发现可以通过迭代器来改变set的元素，改变会破坏红黑树，但编译通过，这个是比较严重的BUG。

可以的话建议安装SGI版本的STL库。

在笔记中，我主要介绍各容器的用法，工具选用VC6.0。关于自定义类型数据如何使用容器，这个是许多人纠结的问题，我尽量写一些例子。

因为是新学C++，所以文中不可避免会存在错误的地方，希望大家批评指正。

C++ STL学习笔记二 vector向量容器

/*
*
********************************************
*vector容器的基础说明：
********************************************
*
*可进行随机访问，并且实现了在容器的尾端插入新元素
*Random Access Container 和 Back Insertion Sequence
*在尾端插入、删除元素的时间复杂度为O(1)，其它位置为O(n)，n为元素个数
*对于插入的元素可以动态调整所占空间
*使用vector必须使用宏语句#include <vector>
*
**************************************************************************************
*
*创建vector对象:
*1.vector<int> a;
*2.vector<int> a(10);//具有10个元素的对象a，每个元素默认值为0
*3.vector<char> a(5,'k');
*4.vector<char> b(a);//vector<char> c(a.begin(),a.end())
*
**************************************************************************************
*
*初始化赋值
*void push_back(const T& value)
*
**************************************************************************************
*
*遍历访问
*reference operator[](size_type n)//可用数组方式访问vector元素
*
**************************************************************************************
*
*常用函数
*
*bool empty();
*size_type size();size_type max_size();size_type capacity();
*reference front();reference back();
*void pop_back();void push_back();
*void clear();
*
*
*
********************************************
*Author: cumirror
*Email:[e-mail]
********************************************
*
*/

#include <iostream>
#include <vector>

int main()
{
using namespace std;
vector<int> a(10,5);
//数组方式
cout<<"数组"<<endl;
a[0]=100;
for(int s=0;s<a.size();s++){
cout<<a[s]<<endl;
}
//迭代器方式
cout<<"迭代器"<<endl;
vector<int>::iterator i,iend;
i=a.begin();
iend=a.end();
*i=101;
for(vector<int>::iterator j=i;j!=iend;j++){
cout<<*j<<endl;
}
//元素插入，插入位置为迭代器所指之前
//注意：有元素插入后，原来的迭代器会失效
cout<<"插入"<<endl;
a.insert(a.begin(),102);
//删除时注意，它是一个半闭区间
//也支持 erase(iterator pos)单个元素的删除
cout<<"删除"<<endl;
a.erase(a.begin()+4,a.begin()+6);
for(vector<int>::iterator k=a.begin();k!=a.end();k++){
cout<<*k<<endl;
}
//反向遍历访问
cout<<"反向访问"<<endl;
vector<int>::reverse_iterator ri;
for(ri=a.rbegin();ri!=a.rend();ri++){
cout<<*ri<<endl;
}
return 0;
}

C++ STL学习笔记三 deque双端队列容器

/*
*
********************************************
*deque双端队列容器的基础说明：
********************************************
*
*
*可进行随机访问，在**头部和尾端**插入、删除元素，时间复杂度为O(1)
*Random Access Container Back Insertion Sequence Front Insertion Sequence
*
************************************************************************************
*当考虑容器元素的内存分配策略和操作的性能时，deque较vector更具优势*
*map管理块，块中包含一组数据，内存分配更细致(以块为单位，使用二级的MAP进行管理)*
************************************************************************************
*
*使用deque必须使用宏语句#include <deque>
*
**************************************************************************************
*
*创建deque对象:
*1.deque<int> a;
*2.deque<int> a(10);//具有10个元素的对象a，每个元素默认值为0
*3.deque<char> a(5,'k');
*4.deque<char> b(a);//deque<char> c(a.begin(),a.end())
*
**************************************************************************************
*
*初始化赋值
*void push_back(const T& value)
*
**************************************************************************************
*
*遍历访问
*reference operator[](size_type n)
*iterator begin()
*iterator end()
*
**************************************************************************************
*
*常用函数
*
*bool empty();
*size_type size();size_type max_size();//无size_type capacity();reverse();
*reference front();reference back();
*void pop_front();void push_front();//相较vector增加部分
*void pop_back();void push_back();
*void clear();
*//还有些函数直接见代码如erase();
*
*
*
********************************************
*Author: cumirror
*Email:[e-mail]
********************************************
*
*/

#include <iostream>
#include <deque>

int main()
{
using namespace std;
deque<int> a(10,5);

//数组方式
cout<<"数组方式访问:"<<endl;
a[0]=100;
for(int s=0;s<a.size();s++){
cout<<a[s]<<endl;
}

//迭代器方式
cout<<"迭代器方式访问:"<<endl;
deque<int>::iterator i,iend;
i=a.begin();
iend=a.end();
*i=101;
for(deque<int>::iterator j=i;j!=iend;j++){
cout<<*j<<endl;
}

//注意插入删除时迭代器的失效问题,偷个懒,大家可以看下面的网页,里面有说明但没介绍原因,其实这与各个容器是如何实现的有很大关系,若想深究可看《STL源码剖析》
//http://blog.csdn.net/jokenchang2000/archive/2008/07/01/2603485.aspx
cout<<"插入"<<endl;
a.insert(a.begin(),102);

//删除时注意，它是一个半闭区间
//也支持 erase(iterator pos)单个元素的删除
cout<<"删除"<<endl;
a.erase(a.begin()+4,a.begin()+6);
for(deque<int>::iterator k=a.begin();k!=a.end();k++){
cout<<*k<<endl;
}

//头部插入
a.push_front(999);

//反向遍历访问
cout<<"反向访问"<<endl;
deque<int>::reverse_iterator ri;
for(ri=a.rbegin();ri!=a.rend();ri++){
cout<<*ri<<endl;
}

deque<int> b;
b.push_back(4);
b.push_back(5);
b.push_front(3);
b.push_front(2);
cout<<"互换"<<endl;
b.swap(a);
for(int l=0;l<a.size();l++){
cout<<a[l]<<endl;
}
return 0;
}

C++ STL学习笔记四 list双向链表容器

/*
*
********************************************
*list双向链表容器的基础说明：
********************************************
*
*list双向链表容器采用双向链表的数据结构来存储元素数据，可以高效查找、插入、删除容器元素
*
*Reversibe Container Back Insertion Sequence Front Insertion Sequence
*不同于vector，list查找、插入、删除元素的时间复杂度均为O(1)
*
*使用list必须使用宏语句#include <list>
*
**************************************************************************************
*
*创建list对象:
*1.list<int> a;
*2.list<int> a(10);//具有10个元素的对象a，每个元素默认值为0
*3.list<char> a(5,'k');
*4.list<char> b(a);//list<char> c(a.begin(),a.end())
*
**************************************************************************************
*
*初始化赋值
*void push_back(const T& value)
*
**************************************************************************************
*
*遍历访问
*iterator begin()//只能使用迭代器的方式进行遍历
*iterator end()
* iterator rbegin();//反向遍历
* iterator rbegin();
*
**************************************************************************************
*
*常用函数
*
*bool empty();
*
*void pop_front();void pop_back();
*
*void push_front(const T&);void push_back(const T&);
*iterator insert(iterator pos,const T&x);//注意它是插入到pos前
*
*iterator erase(iterator pos);
*iterator erase(iterator first,iterator last);
*void clear();
*void remove(const T& value);
*
*void swap()//通过交换头指针来实现元素的交换
*//list内部提供的一个迁移操作
*void transfer();//transfer(iterator position,iterator first,iterator last)在A链表position位置前插入
*//B链表迭代器区间[first,last)的元素，并将这部分元素从B链表中抹去
*void splice(iterator pos,list& X);//调用transfer函数将一个链表的所有元素全部归并到当前链表，
*//并将链表对象X清空，
*void splice(iterator pos,list& X,iterator i);//将X中迭代器i所指的元素归并到当前链表pos前，并将X中i所指元素抹去
*
*void merge(list&X);//对两个链表进行归并，要求先排序，否则merge没有太大意义
*
*void unique();//可将连续重复的元素删除，只保留一个
*
*
*
********************************************
*Author: cumirror
*Email:[e-mail]
********************************************
*
*/

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

struct student{
char* name;
int age;
char* city;
char* phone;
};

class studentNew{
public:
char name[10];
int age;
char city[10];
char phone[11];
studentNew(){}
studentNew(char* a,int b,char* c,char* d){
strcpy(name,a);
age=b;
strcpy(city,c);
strcpy(phone,d);
}

//为何友元函数在类外定义，出现错误error C2593: 'operator >' is ambiguous
//friend bool operator < (studentNew&a,studentNew& b);
//friend bool operator > (studentNew&a,studentNew& b);
//friend bool operator == (studentNew&a,studentNew& b);

friend bool operator< (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)<0;
}
friend bool operator> (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)>0;
}
friend bool operator== (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)==0;
}

bool operator() (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)==-1;
}
};
/*
bool operator < (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)<0?true:false;
}
bool operator > (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)>0?true:false;
}
bool operator == (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)==0?true:false;
}
*/

int main(){
/*list<int> a;
a.push_back(4);
a.push_back(3);
a.push_back(2);
a.push_back(8);
a.push_back(7);
a.push_back(5);
a.push_back(6);
a.push_back(9);
a.push_back(10);
a.push_back(1);

//list的sort函数实现方法，如下

list<int> carry;
list<int> counter[64];
int fill=0;
while(!a.empty()){
carry.splice(carry.begin(),a,a.begin());
int i=0;
while(i<fill&&!counter[i].empty()){
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if(i==fill)++fill;
}
for(int i=1;i<fill;++i){
counter[i].merge(counter[i-1]);
a.swap(counter[fill-1]);
}
for(list<int>::iterator j=a.begin();j!=a.end();j++){
cout<<*j<<endl;
}
*/
//其它函数使用示例,如下：

student s[]={
{"童进",23,"武汉","XXX"},
{"老大",23,"武汉","XXX"},
{"饺子",23,"武汉","XXX"}
};
list<student> classA;
classA.push_back(s[0]);
classA.insert(classA.begin(),s[1]);
classA.push_back(s[3]);
cout<<classA.begin()->name<<endl;
//classA.sort();//对于自定义结构体，没有重载</>/==这些操作符，故无法排序

//自己创建一个新类studentNew重载操作符再进行判断
studentNew m1("童进",23,"武汉","XXX");
studentNew m2("老大",23,"武汉","XXX");
studentNew m3("饺子",23,"武汉","XXX");
list<studentNew> classNew;
classNew.push_back(m1);
classNew.push_back(m2);
classNew.push_back(m3);
//判断友元函数是否起作用
if( m1>m2 ){
cout<<"新类中操作已经重载成功"<<endl;
}
//运用SGI STL库时
//用函数对象studentNew,替换了greater<T>
classNew.sort(studentNew());
//若用VC自带的STL库时,下面这样书写即可实现.至于为何有这样的差异,目前我还不知
// classNew.sort();
for(list<studentNew>::iterator m=classNew.begin();m!=classNew.end();m++){//通过结果可以看出
cout<<m->name<<endl;//classNew已经进行了重新排列
}

list<string> classB;
classB.push_back("童");
classB.push_back("兰");
classB.push_front("张");
classB.push_back("童");
classB.sort();//对于string类型,有默认类型的greater<T>
classB.unique();//剔除重复数据
for(list<string>::iterator k=classB.begin();k!=classB.end();k++){
cout<<*k<<endl;
}
return 0;
}

C++ STL学习笔记五 slist单向链表容器

/*
*
********************************************
*slist单向链表容器的基础说明：
********************************************
*
*slist是SGI C++STL自设的一个容器，要安装配置stlport才可以使用
*
*Front Insertion Sequence
*slist为单向链表的泛化容器,故不再支持迭代器的反向移动
*
*使用slist必须使用宏语句#include <slist>
*
**************************************************************************************
*
*创建slist对象:
*1.slist<int> a;
*2.slist<int> a(10);//具有10个元素的对象a，每个元素默认值为0
*3.slist<char> a(5,'k');
*4.slist<char> b(a);
*5.slist(InputIterator first,InputIterator last);//slist<char> c(a.begin(),a.end())
*
**************************************************************************************
*
*初始化赋值
*void push_front(const T& value)
*
**************************************************************************************
*
*遍历访问
*仅定义了向前移动的迭代器iterator和const_iterator
*iterator begin();iterator end();
*
**************************************************************************************
*
*常用函数
*
*void swap(slist&);
*iterator insert_after(iterator pos,const T& x);//注意与前面不同的是，这里是在POS位置之后进行插入
*//vector、deque、list都是POS前插入
*iterator insert(iterator pos,const T& X);//找到pos的前驱，再调用insert_after进行插入(pos前插入)
*
*void pop_front();
*
*iterator erase(iterator pos);
*iterator erase(iterator first,iterator last);//注意是半闭区间[first,last)
*void clear();
*void remove(const T& x);//删除所有等于value的元素
*
*void splice(iterator pos,slist& x);
*void splice(iterator pos,iterator i);
*
*void merge(slist& x);
*
*void sort();//按"<"关系进行排序
*void unique();//删除重复元素，仅保留一个
*
*
*
********************************************
*Author: cumirror
*Email:[e-mail]
********************************************
*
*/

#include <slist>
#include <string>
#include <iostream>
using namespace std;

//具体使用请参照前面的容器例子，这里不进行举例说明
int main(){
slist<string> a;
a.push_front("武汉");
a.push_front("长沙");
for(slist<string>::iterator i=a.begin();i!=a.end();i++){
cout<<*i<<endl;
}
return 0;
}

C++ STL学习笔记六 bit_vector位向量容器

C++ STL学习笔记七 set容器

/*
*
********************************************
*set集合容器的基础说明：
********************************************
*
*set集合容器使用RB-Tree的平衡二叉检索树的数据结构,不允许插入重复键值
*每个子树根节点的键值大于左子树所有节点的键值，而小于右子树所有节点的所有键值
*插入过程中要进行平衡处理，但检索过程效率高
*
*提供了元素插入、删除、检索的功能
*Unique Sorted Associative Container Simple Associative Container
*
*使用set必须使用宏语句#include <set>
*
**************************************************************************************
*
*创建set对象:
*1.set<int> a;
*2.set(const key_compare& comp)//指定一个比较函数对象comp来创建set对象
*
*srtuct strLess{
*bool operator()(const char* s1,const char* s2) const{
*return strcmp(s1,s2)<0;
*}
*};
*set<const char*,strLess> s(strLess());
*
* 3.set(const set&);//set<int> b(a);
*4.set(first,last);//set<char> c(a.begin(),a.end())
*5.set(first,last,const key_compare& comp);
**************************************************************************************
*
*元素的插入//不允许插入重复键值
*pair<iterator,bool> insert(const value_type& v);//可用于判断是否重复插入元素,对于特殊的信息可以提供这样的判断
*iterator insert(iterator pos,const value_type& v);
*void insert(first,last);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();
*reverse_iterator rbegin();reverse_iterator rend();
*
*iterator find(const key_type& k) const;
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*void swap();
*
*//下面三个函数还没找到合适的例子，故不做说明
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <set>
#include <iostream>

//自定义数据的插入
struct student{
char name[20];
int age;
char city[20];
char phone[20];
bool operator()(const student& a,const student& b) const{
return strcmp(a.name,b.name)<0;
}
};

int main(){
using namespace std;
set<int> a;
a.insert(10);
a.insert(19);
a.insert(8);
a.insert(102);
a.insert(1);
pair<set<int>::iterator, bool> p=a.insert(18);
if(p.second){
cout<<"插入的新元素为："<<*(p.first)<<endl;
}
else{
cout<<"已存在该元素，重复插入"<<endl;
}

set<int>::iterator i=a.find(8);
//*i=250;//与侯捷STL源码剖析237页所述有出入
cout<<*i<<endl;//原文为：企图通过迭代器改变元素是不被允许的
//a.insert(251);//但VC6.0编译运行没有问题，只是set中的排序不正确了
//即使重新插入251，因没有违反红黑树标准，错误不被修正
//是否是因为STL版本问题:换STLport后编译果然报错
//vc6.0中的STL库存在一定问题,大家注意
cout<<"元素访问："<<endl;
for(set<int>::iterator j=a.begin();j!=a.end();j++){
cout<<*j<<endl;
}

//为何称为容器，我认为在于对于用户自定义数据的包容，故写如下例子进行测试验证
//也可以尝试用age作为判断条件
student stu1={"童进",23,"武汉","XXX"};
student stu2={"老大",28,"武汉","XXX"};//老大，你成熟了5岁，哈哈
student stu3={"饺子",23,"武汉","XXX"};
set<student,student> b(student());
b.insert(stu1);
b.insert(stu2);
b.insert(stu3);

student stu4={"饺子123",88,"福州","XXX"};
pair<set<student,student>::iterator,bool> query=b.insert(stu4);
if(query.second==false)//query.first返回插入元素的迭代器;query.second代表插入是否成功,true成功:false失败
cout<<"重复元素插入会失败"<<endl;
cout<<query.first->name<<endl;
for(set<student,student>::iterator k=b.begin();k!=b.end();k++){
cout<<k->name<<endl;
}

//student test1={"老大",23,"武汉","XXX"};//这样的元素，可以找到
//set<student,student>::iterator v=b.find(test1);
//student test2={"",23,"武汉","XXX"};//无法找到
//set<student,student>::iterator v=b.find(test2);
student test3={"老大",99,"",""};//可以找到，推测：
set<student,student>::iterator v=b.find(test3);//1.键值的设定依据key_compare()函数中的设置
cout<<v->age<<endl;//2.键值直接为定义数据类型中的第一个元素
//结论：推测1正确。
//可以修改operator()函数进行验证，也可以看后续multiset中的例子
return 0;
}

C++ STL学习笔记八 multiset多重集合容器

/*
*
********************************************
*multiset多重集合容器的基础说明：
********************************************
*
*multiset多重集合容器使用RB-Tree的平衡二叉检索树的数据结构。
*允许将重复键值的元素插入到multiset中
*插入过程中要进行平衡处理，但检索过程效率高
*
*提供了元素插入、删除、检索的功能
*Sorted Associative Container Simple Associative Container Multiple Associative Container
*
*使用multisetr必须使用宏语句#include <set>//与set相同
*
**************************************************************************************
*
*创建multisetr对象:
*template < class Key, class Compare=less<Key>, class Alloc=alloc >
*
*1.multisetr<int> a;
*2.multisetr(const key_compare& comp)//指定一个比较函数对象comp来创建set对象，详细使用见main()中示例
* 3.multisetr(const multisetr&);//multisetr<int> b(a);
*4.multisetr(first,last);//multisetr<char> c(a.begin(),a.end())
*5.multisetr(first,last,const key_compare& comp);//依据comp函数进行插入排序
**************************************************************************************
*
*元素的插入
*iterator insert(const value_type& v);//不再是返回pair，而是插入的迭代器位置
*iterator insert(iterator pos,const value_type& v);
*void insert(first,last);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();//企图通过迭代器改变元素是不被允许的
*reverse_iterator rbegin();reverse_iterator rend();
*
*iterator find(const key_type& k) const;
*pair<iterator,iterator> equal_range(const key_type& k) const;//返回的pair对象，
*//first为lower_bound(k);大于等于k的第一个元素位置
*//second为upper_bound();大于k的第一个元素位置
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*size_type count(const key_type& k) const;//返回键值等于k的元素个数
*void swap();
*
*//main中包含了一下函数的简单例子
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <set>
#include <iostream>

//自定义数据的插入
struct student{
char name[20];
int age;
char city[20];
char phone[20];
};

//这里采用函数对象的方式设置,与set中有不同,key设置为city,注意应设置为public
class stuCmp{
public:
bool operator()(const student& a,const student& b) const{
return strcmp(a.city,b.city)<0;
}
};

//对于一些基本数据类型，如int，string等可参照set
int main(){
using namespace std;
student stu1={"童进",23,"长沙","XXX"};
student stu2={"老大",28,"武汉","XXX"};//老大，你成熟了5岁，哈哈
student stu3={"饺子",23,"福州","XXX"};
//multiset<student,stuCmp> b;
multiset<student,stuCmp> b(stuCmp());
b.insert(stu1);
b.insert(stu2);
b.insert(stu3);
//武汉同学最多,只是现在大家又都天各一方
student stu4={"小芳",23,"武汉","XXX"};
student stu5={"黄庆",23,"武汉","XXX"};
student stu6={"英俊",23,"武汉","XXX"};
b.insert(stu4);
b.insert(stu5);
b.insert(stu6);

for(multiset<student,stuCmp>::iterator i=b.begin();i!=b.end();i++){
cout<<i->name<<endl;
}

student key={"",99,"武汉","XXX"};
cout<<"武汉朋友数目："<<b.count(key)<<endl;
cout<<"武汉的第一个朋友："<<b.lower_bound(key)->name<<endl;
cout<<"武汉最后一个朋友："<<(--b.upper_bound(key))->name<<endl;//这里武汉是最后的,再大于这个键值,就会返回end()指向头节点,所以--
for(multiset<student,stuCmp>::reverse_iterator j=b.rbegin();j!=b.rend();j++){
cout<<j->name<<endl;
}

//验证set中的猜测,此时键值为city
student test={"路人甲",99,"武汉","XXX"};
multiset<student,stuCmp>::iterator v=b.find(test);//返回第一个与键值相等的迭代器
cout<<"寻找武汉的路人甲："<<v->name<<endl;

//元素搜索
cout<<"搜索武汉的朋友们："<<endl;
pair<multiset<student,stuCmp>::iterator,multiset<student,stuCmp>::iterator> p=b.equal_range(test);
for(multiset<student,stuCmp>::iterator k=p.first;k!=p.second;k++){
cout<<k->name<<endl;
}
return 0;
}

C++ STL学习笔记九 map映照容器

/*
*
********************************************
*map映照容器的基础说明：
********************************************
*
*map映照容器:容器的数据结构采用红黑树进行管理,插入的元素键值不允许重复
*map的所有元素都是pair:第一元素为键值(key),不能修改;第二元素为实值(value),可被修改
*
*map和list一样,使用insert或erase后,操作前的所有迭代器,在操作完成后依然有效
*[]:不仅可用键值的数组方式访问元素的映照数据,还可用来添加map容器的元素//main中示例
*
*Sorted Associative Container Pair Associative Container Unique Associative Container
*
*使用map必须使用宏语句#include <map>
*
**************************************************************************************
*
*创建map对象:
*1.map<char,int,greater<char> > a;//元素键值类型为char,映照数据类型为int,键值的比较函数对象为greater<char>
*2.map(const key_compare& comp)//指定一个比较函数对象comp来创建map对象
* 3.map(const map&);//map<int,char*> b(a);//此时使用默认的键值比较函数less<int>
*4.map(first,last);
*5.map(first,last,const key_compare& comp);
*
*//Example:
*pair<const int ,char> p1(1,'a');
*pair<const int ,char> p2(2,'b');
*pair<const int ,char> p3(3,'c');
*pair<const int ,char> p4(4,'d');
*pair<const int ,char> pairArray[]={p1,p2,p3,p4};
*map<const int,char> m4(pairArray,pairArray+5);
*map<const int,char> m3(m4);
*map<const int,char,greater<const int> > m5(pairArray,pairArray+5,greater<const int>());
*
**************************************************************************************
*
*元素的插入
*//typedef pair<const key,T> value_type;
*pair<iterator,bool> insert(const value_type& v);
*iterator insert(iterator pos,const value_type& v);
*void insert(first,last);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();//企图通过迭代器改变元素是不被允许的
*reverse_iterator rbegin();reverse_iterator rend();
*
*iterator find(const key_type& k) const;
*pair<iterator,iterator> equal_range(const key_type& k) const;//返回的pair对象，
*//first为lower_bound(k);大于等于k的第一个元素位置
*//second为upper_bound();大于k的第一个元素位置
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*void swap();
*
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <map>
#include <string>
#include <iostream>

//基本操作与set类似,牢记map中所有元素都是pair
//对于自定义类,初学者会觉得比较函数如何构造很麻烦,这个可以参照前面的书写示例
//但若设置键值为int或char类型，无须构造比较函数

struct student{
char* name;
int age;
char* city;
char* phone;
};

struct strCmp{
bool operator () (const char* a,const char* b) const{
return strcmp(a,b)<0;
}
};

struct strCmpBig{
bool operator () (const char* a,const char* b) const{
return strcmp(a,b)>0;
}
};

int main(){
using namespace std;
//使用[]操作符
map<string,int> animal;
animal[string("fish")]=12;
animal[string("dog")]=10;
animal[string("cat")]=5;
cout<<animal["cat"]<<endl;

//string类有默认的比较函数,故下面的语句可以执行,若换为char*类型,则执行会出现问题
//迭代器i指向pair类型
for(map<string,int>::iterator i=animal.begin();i!=animal.end();i++){
cout<<"The number of "<<i->first<<" : "<<i->second<<endl;
}

student s[]={
{"童进",23,"武汉","XXX"},
{"老大",23,"武汉","XXX"},
{"饺子",23,"武汉","XXX"}
};
pair<int,student> p1(4,s[0]);
pair<int,student> p2(2,s[1]);
pair<int,student> p3(3,s[2]);
map<int,student> a;
a.insert(p1);
a.insert(p2);
a.insert(p3);
//按照键值2、3、4进行排列输出
for(map<int,student>::iterator j=a.begin();j!=a.end();j++){
cout<<"The name: "<<j->second.name<<" "<<"age: "<<j->second.age<<" "
<<"city: "<<j->second.city<<" "<<"phone: "<<j->second.phone<<endl;
}

//思考，这是按照键值进行排列，若我想变换，按照name或者年龄进行重新排列，那么又该如何实现呢？

cout<<"新的排列"<<endl;
pair<const char*,student> q1(s[0].name,s[0]);
pair<const char*,student> q2(s[1].name,s[1]);
pair<const char*,student> q3(s[2].name,s[2]);

student testStu={"AB",23,"武汉","XXX"};

//为何要采用函数对象的形式，而不只能是函数，这个与C++内部实现机制有关

map<const char*,student,strCmp> b;
b.insert(q1);
b.insert(q2);
b.insert(q3);

//insert函数的测试,观察其放回迭代器的值,可改变名字看看,插入位置视实际情况定
//返回插入元素的迭代器
pair<const char*,student> q4(testStu.name,testStu);
map<const char*,student,strCmp>::iterator test=b.insert(b.begin()++,q4);
cout<<test->second.name<<endl;

for(map<const char*,student,strCmp>::iterator k=b.begin();k!=b.end();k++){
cout<<"The name: "<<k->second.name<<" "<<"age: "<<k->second.age<<" "
<<"city: "<<k->second.city<<" "<<"phone: "<<k->second.phone<<endl;
}

//拷贝的时候也可以进行函数对象的设置，那如果函数对象变换了，能实现顺序的变化吗？
//目前还没实现，不知道具体可行吗？以后再进行测试吧

//个人观点：不可行。函数对象比较的是key，若重新排列，key不能变换，
//那么所谓的重新排列，岂不仅仅是反序排列，而反序输出map已经具有了这样的函数了。

cout<<"拷贝时实现重新排列"<<endl;//并未实现
map<const char*,student,strCmp> c(b);
for(map<const char*,student,strCmp/*strCmpBig*/>::iterator m=c.begin();m!=c.end();m++){
cout<<"The name: "<<m->second.name<<" "<<"age: "<<m->second.age<<" "
<<"city: "<<m->second.city<<" "<<"phone: "<<m->second.phone<<endl;
}

return 0;
}

C++ STL学习笔记十 multimap多重映照容器

/*
*
********************************************
*multimap多重映照容器的基础说明：
********************************************
*
*multimap多重映照容器:容器的数据结构采用红黑树进行管理
*multimap的所有元素都是pair:第一元素为键值(key),不能修改;第二元素为实值(value),可被修改
*
*multimap特性以及用法与map完全相同，唯一的差别在于:
*允许重复键值的元素插入容器(使用了RB-Tree的insert_equal函数)
*因此:
*键值key与元素value的映照关系是多对多的关系
*没有定义[]操作运算
*
*Sorted Associative Container Pair Associative Container Unique Associative Container
*
*使用multimap必须使用宏语句#include <map>
*
**************************************************************************************
*
*创建multimap对象:
*1.multimap<char,int,greater<char> > a;//元素键值类型为char,映照数据类型为int,键值的比较函数对象为greater<char>
*2.multimap(const key_compare& comp)//指定一个比较函数对象comp来创建map对象
* 3.multimap(const multisetr&);//multimap<int,char*> b(a);//此时使用默认的键值比较函数less<int>
*4.multimap(first,last);
*5.multimap(first,last,const key_compare& comp);
*
*//Example:
*pair<const int ,char> p1(1,'a');
*pair<const int ,char> p2(2,'b');
*pair<const int ,char> p3(3,'c');
*pair<const int ,char> p4(4,'d');
*pair<const int ,char> pairArray[]={p1,p2,p3,p4};
*multimap<const int,char> m4(pairArray,pairArray+5);
*multimap<const int,char> m3(m4);
*multimap<const int,char,greater<const int> > m5(pairArray,pairArray+5,greater<const int>());
*
**************************************************************************************
*
*元素的插入
*//typedef pair<const key,T> value_type;
*pair<iterator,bool> insert(const value_type& v);
*iterator insert(iterator pos,const value_type& v);
*void insert(first,last);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();//企图通过迭代器改变元素是不被允许的
*reverse_iterator rbegin();reverse_iterator rend();
*
*iterator find(const key_type& k) const;
*pair<iterator,iterator> equal_range(const key_type& k) const;//返回的pair对象，
*//first为lower_bound(k);大于等于k的第一个元素位置
*//second为upper_bound();大于k的第一个元素位置
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*size_type count(const key_type& k) const;//返回键值等于k的元素个数
*void swap();
*
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <map>
#include <string>
#include <iostream>

//基本操作与set类型,牢记map中所有元素都是pair
//对于自定义类,初学者会觉得比较函数如何构造很麻烦,这个可以参照前面的书写示例
//但若设置键值为int或char类型，无须构造比较函数

struct student{
char* name;
int age;
char* city;
char* phone;
};

int main(){
using namespace std;

student s[]={
{"童进",23,"武汉","XXX"},
{"老大",23,"武汉","XXX"},
{"饺子",23,"武汉","XXX"},
{"王老虎",23,"武汉","XXX"},
{"周润发",23,"武汉","XXX"},
{"周星星",23,"武汉","XXX"}
};
pair<int,student> p1(4,s[0]);
pair<int,student> p2(2,s[1]);
pair<int,student> p3(3,s[2]);
pair<int,student> p4(4,s[3]);//键值key与p1相同
pair<int,student> p5(5,s[4]);
pair<int,student> p6(6,s[5]);
multimap<int,student> a;
a.insert(p1);
a.insert(p2);
a.insert(p3);
a.insert(p4);
a.insert(p5);
a.insert(p6);
typedef multimap<int,student>::iterator int_multimap;
pair<int_multimap,int_multimap> p=a.equal_range(4);
int_multimap i=a.find(4);
cout<<"班上key值为"<<i->first<<"的学生有："<<a.count(4)<<"名,"<<" 他们是:"<<endl;
for(int_multimap k=p.first;k!=p.second;k++){
cout<<k->second.name<<endl;
}
cout<<"删除重复键值的同学"<<endl;
a.erase(i);
cout<<"现在班上总人数为："<<a.size()<<". 人员如下："<<endl;
for(multimap<int,student>::iterator j=a.begin();j!=a.end();j++){
cout<<"The name: "<<j->second.name<<" "<<"age: "<<j->second.age<<" "
<<"city: "<<j->second.city<<" "<<"phone: "<<j->second.phone<<endl;
}

return 0;
}

C++ STL学习笔记十一 hash_set哈希集合容器

/*
*
************************************************************************************
*hash_set哈希集合容器的基础说明：
************************************************************************************
*
*hash_set哈希集合容器:使用hashtable数据结构的具有高效数据检索的关联容器
*
*不提供反向迭代器，只有前向迭代器iterator和const_iterator
*不允许插入重复的元素键值
*Hashed Associative Container Simple Associative Container Unique Associative Container
*
*目前还不是C++的标准容器，只是SGI C++ STL的一个扩展容器
*使用hash_set必须使用宏语句#include <hash_set>
*
**************************************************************************************
*
*创建hash_set对象:
*1.hash_set<int> hs;//键值比较使用默认的函数对象equal_to<Value>
*2.hash_set(size_type n);//在质数列表中找出第一个大于等于n的质数作为表长:hash_set<int> hs(100);
* 3.hash_set(size_type n,const hasher& h);//hash函数对象为h
*4.hash_set(size_type n,const hasher& h,const key_equal& k);//键值比较函数对象k
*5.hash_set(const hash_set& h);//用一个hash集合容器拷贝生成另一个hash集合容器:hash_set<int> hs2(hs);
*
**************************************************************************************
*
*元素的插入
*//typedef pair<const key,T> value_type;
*pair<iterator,bool> insert(const value_type& v);//second:返回true/false插入成功标志
*void insert(iterator pos,const value_type& v);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();//不会将元素排序遍历出来
*
*iterator find(const key_type& k) const;//对于非默认类型如char*,在搜素时应定义相关的函数对象
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*size_type bucket_count(const key_type& k) const;//获得hash表的表长
*void swap();
*resize();
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*在SGI STL中，提供了以下hash函数：
*struct hash<char*>
*struct hash<const char*>
*struct hash<char>
*struct hash<unsigned char>
*struct hash<signed char>
*struct hash<short>
*struct hash<unsigned short>
*struct hash<int>
*struct hash<unsigned int>
*struct hash<long>
*struct hash<unsigned long>
*
*hash函数决定了如何划分散列表
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <hash_set>
#include <iostream>

struct student{
char* name;
int age;
char* city;
char* phone;
};
//自定义数据的比较函数
class stuequal{
public:
bool operator() (const student& a,const student& b){
return strcmp(a.city,b.city)==0;//不允许同名，name为键值
}//将name换为city测试下
};
//自定义数据的hash函数
//typedef unsigned int size_t;
struct stu_hash{
size_t operator()(const student& stu) const
{
unsigned long res = 0;
char* s=stu.city;
for( ; *s; ++s ){
res=5*res+*s;
}
return size_t(res);
}
};

//针对字符串的比较函数对象
class strequal{
public:
bool operator () (const char* a,const char* b)const{
return strcmp(a,b)==0;
}
};

int main(){
using namespace std;

hash_set<const char*,hash<const char*>,strequal> a;
a.insert("tongjin");
a.insert("cumirror");
a.insert("makelaugh");
a.insert("feiguodeyun");

//hash<const char*>默认提供的hash函数对象
hash_set<const char*,hash<const char*>,strequal>::const_iterator b=a.find("tongjin");
cout<<*b<<" is "<<(b!=a.end()?"present":"not present")<<endl;

//对于自定义类型数据,使用hash相关容器时应构造hash函数对象、比较函数对象
//注意区别hash函数对象与比较函数对象各自的作用
student s[]={
{"童进",23,"长沙","XXX"},
{"老大",23,"武汉","XXX"},
{"饺子",23,"福州","XXX"},
{"王老虎",23,"地球","XXX"},
{"周润发",23,"香港","XXX"},
{"周星星",23,"香港","XXX"},//city重复
{"童进",23,"香港","XXX"}//name重复、city也有重复
};

hash_set<student,stu_hash,stuequal> c;
c.insert(s[0]);
c.insert(s[1]);
c.insert(s[2]);
c.insert(s[3]);
c.insert(s[4]);
c.insert(s[5]);
c.insert(s[6]);
//注意hash容器并不能实现排序
for(hash_set<student,stu_hash,stuequal>::iterator i=c.begin();i!=c.end();i++){
cout<<i->name<<""<<i->age<<""<<i->city<<endl;
}
return 0;
}

C++ STL学习笔记十二 hash_map映照容器

/*
*
************************************************************************************
*hash_map映照容器的基础说明：
************************************************************************************
*
*hash_map哈希映照容器:使用hash表的数据结构,插入的元素键值不允许重复
*hash_map的所有元素都是pair:第一元素为键值(key),不能修改;第二元素为实值(value),可被修改
*
*不提供反向迭代器,只有前向迭代器iterator和const_iterator
*可定义出操作符[]
*
*Hashed Associative Container Pair Associative Container Unique Associative Container
*
*目前还不是C++的标准容器，只是SGI C++ STL的一个扩展容器
*使用hash_map必须使用宏语句#include <hash_map>
*可与map作比较:hash_map检索时使用的键值比较次数少，容器需占用较多的空间，用迭代器遍历出来的元素是非排序的；
*map则使用链表的二分法进行检索，空间使用率高，遍历出来的元素是排序的，而且可提供反向迭代器。
*
**************************************************************************************
*
*创建map对象:
*1.hash_map<char,int> a;//键值类型为char,映照数据类型为int,默认表长为193
*2.hash_map(size_type n);//hash_map<char,int> a(300);此时表长为389
* * 3.hash_map(size_type n,const hasher& h);
* *4.hash_map(size_type n,const hasher& h,const key_equal& k);
*5.hash_map(const hash_map&);
*
*//Example4:
*struct strequal{
*bool operator() (const char* a,const char* b) const {
*return strcmp(a,b)==0;}
*};
*hash_map<char*,int,hash<char*>,strequal> hm(300,hash<char*>(),strequal());
*
**************************************************************************************
*
*元素的插入
*//typedef pair<const key,T> value_type;
*pair<iterator,bool> insert(const value_type& v);
*void insert(first,last);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();//企图通过迭代器改变元素是不被允许的
*
*iterator find(const key_type& k) const;
*pair<iterator,iterator> equal_range(const key_type& k) const;//此时键值不允许重复，故没有太大用途
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*size_type bucket_count(const key_type& k) const;//获得hash表的表长
*void swap();
*resize();
*void swap();
*
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <string>
#include <hash_map>
#include <iostream>
using namespace std;

template<class Key,class NameType,class AgeType,class AdressType>
struct StudentRecord_tag{//学生记录结构体
struct StudentInfo_tag{
NameType name;
AgeType age;
AdressType city;
};
typedef Key IdType;
typedef StudentInfo_tag StudentInfo;
IdType id;
StudentInfo stuinfo;
};

//针对最后的示例，设置的hash函数
struct myhash{
size_t operator() (const string& str) const
{
unsigned long __h = 0;
for (size_t i = 0 ; i < str.size() ; i ++)
__h = 5*__h + str[i];
return size_t(__h);
}
};

class str_compare{
public:
bool operator()(const string& str1,const string& str2)const
{
return str1==str2;
}
};

int main(){
//使用[]操作符
hash_map<string,int> animal;
animal[string("fish")]=12;
animal[string("dog")]=10;
animal[string("cat")]=5;
cout<<animal["cat"]<<endl;
//结构体A中定义的结构体B，在结构体A外可以使用吗？
//StudentInfo_tag a;//直接这样是无法使用的,若想独立使用可以参照下面的方法
//typedef StudentRecord_tag<int,char*,int,char*> StudentRecorda;
//StudentRecorda::StudentInfo_tag testa;

typedef StudentRecord_tag<int,char*,int,char*> StudentRecord;
StudentRecord stuArray[]={
{192,"黄庆",23,"北京"},
{191,"童进",23,"长沙"},
{194,"饺子",23,"福州"},
{193,"小芳",23,"宁波"},
};
//此处应该留意typedef的使用
hash_map<StudentRecord::IdType,StudentRecord::StudentInfo> school;
typedef pair<const StudentRecord::IdType,StudentRecord::StudentInfo> value_type;
for(int i=0;i<4;i++){
value_type p(stuArray[i].id,stuArray[i].stuinfo);
school.insert(p);
}
//测试是否插入成功
cout<<school[193].name<<endl;
//采用迭代器访问，注意map类型容器，其元素为pair类型，pair中first/second要明白
hash_map<StudentRecord::IdType,StudentRecord::StudentInfo>::iterator j;
cout<<"同学"<<""<<"住址"<<endl;
for(j=school.begin();j!=school.end();j++){
cout<<j->second.name<<""<<
j->second.city<<endl;
}
//其它函数示例
//元素的重复插入
value_type p(stuArray[0].id,stuArray[0].stuinfo);
pair<hash_map<const StudentRecord::IdType,StudentRecord::StudentInfo>::iterator,bool> insertReturn;
cout<<(
(insertReturn=school.insert(p)).second==true?"插入成功":"插入失败"
)
<<endl;
cout<<"总人数："<<school.size()<<endl;
cout<<"hash表长："<<school.bucket_count()<<endl;

//如下思考：

//上例中key:IdType为int型,故不用定义hash函数对象,也可将IdType定为string类型，形如"0120504140227"这样的类型
//此时需要定义hash函数,具体解法如下:(在原来定义的变量名后+1)

//原想在上面例子的基础上进行改进,但不成功，可能与string类型内存分配模式有关

//typedef StudentRecord_tag< string,char*,int,char*> StudentRecord1;
//StudentRecord1 stuArray1[]={//不好意思,你们暂时先入我班吧
//{string("0120504140208"),"黄庆",23,"北京"},
//{string("0120504140227"),"童进",23,"长沙"},
//{string("0120504140209"),"饺子",23,"福州"},
//{string("0120504140216"),"小芳",23,"宁波"},
//};
//hash_map<StudentRecord1::IdType,StudentRecord1::StudentInfo,myhash> school1;
//typedef pair<const StudentRecord1::IdType,StudentRecord1::StudentInfo> value_type1;
//for(int i=0;i<4;i++){
//value_type1 p(stuArray1[i].id,stuArray1[i].stuinfo);
//school.insert(p);
//}

//在网上看到一份较为简单的例子,根据自己的稍稍改了下(注意前面的hash函数与比较函数)
hash_map<string,string,myhash,str_compare> myHash;
string strArray[][2]={
{"0120504140227","童进"},
{"0120504140236","zyl"},
{"0120504140216","hq"},
{"0120504140209","jz"},
};
typedef pair<string,string> value_type2;

for(int k=0;k<4;k++){
value_type2 p(strArray[k][0],strArray[k][1]);
myHash.insert(p);
}
hash_map<string,string,myhash,str_compare>::iterator p1;
for(p1=myHash.begin();p1!=myHash.end();p1++){
cout<<p1->first<<""<<
p1->second<<endl;
}
return 0;
}

为何要学习STL：

数据结构与算法是编程的核心，STL中包含各种数据结构和优秀的算法，确实值得深入学习，本文中虽然着重使用，但希望有心的朋友能多看看相关数据结构的实现，对于C++语言确实会有较大帮助。

STL库有多个版本，我采用的是SGI版本，编译安装方法请参考如下链接：

http://blog.csdn.net/hong201/archive/2009/07/06/4322975.aspx

PS：按照网上孟岩老师的安装方法，我出现了一些问题，后来按照上面文章所说的安装成功。

关于为何采用SGI版本STL库，目前我并没有较深感触，网上的说法是：

1.开源

2.可读性强

3.自设了一些容器，如slist、hash_set等

谈点我的感觉：运用VC自带库使用set容器时，发现可以通过迭代器来改变set的元素，改变会破坏红黑树，但编译通过，这个是比较严重的BUG。

可以的话建议安装SGI版本的STL库。

在笔记中，我主要介绍各容器的用法，工具选用VC6.0。关于自定义类型数据如何使用容器，这个是许多人纠结的问题，我尽量写一些例子。

因为是新学C++，所以文中不可避免会存在错误的地方，希望大家批评指正。

/*
*
********************************************
*deque双端队列容器的基础说明：
********************************************
*
*
*可进行随机访问，在**头部和尾端**插入、删除元素，时间复杂度为O(1)
*Random Access Container Back Insertion Sequence Front Insertion Sequence
*
************************************************************************************
*当考虑容器元素的内存分配策略和操作的性能时，deque较vector更具优势*
*map管理块，块中包含一组数据，内存分配更细致(以块为单位，使用二级的MAP进行管理)*
************************************************************************************
*
*使用deque必须使用宏语句#include <deque>
*
**************************************************************************************
*
*创建deque对象:
*1.deque<int> a;
*2.deque<int> a(10);//具有10个元素的对象a，每个元素默认值为0
*3.deque<char> a(5,'k');
*4.deque<char> b(a);//deque<char> c(a.begin(),a.end())
*
**************************************************************************************
*
*初始化赋值
*void push_back(const T& value)
*
**************************************************************************************
*
*遍历访问
*reference operator[](size_type n)
*iterator begin()
*iterator end()
*
**************************************************************************************
*
*常用函数
*
*bool empty();
*size_type size();size_type max_size();//无size_type capacity();reverse();
*reference front();reference back();
*void pop_front();void push_front();//相较vector增加部分
*void pop_back();void push_back();
*void clear();
*//还有些函数直接见代码如erase();
*
*
*
********************************************
*Author: cumirror
*Email:[e-mail]
********************************************
*
*/

#include <iostream>
#include <deque>

int main()
{
using namespace std;
deque<int> a(10,5);

//数组方式
cout<<"数组方式访问:"<<endl;
a[0]=100;
for(int s=0;s<a.size();s++){
cout<<a[s]<<endl;
}

//迭代器方式
cout<<"迭代器方式访问:"<<endl;
deque<int>::iterator i,iend;
i=a.begin();
iend=a.end();
*i=101;
for(deque<int>::iterator j=i;j!=iend;j++){
cout<<*j<<endl;
}

//注意插入删除时迭代器的失效问题,偷个懒,大家可以看下面的网页,里面有说明但没介绍原因,其实这与各个容器是如何实现的有很大关系,若想深究可看《STL源码剖析》
//http://blog.csdn.net/jokenchang2000/archive/2008/07/01/2603485.aspx
cout<<"插入"<<endl;
a.insert(a.begin(),102);

//删除时注意，它是一个半闭区间
//也支持 erase(iterator pos)单个元素的删除
cout<<"删除"<<endl;
a.erase(a.begin()+4,a.begin()+6);
for(deque<int>::iterator k=a.begin();k!=a.end();k++){
cout<<*k<<endl;
}

//头部插入
a.push_front(999);

//反向遍历访问
cout<<"反向访问"<<endl;
deque<int>::reverse_iterator ri;
for(ri=a.rbegin();ri!=a.rend();ri++){
cout<<*ri<<endl;
}

deque<int> b;
b.push_back(4);
b.push_back(5);
b.push_front(3);
b.push_front(2);
cout<<"互换"<<endl;
b.swap(a);
for(int l=0;l<a.size();l++){
cout<<a[l]<<endl;
}
return 0;
}

/*
*
********************************************
*list双向链表容器的基础说明：
********************************************
*
*list双向链表容器采用双向链表的数据结构来存储元素数据，可以高效查找、插入、删除容器元素
*
*Reversibe Container Back Insertion Sequence Front Insertion Sequence
*不同于vector，list查找、插入、删除元素的时间复杂度均为O(1)
*
*使用list必须使用宏语句#include <list>
*
**************************************************************************************
*
*创建list对象:
*1.list<int> a;
*2.list<int> a(10);//具有10个元素的对象a，每个元素默认值为0
*3.list<char> a(5,'k');
*4.list<char> b(a);//list<char> c(a.begin(),a.end())
*
**************************************************************************************
*
*初始化赋值
*void push_back(const T& value)
*
**************************************************************************************
*
*遍历访问
*iterator begin()//只能使用迭代器的方式进行遍历
*iterator end()
* iterator rbegin();//反向遍历
* iterator rbegin();
*
**************************************************************************************
*
*常用函数
*
*bool empty();
*
*void pop_front();void pop_back();
*
*void push_front(const T&);void push_back(const T&);
*iterator insert(iterator pos,const T&x);//注意它是插入到pos前
*
*iterator erase(iterator pos);
*iterator erase(iterator first,iterator last);
*void clear();
*void remove(const T& value);
*
*void swap()//通过交换头指针来实现元素的交换
*//list内部提供的一个迁移操作
*void transfer();//transfer(iterator position,iterator first,iterator last)在A链表position位置前插入
*//B链表迭代器区间[first,last)的元素，并将这部分元素从B链表中抹去
*void splice(iterator pos,list& X);//调用transfer函数将一个链表的所有元素全部归并到当前链表，
*//并将链表对象X清空，
*void splice(iterator pos,list& X,iterator i);//将X中迭代器i所指的元素归并到当前链表pos前，并将X中i所指元素抹去
*
*void merge(list&X);//对两个链表进行归并，要求先排序，否则merge没有太大意义
*
*void unique();//可将连续重复的元素删除，只保留一个
*
*
*
********************************************
*Author: cumirror
*Email:[e-mail]
********************************************
*
*/

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

struct student{
char* name;
int age;
char* city;
char* phone;
};

class studentNew{
public:
char name[10];
int age;
char city[10];
char phone[11];
studentNew(){}
studentNew(char* a,int b,char* c,char* d){
strcpy(name,a);
age=b;
strcpy(city,c);
strcpy(phone,d);
}

//为何友元函数在类外定义，出现错误error C2593: 'operator >' is ambiguous
//friend bool operator < (studentNew&a,studentNew& b);
//friend bool operator > (studentNew&a,studentNew& b);
//friend bool operator == (studentNew&a,studentNew& b);

friend bool operator< (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)<0;
}
friend bool operator> (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)>0;
}
friend bool operator== (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)==0;
}

bool operator() (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)==-1;
}
};
/*
bool operator < (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)<0?true:false;
}
bool operator > (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)>0?true:false;
}
bool operator == (studentNew& a,studentNew& b){
return strcmp(a.name,b.name)==0?true:false;
}
*/

int main(){
/*list<int> a;
a.push_back(4);
a.push_back(3);
a.push_back(2);
a.push_back(8);
a.push_back(7);
a.push_back(5);
a.push_back(6);
a.push_back(9);
a.push_back(10);
a.push_back(1);

//list的sort函数实现方法，如下

list<int> carry;
list<int> counter[64];
int fill=0;
while(!a.empty()){
carry.splice(carry.begin(),a,a.begin());
int i=0;
while(i<fill&&!counter[i].empty()){
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if(i==fill)++fill;
}
for(int i=1;i<fill;++i){
counter[i].merge(counter[i-1]);
a.swap(counter[fill-1]);
}
for(list<int>::iterator j=a.begin();j!=a.end();j++){
cout<<*j<<endl;
}
*/
//其它函数使用示例,如下：

student s[]={
{"童进",23,"武汉","XXX"},
{"老大",23,"武汉","XXX"},
{"饺子",23,"武汉","XXX"}
};
list<student> classA;
classA.push_back(s[0]);
classA.insert(classA.begin(),s[1]);
classA.push_back(s[3]);
cout<<classA.begin()->name<<endl;
//classA.sort();//对于自定义结构体，没有重载</>/==这些操作符，故无法排序

//自己创建一个新类studentNew重载操作符再进行判断
studentNew m1("童进",23,"武汉","XXX");
studentNew m2("老大",23,"武汉","XXX");
studentNew m3("饺子",23,"武汉","XXX");
list<studentNew> classNew;
classNew.push_back(m1);
classNew.push_back(m2);
classNew.push_back(m3);
//判断友元函数是否起作用
if( m1>m2 ){
cout<<"新类中操作已经重载成功"<<endl;
}
//运用SGI STL库时
//用函数对象studentNew,替换了greater<T>
classNew.sort(studentNew());
//若用VC自带的STL库时,下面这样书写即可实现.至于为何有这样的差异,目前我还不知
// classNew.sort();
for(list<studentNew>::iterator m=classNew.begin();m!=classNew.end();m++){//通过结果可以看出
cout<<m->name<<endl;//classNew已经进行了重新排列
}

list<string> classB;
classB.push_back("童");
classB.push_back("兰");
classB.push_front("张");
classB.push_back("童");
classB.sort();//对于string类型,有默认类型的greater<T>
classB.unique();//剔除重复数据
for(list<string>::iterator k=classB.begin();k!=classB.end();k++){
cout<<*k<<endl;
}
return 0;
}

/*
*
********************************************
*slist单向链表容器的基础说明：
********************************************
*
*slist是SGI C++STL自设的一个容器，要安装配置stlport才可以使用
*
*Front Insertion Sequence
*slist为单向链表的泛化容器,故不再支持迭代器的反向移动
*
*使用slist必须使用宏语句#include <slist>
*
**************************************************************************************
*
*创建slist对象:
*1.slist<int> a;
*2.slist<int> a(10);//具有10个元素的对象a，每个元素默认值为0
*3.slist<char> a(5,'k');
*4.slist<char> b(a);
*5.slist(InputIterator first,InputIterator last);//slist<char> c(a.begin(),a.end())
*
**************************************************************************************
*
*初始化赋值
*void push_front(const T& value)
*
**************************************************************************************
*
*遍历访问
*仅定义了向前移动的迭代器iterator和const_iterator
*iterator begin();iterator end();
*
**************************************************************************************
*
*常用函数
*
*void swap(slist&);
*iterator insert_after(iterator pos,const T& x);//注意与前面不同的是，这里是在POS位置之后进行插入
*//vector、deque、list都是POS前插入
*iterator insert(iterator pos,const T& X);//找到pos的前驱，再调用insert_after进行插入(pos前插入)
*
*void pop_front();
*
*iterator erase(iterator pos);
*iterator erase(iterator first,iterator last);//注意是半闭区间[first,last)
*void clear();
*void remove(const T& x);//删除所有等于value的元素
*
*void splice(iterator pos,slist& x);
*void splice(iterator pos,iterator i);
*
*void merge(slist& x);
*
*void sort();//按"<"关系进行排序
*void unique();//删除重复元素，仅保留一个
*
*
*
********************************************
*Author: cumirror
*Email:[e-mail]
********************************************
*
*/

#include <slist>
#include <string>
#include <iostream>
using namespace std;

//具体使用请参照前面的容器例子，这里不进行举例说明
int main(){
slist<string> a;
a.push_front("武汉");
a.push_front("长沙");
for(slist<string>::iterator i=a.begin();i!=a.end();i++){
cout<<*i<<endl;
}
return 0;
}

/*
*
********************************************
*set集合容器的基础说明：
********************************************
*
*set集合容器使用RB-Tree的平衡二叉检索树的数据结构,不允许插入重复键值
*每个子树根节点的键值大于左子树所有节点的键值，而小于右子树所有节点的所有键值
*插入过程中要进行平衡处理，但检索过程效率高
*
*提供了元素插入、删除、检索的功能
*Unique Sorted Associative Container Simple Associative Container
*
*使用set必须使用宏语句#include <set>
*
**************************************************************************************
*
*创建set对象:
*1.set<int> a;
*2.set(const key_compare& comp)//指定一个比较函数对象comp来创建set对象
*
*srtuct strLess{
*bool operator()(const char* s1,const char* s2) const{
*return strcmp(s1,s2)<0;
*}
*};
*set<const char*,strLess> s(strLess());
*
* 3.set(const set&);//set<int> b(a);
*4.set(first,last);//set<char> c(a.begin(),a.end())
*5.set(first,last,const key_compare& comp);
**************************************************************************************
*
*元素的插入//不允许插入重复键值
*pair<iterator,bool> insert(const value_type& v);//可用于判断是否重复插入元素,对于特殊的信息可以提供这样的判断
*iterator insert(iterator pos,const value_type& v);
*void insert(first,last);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();
*reverse_iterator rbegin();reverse_iterator rend();
*
*iterator find(const key_type& k) const;
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*void swap();
*
*//下面三个函数还没找到合适的例子，故不做说明
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <set>
#include <iostream>

//自定义数据的插入
struct student{
char name[20];
int age;
char city[20];
char phone[20];
bool operator()(const student& a,const student& b) const{
return strcmp(a.name,b.name)<0;
}
};

int main(){
using namespace std;
set<int> a;
a.insert(10);
a.insert(19);
a.insert(8);
a.insert(102);
a.insert(1);
pair<set<int>::iterator, bool> p=a.insert(18);
if(p.second){
cout<<"插入的新元素为："<<*(p.first)<<endl;
}
else{
cout<<"已存在该元素，重复插入"<<endl;
}

set<int>::iterator i=a.find(8);
//*i=250;//与侯捷STL源码剖析237页所述有出入
cout<<*i<<endl;//原文为：企图通过迭代器改变元素是不被允许的
//a.insert(251);//但VC6.0编译运行没有问题，只是set中的排序不正确了
//即使重新插入251，因没有违反红黑树标准，错误不被修正
//是否是因为STL版本问题:换STLport后编译果然报错
//vc6.0中的STL库存在一定问题,大家注意
cout<<"元素访问："<<endl;
for(set<int>::iterator j=a.begin();j!=a.end();j++){
cout<<*j<<endl;
}

//为何称为容器，我认为在于对于用户自定义数据的包容，故写如下例子进行测试验证
//也可以尝试用age作为判断条件
student stu1={"童进",23,"武汉","XXX"};
student stu2={"老大",28,"武汉","XXX"};//老大，你成熟了5岁，哈哈
student stu3={"饺子",23,"武汉","XXX"};
set<student,student> b(student());
b.insert(stu1);
b.insert(stu2);
b.insert(stu3);

student stu4={"饺子123",88,"福州","XXX"};
pair<set<student,student>::iterator,bool> query=b.insert(stu4);
if(query.second==false)//query.first返回插入元素的迭代器;query.second代表插入是否成功,true成功:false失败
cout<<"重复元素插入会失败"<<endl;
cout<<query.first->name<<endl;
for(set<student,student>::iterator k=b.begin();k!=b.end();k++){
cout<<k->name<<endl;
}

//student test1={"老大",23,"武汉","XXX"};//这样的元素，可以找到
//set<student,student>::iterator v=b.find(test1);
//student test2={"",23,"武汉","XXX"};//无法找到
//set<student,student>::iterator v=b.find(test2);
student test3={"老大",99,"",""};//可以找到，推测：
set<student,student>::iterator v=b.find(test3);//1.键值的设定依据key_compare()函数中的设置
cout<<v->age<<endl;//2.键值直接为定义数据类型中的第一个元素
//结论：推测1正确。
//可以修改operator()函数进行验证，也可以看后续multiset中的例子
return 0;
}

/*
*
********************************************
*multiset多重集合容器的基础说明：
********************************************
*
*multiset多重集合容器使用RB-Tree的平衡二叉检索树的数据结构。
*允许将重复键值的元素插入到multiset中
*插入过程中要进行平衡处理，但检索过程效率高
*
*提供了元素插入、删除、检索的功能
*Sorted Associative Container Simple Associative Container Multiple Associative Container
*
*使用multisetr必须使用宏语句#include <set>//与set相同
*
**************************************************************************************
*
*创建multisetr对象:
*template < class Key, class Compare=less<Key>, class Alloc=alloc >
*
*1.multisetr<int> a;
*2.multisetr(const key_compare& comp)//指定一个比较函数对象comp来创建set对象，详细使用见main()中示例
* 3.multisetr(const multisetr&);//multisetr<int> b(a);
*4.multisetr(first,last);//multisetr<char> c(a.begin(),a.end())
*5.multisetr(first,last,const key_compare& comp);//依据comp函数进行插入排序
**************************************************************************************
*
*元素的插入
*iterator insert(const value_type& v);//不再是返回pair，而是插入的迭代器位置
*iterator insert(iterator pos,const value_type& v);
*void insert(first,last);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();//企图通过迭代器改变元素是不被允许的
*reverse_iterator rbegin();reverse_iterator rend();
*
*iterator find(const key_type& k) const;
*pair<iterator,iterator> equal_range(const key_type& k) const;//返回的pair对象，
*//first为lower_bound(k);大于等于k的第一个元素位置
*//second为upper_bound();大于k的第一个元素位置
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*size_type count(const key_type& k) const;//返回键值等于k的元素个数
*void swap();
*
*//main中包含了一下函数的简单例子
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <set>
#include <iostream>

//自定义数据的插入
struct student{
char name[20];
int age;
char city[20];
char phone[20];
};

//这里采用函数对象的方式设置,与set中有不同,key设置为city,注意应设置为public
class stuCmp{
public:
bool operator()(const student& a,const student& b) const{
return strcmp(a.city,b.city)<0;
}
};

//对于一些基本数据类型，如int，string等可参照set
int main(){
using namespace std;
student stu1={"童进",23,"长沙","XXX"};
student stu2={"老大",28,"武汉","XXX"};//老大，你成熟了5岁，哈哈
student stu3={"饺子",23,"福州","XXX"};
//multiset<student,stuCmp> b;
multiset<student,stuCmp> b(stuCmp());
b.insert(stu1);
b.insert(stu2);
b.insert(stu3);
//武汉同学最多,只是现在大家又都天各一方
student stu4={"小芳",23,"武汉","XXX"};
student stu5={"黄庆",23,"武汉","XXX"};
student stu6={"英俊",23,"武汉","XXX"};
b.insert(stu4);
b.insert(stu5);
b.insert(stu6);

for(multiset<student,stuCmp>::iterator i=b.begin();i!=b.end();i++){
cout<<i->name<<endl;
}

student key={"",99,"武汉","XXX"};
cout<<"武汉朋友数目："<<b.count(key)<<endl;
cout<<"武汉的第一个朋友："<<b.lower_bound(key)->name<<endl;
cout<<"武汉最后一个朋友："<<(--b.upper_bound(key))->name<<endl;//这里武汉是最后的,再大于这个键值,就会返回end()指向头节点,所以--
for(multiset<student,stuCmp>::reverse_iterator j=b.rbegin();j!=b.rend();j++){
cout<<j->name<<endl;
}

//验证set中的猜测,此时键值为city
student test={"路人甲",99,"武汉","XXX"};
multiset<student,stuCmp>::iterator v=b.find(test);//返回第一个与键值相等的迭代器
cout<<"寻找武汉的路人甲："<<v->name<<endl;

//元素搜索
cout<<"搜索武汉的朋友们："<<endl;
pair<multiset<student,stuCmp>::iterator,multiset<student,stuCmp>::iterator> p=b.equal_range(test);
for(multiset<student,stuCmp>::iterator k=p.first;k!=p.second;k++){
cout<<k->name<<endl;
}
return 0;
}

/*
*
********************************************
*map映照容器的基础说明：
********************************************
*
*map映照容器:容器的数据结构采用红黑树进行管理,插入的元素键值不允许重复
*map的所有元素都是pair:第一元素为键值(key),不能修改;第二元素为实值(value),可被修改
*
*map和list一样,使用insert或erase后,操作前的所有迭代器,在操作完成后依然有效
*[]:不仅可用键值的数组方式访问元素的映照数据,还可用来添加map容器的元素//main中示例
*
*Sorted Associative Container Pair Associative Container Unique Associative Container
*
*使用map必须使用宏语句#include <map>
*
**************************************************************************************
*
*创建map对象:
*1.map<char,int,greater<char> > a;//元素键值类型为char,映照数据类型为int,键值的比较函数对象为greater<char>
*2.map(const key_compare& comp)//指定一个比较函数对象comp来创建map对象
* 3.map(const map&);//map<int,char*> b(a);//此时使用默认的键值比较函数less<int>
*4.map(first,last);
*5.map(first,last,const key_compare& comp);
*
*//Example:
*pair<const int ,char> p1(1,'a');
*pair<const int ,char> p2(2,'b');
*pair<const int ,char> p3(3,'c');
*pair<const int ,char> p4(4,'d');
*pair<const int ,char> pairArray[]={p1,p2,p3,p4};
*map<const int,char> m4(pairArray,pairArray+5);
*map<const int,char> m3(m4);
*map<const int,char,greater<const int> > m5(pairArray,pairArray+5,greater<const int>());
*
**************************************************************************************
*
*元素的插入
*//typedef pair<const key,T> value_type;
*pair<iterator,bool> insert(const value_type& v);
*iterator insert(iterator pos,const value_type& v);
*void insert(first,last);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();//企图通过迭代器改变元素是不被允许的
*reverse_iterator rbegin();reverse_iterator rend();
*
*iterator find(const key_type& k) const;
*pair<iterator,iterator> equal_range(const key_type& k) const;//返回的pair对象，
*//first为lower_bound(k);大于等于k的第一个元素位置
*//second为upper_bound();大于k的第一个元素位置
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*void swap();
*
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <map>
#include <string>
#include <iostream>

//基本操作与set类似,牢记map中所有元素都是pair
//对于自定义类,初学者会觉得比较函数如何构造很麻烦,这个可以参照前面的书写示例
//但若设置键值为int或char类型，无须构造比较函数

struct student{
char* name;
int age;
char* city;
char* phone;
};

struct strCmp{
bool operator () (const char* a,const char* b) const{
return strcmp(a,b)<0;
}
};

struct strCmpBig{
bool operator () (const char* a,const char* b) const{
return strcmp(a,b)>0;
}
};

int main(){
using namespace std;
//使用[]操作符
map<string,int> animal;
animal[string("fish")]=12;
animal[string("dog")]=10;
animal[string("cat")]=5;
cout<<animal["cat"]<<endl;

//string类有默认的比较函数,故下面的语句可以执行,若换为char*类型,则执行会出现问题
//迭代器i指向pair类型
for(map<string,int>::iterator i=animal.begin();i!=animal.end();i++){
cout<<"The number of "<<i->first<<" : "<<i->second<<endl;
}

student s[]={
{"童进",23,"武汉","XXX"},
{"老大",23,"武汉","XXX"},
{"饺子",23,"武汉","XXX"}
};
pair<int,student> p1(4,s[0]);
pair<int,student> p2(2,s[1]);
pair<int,student> p3(3,s[2]);
map<int,student> a;
a.insert(p1);
a.insert(p2);
a.insert(p3);
//按照键值2、3、4进行排列输出
for(map<int,student>::iterator j=a.begin();j!=a.end();j++){
cout<<"The name: "<<j->second.name<<" "<<"age: "<<j->second.age<<" "
<<"city: "<<j->second.city<<" "<<"phone: "<<j->second.phone<<endl;
}

//思考，这是按照键值进行排列，若我想变换，按照name或者年龄进行重新排列，那么又该如何实现呢？

cout<<"新的排列"<<endl;
pair<const char*,student> q1(s[0].name,s[0]);
pair<const char*,student> q2(s[1].name,s[1]);
pair<const char*,student> q3(s[2].name,s[2]);

student testStu={"AB",23,"武汉","XXX"};

//为何要采用函数对象的形式，而不只能是函数，这个与C++内部实现机制有关

map<const char*,student,strCmp> b;
b.insert(q1);
b.insert(q2);
b.insert(q3);

//insert函数的测试,观察其放回迭代器的值,可改变名字看看,插入位置视实际情况定
//返回插入元素的迭代器
pair<const char*,student> q4(testStu.name,testStu);
map<const char*,student,strCmp>::iterator test=b.insert(b.begin()++,q4);
cout<<test->second.name<<endl;

for(map<const char*,student,strCmp>::iterator k=b.begin();k!=b.end();k++){
cout<<"The name: "<<k->second.name<<" "<<"age: "<<k->second.age<<" "
<<"city: "<<k->second.city<<" "<<"phone: "<<k->second.phone<<endl;
}

//拷贝的时候也可以进行函数对象的设置，那如果函数对象变换了，能实现顺序的变化吗？
//目前还没实现，不知道具体可行吗？以后再进行测试吧

//个人观点：不可行。函数对象比较的是key，若重新排列，key不能变换，
//那么所谓的重新排列，岂不仅仅是反序排列，而反序输出map已经具有了这样的函数了。

cout<<"拷贝时实现重新排列"<<endl;//并未实现
map<const char*,student,strCmp> c(b);
for(map<const char*,student,strCmp/*strCmpBig*/>::iterator m=c.begin();m!=c.end();m++){
cout<<"The name: "<<m->second.name<<" "<<"age: "<<m->second.age<<" "
<<"city: "<<m->second.city<<" "<<"phone: "<<m->second.phone<<endl;
}

return 0;
}

/*
*
********************************************
*multimap多重映照容器的基础说明：
********************************************
*
*multimap多重映照容器:容器的数据结构采用红黑树进行管理
*multimap的所有元素都是pair:第一元素为键值(key),不能修改;第二元素为实值(value),可被修改
*
*multimap特性以及用法与map完全相同，唯一的差别在于:
*允许重复键值的元素插入容器(使用了RB-Tree的insert_equal函数)
*因此:
*键值key与元素value的映照关系是多对多的关系
*没有定义[]操作运算
*
*Sorted Associative Container Pair Associative Container Unique Associative Container
*
*使用multimap必须使用宏语句#include <map>
*
**************************************************************************************
*
*创建multimap对象:
*1.multimap<char,int,greater<char> > a;//元素键值类型为char,映照数据类型为int,键值的比较函数对象为greater<char>
*2.multimap(const key_compare& comp)//指定一个比较函数对象comp来创建map对象
* 3.multimap(const multisetr&);//multimap<int,char*> b(a);//此时使用默认的键值比较函数less<int>
*4.multimap(first,last);
*5.multimap(first,last,const key_compare& comp);
*
*//Example:
*pair<const int ,char> p1(1,'a');
*pair<const int ,char> p2(2,'b');
*pair<const int ,char> p3(3,'c');
*pair<const int ,char> p4(4,'d');
*pair<const int ,char> pairArray[]={p1,p2,p3,p4};
*multimap<const int,char> m4(pairArray,pairArray+5);
*multimap<const int,char> m3(m4);
*multimap<const int,char,greater<const int> > m5(pairArray,pairArray+5,greater<const int>());
*
**************************************************************************************
*
*元素的插入
*//typedef pair<const key,T> value_type;
*pair<iterator,bool> insert(const value_type& v);
*iterator insert(iterator pos,const value_type& v);
*void insert(first,last);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();//企图通过迭代器改变元素是不被允许的
*reverse_iterator rbegin();reverse_iterator rend();
*
*iterator find(const key_type& k) const;
*pair<iterator,iterator> equal_range(const key_type& k) const;//返回的pair对象，
*//first为lower_bound(k);大于等于k的第一个元素位置
*//second为upper_bound();大于k的第一个元素位置
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*size_type count(const key_type& k) const;//返回键值等于k的元素个数
*void swap();
*
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <map>
#include <string>
#include <iostream>

//基本操作与set类型,牢记map中所有元素都是pair
//对于自定义类,初学者会觉得比较函数如何构造很麻烦,这个可以参照前面的书写示例
//但若设置键值为int或char类型，无须构造比较函数

struct student{
char* name;
int age;
char* city;
char* phone;
};

int main(){
using namespace std;

student s[]={
{"童进",23,"武汉","XXX"},
{"老大",23,"武汉","XXX"},
{"饺子",23,"武汉","XXX"},
{"王老虎",23,"武汉","XXX"},
{"周润发",23,"武汉","XXX"},
{"周星星",23,"武汉","XXX"}
};
pair<int,student> p1(4,s[0]);
pair<int,student> p2(2,s[1]);
pair<int,student> p3(3,s[2]);
pair<int,student> p4(4,s[3]);//键值key与p1相同
pair<int,student> p5(5,s[4]);
pair<int,student> p6(6,s[5]);
multimap<int,student> a;
a.insert(p1);
a.insert(p2);
a.insert(p3);
a.insert(p4);
a.insert(p5);
a.insert(p6);
typedef multimap<int,student>::iterator int_multimap;
pair<int_multimap,int_multimap> p=a.equal_range(4);
int_multimap i=a.find(4);
cout<<"班上key值为"<<i->first<<"的学生有："<<a.count(4)<<"名,"<<" 他们是:"<<endl;
for(int_multimap k=p.first;k!=p.second;k++){
cout<<k->second.name<<endl;
}
cout<<"删除重复键值的同学"<<endl;
a.erase(i);
cout<<"现在班上总人数为："<<a.size()<<". 人员如下："<<endl;
for(multimap<int,student>::iterator j=a.begin();j!=a.end();j++){
cout<<"The name: "<<j->second.name<<" "<<"age: "<<j->second.age<<" "
<<"city: "<<j->second.city<<" "<<"phone: "<<j->second.phone<<endl;
}

return 0;
}

/*
*
************************************************************************************
*hash_set哈希集合容器的基础说明：
************************************************************************************
*
*hash_set哈希集合容器:使用hashtable数据结构的具有高效数据检索的关联容器
*
*不提供反向迭代器，只有前向迭代器iterator和const_iterator
*不允许插入重复的元素键值
*Hashed Associative Container Simple Associative Container Unique Associative Container
*
*目前还不是C++的标准容器，只是SGI C++ STL的一个扩展容器
*使用hash_set必须使用宏语句#include <hash_set>
*
**************************************************************************************
*
*创建hash_set对象:
*1.hash_set<int> hs;//键值比较使用默认的函数对象equal_to<Value>
*2.hash_set(size_type n);//在质数列表中找出第一个大于等于n的质数作为表长:hash_set<int> hs(100);
* 3.hash_set(size_type n,const hasher& h);//hash函数对象为h
*4.hash_set(size_type n,const hasher& h,const key_equal& k);//键值比较函数对象k
*5.hash_set(const hash_set& h);//用一个hash集合容器拷贝生成另一个hash集合容器:hash_set<int> hs2(hs);
*
**************************************************************************************
*
*元素的插入
*//typedef pair<const key,T> value_type;
*pair<iterator,bool> insert(const value_type& v);//second:返回true/false插入成功标志
*void insert(iterator pos,const value_type& v);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();//不会将元素排序遍历出来
*
*iterator find(const key_type& k) const;//对于非默认类型如char*,在搜素时应定义相关的函数对象
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*size_type bucket_count(const key_type& k) const;//获得hash表的表长
*void swap();
*resize();
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*在SGI STL中，提供了以下hash函数：
*struct hash<char*>
*struct hash<const char*>
*struct hash<char>
*struct hash<unsigned char>
*struct hash<signed char>
*struct hash<short>
*struct hash<unsigned short>
*struct hash<int>
*struct hash<unsigned int>
*struct hash<long>
*struct hash<unsigned long>
*
*hash函数决定了如何划分散列表
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <hash_set>
#include <iostream>

struct student{
char* name;
int age;
char* city;
char* phone;
};
//自定义数据的比较函数
class stuequal{
public:
bool operator() (const student& a,const student& b){
return strcmp(a.city,b.city)==0;//不允许同名，name为键值
}//将name换为city测试下
};
//自定义数据的hash函数
//typedef unsigned int size_t;
struct stu_hash{
size_t operator()(const student& stu) const
{
unsigned long res = 0;
char* s=stu.city;
for( ; *s; ++s ){
res=5*res+*s;
}
return size_t(res);
}
};

//针对字符串的比较函数对象
class strequal{
public:
bool operator () (const char* a,const char* b)const{
return strcmp(a,b)==0;
}
};

int main(){
using namespace std;

hash_set<const char*,hash<const char*>,strequal> a;
a.insert("tongjin");
a.insert("cumirror");
a.insert("makelaugh");
a.insert("feiguodeyun");

//hash<const char*>默认提供的hash函数对象
hash_set<const char*,hash<const char*>,strequal>::const_iterator b=a.find("tongjin");
cout<<*b<<" is "<<(b!=a.end()?"present":"not present")<<endl;

//对于自定义类型数据,使用hash相关容器时应构造hash函数对象、比较函数对象
//注意区别hash函数对象与比较函数对象各自的作用
student s[]={
{"童进",23,"长沙","XXX"},
{"老大",23,"武汉","XXX"},
{"饺子",23,"福州","XXX"},
{"王老虎",23,"地球","XXX"},
{"周润发",23,"香港","XXX"},
{"周星星",23,"香港","XXX"},//city重复
{"童进",23,"香港","XXX"}//name重复、city也有重复
};

hash_set<student,stu_hash,stuequal> c;
c.insert(s[0]);
c.insert(s[1]);
c.insert(s[2]);
c.insert(s[3]);
c.insert(s[4]);
c.insert(s[5]);
c.insert(s[6]);
//注意hash容器并不能实现排序
for(hash_set<student,stu_hash,stuequal>::iterator i=c.begin();i!=c.end();i++){
cout<<i->name<<""<<i->age<<""<<i->city<<endl;
}
return 0;
}

/*
*
************************************************************************************
*hash_map映照容器的基础说明：
************************************************************************************
*
*hash_map哈希映照容器:使用hash表的数据结构,插入的元素键值不允许重复
*hash_map的所有元素都是pair:第一元素为键值(key),不能修改;第二元素为实值(value),可被修改
*
*不提供反向迭代器,只有前向迭代器iterator和const_iterator
*可定义出操作符[]
*
*Hashed Associative Container Pair Associative Container Unique Associative Container
*
*目前还不是C++的标准容器，只是SGI C++ STL的一个扩展容器
*使用hash_map必须使用宏语句#include <hash_map>
*可与map作比较:hash_map检索时使用的键值比较次数少，容器需占用较多的空间，用迭代器遍历出来的元素是非排序的；
*map则使用链表的二分法进行检索，空间使用率高，遍历出来的元素是排序的，而且可提供反向迭代器。
*
**************************************************************************************
*
*创建map对象:
*1.hash_map<char,int> a;//键值类型为char,映照数据类型为int,默认表长为193
*2.hash_map(size_type n);//hash_map<char,int> a(300);此时表长为389
* * 3.hash_map(size_type n,const hasher& h);
* *4.hash_map(size_type n,const hasher& h,const key_equal& k);
*5.hash_map(const hash_map&);
*
*//Example4:
*struct strequal{
*bool operator() (const char* a,const char* b) const {
*return strcmp(a,b)==0;}
*};
*hash_map<char*,int,hash<char*>,strequal> hm(300,hash<char*>(),strequal());
*
**************************************************************************************
*
*元素的插入
*//typedef pair<const key,T> value_type;
*pair<iterator,bool> insert(const value_type& v);
*void insert(first,last);
*
**************************************************************************************
*
*元素的删除
*void erase(iterator pos);
*size_type erase(const key_type& k);//删除等于键值k的元素
*void erase(first,last);//删除[first,last)区间的元素
*void clear();
*
**************************************************************************************
*
*访问与搜索
*
*iterator begin();iterator end();//企图通过迭代器改变元素是不被允许的
*
*iterator find(const key_type& k) const;
*pair<iterator,iterator> equal_range(const key_type& k) const;//此时键值不允许重复，故没有太大用途
*
*其它常用函数
*bool empty() const;
*size_type size() const;
*size_type bucket_count(const key_type& k) const;//获得hash表的表长
*void swap();
*resize();
*void swap();
*
*iterator lower_bound();iterator upper_bound();pair<iterator,iterator> equal_range();//上界、下届、确定区间
*
*
*
********************************************
** cumirror ** [e-mail] ** **
********************************************
*
*/

#include <string>
#include <hash_map>
#include <iostream>
using namespace std;

template<class Key,class NameType,class AgeType,class AdressType>
struct StudentRecord_tag{//学生记录结构体
struct StudentInfo_tag{
NameType name;
AgeType age;
AdressType city;
};
typedef Key IdType;
typedef StudentInfo_tag StudentInfo;
IdType id;
StudentInfo stuinfo;
};

//针对最后的示例，设置的hash函数
struct myhash{
size_t operator() (const string& str) const
{
unsigned long __h = 0;
for (size_t i = 0 ; i < str.size() ; i ++)
__h = 5*__h + str[i];
return size_t(__h);
}
};

class str_compare{
public:
bool operator()(const string& str1,const string& str2)const
{
return str1==str2;
}
};

int main(){
//使用[]操作符
hash_map<string,int> animal;
animal[string("fish")]=12;
animal[string("dog")]=10;
animal[string("cat")]=5;
cout<<animal["cat"]<<endl;
//结构体A中定义的结构体B，在结构体A外可以使用吗？
//StudentInfo_tag a;//直接这样是无法使用的,若想独立使用可以参照下面的方法
//typedef StudentRecord_tag<int,char*,int,char*> StudentRecorda;
//StudentRecorda::StudentInfo_tag testa;

typedef StudentRecord_tag<int,char*,int,char*> StudentRecord;
StudentRecord stuArray[]={
{192,"黄庆",23,"北京"},
{191,"童进",23,"长沙"},
{194,"饺子",23,"福州"},
{193,"小芳",23,"宁波"},
};
//此处应该留意typedef的使用
hash_map<StudentRecord::IdType,StudentRecord::StudentInfo> school;
typedef pair<const StudentRecord::IdType,StudentRecord::StudentInfo> value_type;
for(int i=0;i<4;i++){
value_type p(stuArray[i].id,stuArray[i].stuinfo);
school.insert(p);
}
//测试是否插入成功
cout<<school[193].name<<endl;
//采用迭代器访问，注意map类型容器，其元素为pair类型，pair中first/second要明白
hash_map<StudentRecord::IdType,StudentRecord::StudentInfo>::iterator j;
cout<<"同学"<<""<<"住址"<<endl;
for(j=school.begin();j!=school.end();j++){
cout<<j->second.name<<""<<
j->second.city<<endl;
}
//其它函数示例
//元素的重复插入
value_type p(stuArray[0].id,stuArray[0].stuinfo);
pair<hash_map<const StudentRecord::IdType,StudentRecord::StudentInfo>::iterator,bool> insertReturn;
cout<<(
(insertReturn=school.insert(p)).second==true?"插入成功":"插入失败"
)
<<endl;
cout<<"总人数："<<school.size()<<endl;
cout<<"hash表长："<<school.bucket_count()<<endl;

//如下思考：

//上例中key:IdType为int型,故不用定义hash函数对象,也可将IdType定为string类型，形如"0120504140227"这样的类型
//此时需要定义hash函数,具体解法如下:(在原来定义的变量名后+1)

//原想在上面例子的基础上进行改进,但不成功，可能与string类型内存分配模式有关

//typedef StudentRecord_tag< string,char*,int,char*> StudentRecord1;
//StudentRecord1 stuArray1[]={//不好意思,你们暂时先入我班吧
//{string("0120504140208"),"黄庆",23,"北京"},
//{string("0120504140227"),"童进",23,"长沙"},
//{string("0120504140209"),"饺子",23,"福州"},
//{string("0120504140216"),"小芳",23,"宁波"},
//};
//hash_map<StudentRecord1::IdType,StudentRecord1::StudentInfo,myhash> school1;
//typedef pair<const StudentRecord1::IdType,StudentRecord1::StudentInfo> value_type1;
//for(int i=0;i<4;i++){
//value_type1 p(stuArray1[i].id,stuArray1[i].stuinfo);
//school.insert(p);
//}

//在网上看到一份较为简单的例子,根据自己的稍稍改了下(注意前面的hash函数与比较函数)
hash_map<string,string,myhash,str_compare> myHash;
string strArray[][2]={
{"0120504140227","童进"},
{"0120504140236","zyl"},
{"0120504140216","hq"},
{"0120504140209","jz"},
};
typedef pair<string,string> value_type2;

for(int k=0;k<4;k++){
value_type2 p(strArray[k][0],strArray[k][1]);
myHash.insert(p);
}
hash_map<string,string,myhash,str_compare>::iterator p1;
for(p1=myHash.begin();p1!=myHash.end();p1++){
cout<<p1->first<<""<<
p1->second<<endl;
}
return 0;
}