STL之set和map

set

set的特性是，所有元素都会根据元素的键值自动排序，set的键值就是实值，实值就是键值。set不允许两个元素相同。不能通过set的迭代器改变set的元素值，因为set元素值就是其键值，关系到set元素的排列规则。set<T>::iterator被定义为底层RB-TREE的const_iterator。

set和list拥有某些相同的性质：当客户端对它进行元素新增操作或删除操作时，操作之前的所有迭代器，在操作完成之后都亦然有效。

由于RE-tree是一种平衡二叉树，自动排序效果不错，所以标准STL set即以RB-tree为底层机制。

#include <set>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
intmain()
{
   int ia[5] = {0,1,2,3,4};
   set<int> iset(ia, ia+5);
 
   set<int>::iterator ite1 = iset.begin();
   set<int>::iterator ite2 = iset.end();
 
   //使用STL算法find()来搜索元素，可以有效运作，但效率低
   ite1= find(iset.begin(), iset.end(), 3);
   if(ite1 != iset.end())
      cout<< "3 found" << endl;
  
   //面对关联式容器，应该使用其所提供的find函数来搜寻元素，
   //这样会比使用STL算法find()更有效率。因为STL算法find()
   //只是循序搜寻，而关联式容器提供的find()利用了红黑树的性质
   ite1= iset.find(3);
   if(ite1 != iset.end())
      cout << "3found" << endl;
 
   return 0;
}

map

map的特性是，所以元素都会根据元素的键值自动被排序。map的所有元素都是pair，同时拥有实值和键值。Pair的第一元素被视为键值，第二元素被视为实值。Map不允许两个元素拥有相同的键值。

我们可以用map的迭代器修改元素的实值，但不能修改键值。因此map的迭代器既不是constant iterator，也不是一种mutable iterator。

map和list拥有某些相同的性质：当客户端对它进行元素新增操作或删除操作时，操作之前的所有迭代器，在操作完成之后都亦然有效。

标准STL map即以RB-tree为底层机制。

multiset

multiset的特性和set有完全相同，唯一差别在于它允许键值冲重复，因为它的插入操作采用的是底层机制rb-tree的insert_equal()，而非insert_unique()。

multimap

multimap的特性和set有完全相同，唯一差别在于它允许键值冲重复，因为它的插入操作采用的是底层机制rb-tree的insert_equal()，而非insert_unique()。

hash_table

以上关联式容器除了可以用红黑树实现外，还可以用hash_table实现。

区别主要有两点：

1．在于hash_table这种结果在插入、删除、搜寻等操作上具有常数平均时间，这种表现是以统计为基础，不需要元素的随机性。而红黑树具有对数平均时间，且这样的表现构造在一个假设上：输入数据具有足够的随机性。

2.基于hash_table实现的容器没有自动排序功能，而基于rb_tree具有自动排序功能。