STL 容器 Ⅱ

函数对象

在C++中，我们把所有能当做函数使用的对象统称为函数对象.

class MyLess{
public:
    bool operator()(int x,int y){
        return x>y;
    }
};

MyLess obj;
cout<<obj(1,2);//可以像函数一样使用。
cout<<obj(2,1);

priority_queue 优先队列

也是一个容器适配器，支持push、pop、top等操作，其内部的元素是排序的，默认的Compare模板参数是less，所以默认值最大的元素是放在容器的顶部的，可通过函数对象greater改变排序，当然也可以自定义排序方法。

int main(){

    priority_queue<int,vector<int>,MyLess> que;
    que.push(1);
    que.push(0);
    que.push(-9);
    que.push(10);

    while(!que.empty())
    {
        cout<<que.top()<<endl;
        que.pop();
    }
}

关联容器

有序关联容器。

set、map、multiset、multimap
set 、map 不允许重复的键值。

multiset、multimap允许重复的键值。

与序列容器相比，关联容器没有前、后的概念及相关的成员函数，但同样提供 insert、emplace 等成员函数。此外，关联容器都有 find、lower_bound、upper_bound等查找函数，返回结果是一个迭代器

如果你需要在 multimap 里精确查找满足某个键的区间的话，建议使用equal_range，可以一次性取得上下界（半开半闭）.

返回一个pair<iterator, iterator>

std::tie std::tie 可用于解包 std::pair

    multimap<string,int> mp;
    mp.insert({"one",1});
    mp.insert({"one",2});
    mp.insert({"one",3});

    multimap<string,int>::iterator lower,upper;

    tie(lower,upper) = mp.equal_range("one");

    for (auto iter = lower ; iter != mp.end() ; iter++) {
        cout<<iter->first<<" is " << iter->second<<endl;
    }

    pair<multimap<string,int>::iterator,multimap<string,int>::iterator> map_pair = mp.equal_range("one");
    for (auto iter = map_pair.first;iter != mp.end() ; iter++) {
        cout<<iter->first<<" is " << iter->second<<endl;
    }

无序关联容器

与有序关联容器相对应，分别有以下无序的关联容器:

• unordered_set
• unordered_map
• unordered_multiset
• unordered_multimap

这些容器内部的元素都是无序的，这些容器不要求一个排序的函数对象，但是要求一个可以计算哈希值的对象。

无序关联容器的主要优点在于其性能。关联容器和 priority_queue 的插入和删除操作，以及关联容器的查找操作，其复杂度都是 O(log(n))，而无序关联容器的实现使用哈希表，可以达到平均 O(1)。