关联容器

概述

set, multiset, map, multimap 是一种非线性的树结构，具体的说采用的是一种比较高效的特殊的平衡二叉查找树—— 红黑树结构。

因为关联容器的这四种容器类都使用同一原理，所以他们核心的算法是一致的，但是它们在应用上又有一些差别，先描述一下它们之间的差别。

set ，又称集合，实际上就是一组元素的集合，但其中所包含的元素的值是唯一的，且是按一定顺序排列的，集合中的每个元素被称作集合中的实例。因为其内部是通过链表的方式来组织，所以在插入的时候比vector 快，但在查找和末尾添加上被vector 慢。

multiset ，是多重集合，其实现方式和set 是相似的，只是它不要求集合中的元素是唯一的，也就是说集合中的同一个元素可以出现多次。

map ，提供一种“键- 值”关系的一对一的数据存储能力。其“键”在容器中不可重复，且按一定顺序排列（其实我们可以将set 也看成是一种键- 值关系的存储，只是它只有键没有值。它是map 的一种特殊形式）。由于其是按链表的方式存储，它也继承了链表的优缺点。

multimap，和map的原理基本相似，它允许“键”在容器中可以不唯一。

关联容器的特点是明显的，相对于顺序容器，有以下几个主要特点：

1. 其内部实现是采用非线性的二叉树结构，具体的说是红黑树的结构原理实现的；
2. set 和map 保证了元素的唯一性，mulset 和mulmap 扩展了这一属性，可以允许元素不唯一；
3. 元素是有序的集合，默认在插入的时候按升序排列。

基于以上特点，

1. 关联容器对元素的插入和删除操作比vector 要快，因为vector 是顺序存储，而关联容器是链式存储；比list 要慢，是因为即使它们同是链式结构，但list 是线性的，而关联容器是二叉树结构，其改变一个元素涉及到其它元素的变动比list 要多，并且它是排序的，每次插入和删除都需要对元素重新排序；

2. 关联容器对元素的检索操作比vector 慢，但是比list 要快很多。vector 是顺序的连续存储，当然是比不上的，但相对链式的list 要快很多是因为list 是逐个搜索，它搜索的时间是跟容器的大小成正比，而关联容器 查找的复杂度基本是Log(N) ，比如如果有1000 个记录，最多查找10 次，1,000,000 个记录，最多查找20 次。容器越大，关联容器相对list 的优越性就越能体现；

3. 在使用上set 区别于vector,deque,list 的最大特点就是set 是内部排序的，这在查询上虽然逊色于vector ，但是却大大的强于list 。

4. 在使用上map 的功能是不可取代的，它保存了“键- 值”关系的数据，而这种键值关系采用了类数组的方式。数组是用数字类型的下标来索引元素的位置，而map 是用字符型关键字来索引元素的位置。在使用上map 也提供了一种类数组操作的方式，即它可以通过下标来检索数据，这是其他容器做不到的，当然也包括set 。

关联容器类型

按关键字有序保存元素

无序集合

set

c++ stl集合(Set)是一种包含已排序对象的关联容器。set/multiset会根据待定的排序准则，自动将元素排序。两者不同在于前者不允许元素重复，而后者允许。

1. 不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，则插入新元素
2. 不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取，而且从迭代器角度来看，元素值是常数
3. 元素比较动作只能用于型别相同的容器(即元素和排序准则必须相同)

常用操作

pair<iterator,bool> insert (const value_type& val); //Extends the container by inserting new elements, effectively increasing the container size by the number of elements inserted.

const_iterator find (const value_type& val) const; //Searches the container for an element equivalent to val and returns an iterator to it if found, otherwise it returns an iterator to set::end.
iterator find (const value_type& val);

iterator  erase (const_iterator position);
size_type erase (const value_type& val);

