[系统运维]（二）顺序容器、关联容器的简介

容器的结构与分类

• 容器可分为两类
  • 顺序容器
  • 关联式容器

• 顺序容器有五个，是按照放入容器的顺序排列的
  • Array数组，容量固定的连续空间
  • Vector，后面是可以扩充的顺序容器，它的自动增长由分配器处理内存实现
  • Deque双端队列，两端可进可出，前后均可以扩充
  • List双向链表，节点之间通过前后指针连接
  • Forward-List单向链表
• 关联容器，适用于有大量查找动作的场合，底层实现是红黑树
  • Set，key就是value，放入的元素不能重复
  • Multiset，key就是value，放入的元素可以重复
  • Map，key与value是一一对应的，放入的元素不能重复
  • Multimap，key与value是一一对应的，放入的元素可以重复
  • Unorderde Set/Multiset，实现是采用独立链发实现的哈希表，即每一个bucket里存放链表的头指针，一旦冲突就将它放到链表的下一个节点中
  • Unordered Map/Multimap,实现是采用独立链法实现的哈希表

容器的效率测试

• 测试原理：选择使用哪种容器，用户输入元素的个数，程序将满足数量的随机数放入容器中，程序输出一共花费的时间

顺序容器

Array

array<long, ASIZE> c;//模板参数有两个，一共是array的数据类型，另一个是array的大小
for(long i=0; i<ASIZE; ++i){
	c[i] = rand();
}

cout<< c.size()<< endl;//输出数组的大小
cout<< c.front()<< endl;//输出数组的第一个元素
cout<< c.back()<< endl;//输出数组的最后一个元素
cout<< c.data()<< endl;//输出数组的首元素地址
//对数组中的元素进行快排，是c的头文件
//第一个参数是数组的起始地址，第二个参数是元素个数，第三个参数是元素的大小，最后一个参数是如何比较大小的函数
qsort(c.data(), ASIZE, sizeof(long), compareLongs);

Vector

• 小技巧
  • 将每一个测试程序都用namespace包起来，在它的外面写上每次使用的头文件，而不是将所有的头文件都放在测试程序的最上面。头文件有保护机制，它多次引入不会出现问题。
  • 写测试程序时，用到变量时再定义变量，且不要缩进，而函数则正常缩进，这样方便寻找变量的定义。

#include<array>
#include<iostream>
namespace testarray
{
...
}

#include<vector>
#include<iostream>
namespace testvector
{
...
} 

• vector在内存中是向后扩张的，且是两倍增长

vector<string> c;
char buf[10];

for(long i = 0; i < value; ++i)//value是想往vector中插入的元素数量
{
	try{//尝试在抓取由于数据太多导致内存不够，分配失败
		sprintf(buf, 10, "%d", rand());//将随机数变为字符串
		c.push_back(string(buf));
	}
	catch(exception& p){//输出最多有多少个i，然后退出程序
		cout<< "i=" << i << " "<< p.what() << endl;
		abort();
	}
}

cout<<"vector.data()="<<c.data()<<endl;//输出vector的起始地址

List

list<string> c;
char buf[10];

for(long i=0; i<value; ++i)
{
	try{
		snprintf(buf, 10, "%d", rand());
		c.push_back(string(buf));//链表的插入也是push_back()
	}
	catch(exception& p){
		cout<< "i=" << i << " "<<p.what() << endl;
		abort();
	}
}
cout<< c.size()<<endl;//输出链表中元素的个数
cout<< c.max_size()<<endl;
cout<< c.front()<<endl;//输出链表中第一个元素
cout<< c.back()<<endl;//输出链表中最后一个元素
c.sort()//链表自定义了它的sort

forward_list

• 只提供push_back()
• 只提供front()返回头结点，要返回最后一个元素要遍历整个链表，没有back()这种用法

forward_list<string> c;
char buf[10];

for(long i = 0; i<value; ++i)
{
	try{
		snprintf(buf, 10, "%d", rand());
		c.push_front(string(buf));
	}
	catch(exception& p){
		cout<< "i=" << i << p.what() << endl;
		abort();
	}
}
cout<< c.max_size()<<endl;
cout<< c.front()<<endl;
//不存在c.back()
//不存在c.size()
c.sort()//单向链表提供了自己sort

