//STL之容器
//学习目的：各个容器的使用。
/*
容器分为：序列式容器和关联式容器。
序列式容器：array, vector, list, deque
关联式容器：set, map, multiset, multimap
vector的数据安排以及操作方式，与array非常相似两者唯一的差别在于，array是静态空间，一旦配置了
就不能改变，想要扩充，一切琐碎得由客户端自己来：首先，配置新空间，然后将元素从旧址一一搬往新址，
再释放旧空间；vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。
list不再能够像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在。list有一个
重要性质：插入操作和结合操作都不会造成原有的list迭代器失效。这在vector是不成立的。list不仅是一个
双向链表，而且还是一个环状双向链表。
set的特性是，所有元素都会根据元素的键值自动被排序。set的元素不像map那样可以同时拥有实值(value)和
键值(key),set元素的键值就是实值，实值就是键值，set不允许两个元素有相同的键值。
我们可以通过set的迭代器改变set的元素值吗？不行，因为set元素值就是其键值，关系到set元素的排列规则。
如果任意改变set元素值，会严重破坏set组织。因此set是const_iterator。（map能修改实值，不能修改键值）
set拥有与list相同的某些性质：当客户端对它进行元素新增操作和删除操作时，操作之前的所有迭代器，
在操作完成之后都依然有效。（同样试用于map）
map的特性是，所有元素都会根据元素的键值自动被排序，map的所有元素都是pair，同时拥有实值和键值。
pair的第一元素被视为键值，第二元素被视为实值。map不允许两个元素拥有相同的键值。
//本程序代码来源《STL源码剖析》
*/
//下面是一个set和map的测试程序
//file：5set-test.cpp
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
void main()
{
///////////////////////////////set/////////////////////////////////
int i;
int ia[5] = {0, 1, 2, 3, 4};
set<int> iset(ia, ia + 5);
cout << "size = " << iset.size() << endl; //size = 5
cout << "3 count = " << iset.count(3) << endl; //3 count = 1
iset.insert(3);//此语句执行结果无效，因为已有3
cout << "3 count = " << iset.count(3) << endl; //3 count = 1
set<int>::iterator ite1 = iset.begin();
set<int>::iterator ite2 = iset.end();
for (; ite1 != ite2; ++ite1)
{
cout << *ite1;
}
cout << endl; //01234
//使用STL算法find()来搜寻元素，可以有效运作，但不是好办法
ite1 = find(iset.begin(), iset.end(), 1);
if (ite1 != iset.end())
{
cout << "3 found" << endl;
}
//面对关联式容器，应该使用其所提供的find函数来搜寻元素，会比
//使用STL算法find，更有效率，因为STL算法find只是循序搜寻。
ite1 = iset.find(3);
if (ite1 != iset.end())
{
cout << "3 found" << endl;
}
//企图通过迭代器来改变set元素，是不被允许的。
*ite1 = 9; //error, assignment of read-only location
map<string,int> simap;
simap[string("jjhou")] = 1;
simap[string("jerry")] = 2;
simap[string("jason")] = 3;
simap[string("jimmy")] = 4;
pair<string,int> value(string("david"), 5);
pair<map<string,int>::iterator,bool> IstRt;
IstRt = simap.insert(value);
cout << IstRt.first->first << endl;
cout << IstRt.first->second << endl;
map<string,int>::iterator simap_iter = simap.begin();
for (; simap_iter != simap.end(); ++simap_iter)
{
cout << simap_iter->first << ' ' << simap_iter->second << endl;
}
int number = simap[string("jjhou")];
cout << number << endl;
//面对关联式容器，应该使用其所提供的find函数来搜寻元素，会比
//使用STL算法find，更有效率，因为STL算法find只是循序搜寻。
simap_iter = simap.find(string("jerry"));
if (simap_iter != simap.end())
{
cout << "jerry found" << endl;
}
//simap_iter->first = string("hhhh"); //error
simap_iter->second = 9; //right
getchar();
}