size_type count (const value_type& val) const; //Searches the container for elements equivalent to val and returns the number of matches.
iterator upper_bound (const value_type& val); //Returns an iterator pointing to the first element in the container which is considered to go after val.
iterator lower_bound (const value_type& val); //Returns an iterator pointing to the first element in the container which is not considered to go before val 
pair<iterator,iterator> equal_range (const value_type& val); //Returns the bounds of a range that includes all the elements in the container that are equivalent to val.

map

头文件<map>
对于迭代器来说，可以修改实值，而不能修改key。

key_compare key_comp() const; //Returns a copy of the comparison object used by the container to compare keys.
value_compare value_comp() const; //Returns a comparison object that can be used to compare two elements to get whether the key of the first one goes before the second.

iterator find (const key_type& k);

begin()         //返回指向map头部的迭代器
clear(）        //删除所有元素
count()         //返回指定元素出现的次数
empty()         //如果map为空则返回true
end()           //返回指向map末尾的迭代器
equal_range()   //返回特殊条目的迭代器对
erase()         //删除一个元素
find()          //查找一个元素
get_allocator() //返回map的配置器
insert()        //插入元素
key_comp()      //返回比较元素key的函数
lower_bound()   //返回键值>=给定元素的第一个位置
max_size()      //返回可以容纳的最大元素个数
rbegin()        //返回一个指向map尾部的逆向迭代器
rend()          //返回一个指向map头部的逆向迭代器
size()          //返回map中元素的个数
swap()           //交换两个map
upper_bound()    //返回键值>给定元素的第一个位置
value_comp()     //返回比较元素value的函数

容器适配器

STL 中包含三种适配器：栈stack 、队列queue 和优先级priority_queue 。

适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作“它保存一个容器，这个容器再保存所有元素”。

STL 中提供的三种适配器可以由某一种顺序容器去实现。默认下stack 和queue 基于deque 容器实现，priority_queue 则基于vector 容器实现。当然在创建一个适配器时也可以指定具体的实现容器，创建适配器时在第二个参数上指定具体的顺序容器可以覆盖适配器的默认实现。

由于适配器的特点，一个适配器不是可以由任一个顺序容器都可以实现的。

栈stack 的特点是后进先出，所以它关联的基本容器可以是任意一种顺序容器，因为这些容器类型结构都可以提供栈的操作有求，它们都提供了push_back 、pop_back 和back 操作；

队列queue 的特点是先进先出，适配器要求其关联的基础容器必须提供pop_front 操作，因此其不能建立在vector 容器上；

优先级队列priority_queue 适配器要求提供随机访问功能，因此不能建立在list 容器上。

stack

头文件<stack>

常用操作

void push (value_type&& val); //Inserts a new element at the top of the stack, above its current top element. 
reference& top(); //Returns a reference to the top element in the stack. 
void pop(); //Remove top element
void swap (stack& x) //Exchanges the contents of the container adaptor (*this) by those of x.

queue

头文件<queue>

empty()
size()
front()
back()
push()
emplace()
pop()
swap()

priority_queue

priority_queue调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现。

模板声明带有三个参数:
priority_queue<Type, Container, Functional>
STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果声明时把后面俩个参数缺省的话，优先队列就是大顶堆，队头元素最大。

empty()
size()
top()
push()
emplace()
pop()
swap()

//实现自定义类型的小顶堆
#include <iostream>
#include <queue>
 
using namespace std;
 
struct Node{
    int x, y;
    Node( int a= 0, int b= 0 ):
        x(a), y(b) {}
};
 
struct cmp{
    bool operator() ( Node a, Node b ){
        if( a.x== b.x ) return a.y> b.y;
         
        return a.x> b.x; }
};
 
int main(){
    priority_queue<Node, vector<Node>, cmp> q;
     
    for( int i= 0; i< 10; ++i )
    q.push( Node( rand(), rand() ) );
     
    while( !q.empty() ){
        cout << q.top().x << ' ' << q.top().y << endl;
        q.pop();
    }
     
    getchar();
    return 0;
}