deque

• 双端队列，可以左右扩充
• deque中把一段称作一个buffer,它是由许多段组成的，是分段连续的，但是让使用者感觉是整体连续的。
• 如果不断的插入将当前buffer用完了，会再次扩充一个buffer。
• 结构如下

deque<string> c;
char buf[10];

for(long i = 0; i < value; ++i)
{
	try{
		snprintf(buf, 10, "%d", rand());
		c.push_back(string(buf));
	}
	catch(exception& p){
		cout << "i = "<< i << " " <<p.what()<<endl;
		abort();
	}
}
cout<<c.size()<<endl;
cout<<c.front()<<endl;
cout<<c.back()<<endl;
cout<<max_size()<<endl;

stack与queue

• 二者的底层实现都是deque
• 均有push()、pop()
• 由于这两种容器实质上并没有自己的数据结构，而是借用deque的数据结构，所以把它叫做容器适配器

关联容器

multiset

• 底层实现是红黑树

multiset<string> c;
char buf[10];

for(long i = 0; i<value; ++i)
{
	try{
		snprintf(buf, 10, "%d", rand());
		c.insert(string(buf));
	}
	catch(exception& p){
		cout<< "i=" << i << " "<< p.what()<<endl;
		abort();
	}
}

cout<< c.size()<<endl;
cout<<c.max_size()<<endl;
auto pItem = c.find(target); 
if(pItem != c.end())
	cout<<*Item<<endl;
else
	cout<<"not find"<<endl;

multimap

• 底层实现是红黑树
• pair输出只能输出first和second，不能一次性全部输出。因为它并没有这种操作符重载
• 不可以用[ ] 插入元素，如果key相同的话会将key对应的值改为value，而不是插入新的元素

multimap<long, string> c;
char buf[10];

for(long i = 0; i<value; ++i)
{
	try{
		snprintf(buf, 10, "%d", rand());
		c.insert(pair<long, string>(i, buf));
		//不可以用[]做插入
	}
	catch(exception& p){
		cout<<"i = "<<i << p.what() << endl;
		abort();
	}
}
cout<< c.size() <<endl;
cout<<c.max_size() <<endl;
auto pItem = c.find(target);
if(pItem != c.end())
	cout<<*(Item).second<<endl;
else
	cout<<"not find"<<endl;

unordered_multiset

• 底层实现是哈希表
• 篮子bucket一定比元素多，一些篮子里面没有元素，且每一个篮子里的链表不能太长，如果太长的话查找要遍历链表，会很慢
• 经验法则，如果元素的总数大于等于篮子，这个篮子就要重新扩充，变成原来个数的大约两倍，再将原来的散列表重新打散，挂在不同的篮子上
  

unordered_multiset<string> c;
char buf[10];

for(long i = 0 ; i<value; ++i)
{
	try{
		snprintf(buf, 10, "%d", rand());
		c.insert(string(buf));
	}
	catch(exception& p){
		cout<<"i =" << i<< " "<<endl;
		abort();
	}
}

cout<< c.size()<<endl;//输出元素的总数
cout<< c.max_size()<<endl;
cout<< c.bucket_count()<<endl;//输出篮子的个数
cout<< c.load_factor()<<endl;//输出装填因子
cout<< c.max_load_factor()<<endl;//输出最大的载重因子
cout<< c.max_bucket_count()<<endl;

auto pItem = c.find(target);
if(pItem != c.end())
	cout<<*Item<<endl;
else
	cout<<"not find"<<endl;

unordered_multimap

unordered_multimap<long, string> c;
char buf[10];

for(int i=0; i < value; ++i)
{
	try{
		snprintf(buf, 10, "%d", rand());
		c.insert(pair<long, string>(i, buf));
	}
	catch(exception& p){
		cout<< "i=" << i << " "<< p.what()<< endl;
		abort();
	}
}

cout<< c.size()<< endl;
cout<< c.max_size()<< endl;

auto pItem = c.find(target);
if(pItem != c.end())
	cout<<*(Item).second<<endl;
else
	cout<<"not find"<<endl;

set/map

• 底层都是红黑树，不允许重复元素
• map可以使用[ ]插入元素，它会将key和value绑定成一个pair插入到map中。

unordered_set/unordered_set

• 用哈希表实现的set和map